Dynamic Inversions 50个树状数组

Dynamic Inversions

Time Limit: 30000/15000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

SubmitStatus

Problem Description

给出N个数a[1],a[2] ... a[N]，有M个操作，每个操作给出x,y两个数，你将a[x]，a[y]交换，然后求交换后数组的逆序对个数。
逆序对的意思是1 <= i < j <= N 且a[i] > a[j].

Input

多组数据，每组数据:

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

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

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

Output

对于每组数据，输出M + 1行，第一行是开始时的逆序对数目，接下去M行每行一个数，表示这次修改后的逆序对数目

Sample Input

Sample Output

Hint

第二个样例，一开始1 2 3，逆序对数为0，交换第1,2个元素，变为2 1 3,答案为1，交换第2和3个元素，变为2 3 1，逆序对数为2，交换第3和1个元素，逆序对数为1，此时序列变成1 3 2

二维树状数组做法：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 #define ll long long

 int b[][],a[],n,c[];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update1(int x)

 {

     while(x<)

     {

         c[x]++;

         x+=lowbit(x);

     }

 }

 int query1(int x)

 {

     int sum=;

     while(x>)

     {

         sum+=c[x];

         x-=lowbit(x);

     }

     return sum;

 }

 void update(int x,int y,int z)

 {

     for(int i=x; i<=; i+=lowbit(i))

         for(int j=y; j<=n; j+=lowbit(j))

             b[i][j]+=z;

 }

 int query(int x,int y,int x1,int y1)

 {

     int ans=,i,j;

     for(i=y;i>;i-=lowbit(i))

     for(j=y1;j>;j-=lowbit(j))

     ans+=b[i][j];

     for(i=x-;i>;i-=lowbit(i))

     for(j=y1;j>;j-=lowbit(j))

     ans-=b[i][j];

     for(i=y;i>;i-=lowbit(i))

     for(j=x1-;j>;j-=lowbit(j))

     ans-=b[i][j];

     for(i=x-;i>;i-=lowbit(i))

     for(j=x1-;j>;j-=lowbit(j))

     ans+=b[i][j];

     return ans;

 }

 int main()

 {

     int i,m,x,y;

     ll ans;

     while(~scanf("%d",&n))

     {

         ans=;

         memset(b,,sizeof(b));

         memset(c,,sizeof(c));

         for(i=; i<=n; i++)

         {

             scanf("%d",&a[i]);

             update1(a[i]);

             ans+=i-query1(a[i]);

             update(a[i],i,);

         }

         printf("%lld\n",ans);

         scanf("%d",&m);

         for(i=; i<m; i++)

         {

             scanf("%d%d",&x,&y);

             if(x>y)swap(x,y);

             ans-=query(a[y]+,,x+,y);

             ans+=query(,a[y]-,x+,y);

             ans+=query(a[x]+,,x,y-);

             ans-=query(,a[x]-,x,y-);

             if(a[x]>a[y])ans--;

             else if(a[x]<a[y])ans++;

             update(a[x],x,-);

             update(a[x],y,);

             update(a[y],y,-);

             update(a[y],x,);

              swap(a[x],a[y]);

             printf("%lld\n",ans);

         }

     }

 }

50个一维的做法：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 #define ll long long

 int a[][],b[],n,c[];

 int lowbit(int x)

 {

     return x&(-x);

 }

 int update(int x)

 {

     while(x<)

     {

         b[x]++;

         x+=lowbit(x);

     }

 }

 int update1(int i,int x,int y)

 {

     while(x<=n)

     {

         a[i][x]+=y;

         x+=lowbit(x);

     }

 }

 int query(int x)

 {

     int sum=;

     while(x>)

     {

         sum+=b[x];

         x-=lowbit(x);

     }

     return sum;

 }

 int query1(int i,int x)

 {

     int sum=;

     while(x>)

     {

         sum+=a[i][x];

         x-=lowbit(x);

     }

     return sum;

 }

 int main()

 {

     int i,j,m,x,y,z;

     ll ans,temp,temp1;

     while(~scanf("%d",&n))

     {

         memset(b,,sizeof(b));

         memset(a,,sizeof(a));

         memset(c,,sizeof(c));

         ans=;

         for(i=; i<=n; i++)

         {

             scanf("%d",&a[][i]);

             c[a[][i]]++;

             ans+=i-query(a[][i])-;

             update(a[][i]);

             update1(a[][i],i,);

         }

         printf("%lld\n",ans);

         scanf("%d",&m);

         for(i=; i<m; i++)

         {

             scanf("%d%d",&x,&y);

             if(x>y)swap(x,y);

             z=y-x;

             temp=;

             for(j=; j<a[][y]; j++)

             {

                 temp+=query1(j,y-)-query1(j,x-);

             }

             temp1=query1(j,y-)-query1(j,x-);

             ans+=temp-(z-temp1-temp);

             temp=;

             for(j=; j<a[][x]; j++)

             {

                 temp+=query1(j,y-)-query1(j,x-);

             }

             temp1=query1(j,y-)-query1(j,x-);

             ans+=(z-temp1-temp)-temp;

             update1(a[][x],x,-);

             update1(a[][x],y,);

             update1(a[][y],y,-);

             update1(a[][y],x,);

             swap(a[][y],a[][x]);

             printf("%lld\n",ans);

         }

     }

 }

秒客网