[洛谷春令营 省选第二次模拟T1] 数列维护100合1【差分+Splay+操作树】
Problem:
时间限制: 1000MS / 空间限制: 32MB-512MB
题目描述
现在你有一个长度为n的数列,你要支持以下100种操作:
- 操作001:询问若可以使用膜法一次令任一区间内的所有数同时+1s或同时-1s,要把某一区间恰好续光都变为0,至少需要几次膜法;
- 操作010:使一个区间内的所有数加上x;
- 操作011:翻转一个区间;
- 操作100:你突然需要大量的膜力,需要回到k次操作之前的状态。此操作也同样视为一种操作。无论之前是否进行过操作100,假设此时是第i次操作,此处就会回到第i-k次操作之前的状态。
输入输出格式
输入格式:
第一行包括两个整数n,m,表示数列长度和操作数量。
第二行n个整数,表示初始数列ai。
接下来m行,每行先给出一个3位的二进制数t,表示操作类型,若t=001,接下来两个整数l,r,表示询问[l,r];若t=010,接下来三个整数l,r,x,表示要把[l,r]中的数都加上x;若t=011,接下来两个整数l,r,表示要翻转[l,r];若t=100,接下来一个整数k,意义同问题描述。
输出格式:
对于每一个询问,输出一行一个整数表示答案。
输入输出样例
输入样例#1:
5 6 3 2 5 4 1 001 1 5 010 1 3 1 001 1 4 011 1 4 100 1 001 1 5
输出样例#1:
6 7 7
说明
对于所有数据点,满足 1<=l<=r<=n, |ai|,|x|<=10000, 0<=ki<i。
各数据点的数据范围见下表, 其中 si 表示操作 i 的数量, 表格中数值均为该数据点可能的最大数值, 保证Σsi=m。
Solution:
这是一道毒瘤题。。调了整整一天才调出来,代码接近 7K。。做题时思路一定要清晰,要注意边界条件的特判!
我们发现,在原数组区间 [l, r] 加 x 在差分数组上体现为单点 l 加 x,单点 r + 1 减 x。
同时,差分的特点是如果把原数组 l 以前和 r 以后的数看成 0 的话,差分数组 [l, r] 的和一定为 0。
所以将区间通过 +1s 和 -1s 续成 0 的最小操作次树就是在上述条件下,差分数组 [l, r + 1] 的正数和。
然后考虑其余操作,操作 010 显然就是两次单点加/减。
操作 011 比较复杂,涉及到区间翻转,需要用 Splay Tree 来维护。
进一步发现,原数组区间 [l, r] 翻转等价于差分数组 [l + 1, r] 翻转,l 和 r + 1 特判修改。
这里的细节一定要注意。。
对于最后一个操作 100,乍一看需要可持久化数据结构,Splay Tree 不可维护。但是由于本题允许离线,可以将操作建成一棵操作树,表示各操作的相对顺序。在操作树上跑一遍 DFS,即可得到所有答案。而且回溯的时候,我们发现操作 010 的区间加可以通过区间减撤销,操作 011 的区间翻转可以通过区间翻转撤销。
部分其他细节见代码。
Code: O(mlogn) [21882K, 3064MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #define MAXN 100005 #define MAXM 100005 using namespace std; typedef long long ll; inline void getint(int &num){ char ch; bool neg = 0; while(!isdigit(ch = getchar())) if(ch == '-') neg = 1; num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; if(neg) num = -num; } int n, m, a[MAXN]; ll ans[MAXM]; int opt[MAXM], l[MAXM], r[MAXM], x[MAXM], topv = 0; vector<int> v[MAXM]; int stk[MAXM], tops = 0; inline void build_operation_tree(){ stk[tops] = ++topv; // 起始节点 for(register int i = 1; i <= m; i++){ int _opt, _x; getint(_opt); if(_opt == 100) getint(_x), stk[tops + 1] = stk[tops - _x], tops++; // 栈中路径回退 _x 步 else{ v[stk[tops]].push_back(++topv), stk[++tops] = topv; opt[topv] = _opt, getint(l[topv]), getint(r[topv]); if(_opt == 10) getint(x[topv]); } } } struct Node{ #define islc(u) ((u) == (u)->fa->lc) #define isrc(u) ((u) == (u)->fa->rc) #define prot(u, nam) ((u) ? (u)->nam : 0) int val, size, revf, addf; ll possum, sum; // 维护区间正数和以及区间和 Node *fa, *lc, *rc; Node() {} Node(int v, int s, Node *f, Node *l, Node *r): val(v), size(s), revf(0), addf(0), fa(f), lc(l), rc(r) {} inline void update(){ size = prot(lc, size) + prot(rc, size) + 1; possum = prot(lc, possum) + prot(rc, possum) + (val > 0 ? val : 0); sum = prot(lc, sum) + prot(rc, sum) + val; } inline void pushdown(){ if(addf){ if(lc) lc->val += addf, lc->addf += addf; if(rc) rc->val += addf, rc->addf += addf; addf = 0, update(); // 此处由于左右子树被修改, 需要 update() 来维护 } if(revf){ swap(lc, rc); if(lc) lc->revf ^= 1, lc->val = -lc->val, lc->possum -= lc->sum, lc->sum = -lc->sum; if(rc) rc->revf ^= 1, rc->val = -rc->val, rc->possum -= rc->sum, rc->sum = -rc->sum; revf = 0, update(); // 此处由于左右子树被修改, 需要 update() 来维护 } } } pool[MAXN << 2], *root; inline Node* newNode(int v, int s, Node *f, Node *l, Node *r){ static int topp = 0; pool[topp] = Node(v, s, f, l, r); return &pool[topp++]; } inline Node* build(int *a, int l, int r, Node *fa = NULL){ int smid = l + r >> 1; Node *cur = newNode(a[smid], 0, fa, NULL, NULL); if(l < smid) cur->lc = build(a, l, smid - 1, cur); if(smid < r) cur->rc = build(a, smid + 1, r, cur); return cur->update(), cur; } inline void right_rotate(Node *cur){ Node *o = cur->lc; if(!o) return; cur->pushdown(), o->pushdown(); cur->lc = o->rc, o->rc ? o->rc->fa = cur : 0; o->fa = cur->fa, !cur->fa ? root = o : islc(cur) ? cur->fa->lc = o : cur->fa->rc = o; o->rc = cur, cur->fa = o; cur->update(), o->update(); } inline void left_rotate(Node *cur){ Node *o = cur->rc; if(!o) return; cur->pushdown(), o->pushdown(); cur->rc = o->lc, o->lc ? o->lc->fa = cur : 0; o->fa = cur->fa, !cur->fa ? root = o : islc(cur) ? cur->fa->lc = o : cur->fa->rc = o; o->lc = cur, cur->fa = o; cur->update(), o->update(); } inline void splay(Node *cur, Node *tf){ while(cur->fa != tf){ if(cur->fa->fa == tf) islc(cur) ? right_rotate(cur->fa) : left_rotate(cur->fa); else if(islc(cur) && islc(cur->fa)) right_rotate(cur->fa->fa), right_rotate(cur->fa); else if(isrc(cur) && isrc(cur->fa)) left_rotate(cur->fa->fa), left_rotate(cur->fa); else if(islc(cur) && isrc(cur->fa)) right_rotate(cur->fa), left_rotate(cur->fa); else left_rotate(cur->fa), right_rotate(cur->fa); } } inline Node* find(int id){ Node *p = root; while(p){ p->pushdown(); int lsize = prot(p->lc, size) + 1; if(id < lsize) p = p->lc; else if(id > lsize) id -= lsize, p = p->rc; else return p; } return NULL; } inline void reverse(int l, int r){ if(l > r) return; Node *pl = find(l - 1), *pr = find(r + 1); if(pl && pr) splay(pl, NULL), splay(pr, pl), pr->lc ? pr->lc->revf ^= 1, pr->lc->val = -pr->lc->val, pr->lc->possum -= pr->lc->sum, pr->lc->sum = -pr->lc->sum : 0; else if(pl) splay(pl, NULL), pl->rc ? pl->rc->revf ^= 1, pl->rc->val = -pl->rc->val, pl->rc->possum -= pl->rc->sum, pl->rc->sum = -pl->rc->sum : 0; else if(pr) splay(pr, NULL), pr->lc ? pr->lc->revf ^= 1, pr->lc->val = -pr->lc->val, pr->lc->possum -= pr->lc->sum, pr->lc->sum = -pr->lc->sum : 0; else root ? root->revf ^= 1, root->val = -root->val, root->possum -= root->sum, root->sum = -root->sum : 0; // reverse() 的同时需要将区间取反, 注意维护 } inline void modify(int id, int v){ Node *pid = find(id); if(!pid) return; pid->val = v; while(pid) pid->update(), pid = pid->fa; } inline void add(int id, int v){ Node *pid = find(id); if(!pid) return; pid->val += v; while(pid) pid->update(), pid = pid->fa; } inline ll query_possum(int l, int r){ if(l > r) return 0; Node *pl = find(l - 1), *pr = find(r + 1); if(pl && pr) return splay(pl, NULL), splay(pr, pl), pr->lc ? pr->lc->possum : 0; else if(pl) return splay(pl, NULL), pl->rc ? pl->rc->possum : 0; else if(pr) return splay(pr, NULL), pr->lc ? pr->lc->possum : 0; else return root ? root->possum : 0; } inline ll query_sum(int l, int r){ if(l > r) return 0; Node *pl = find(l - 1), *pr = find(r + 1); if(pl && pr) return splay(pl, NULL), splay(pr, pl), pr->lc ? pr->lc->sum : 0; else if(pl) return splay(pl, NULL), pl->rc ? pl->rc->sum : 0; else if(pr) return splay(pr, NULL), pr->lc ? pr->lc->sum : 0; else return root ? root->sum : 0; } inline void dfs(int u){ if(opt[u] == 1){ ll lnum = query_sum(1, l[u] - 1); add(l[u], lnum); ll rnum = -query_sum(l[u], r[u]); ans[u] = query_possum(l[u], r[u]) + (rnum > 0 ? rnum : 0); add(l[u], -lnum); // 玄学操作, 将查询区间外的数看作 0, 那么 l, r + 1 两处差分值需要重新计算 // 重新计算完毕后, 易证得区间 +1/-1 操作最少次数即为差分值的正数和 } else if(opt[u] == 10) add(l[u], x[u]), add(r[u] + 1, -x[u]); else if(opt[u] == 11){ ll lval = query_sum(l[u], r[u]), rval = query_sum(l[u] + 1, r[u] + 1); reverse(l[u] + 1, r[u]), modify(l[u], lval), modify(r[u] + 1, rval); // 玄学操作, 区间 [l, r] 翻转相当于差分值 [l + 1, r] 翻转并取反, 然后 l, r + 1 需要特判修改 } int sz = v[u].size(); for(register int i = 0; i < sz; i++) dfs(v[u][i]); if(opt[u] == 10) add(l[u], -x[u]), add(r[u] + 1, x[u]); else if(opt[u] == 11){ ll lval = query_sum(l[u], r[u]), rval = query_sum(l[u] + 1, r[u] + 1); reverse(l[u] + 1, r[u]), modify(l[u], lval), modify(r[u] + 1, rval); } // 模拟回溯过程, 区间加 <=> 区间减, 区间翻转 <=> 区间反转 } int main(){ getint(n), getint(m); for(register int i = 1; i <= n; i++) getint(a[i]); a[n + 1] = -a[n]; for(register int i = n; i; i--) a[i] -= a[i - 1]; // 差分 root = build(a, 1, ++n), build_operation_tree(); memset(ans, -1, sizeof(ans)), dfs(1); for(register int i = 2; i <= m + 1; i++) if(ans[i] != -1) printf("%lld\n", ans[i]); // 保证先后顺序 return 0; }
发表评论