pkh68 @ 2018-09-30 09:10:39
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define N 100010
#define re register
#define lc node[u].ch[0]
#define rc node[u].ch[1]
using namespace std;
int n,m,seq[N];
struct Node{
int v,ch[2],flip,size;
Node(){}
Node(int a ,int b,int c,int d,int e){ v=a,ch[0]=b,ch[1]=c,flip=d;size=e; }
}node[N];
int cmp(int u,int k){ int d=k-node[lc].size;if(d==1) return -1;return d<=0?0:1; }
void Maintain(int u){ node[u].size=1+node[lc].size+node[rc].size; }
void PushDown(int u){
if(node[u].flip){
node[u].flip=0;
swap(lc,rc);node[lc].flip=!node[lc].flip;node[rc].flip=!node[rc].flip;
}
}
void rotate(int &u,int d){
int k=node[u].ch[d^1];node[u].ch[d^1]=node[k].ch[d];node[k].ch[d]=u;
Maintain(u);Maintain(k);u=k;
}
void splay(int &u,int k){
PushDown(u);
int d=cmp(u,k);
if(d==1) k-=node[lc].size+1;
if(d!=-1){
int p=node[u].ch[d];
PushDown(p);
int d2=cmp(p,k);
int k2=(d2==0?k:k-node[node[p].ch[0]].size-1);
if(d2!=-1){ splay(node[p].ch[d2],k2);if(d==d2) rotate(u,d^1);else rotate(node[u].ch[d],d);}
rotate(u,d^1);
}
}
int merge(int left,int right){
splay(left,node[left].size);
node[left].ch[1]=right;
Maintain(left);
return left;
}
void split(int u,int k,int &left,int &right){
splay(u,k);
left=u;right=rc;rc=0;
Maintain(left);
}
struct Splay{
int tot=0,root;
int Build(int sz){
if(!sz) return 0;
int sn=++tot,l=Build(sz>>1);
node[tot]=Node(tot,l,Build(sz-(sz>>1)-1),0,0);
Maintain(sn);
return sn;
}
}s;
vector<int> ans;
void print(int u){ if(u){ PushDown(u);print(lc);ans.push_back(node[u].v);print(rc); } }
int main(){
scanf("%d%d",&n,&m);
s.root=s.Build(n+1);
for(re int i=1,l,r;i<=m;++i){
scanf("%d%d",&l,&r);
int left,mid,right,u;
split(s.root,l,left,u);
split(u,r-l+1,mid,right);
node[mid].flip^=1;
s.root=merge(merge(left,mid),right);
}
print(s.root);
for(re int i=1;i<ans.size();++i) printf("%d\n",ans[i]);
return 0;
}```
by aoweiyin @ 2018-09-30 09:13:48
感觉我又要惭愧一波了QAQ
by Danny_boodman @ 2018-09-30 09:13:58
为什么您要强调萌新呢?
by Danny_boodman @ 2018-09-30 09:15:01
@坐看云起时6b 捕捉大佬
by ACINE @ 2018-09-30 09:27:44
坐看云起时6b啊大佬!
by Ousmane_Dembele @ 2018-10-18 14:09:00
打破无蒟蒻的一帖
by 萌田薰子 @ 2018-10-25 22:46:44
打破只有一蒟蒻的一贴