題目描述
我們用文本處理器來處理一個特殊的文本文件，該文本文件共有N行文本，每一行文本僅包含一個自然數，第一行為1、第二行為2，以此類推至N行為自然數N。
假設對該文本文件執行一次“剪切和粘貼”操作含義如下：首先選定連續的若干行文本，“剪切”操作將選定的文本從文件中剪下，而“粘貼”操作將剪切下來的文本插入到文件中的其他地方。
編寫一個程序求出在進行了連續若干次“剪切和粘貼”操作后，文本文件中前十行的內容。
題目大意
將區間內的一段數字移動到另一個地方，求操作后的區間前10個數字。
數據范圍
10<=n<=100000 1<=k<=1000
樣例輸入
13 3
6 12 1
2 9 0
10 13 8
樣例輸出
6
7
8
9
10
11
12
2
3
4
解題思路
Splay 維護區間，如果要剪切，就先把區間旋轉出來，再斷邊，在把要插入的地方旋轉出來，連邊。(雖然我并不知道這道題目的標解是什么。。)
Update:最后發現O(nk)的模擬可以直接過QAQ
代碼
#include <bits/stdc++.h>
#define Maxn 100005
using namespace std;
inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n,q;
struct splay{int f[Maxn],son[Maxn][2],size[Maxn],vl[Maxn],root;void PushUp(int v){if(v)size[v]=size[son[v][0]]+size[son[v][1]]+1;}void Rotate(int x){int fa=f[x],gr=f[fa],s=son[fa][1]==x,sn=son[x][!s];son[f[x]=gr][son[gr][1]==fa]=x;son[f[fa]=x][!s]=fa;son[f[sn]=fa][s]=sn;PushUp(sn);PushUp(fa);PushUp(x);}void Splay(int x,int goal){if(x==goal)return;while(f[x]!=goal){if(f[f[x]]!=goal&&(son[f[f[x]]][1]==f[x])==(son[f[x]][1]==x))Rotate(f[x]);Rotate(x);}if(!goal)root=x;}int Select(int pos){int p=root;while(size[son[p][0]]+1!=pos){if(pos<=size[son[p][0]])p=son[p][0];else pos-=size[son[p][0]]+1,p=son[p][1];}return p;}void Insert(int pos,int k){int u=Select(pos+1),v=Select(pos+2);Splay(u,0);Splay(v,u);son[v][0]=k;f[son[v][0]]=v;PushUp(v);PushUp(u);}int Delete(int L,int r){int u=Select(L),v=Select(r+2);Splay(u,0);Splay(v,u);f[son[v][0]]=0;PushUp(v);PushUp(u);int t=son[v][0];son[v][0]=0;return t;}void Build(int L,int r,int fa){if(L>r)return;int mid=(L+r)/2;if(L!=r)Build(L,mid-1,mid),Build(mid+1,r,mid);vl[mid]=(mid-1<=n?mid-1:0);PushUp(mid);f[mid]=fa;son[fa][mid>=fa]=mid;}void Init(){Build(1,n+2,0);root=n+3>>1;}
}Solver;
int main(){n=Getint(),q=Getint();Solver.Init();while(q--){int L=Getint(),r=Getint(),k=Getint();Solver.Insert(k,Solver.Delete(L,r));}for(int i=1;i<=10;i++)cout<<Solver.vl[Solver.Select(i+1)]<<"\n";return 0;
}
