文艺平衡树[区间翻转]

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入输出格式

输入格式：

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) m表示翻转操作次数

接下来m行每行两个数 [l,r][数据保证1≤l≤r≤n

输出格式：

输出一行n个数字，表示原始序列经过m次变换后的结果

输入样例#1： 

5 3
1 3
1 3
1 4      

输出样例#1： 

4 3 2 1 5      

说明

n,m≤100000

分析

splay 区间翻转

对于每次l,r的翻转

我们找到l-1并转到根,在找到r+1并转到l-1的右儿子

r+1的左儿子就是区间,然后打标记

查询和输出时标记都要下传

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,root,tot;
struct Node{
	int ch[2],key,fa,num,size,tag;
}t[N];
int read(){
    int cnt=0,f=1;char ch=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}
    while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
    return cnt*f;
}
void newnode(int &o,int f,int val){
	o=++tot;t[o].fa=f;
	t[o].size=t[o].num=1,t[o].key=val;
}
void update_size(int o){
	t[o].size=t[t[o].ch[0]].size+t[t[o].ch[1]].size+t[o].num;
}
void spread(int o){
	if(t[o].tag){
		swap(t[o].ch[0],t[o].ch[1]);
		t[t[o].ch[0]].tag^=1;
		t[t[o].ch[1]].tag^=1;
		t[o].tag=0;
	}
}
void rotate(int x){
	int y=t[x].fa,z=t[y].fa;
	int k=(t[y].ch[1]==x);
	t[z].ch[t[z].ch[1]==y]=x;
	t[x].fa=z;
	
	t[y].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].fa=y;
	
	t[x].ch[k^1]=y;
	t[y].fa=x;
	update_size(x),update_size(y);
}
void splay(int x,int goal){
	while(t[x].fa!=goal){
		int y=t[x].fa,z=t[y].fa;
		if(z!=goal) 
			(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
		rotate(x);
	}if(goal==0) root=x;
}
void insert(int root,int val){
	int o=root;
	while(t[o].ch[val>t[o].key]) o=t[o].ch[val>t[o].key];
	newnode(t[o].ch[val>t[o].key],o,val);
	splay(t[o].ch[val>t[o].key],0);
}
int quary_k(int o,int k){
	spread(o);
	if(t[t[o].ch[0]].size>=k) return quary_k(t[o].ch[0],k);
	else if(k>t[t[o].ch[0]].size+t[o].num) 
		return quary_k(t[o].ch[1],k-t[t[o].ch[0]].size-t[o].num);
	else return t[o].key;
}
void solve(int l,int r){
	l=quary_k(root,l),r=quary_k(root,r+2);
	splay(l,0),splay(r,l);
	t[t[t[root].ch[1]].ch[0]].tag^=1;
}
void Cout(int o){
	spread(o);
	if(t[o].ch[0]) Cout(t[o].ch[0]);
	if(t[o].key!=1&&t[o].key!=n+2)cout<<t[o].key-1<<" ";
	if(t[o].ch[1]) Cout(t[o].ch[1]);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n+2;i++) insert(root,i);
	while(m--){
		int l=read(),r=read();
		solve(l,r);
	}
	Cout(root);
	return 0;
}