题目：Permutation Transformer
思路：splay分裂、合并、区间翻转模板
代码：
using namespace std;#define maxn 100000struct Node {int fa,ch[2];int sz,lzy;void init() {fa=ch[0]=ch[1]=lzy=0;sz=1;}
};int n,m;
Node a[maxn+5]= {
0};
int rt=0;void push_down(int o) {if(a[o].lzy==0) return ;a[o].lzy=0;swap(a[o].ch[0],a[o].ch[1]);a[a[o].ch[0]].lzy^=1;a[a[o].ch[1]].lzy^=1;
}void print(int u) {push_down(u);if(a[u].ch[0]) print(a[u].ch[0]);if(u!=1&&u!=n+2)printf("%d\n",u-1);if(a[u].ch[1]) print(a[u].ch[1]);
}void push_up(int o) {a[o].sz=a[a[o].ch[0]].sz+a[a[o].ch[1]].sz+1;
}void make_tree(int o,int l,int r) {if(l>r) return ;int mid=l+(r-l)/2;a[mid].fa=o,a[mid].sz=1;if(mid<o) a[o].ch[0]=mid;else a[o].ch[1]=mid;if(l==r) return ;make_tree(mid,l,mid-1),make_tree(mid,mid+1,r);push_up(mid);
}void rotate(int x) {int y=a[x].fa,z=a[y].fa;int k=(a[y].ch[1]==x);a[z].ch[a[z].ch[1]==y]=x,a[x].fa=z;a[y].ch[k]=a[x].ch[k^1],a[a[x].ch[k^1]].fa=y;a[x].ch[k^1]=y,a[y].fa=x;push_up(y),push_up(x);
}void splay(int x,int k) {while(a[x].fa!=k) {int y=a[x].fa,z=a[y].fa;if(k!=z) {if((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);else rotate(y);}rotate(x);}if(!k) rt=x;
}int find(int x,int k) {push_down(x);push_up(x);int s=a[a[x].ch[0]].sz;if(k==s+1) return x;if(k<=s) return find(a[x].ch[0],k);else return find(a[x].ch[1],k-s-1);
}void rev(int p,int q) {int x=find(rt,p-1),y=find(rt,q+1);splay(x,0);splay(y,rt);a[a[y].ch[0]].lzy^=1;
}int findright(int u) {push_down(u);if(a[u].ch[1]==0) return u;else return findright(a[u].ch[1]);
}void divide(int fa,int son) {push_down(fa);a[fa].ch[0]=0,a[fa].sz-=a[son].sz;a[son].fa=0;
}void merge(int fa,int son) {push_down(fa);a[fa].ch[0]=son;a[son].fa=fa;a[fa].sz+=a[son].sz;
}void Move(int p,int q) {push_down(rt);int fa=a[rt].ch[1];push_down(fa);int son=a[fa].ch[0];divide(fa,son);int r=findright(rt);if(a[r].ch[0]) splay(findright(a[r].ch[0]),0);push_down(rt);merge(r,son);
}int main() {scanf("%d%d",&n,&m);rt=(n+3)/2;make_tree(rt,1,n+2);a[0].ch[1]=rt;a[rt].fa=0;while(m--) {int p,q;scanf("%d%d",&p,&q);p++,q++;rev(p,q);Move(p,q);}print(rt);return 0;
}数据生成器
#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define maxm 100000
#define Rand() (rand()+rand()%1000000007)int main() {srand(time(NULL));int n,m;n=Rand()%maxn+1;m=Rand()%maxm+1;printf("%d %d\n",n,m);while(m--) {int l=1,r=0;while(l>r) {l=Rand()%n+1;r=n-Rand()%n;}printf("%d %d\n",l,r);}return 0;
}对拍：
#include<iostream>
#include<windows.h>
using namespace std;
int main() {while(1) {system("rand.exe > rand.txt");system("11922.exe < rand.txt > 11922.txt");system("std.exe < rand.txt > std.txt");if(system("fc 11922.txt std.txt")) break;printf("ACCEPT\n");}printf("UNACCEPT\n");return 0;
}