题目描述
逝者如斯夫，不舍昼夜！
叶良辰认为，他的寿命是无限长的，而且每天都会进步。
叶良辰的生命的第一天，他有1点能力值。第二天，有2点。第n天，就有n点。也就是S[i]=i
但是调皮的小A使用时光机，告诉他第x天和第y天，就可以任意交换某两天的能力值。即S[x]<–>S[y]
小A玩啊玩，终于玩腻了。
叶良辰：小A你给我等着，我有100种办法让你生不如死。除非能在1秒钟之内告知有多少对“异常对”。也就是说，最后的能力值序列，有多少对的两天x,y，其中x<y，但是能力值S[x]>S[y]？
小A：我好怕怕啊。
于是找到了你。
对于30%的数据，x_i,y_i <= 2000
对于70%的数据, x_i,y_i <= 100000
对于100%的数据, x_i.y_i <= 2^31-1 k<=100000
逆序对裸题
由于xy这么大我们来离散化
把只要是交换过的（不管几次）都标记下来，排下序（点权为1）
没交换过的一些区间缩成一个点（点权为区间长度）
然后进行离散化操作，离散成新的段，相邻两点间下标严格递增1（还有一个就是开头没被交换的区间对答案没有影响直接扔掉）
我们离线了交换操作，这个时候就二分查找，把原来应该换哪两个点映射成现在应该换哪两个点
全换完之后就是个裸的逆序对问题，按点权建树状数组，然后统计区间和就行了。
·
//注释是做题的时候瞎写的凑合着看看吧，要说的都说了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<iterator> #include<algorithm> #include<cstdlib> #define inf 1e18 using namespace std; struct ch { long long ca,cb; }oprates[100010]={0}; long long changep[200010]={0};//被操作的区间 long long setx[200010]={0};//离散化映射 int k,totlen=0,upat=2; int final[400010]={0},zonecount[200010]={0}; long long fwt[400010]={0}; inline void uniq() { int old_len=totlen; for (int i=1;i<=old_len;i++) if (changep[i]==changep[i+1]) { changep[i]=inf; totlen--; } sort(changep+1,changep+old_len+1); // for (int i=1;i<=totlen;i++) printf("%lld ",changep[i]); printf("\n"); } inline void makeset() { fill(zonecount,zonecount+200000,1); setx[1]=changep[1];//一定以第一个被交换的位置开始算 for (int i=2;i<=totlen;i++) { if (changep[i]!=changep[i-1]+1)//有一段正常的区间 { zonecount[upat]=changep[i]-changep[i-1]-1; setx[upat]=changep[i-1]+1; upat++; setx[upat]=changep[i]; upat++; } else//相邻的两个元素都交换了 { setx[upat]=changep[i]; upat++; } } upat--; // for (int i=1;i<=upat;i++) printf("%lld ",setx[i]); printf("\n"); } inline int BinSearch(long long element) { int l=1,r=upat,mid; while (l<=r) { mid=(l+r)>>1; if (setx[mid]==element) return mid; else if (setx[mid]>element) r=mid-1; else l=mid+1; } } long long getsum(long long pos) { long long res=0; while (pos) { res+=fwt[pos]; pos-=(pos&(-pos)); } return res; } inline void add(long long pos,long long val) { while (pos<=upat) { fwt[pos]+=val; pos+=(pos&(-pos)); } } int main() { scanf("%d",&k); for (int i=1;i<=k;i++) { scanf("%lld%lld",&oprates[i].ca,&oprates[i].cb); changep[++totlen]=oprates[i].ca; changep[++totlen]=oprates[i].cb; } //离散化 sort(changep+1,changep+totlen+1); uniq(); makeset(); for (int i=1;i<=upat;i++) final[i]=i; for (int i=1;i<=k;i++) { int posa=BinSearch(oprates[i].ca),posb=BinSearch(oprates[i].cb); swap(final[posa],final[posb]); swap(zonecount[posa],zonecount[posb]); } // for (int i=1;i<=upat;i++) printf("%lld ",final[i]); printf("\n"); // for (int i=1;i<=upat;i++) printf("%lld ",zonecount[i]); printf("\n"); unsigned long long ans=0; for (int i=1;i<=upat;i++) { ans+=zonecount[i]*(getsum(upat)-getsum(final[i])); add(final[i],zonecount[i]); // cout<<ans<<endl; } printf("%lld\n",ans); return 0; } |