本文共 2989 字，大约阅读时间需要 9 分钟。

题目

思路

题外话：一开始用$\text{Splay}$写了一发，结果……

然后就换成了$\text{Treap}$。嗯，无旋$\text{Treap}$。

直接用$\text{split}$把$[l,r]$割下来，然后打标记。当然，因为翻转之后将不满足二叉搜索树的性质，所以按照个数划分——按照前$x$个为一颗树的原则分裂。

好像就没了？毕竟是板题嘛。

代码

#include <cstdio>#include <iostream>#include <algorithm>#include <vector>#include <cstdlib>#include <map>using namespace std;inline int readint(){   	int a = 0, f = 1; char c = getchar();	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -1;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}inline void writeint(int x){   	if(x < 0) putchar('-'), x = -x;	if(x > 9) writeint(x/10);	putchar(x%10+'0');}const int MaxN = 100005;namespace Treap{   	int prio[MaxN], data[MaxN];	int son[MaxN][2], root;	unsigned size[MaxN], cnt[MaxN];	bool tag[MaxN];	vector<int> pool;	void newTreap(){   		pool.clear();		for(int i=1; i<MaxN; ++i)			pool.push_back(i);		root = cnt[0] = size[0] = prio[0] = 0;	}	int newNode(int x){   		int id = pool.back(); pool.pop_back();		data[id] = x, size[id] = cnt[id] = 1;		son[id][0] = son[id][1] = 0, prio[id] = rand();		return id;	}	void deleteNode(int id){   		pool.push_back(id);	}	void pushUp(int o){   		size[o] = cnt[o]+size[son[o][0]]+size[son[o][1]];	}	void pushDown(int o){   		tag[son[o][0]] ^= tag[o];		tag[son[o][1]] ^= tag[o];		if(tag[o])			swap(son[o][0],son[o][1]);		tag[o] = 0;	}	void changeNode(int o,int addv){   		cnt[o] += addv, size[o] += addv;	}	int merge(int a,int b){   		pushDown(a), pushDown(b);		if(not a or not b) return a+b;		if(prio[a] < prio[b]) son[b][0] = merge(a,son[b][0]);		else son[a][1] = merge(son[a][1],b);		pushUp(a), pushUp(b);		return prio[a] < prio[b] ? b : a;	}	pair<int,int> split(unsigned count,int o){   		if(not o) return make_pair(0,0);		pushDown(o); pair<int,int> ppl;		if(count >= size[son[o][0]]+cnt[o]){   			ppl = split(count-size[son[o][0]]-cnt[o],son[o][1]);			son[o][1] = ppl.first; ppl.first = o;		}		else{   			ppl = split(count,son[o][0]);			son[o][0] = ppl.second; ppl.second = o;		}		pushUp(o); return ppl;	}	void init(int n){    // 笛卡尔树构建法 		vector<int> v; v.clear(); newTreap();		for(int i=1,o,k; i<=n; ++i){   			o = newNode(i);			while(not v.empty()){   				k = v.back(); son[k][1] = o;				if(prio[k] < prio[o]){   					son[k][1] = son[o][0];					son[o][0] = k;				}				pushUp(k), pushUp(o);				if(prio[k] > prio[o]) break;				v.pop_back();			}			if(v.empty()) root = o;			v.push_back(o);		}	}	void flip(int l,int r){   		pair<int,int> lPart = split(l-1,root);		pair<int,int> rPart = split(r-l+1,lPart.second);		tag[rPart.first] ^= 1;		root = merge(lPart.first,merge(rPart.first,rPart.second));	}	void print(int o){   		if(not o) return ;		pushDown(o);		print(son[o][0]);		writeint(data[o]), putchar(' ');		print(son[o][1]);	}}using namespace Treap;int main(){   	srand(5201314);// 这是一个绝佳的种子。 	int n = readint(), m = readint();	init(n);	for(int i=1,l,r; i<=m; ++i)		l = readint(), r = readint(), flip(l,r);	print(root);	return 0;}