Rockdu's Blog
BZOJ3295 动态逆序对
? 解题记录 ? ? BZOJ ? ? Splay ? ? 树套树 ? ? 平衡树 ?    2017-09-21 21:18:12    371    0    0
rockdu   ? 解题记录 ? ? BZOJ ? ? Splay ? ? 树套树 ? ? 平衡树 ?

 

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

Input

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

Output

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

Sample Input

  1. 5 4
  2. 1
  3. 5
  4. 3
  5. 4
  6. 2
  7. 5
  8. 1
  9. 4
  10. 2

Sample Output

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

Hint

 

N<= 100000 M <=50000

二话不说上树套树。用树状数组套平衡树。顺着蓝书上的思路走，我们不妨可以用Splay代替普通平衡树来获得更方便的查询操作。事实证明用Splay的速度也是很可观的。值得注意的是，删除操作并不用将节点直接真正的删除，而可以做一个“假删除”——把节点留下，权值为0，可以减少代码量。

这里提供一个常数巨大的代码……

  1. #include<cstdio>
  2. #define lowbit(x) ((x) & (-x))
  3. using namespace std;
  4. const int maxn = 1e5 + 5;
  5. int n, m;
  6. long long ans;
  7. int org[maxn];
  8. inline void read(int & x) {
  9. 	x = 0;char c = getchar();
  10. 	while(c > '9' || c < '0') c = getchar();
  11. 	while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
  12. }
  13.  
  14. namespace Splay {
  15.     struct node {
  16.         int ch[2], num, sum, cnt, fa;
  17.     }tree[maxn * 30];
  18.     int cnt;
  19.     void push_up(int rt) {
  20.         if(rt == 0) return;
  21.         int tl = tree[rt].ch[0];
  22.         int tr = tree[rt].ch[1];
  23.         tree[rt].sum = tree[rt].cnt + tree[tl].sum + tree[tr].sum;
  24.     }
  25.     void rotate(int rt) {
  26.         int p = tree[rt].fa;
  27.         int a = tree[p].fa;
  28.         int l = tree[p].ch[1] == rt;
  29.         int r = l ^ 1;
  30.         if(a) tree[a].ch[tree[a].ch[1] == p] = rt;
  31.         tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[r]].fa = tree[rt].ch[r] ? p : 0;
  32.         tree[p].ch[l] = tree[rt].ch[r], tree[rt].ch[r] = p;
  33.         push_up(p), push_up(rt);
  34.     }
  35.     void splay(int x, int y, int & root) {
  36.         int des = tree[y].fa;
  37.         while(tree[x].fa != des) {
  38.             int p = tree[x].fa;
  39.             int a = tree[p].fa;
  40.             if(a)
  41.                 if((tree[p].ch[1] == x) ^ (tree[a].ch[1] == p)) rotate(x);
  42.                 else rotate(p);
  43.             rotate(x);
  44.         }
  45.         if(y == root) root = x;
  46.         push_up(x); // 如果没有伸展 
  47.     }
  48.     void insert(int & root, int & now, int x, int last) {
  49.         if(now == 0) { now = ++cnt, tree[now] = (node) {0, 0, x, 1, 1, last};
  50.             splay(now, root, root);return ;}
  51.         if(tree[now].num == x) {++tree[now].cnt, ++tree[now].sum, splay(now, root, root); return;}
  52.         insert(root, tree[now].ch[tree[now].num < x], x, now);
  53.         push_up(now);
  54.     }
  55.     int find(int x, int root) {
  56.         int rt = root, last = 0, lm = 0;
  57.         while(tree[rt].num != x && rt != 0) {
  58.             if(tree[rt].num <= x && tree[rt].num > lm)    
  59.                 lm = tree[rt].num, last = rt;
  60.             rt = tree[rt].ch[x > tree[rt].num];
  61.         }
  62.         return rt == 0 ? last : rt;
  63.     }
  64.     void del(int x, int & root) {
  65.         int rt = find(x, root);
  66.         --tree[rt].sum, --tree[rt].cnt;
  67.         splay(rt, root, root);
  68.     }
  69.     int query(int x, int & root, bool type) { // 0小 1大 
  70.         int rt = find(x, root);
  71.         if(rt == 0)	return type ? tree[root].sum : 0;
  72.         splay(rt, root, root);
  73.         int ret = tree[tree[root].ch[type]].sum;
  74.         if(x != tree[rt].num && type == 0) 
  75. 			ret += tree[rt].cnt;
  76.         return ret;
  77.     }
  78. }
  79.  
  80. namespace BIT{
  81.     int root[maxn << 4], N;
  82.     void init(int n){N = n;}
  83.     int add(int pos, int num) {
  84.         while(pos <= N) Splay::insert(root[pos], root[pos], num, 0), pos += lowbit(pos);
  85.     }
  86.     void del(int pos, int num) {
  87.         while(pos <= N) Splay::del(num, root[pos]), pos += lowbit(pos);
  88.     }
  89.     int query(int pos, int num, bool type) {
  90.         int ret = 0;
  91.         while(pos) {
  92. 			ret += Splay::query(num, root[pos], type);
  93. 			pos -= lowbit(pos);
  94.         }
  95. 		return ret;
  96.     }
  97. }
  98.  
  99. namespace WBIT{
  100.     int tree[maxn << 4], N;
  101.     void init(int n) {N = n;}
  102.     void add(int pos) {while(pos <= N) ++tree[pos], pos += lowbit(pos);}
  103.     int query(int pos) {int ret = 0;while(pos) ret += tree[pos], pos -= lowbit(pos);return ret;}
  104. }
  105.  
  106. int main() {
  107.     read(n), read(m);
  108.     int a;
  109.     BIT::init(n); 
  110.     WBIT::init(n);
  111.     for(register int i = 1; i <= n; ++i) {
  112.         read(a), org[a] = i;
  113.         BIT::add(i, a);
  114.         ans += i - WBIT::query(a) - 1, WBIT::add(a);
  115.     }
  116.     for(register int i = 1; i <= m; ++i) {
  117.         read(a);
  118.         long long sol1 = BIT::query(org[a], a, 1);
  119.         long long sol2 = BIT::query(n, a, 0) - BIT::query(org[a], a, 0);
  120.         printf("%lld\n", ans);
  121.         ans -= (sol1 + sol2);
  122.         BIT::del(org[a], a);
  123.     }  
  124.     return 0;
  125. }

 

上一篇: WUOJ#15 奇妙的棋盘

下一篇: BZOJ3196 二逼平衡树

371 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
Proudly powered by Leanote
文档导航