[洛谷春令营 省选第二次模拟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;
}
发表评论