题目大意
有一个0~n-1的序列，有m次操作，操作包含三个元素：pl，len，ti，表示这个操作进行ti次，每次将从pl+1开始的len个元素移到序列头部。
分析
看到题不难想到使用平衡树将需移动部分切出来挂到顶部。本题我使用fhqtreap来实现，但需要注意的是对于挪动部分使用的split不再以节点值为关键字切割而改用它在树中的排名作为关键字。具体实现详见代码。注意输出格式！！！！！！！！
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int root,son[1100000][2],a[1100000],rd[1100000],siz[1100000],cnt,n;
inline void up(int x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}
inline int bnode(int x){
siz[++cnt]=1;
a[cnt]=x;
rd[cnt]=rand();
return cnt;
}
inline int gk(int rt,int k){
while(1){
if(k<=siz[son[rt][0]])rt=son[rt][0];
else if(k==siz[son[rt][0]]+1)return rt;
else k-=siz[son[rt][0]]+1,rt=son[rt][1];
}
}
inline void spt1(int rt,int k,int &x,int &y){
if(!rt)x=y=0;
else {
if(a[rt]<=k)x=rt,spt1(son[rt][1],k,son[rt][1],y);
else y=rt,spt1(son[rt][0],k,x,son[rt][0]);
up(rt);
}
}
inline int mer(int x,int y){
if(!x||!y)return x+y;
if(rd[x]<rd[y]){
son[x][1]=mer(son[x][1],y);
up(x);
return x;
}else {
son[y][0]=mer(x,son[y][0]);
up(y);
return y;
}
}
inline void spt(int sum,int rt,int k,int &x,int &y){
if(!rt)x=y=0;
else {
if(sum+siz[son[rt][0]]+1<=k){
x=rt,spt(sum+siz[son[rt][0]]+1,
son[rt][1],k,son[rt][1],y);
}else y=rt,spt(sum,son[rt][0],k,x,son[rt][0]);
up(rt);
}
}
inline void init(){
root=cnt=0;
memset(rd,0,sizeof(rd));
memset(a,0,sizeof(a));
memset(son,0,sizeof(son));
memset(siz,0,sizeof(siz));
}
inline long long getans(int n){
long long ans=0;
int i;
for(i=1;i<=n;i+=2)
ans+=(long long)a[gk(root,i)];
return ans;
}
inline void work(int _){
int n,m,i,j,x,y,z,w,pl,len,ti;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
spt1(root,i,x,y);
root=mer(mer(x,bnode(i)),y);
}
for(i=1;i<=m;i++){
scanf("%d%d%d",&pl,&len,&ti);
for(j=1;j<=ti;j++){
spt(0,root,pl,x,y),spt(0,y,len,z,w);
root=mer(z,mer(x,w));
}
}
printf("%lld
",getans(n));
}
int main(){
srand(time(0)+20021023);
int t;
scanf("%d",&t);
for(int _=1;_<=t;_++){
printf("Case %d:
",_);
init();
work(_);
if(_!=t)puts("");
}
return 0;
}