[NOIP2017]列队线段树

题解：

　　之前写的splay，，，然而一直没调出来，我感觉是某个细节想错了，，然而已经重构4次代码不想再写splay了。于是今天尝试了线段树的解法。

　　首先因为每次出列之后的变化都是将当前行左移，然后将最后一列上移，所以最后一列不适合和其他的行放在一起处理。

　　因此对于每行的前m - 1位开一棵线段树，对于最后一列开一棵线段树。

　　但是因为空间开销过大无法承受，因此考虑动态开点。一开始每棵线段树内只有一个节点，这个节点代表了当前行1 ~ m - 1的所有节点。

　　如果我们要从中删除一个节点，就跟普通线段树类似的向下遍历找到单点，然后修改权值为0，并且同步修改这条链上的节点数总和。跟普通线段树不同的是，动态开点需要在函数的最开头判断这个节点是否存在，如果不存在，就建出这个节点，并给这个节点加上一些基本的信息，然后继续向下遍历。

　　如果我们要添加一个节点到树中，那么我们就直接加在这棵树所有已经存在的叶子节点的后面那个叶子节点处即可。即下图。（虚线表示省略的节点）

同时维护所有线段树即可，注意细节。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define R register int
  4 #define AC 301000
  5 #define ac 8000000
  6 #define LL long long
  7 #define D printf("line in %d
", __LINE__);
  8 
  9 int n, m, q, w, cnt, now;
 10 int root[AC], tree[ac], ls[ac], rs[ac], pos[ac];
 11 LL id[ac], go;//id[ac]要开ac啊，，，，
 12 //对于
 13 inline int read()
 14 {
 15     int x = 0;char c = getchar();
 16     while(c > '9' || c < '0') c = getchar();
 17     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
 18     return x;
 19 }
 20 
 21 inline int cal(int l, int r)
 22 {
 23     if(now <= n)
 24     {
 25         if(r <= m - 1) return r - l + 1;
 26         else if(l <= m - 1) return (m - 1) - l + 1;
 27         else return 0;
 28     }
 29     else
 30     {
 31         if(r <= n) return r - l + 1;
 32         else if(l <= n) return n - l + 1;
 33         else return 0;
 34     }
 35 }
 36 
 37 void kth(int &x, int l, int r)//当前节点，当前区间
 38 {
 39     if(!x) x = ++ cnt, tree[x] = cal(l, r);//第一次开出来自然是满的
 40     if(l == r)
 41     {
 42         tree[x] = 0;
 43         if(!id[x]) go = (now <= n) ? (LL)(now - 1) * (LL)m + l : (LL)m * (LL)l;//如果这个点没有被赋过值，那么就应该是原来的编号
 44         else go = id[x]; //编号爆ll，，，
 45         return ;
 46     }
 47     else
 48     {
 49         -- tree[x];//删除一个节点
 50         int mid = (l + r) >> 1;
 51         int tmp = ls[x] ? tree[ls[x]] : cal(l, mid);//获取左边的节点个数
 52         if(w <= tmp) kth(ls[x], l, mid);
 53         else w -= tmp, kth(rs[x], mid + 1, r);
 54     }
 55 }
 56 
 57 void ins(int &x, int l, int r)
 58 {
 59     if(!x) x = ++ cnt, tree[x] = cal(l, r);
 60     if(l == r) {tree[x] = 1, id[x] = go; return ;}
 61     int mid = (l + r) >> 1;
 62     ++ tree[x];//加入一个节点
 63     if(w <= mid) ins(ls[x], l, mid);//因为已经钦定了位置
 64     else ins(rs[x], mid + 1, r);//不然去右边
 65 }
 66 
 67 void pre()
 68 {
 69     n = read(), m = read(), q = read();
 70     for(R i = 1; i <= n; i ++) root[i] = ++cnt, tree[cnt] = m - 1;
 71     root[n + 1] = ++cnt, tree[cnt] = n;//给最后一列单独开一个
 72 }
 73 
 74 void work()
 75 {
 76     int a, b;LL tmp;
 77     for(R i = 1; i <= q; i ++)
 78     {
 79         a = read(), b = read();
 80         if(b < m)
 81         {
 82             now = a, w = b;
 83             kth(root[now], 1, m + q);//对于维护行的线段树，边界应该是m + q吧
 84             w = a, now = n + 1, tmp = go;//记录出来的人
 85             printf("%lld
", tmp);
 86             kth(root[now], 1, n + q);//从最后一列中取人,
 87             now = a, ++ pos[now], w = m - 1 + pos[now];
 88             ins(root[now], 1, m + q);
 89             now = n + 1, ++ pos[now], w = n + pos[now], go = tmp;//把出来的人放在最后一列的最后一个
 90             ins(root[now], 1, n + q); 
 91         }
 92         else
 93         {
 94             now = n + 1, w = a;
 95             kth(root[now], 1, n + q);
 96             printf("%lld
", go);
 97             ++ pos[now], w = n + pos[now];//直接算出来应该放在哪个位置
 98             ins(root[now], 1, n + q);
 99         }
100     }
101 }
102 
103 int main()
104 {
105 //    freopen("in.in", "r", stdin);
106     pre();
107     work();
108 //    fclose(stdin);
109     return 0;
110 }

View Code

[NOIP2017]列队 线段树

[NOIP2017]列队线段树