[洛谷春令营 省选第二次模拟T1] 数列维护100合1【差分+Splay+操作树】

  • 2018-02-26
  • 0
  • 0

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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai