BZOJ3295 [Cqoi2011]动态逆序对 —— CDQ分治

时间：2024-09-21 16:04:32

题目链接：https://vjudge.net/problem/HYSBZ-3295

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 6517  Solved: 2295
[Submit][Status][Discuss]

Description

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删
除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。
以下n行每行包含一个1到n之间的正整数，即初始排列。
以下m行每行一个正整数，依次为每次删除的元素。
N<=100000 M<=50000

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

题解：

1.最核心的问题是：删除当前位置的数，会造成多少对逆序对的减少。

2.要统计删除当前数会造成多少对逆序对的减少，即需要统计：前面比它大的数的个数 + 后面比它小的数的个数 （前提是这些数没有被删除）。

3.由于题目还存在动态删除，则再为每个位置添加一个标志：Di，表明它是第几个被删除的。加上这个限制，就是一个三维偏序问题了。

4.以j为统计对象，sum[j]为删除位置j的数，所减少的逆序对。sum[j] = sum （i<j 且 Ai>Aj 且 Di>Dj）+ （j<i 且 Aj>Ai 且 Di>Dj）

5.得到sum数组之后，即知道删除当前位置的数，会造成多少对逆序对的减少。那么再算出初始的逆序对（不带删除，即二维偏序）即可。

写法一：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e5+;

 struct node

 {

     int x, y, z;

 };

 node a[MAXN], b[MAXN], tmp[MAXN];

 int n, m, c[MAXN];

 int lowbit(int x) {return x&(-x);}

 void add(int x, int val) {for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}

 int query(int x) {int ret=; for(int i=x;i>;i-=lowbit(i))ret+=c[i]; return ret;}

 int sum[MAXN], type;

 void CDQ(int l, int r)

 {

     if(l==r) return;

     int mid = (l+r)>>;

     CDQ(l, mid); CDQ(mid+, r);

     int p1 = l, p2 = mid+;

     for(int i = l; i<=r; i++)

     {

         if(p2>r||(p1<=mid&&a[p1].y>=a[p2].y)) b[i] = a[p1++];

         else b[i] = a[p2++];

     }

     int cnt = ;    //按删除顺序逆序排序了，所以先出现的更后删除

     for(int i = l; i<=r; i++)   //统计前面比它小的

     {

         a[i] = b[i];

         if(a[i].x<=mid) add(a[i].z, ), cnt++;

         else if(a[i].y!=INF) sum[a[i].y] += cnt-query(a[i].z);

     }

     for(int i = l; i<=r; i++)

         if(a[i].x<=mid) add(a[i].z, -);

     for(int i = l; i<=r; i++)   //统计后面比它大的

     {

         a[i] = b[i];

         if(a[i].x>mid) add(a[i].z, );

         else if(a[i].y!=INF) sum[a[i].y] += query(a[i].z-);

     }

     for(int i = l; i<=r; i++)

         if(a[i].x>mid) add(a[i].z, -);

 }

 int M[MAXN];

 int main()

 {

     while(scanf("%d%d", &n,&m)!=EOF)

     {

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

         {

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

             M[a[i].z] = i;

             a[i].x = i; a[i].y = INF;

         }

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

         {

             int del;

             scanf("%d", &del);

             a[M[del]].y = i;

         }

         LL ans = ;

         memset(c, , sizeof(c));

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

         {

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

             add(a[i].z, );

         }

         memset(c, , sizeof(c));

         memset(sum, , sizeof(sum));

         CDQ(,n);

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

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

         {

             ans -= sum[i];

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

         }

     }

 }

写法二：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 1e5+;

 struct node

 {

     int x, y, z;

 };

 node a[MAXN], b[MAXN];

 int n, m, c[MAXN];

 int lowbit(int x) {return x&(-x);}

 void add(int x, int val) {for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}

 int query(int x) {int ret=; for(int i=x;i>;i-=lowbit(i))ret+=c[i]; return ret;}

 int sum[MAXN], type;

 void CDQ(int l, int r)

 {

     if(l==r) return;

     int mid = (l+r)>>;

     CDQ(l, mid); CDQ(mid+, r);

     int p1 = l, p2 = mid+;

     for(int i = l; i<=r; i++)

     {

         if(p2>r||(p1<=mid&&a[p1].y>=a[p2].y)) b[i] = a[p1++];

         else b[i] = a[p2++];

     }

     int cnt = ;

     for(int i = l; i<=r; i++)

     {

         a[i] = b[i];

         if(a[i].x<=mid) add(a[i].z, ), cnt++;

         else if(a[i].y!=INF)

         {

             if(type) sum[a[i].y] += cnt-query(a[i].z);

             else sum[a[i].y] += query(a[i].z-);

         }

     }

     for(int i = l; i<=r; i++)

         if(a[i].x<=mid) add(a[i].z, -);

 }

 node tmp[MAXN];

 int M[MAXN];

 int main()

 {

     while(scanf("%d%d", &n,&m)!=EOF)

     {

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

         {

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

             M[a[i].z] = i;

             a[i].y = INF;

         }

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

         {

             int del;

             scanf("%d", &del);

             a[M[del]].y = i;

         }

         LL ans = ;

         memset(c, , sizeof(c));

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

         {

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

             add(a[i].z, );

         }

         memcpy(tmp, a, sizeof(tmp));

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

             a[i].x = i;

         memset(c, , sizeof(c));

         type = ;

         CDQ(,n);

         memcpy(a, tmp, sizeof(a));

         reverse(a+,a++n);

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

             a[i].x = i;

         type = ;

         CDQ(,n);

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

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

         {

             ans -= sum[i];

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

         }

     }

 }

相关文章