多组数据，每组数据:

一个N，接下来一行有N个数a[1]... a[N]

再下去一行是M，最后M行每行两个数x,y

1 <= N,M <= 10^5, 1 <= x,y <= N，1 <= a[i] <= 50

21 212 131 2 331 22 33 1

010121

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 #define ll long long 8 int b[60][100100],a[100100],n,c[60]; 9 int lowbit(int x)10 {11     return x&(-x);12 }13 void update1(int x)14 {15     while(x<60)16     {17         c[x]++;18         x+=lowbit(x);19     }20 }21 int query1(int x)22 {23     int sum=0;24     while(x>0)25     {26         sum+=c[x];27         x-=lowbit(x);28     }29     return sum;30 }31 void update(int x,int y,int z)32 {33     for(int i=x; i<=50; i+=lowbit(i))34         for(int j=y; j<=n; j+=lowbit(j))35             b[i][j]+=z;36 }37 int query(int x,int y,int x1,int y1)38 {39     int ans=0,i,j;40     for(i=y;i>0;i-=lowbit(i))41     for(j=y1;j>0;j-=lowbit(j))42     ans+=b[i][j];43 44     for(i=x-1;i>0;i-=lowbit(i))45     for(j=y1;j>0;j-=lowbit(j))46     ans-=b[i][j];47 48     for(i=y;i>0;i-=lowbit(i))49     for(j=x1-1;j>0;j-=lowbit(j))50     ans-=b[i][j];51 52     for(i=x-1;i>0;i-=lowbit(i))53     for(j=x1-1;j>0;j-=lowbit(j))54     ans+=b[i][j];55     return ans;56 }57 int main()58 {59     int i,m,x,y;60     ll ans;61     while(~scanf("%d",&n))62     {63         ans=0;64         memset(b,0,sizeof(b));65         memset(c,0,sizeof(c));66         for(i=1; i<=n; i++)67         {68             scanf("%d",&a[i]);69             update1(a[i]);70             ans+=i-query1(a[i]);71             update(a[i],i,1);72         }73         printf("%lld\n",ans);74         scanf("%d",&m);75         for(i=0; i<m; i++)76         {77             scanf("%d%d",&x,&y);78             if(x>y)swap(x,y);79             ans-=query(a[y]+1,50,x+1,y);80             ans+=query(1,a[y]-1,x+1,y);81             ans+=query(a[x]+1,50,x,y-1);82             ans-=query(1,a[x]-1,x,y-1);83             if(a[x]>a[y])ans--;84             else if(a[x]<a[y])ans++;85             update(a[x],x,-1);86             update(a[x],y,1);87             update(a[y],y,-1);88             update(a[y],x,1);89              swap(a[x],a[y]);90             printf("%lld\n",ans);91         }92     }93 }

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 #define ll long long 8 int a[51][100010],b[60],n,c[60]; 9 int lowbit(int x)10 {11     return x&(-x);12 }13 int update(int x)14 {15     while(x<60)16     {17         b[x]++;18         x+=lowbit(x);19     }20 }21 int update1(int i,int x,int y)22 {23     while(x<=n)24     {25         a[i][x]+=y;26         x+=lowbit(x);27     }28 }29 int query(int x)30 {31     int sum=0;32     while(x>0)33     {34         sum+=b[x];35         x-=lowbit(x);36     }37     return sum;38 }39 int query1(int i,int x)40 {41     int sum=0;42     while(x>0)43     {44         sum+=a[i][x];45         x-=lowbit(x);46     }47     return sum;48 }49 int main()50 {51     int i,j,m,x,y,z;52     ll ans,temp,temp1;53     while(~scanf("%d",&n))54     {55         memset(b,0,sizeof(b));56         memset(a,0,sizeof(a));57         memset(c,0,sizeof(c));58         ans=0;59         for(i=1; i<=n; i++)60         {61             scanf("%d",&a[0][i]);62             c[a[0][i]]++;63             ans+=i-query(a[0][i])-1;64             update(a[0][i]);65             update1(a[0][i],i,1);66         }67         printf("%lld\n",ans);68         scanf("%d",&m);69         for(i=0; i<m; i++)70         {71             scanf("%d%d",&x,&y);72             if(x>y)swap(x,y);73             z=y-x;74             temp=0;75             for(j=1; j<a[0][y]; j++)76             {77                 temp+=query1(j,y-1)-query1(j,x-1);78             }79             temp1=query1(j,y-1)-query1(j,x-1);80             ans+=temp-(z-temp1-temp);81             temp=0;82             for(j=1; j<a[0][x]; j++)83             {84                 temp+=query1(j,y-1)-query1(j,x-1);85             }86             temp1=query1(j,y-1)-query1(j,x-1);87             ans+=(z-temp1-temp)-temp;88             update1(a[0][x],x,-1);89             update1(a[0][x],y,1);90             update1(a[0][y],y,-1);91             update1(a[0][y],x,1);92             swap(a[0][y],a[0][x]);93             printf("%lld\n",ans);94         }95     }96 }