【分块】【树套树】bzoj2141 排队

考虑暴力更新的情况，设swap的是L,R位置的数。
swap之后的逆序对数应该等于：
之前的逆序对数
+[L+1,R-1]中比 L位置的数 大的数的个数
-[L+1,R-1]中比 L位置的数 小的数的个数
-[L+1,R-1]中比 R位置的数 大的数的个数
+[L+1,R-1]中比 R位置的数 小的数的个数

并且若L位置的数>R位置的数，逆序对数–；反之，逆序对数++。

分块，对每个块内部进行sort，这样可以二分，在O(log(sqrt(n))的时间内求得某个块内比某个数大/小的数的个数。所以每次更新是O(sqrt(n)*log(sqrt(n))的。
若L和R所在的块相同或相邻时，直接暴力更新即可。

要用树状数组或归并排序求得初始答案。

要注意数据是可重的，所以要打时间戳。
所以为了lower_bound/upper_bound，要定义两套比较法则，一套双关键字，一套单关键字。

 #include<cstdio>
 #include<algorithm>
 #include<cmath>
 using namespace std;
 struct Point{int v,p;Point(const int &a,const int &b){v=a;p=b;}Point(){}};
 bool operator < (const Point &a,const Point &b){return a.v<b.v;}//单关键字比较
 bool operator > (const Point &a,const Point &b){return a.v>b.v;}
 bool operator == (const Point &a,const Point &b){return a.v==b.v ? true : false;}
 bool cmp(const Point &a,const Point &b){return a.v!=b.v ? a.v<b.v : a.p<b.p;}//双关键字比较
 Point b[],a[],c[];
 int n,sz,l[],r[],sum,num[],ans,x,y,m,mid,en;
 int Res,Num;char C,CH[];
 inline int G()
 {
     Res=;C='*';
     while(C<''||C>'')C=getchar();
     while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}
     return Res;
 }
 inline void P(int x)
 {
     if(!x){putchar('');putchar('\n');return;}
     Num=;while(x>)CH[++Num]=x%,x/=;
     while(Num)putchar(CH[Num--]+);
     putchar('\n');
 }
 void LiSan()
 {
     n=G();
     for(int i=;i<=n;i++){b[i].v=G();b[i].p=i;}
     sort(b+,b+n+,cmp);
     for(int i=;i<=n;i++)
       {
           if(b[i].v!=b[i-].v)en++;
         a[b[i].p].v=en;
         a[b[i].p].p=i;
       }
 }
 //树状数组求出初始答案。
 int D[];inline int lowbit(const int &x){return x&(-x);}
 inline int getsum(int x){int res=;while(x>){res+=D[x];x-=lowbit(x);}return res;}
 inline void add(int x,const int &d){while(x<=n){D[x]+=d;x+=lowbit(x);}}
 void Get_First_Ans()
 {for(int i=;i<=n;i++){add(a[i].v,);ans+=(i-getsum(a[i].v));}
 P(ans);}
 void makeblock()
 {
     sz=sqrt(n);
     for(sum=;sum*sz<n;sum++)
       {
         l[sum]=(sum-)*sz+;r[sum]=sum*sz;
           for(int i=l[sum];i<=r[sum];i++)
           num[i]=sum;
       }
     l[sum]=sz*(sum-)+;r[sum]=n;
     for(int i=l[sum];i<=r[sum];i++)
       num[i]=sum;
 }
 void Sort_Each_Block()
 {for(int i=;i<=n;i++)c[i]=a[i];
 for(int i=;i<=sum;i++)sort(a+l[i],a+r[i]+,cmp);}
 inline int Query(const int &L,const int &R)
 {
     swap( a[lower_bound(a+l[num[L]],a+r[num[L]]+,c[L],cmp) - a ]
     , a[lower_bound(a+l[num[R]],a+r[num[R]]+,c[R],cmp)- a ]);//必须双关键字比较
     sort(a+l[num[L]],a+r[num[L]]+,cmp);
     sort(a+l[num[R]],a+r[num[R]]+,cmp);
     int cnt=;
     if(c[L].v<c[R].v)cnt=;
     else if(c[L].v>c[R].v)cnt=-;
     swap(c[L],c[R]);
     if(num[L]+>=num[R])
       for(int i=L+;i<=R-;i++)
           {if(c[i].v>c[R].v)cnt++;else if(c[i].v<c[R].v)cnt--;
            if(c[i].v>c[L].v)cnt--;else if(c[i].v<c[L].v)cnt++;}
     else
       {
           for(int i=L+;i<=r[num[L]];i++)
             {if(c[i].v>c[R].v)cnt++;else if(c[i].v<c[R].v)cnt--;
              if(c[i].v>c[L].v)cnt--;else if(c[i].v<c[L].v)cnt++;}
           for(int i=l[num[R]];i<=R-;i++)
             {if(c[i].v>c[R].v)cnt++;else if(c[i].v<c[R].v)cnt--;
              if(c[i].v>c[L].v)cnt--;else if(c[i].v<c[L].v)cnt++;}
           for(int i=num[L]+;i<=num[R]-;i++)
             {
                 cnt+=( (a+r[i]+) - upper_bound(a+l[i],a+r[i]+,c[R]) );//必须单关键字比较
                 cnt-=( lower_bound(a+l[i],a+r[i]+,c[R]) - (a+l[i]) );
             cnt-=( (a+r[i]+) - upper_bound(a+l[i],a+r[i]+,c[L]) );
             cnt+=( lower_bound(a+l[i],a+r[i]+,c[L]) - (a+l[i]) );
             }
       }
     ans+=cnt;return ans;
 }
 int main()
 {
     LiSan();Get_First_Ans();makeblock();Sort_Each_Block();m=G();
     for(int i=;i<=m;i++){x=G();y=G();if(x>y)swap(x,y);P(Query(x,y));}
     return ;
 }