题目描述
逝者如斯夫，不舍昼夜！
叶良辰认为，他的寿命是无限长的，而且每天都会进步。
叶良辰的生命的第一天，他有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
4 2
1 4
输出样例#1： 复制
4
说明
样例说明
最开始是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
Q1.为什么76行的x是hash[i+1]-hash[i]-1
A1.因为即使离散化了，但是两个数之中的数没有被交换，还是原来的那些数。举例：
比如 1 2 3 4 5 6 7 8
交换 4 7
交换 1 4
-> 7 2 3 1 5 6 4 8
但是之间还是5,6
Q2.为什么87行是change(i,x),而不是change(i,1)，也不是change(a[i],x)
A2.因为既然他们之间有x个数，树状数组求sum的时候必须要将其计算在内，所以把他们加在他们开始的数的编号i上,这样在计算某数前比他大的数的个数时，就可以一次性加上x个比他大的数。至于为什么不是change(a[i],1)，参见A1.
#include<bits/stdc++.h>
#define f(i,l,r) for(i=(l);i<=(r);i++)
#define ff(i,r,l) for(i=(r);i>=(l);i--)
using namespace std;
const int MAXN=100005;
struct Node{
int x,y;
}e[MAXN];
int k;
long long T[MAXN];
int a[MAXN<<1],h[MAXN<<1],b[MAXN],L;
inline int Lowbit(int x)
{
return x&(-x);
}
inline void add(int x,long long d)
{
int i;
if(!x) return;
for(i=x;i<=L;i+=Lowbit(i)){
T[i]+=d;
}
return;
}
inline long long query(int x)
{
int i;
long long res=0;
for(i=x;i;i-=Lowbit(i)){
res+=T[i];
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int i,j,x,y;
long long num;
long long ans=0;
cin>>k;
f(i,1,k){
cin>>e[i].x>>e[i].y;
h[i+i-1]=e[i].x;
h[i+i]=e[i].y;
}
sort(h+1,h+1+k+k);
L=unique(h+1,h+1+k+k)-(h+1);
f(i,1,L){
a[i]=i;
}
f(i,1,k){
int pos1=lower_bound(h+1,h+1+L,e[i].x)-h;
int pos2=lower_bound(h+1,h+1+L,e[i].y)-h;
swap(a[pos1],a[pos2]);
}
ff(i,L,1){
ans+=query(a[i]-1);
add(a[i],1);
// cout<<ans<<"GG ";
num=h[i]-h[i-1]-1;
ans+=query(i-1)*num;
add(i-1,num);
// cout<<num<<" "<<ans<<"GGG"<<endl;
}
cout<<ans<<endl;
return 0;
}
| 
转播
