【NOI2005】维护数列

阳光穿透心脏的1/2处 2023-06-05 08:53 101阅读 0赞

### Description ###

维护一个数列的如下操作：

*  在某个位置后插入一段数列
 *  在某个位置后删除一段数列
 *  将连续的一段数列修改为某个值
 *  将一段数列翻转
 *  求一段数列的和
 *  求整个数列的最大子段和

### Solution ###

魔鬼Splay题

用Splay维护序列，以下标为权值建树。

如果插入一段序列，我们就将这段序列本身先建成一棵树，然后连到原来的树上即可

如果删除一段序列，那么直接切断子树即可

修改和翻转操作可以维护两个标记

最大子段和可以维护三个变量来实现

具体见代码

由于本题的空间限制比较严格，所以我们需要尽可能的节省空间，具体地，每次删除操作的时候，我们记录被删除的点的编号，放入一个“垃圾箱”

如果新建节点时垃圾箱不为空那么直接使用垃圾箱里的节点编号即可

时间复杂度为$O(mlogn)$

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 namespace shl {
      3     typedef long long ll;
      4     using std :: max;
      5     const int N = 500010;
      6     const ll INF = 2147483647;
      7     inline int read() {
      8         int ret = 0, op = 1;
      9         char c = getchar();
     10         while (!isdigit(c)) {
     11             if (c == '-') op = -1; 
     12             c = getchar();
     13         }
     14         while (isdigit(c)) {
     15             ret = (ret << 3) + (ret << 1) + c - '0';
     16             c = getchar();
     17         }
     18         return ret * op;
     19     }
     20     struct Splay {
     21         int fa, ch[2], tag, rev, size;
     22         ll sum, val, lmax, rmax, maxx;
     23     } a[N];
     24     int n, m;
     25     int tot = 0, root = 0;
     26     int bin[N << 2], bintop = 0;
     27     ll in[N];
     28     char opt[15];
     29     int New(int val) {
     30         int id = bintop ? bin[bintop--] : ++tot;
     31         a[id].fa = a[id].ch[0] = a[id].ch[1] = a[id].rev = a[id].tag = 0; 
     32         a[id].size = 1; a[id].val = val;
     33         a[id].sum = a[id].maxx = val; a[id].lmax = a[id].rmax = max(val, 0);
     34         return id;
     35     }
     36     void recycle(int now) {
     37         int l = a[now].ch[0];
     38         int r = a[now].ch[1];
     39         if (l) recycle(l);
     40         if (r) recycle(r);
     41         bin[++bintop] = now;
     42     }
     43     inline void pushup(int now) {
     44         int l = a[now].ch[0], r = a[now].ch[1];
     45         a[now].size = a[l].size + a[r].size + 1;
     46         a[now].sum = a[l].sum + a[r].sum + a[now].val;
     47         a[now].lmax = max(a[l].lmax, a[l].sum + a[now].val + a[r].lmax);
     48         a[now].rmax = max(a[r].rmax, a[r].sum + a[now].val + a[l].rmax);
     49         a[now].maxx = max(max(a[l].maxx, a[r].maxx), a[l].rmax + a[now].val + a[r].lmax);
     50     }
     51     inline void pushdown(int now) {
     52         int l = a[now].ch[0], r = a[now].ch[1];
     53         if (a[now].tag) {
     54             if (l) a[l].val = a[now].val, a[l].tag = 1, a[l].sum = a[now].val * a[l].size;
     55             if (r) a[r].val = a[now].val, a[r].tag = 1, a[r].sum = a[now].val * a[r].size;
     56             if (a[now].val > 0) {
     57                 if (l) a[l].lmax = a[l].rmax = a[l].maxx = a[l].sum;
     58                 if (r) a[r].lmax = a[r].rmax = a[r].maxx = a[r].sum;
     59             }
     60             else {
     61                 if (l) a[l].lmax = a[l].rmax = 0, a[l].maxx = a[l].val;
     62                 if (r) a[r].lmax = a[r].rmax = 0, a[r].maxx = a[r].val;
     63             }
     64             a[now].tag = 0;
     65         }
     66         if (a[now].rev) {
     67             if (l) a[l].rev ^= 1, std :: swap(a[l].ch[0], a[l].ch[1]), std :: swap(a[l].lmax, a[l].rmax);
     68             if (r) a[r].rev ^= 1, std :: swap(a[r].ch[0], a[r].ch[1]), std :: swap(a[r].lmax, a[r].rmax);
     69             a[now].rev = 0;
     70         }
     71     }
     72     inline void connect(int x, int fa, int op) {
     73         a[x].fa = fa; a[fa].ch[op] = x;
     74     }
     75     inline void rotate(int x) {
     76         int y = a[x].fa;
     77         int z = a[y].fa;
     78         int xson = a[y].ch[1] == x;
     79         int yson = a[z].ch[1] == y;
     80         int B = a[x].ch[xson ^ 1];
     81         connect(B, y, xson); connect(y, x, xson ^ 1); connect(x, z, yson);
     82         pushup(y); pushup(x);
     83     }
     84     void splay(int from, int to) {
     85         while (a[from].fa != to) {
     86             int y = a[from].fa;
     87             int z = a[y].fa;
     88             if (z != to) 
     89                 (a[y].ch[0] == from) ^ (a[z].ch[0] == y) ? rotate(from) : rotate(y);
     90             rotate(from);
     91         }
     92         if (to == 0) root = from;
     93     }
     94     int build(int fa, int l, int r) {
     95         if (l > r) return 0;
     96         int mid = l + r >> 1;
     97         int now = New(in[mid]);
     98         a[now].fa = fa;
     99         a[now].ch[0] = build(now, l, mid - 1);
    100         a[now].ch[1] = build(now, mid + 1, r);
    101         pushup(now);
    102         return now;
    103     }
    104     int kth(int now, int k) {
    105         pushdown(now);
    106         int l = a[now].ch[0];
    107         int r = a[now].ch[1];
    108         if (k <= a[l].size) return kth(l, k);
    109         if (k == a[l].size + 1) return now;
    110         return kth(r, k - a[l].size - 1);
    111     }
    112     void insert(int x, int num) {
    113         int now = build(0, 1, num);
    114         int u = kth(root, x); splay(u, 0);
    115         int v = kth(root, x + 1); splay(v, u);
    116         a[v].ch[0] = now;
    117         a[now].fa = v;
    118         pushup(v); pushup(u);
    119     }
    120     void del(int l, int r) {
    121         int u = kth(root, l - 1); splay(u, 0);
    122         int v = kth(root, r + 1); splay(v, u);
    123         recycle(a[v].ch[0]); 
    124         a[v].ch[0] = 0;
    125         pushup(v); pushup(u);
    126     }
    127     void update(int l, int r, int data) {
    128         int u = kth(root, l - 1); splay(u, 0); 
    129         int v = kth(root, r + 1); splay(v, u);    
    130         int now = a[v].ch[0];
    131         a[now].val = data;
    132         a[now].tag = 1;
    133         a[now].sum = data * a[now].size;
    134         if (data > 0) a[now].lmax = a[now].rmax = a[now].maxx = a[now].sum;
    135         else a[now].lmax = a[now].rmax = 0, a[now].maxx = a[now].val;
    136         pushup(v); pushup(u);        
    137     }
    138     void reverse(int l, int r) {
    139         int u = kth(root, l - 1); splay(u, 0); 
    140         int v = kth(root, r + 1); splay(v, u);    
    141         int now = a[v].ch[0];
    142         a[now].rev ^= 1;
    143         std :: swap(a[now].ch[0], a[now].ch[1]);
    144         std :: swap(a[now].lmax, a[now].rmax);
    145         pushup(v); pushup(u);    
    146     }
    147     ll querymaxx() {
    148         return a[root].maxx;
    149     }
    150     ll querysum(int l, int r) {
    151         int u = kth(root, l - 1); splay(u, 0); 
    152         int v = kth(root, r + 1); splay(v, u);
    153         
    154         return a[a[v].ch[0]].sum;
    155     }
    156     inline void init() {
    157         a[0].fa = a[0].ch[0] = a[0].ch[1] = a[0].rev = a[0].tag = 0;
    158         a[0].maxx = -INF;
    159         a[0].sum = a[0].val = a[0].size = 0;
    160         a[0].lmax = a[0].rmax = 0;
    161      }
    162     int main() {
    163         init();
    164         n = read() + 2; m = read();
    165         in[1] = in[n] = -INF;
    166         for (register int i = 2; i < n; ++i) in[i] = read();
    167         root = build(0, 1, n);
    168         while (m--) {
    169             scanf("%s", opt);
    170             if (opt[0] == 'M' && opt[2] == 'X') {printf("%lld\n", querymaxx()); continue ;}
    171             int x = read() + 1;
    172             int num = read();
    173             if (opt[0] == 'I') {
    174                 for (register int i = 1; i <= num; ++i) in[i] = read();
    175                 insert(x, num);
    176             }
    177             else if (opt[0] == 'D') del(x, x + num - 1);
    178             else if (opt[0] == 'M' && opt[2] == 'K') update(x, x + num - 1, read());
    179             else if (opt[0] == 'R') reverse(x, x + num - 1);
    180             else if (opt[0] == 'G') printf("%lld\n", querysum(x, x + num - 1));
    181         }    
    182         return 0;
    183     }
    184 };
    185 int main() {
    186     shl :: main();
    187     return 0;
    188 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11372972.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a31023ae15aa484985a120ee3f9b50c5.png