题目描述
逝者如斯夫，不舍昼夜！
叶良辰认为，他的寿命是无限长的，而且每天都会进步。
叶良辰的生命的第一天，他有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：我好怕怕啊。
于是找到了你。
输入输出格式
输入格式：第一行一个整数k，表示小A玩了多少次时光机
接下来k行，x_i,y_i，表示将S[x_i]与S[y_i]进行交换
输出格式：有多少“异常对”
输入输出样例
说明
样例说明
最开始是1 2 3 4 5 6...
然后是 1 4 3 2 5 6...
然后是 2 4 3 1 5 6...
符合的对是[1 4] [2 3] [2 4] [3 4]
对于30%的数据，x_i,y_i <= 2000
对于70%的数据, x_i,y_i <= 100000
对于100%的数据, x_i.y_i <= 2^31-1 k<=100000
6024
题解：方法千篇一律，主要是自己在草稿纸上模拟一遍，才能领会其中精妙所在！
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; int Hash[maxn<<1],c[maxn<<1],lsh[maxn<<1]; int cnt,top,n,m; pair<int,int>P[maxn]; int lowbit(int x){return x&-x;} void update(int x,int v) { for(int i=x;i<=m;i+=lowbit(i)) c[i]+=v; } ll sum(int x) { ll ans=0; for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i]; return ans; } int main() { int k; cin>>k; for(int i=1;i<=k;i++){ cin>>P[i].first>>P[i].second; Hash[++cnt]=P[i].first; Hash[++cnt]=P[i].second;//先都放入Hash数组里，之后排序去重 } sort(Hash+1,Hash+1+cnt); m=unique(Hash+1,Hash+1+cnt)-Hash-1; for(int i=1;i<=m;i++)lsh[i]=i;//记录原始状态 for(int i=1;i<=k;i++){ int pos1=lower_bound(Hash+1,Hash+1+m,P[i].first)-Hash; int pos2=lower_bound(Hash+1,Hash+1+m,P[i].second)-Hash; swap(lsh[pos1],lsh[pos2]);//找到对应位置进行相应操作 } ll ans=0; for(int i=m;i>=1;i--){ ans+=sum(lsh[i]-1);//单点求逆序对 update(lsh[i],1);//更新单点 ll len=Hash[i]-Hash[i-1]-1;//求连续区间长度 ans+=len*sum(i-1);//连续的不变区间，可以将它看作 i 这个数！ if(i!=1)update(i-1,len);//最后一个不用更新了（也不能更新，会在更新中死循环，因为0的lowbit是0） } cout<<ans<<endl; return 0; }