http://www.zybbs.org/JudgeOnline/problem.php?id=2141

写了N天，花了N小时各种委以后决定换方法，然后写了1小时就A了……这题的数据范围暴力居然比树套树快T^T

动态维护逆序对数目。每次交换两个数。初始逆序对数归并排序暴力乱求，然后呢？

每次交换位于i,j上的两个数后，如果这两个数一样，那么等于没交换，否则呢？

最好自己想一想……（我一开始想错了，然后调了不下5个小时，囧）

考虑哪些数与Ai,Aj的逆序关系会变。1..i-1和j+1..n肯定是没有影响的（原来在前面还是在前面）。有影响的是（假设Ai<Aj）：

1.Ai,Aj，会产生一组逆序对

2.A(i+1..j-1)。这里有五种情况，可以构造出来：2 1 2 3 4 5 4，交换A1,A7，可以发现A2..6中，1和5没变，2和4各产生一组逆序对，3产生两组。

即，A(i+1..j-1)中，等于Ai或Aj的数会产生/消除一个逆序对，大小在Ai和Aj之间的数会产生/消除两个逆序对。

Ai<Aj时全部是产生逆序对，Ai>Aj时全部是消除逆序对。

于是可以树状数组/线段树套平衡树……也可以暴力找（会掉RP）……

一开始写的是每个节点记录数值外再记录一个编号，这样可以保证没有相同节点，调了N天后发生了灵异事件……

我用自己写的maker弄了个小数据出来，死循环了……于是我在自己感觉可能委掉的地方加了个putchar('!')来观察是否运行到了这个地方，另外没动，结果不死循环了……但是换一组数据又死循环……有没有神犇知道这个是神马意思！？

最后写了相同的数值合并在一个节点里，写了个手动堆，1Y……88行，也许是我写过最长的程序了吧……

#include <stdio.h>
#include <string.h>
#define maxn 300000
#define lt(a,b) ((a)==(b))
#define cmp(a,b) ((a)<(b))
#define icmp(a,b) ((a)<=(b))
#define scmp(a,b) ((a)>(b))
typedef struct _Splay{struct _Splay *c[2],*f;int s,v,k;}Splay,*PSplay;
Splay null,st[maxn],*que[maxn],*a[20001];
char str[300000],*p=str,*o=str;
int bq=-1,eq=-1,n,f[20000],b[20000],t[20000],ans;
inline PSplay updt(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+x->k,x;}
inline PSplay near(PSplay x,_Bool c){for(x=x->c[c];x->c[!c]!=&null;x=x->c[!c]);return x;}
inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}
inline PSplay node(v){
	if(++bq==maxn)bq=0;
	if(!que[bq])que[bq]=st+bq;
	que[bq]->f=que[bq]->c[0]=que[bq]->c[1]=&null;
	que[bq]->k=que[bq]->s=1;
	que[bq]->v=v;
	return que[bq];
}inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		updt((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return updt(x);
}inline PSplay Join(PSplay x,PSplay y){
	if(x==&null)return y;if(y==&null)return x;x=splay(extr(x,1),&null);
	return updt((x->c[1]=splay(y,&null))->f=x);
}inline PSplay Remove(PSplay x){
	if(x->k!=1)return x->k--,x->s--,x;
	if(++eq==maxn)eq=0;(que[eq]=x)->c[0]->f=x->c[1]->f=&null;return Join(x->c[0],x->c[1]);
}inline PSplay Insert(PSplay r,int x){
	_Bool c;if(!r||r==&null)return node(x);
	while(1){
		if(lt(r->v,x))return r->k++,r->s++,splay(r,&null);
		if(r->c[c=cmp(r->v,x)]==&null)return splay(((r->c[c]=node(x))->f=r)->c[c],&null);
		r=r->c[c];
	}
}inline PSplay Find(PSplay*r,int x){
	PSplay ans=&null,t=&null,f=(*r)->f;
	for(;*r!=&null;*r=t->c[cmp(t->v,x)])if(lt((t=*r)->v,x))return *r=splay(t,f);
	else if(icmp(t->v,x)&&(ans==&null||scmp(t->v,ans->v)))ans=t;
	*r=splay(ans==&null?t:ans,f);return ans;
}void merge(i,j){
	int c=i,mid=i+j>>1,k=mid,s=0;if(i+1==j)return;merge(i,mid);merge(mid,j);
	while(i!=mid){while(k!=j&&f[k]<f[i])t[s++]=f[k++];t[s++]=f[i++];ans+=k-mid;}
	memcpy(f+c,t,s<<2);
}inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}inline void BitInsert(i,x){for(i++;i<=n;i+=i&-i)a[i]=Insert(a[i],x);}
inline void BitUpdate(i,x,y){for(i++;i<=n;i+=i&-i)a[i]=Remove(Find(a+i,x)),a[i]=Insert(a[i],y);}
inline BitQuery(i,p,q){
	int ans=0;
	for(i++;i;i-=i&-i){
		if(Find(a+i,p)!=&null&&a[i]->v==p)ans+=a[i]->k;
		if(a[i]->v<=p)ans-=a[i]->c[0]->s+a[i]->k<<1;
		if(Find(a+i,q)!=&null&&a[i]->v==q)ans+=a[i]->k;
		if(a[i]->v<=q)ans+=a[i]->c[0]->s<<1;
		if(a[i]->v<q)ans+=a[i]->k<<1;
	}return ans;
}inline void print(x){
	char buf[11],*b=buf;
	if(!x)*o++=48;else{
	while(x){*b++=x%10+48;x/=10;}
	while(b--!=buf)*o++=*b;}
	*o++='\n';
}main(){
	int i=-1,j,t,k,x,y;_Bool d;fread(p,1,300000,stdin);
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++i!=n;BitInsert(i,f[i]=b[i]=getint()));
	merge(0,n);
	for(t=getint();print(ans),t--;){
		if(b[i=getint()-1]==b[j=getint()-1])continue;
		if(i>j)i^=j^=i^=j;x=(d=b[i]<b[j])?b[i]:b[j];y=d?b[j]:b[i];
		k=1;if(j-1!=i)k+=BitQuery(j-1,x,y)-BitQuery(i,x,y);
		ans+=d?k:-k;BitUpdate(j,b[j],k=b[i]);BitUpdate(i,k,b[i]=b[j]);b[j]=k;
	}*--o=0;return puts(str),0;
}

• inline
• block