【BZOJ1895】Pku3580 supermemo
Description
給出一個初始序列fA1;A2;:::Ang，要求你編寫程式支援如下操作： 1. ADDxyD：給子序列fAx:::Ayg的每個元素都加上D。例如對f1,2, 3,4,5g執行"ADD 241" 會得到f1,3,4,5,5g。 2. REVERSExy：将子序列fAx:::Ayg翻轉。例如對f1,2,3,4,5g執 行"REVERSE 24"會得到f1,4,3,2,5g。 3. REVOLVExyT：将子序列fAx:::Ayg旋轉T個機關。例如， 對f1,2,3,4,5g執行"REVOLVE 242"會得到f1,3,4,2,5g。 4. INSERTxP：在Ax後插入P。例如，對f1,2,3,4,5g執行"INSERT 24"會得到f1,2,4,3,4,5g。 5. DELETEx：删去Ax。例如，對f1,2,3,4,5g執行"DELETE 2"會得 到f1,3,4,5g。 6. MINxy：查詢子序列fAx:::Ayg中的最小元素。例如，對于序列f1, 2,3,4,5g，詢問"MIN 24"的傳回應為2。
Input
第一行包含一個整數n，表示初始序列的長度。 以下n行每行包含一個整數，描述初始的序列。 接下來一行包含一個整數m，表示操作的數目。 以下m行每行描述一個操作。
Output
對于所有"MIN"操作，輸出正确的答案，每行一個。
Sample Input
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Sample Output
5
HINT
輸入、輸出以及中間運算結果均不會超過32位整數。
對于30%的資料，n;m 6 1000;
對于100%的資料，n;m 6 100000。
題解：裸的Splay不解釋
個人比較懶，對于區間平移操作直接改為翻轉3次，結果因為沒取模而狂TLE不止，改完後常數大得驚人。。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int tot,root,n,m;
struct node
{
int rev,tag,ch[2],fa,v,siz,sm;
}s[600010];
char str[10];
int rd()
{
int ret=0; char gc=getchar();
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
void pushup(int x)
{
s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;
s[x].sm=min(min(s[x].v,s[s[x].ch[0]].sm),s[s[x].ch[1]].sm);
}
void pushdown(int x)
{
if(s[x].ch[0]) s[s[x].ch[0]].v+=s[x].tag,s[s[x].ch[0]].sm+=s[x].tag,s[s[x].ch[0]].tag+=s[x].tag;
if(s[x].ch[1]) s[s[x].ch[1]].v+=s[x].tag,s[s[x].ch[1]].sm+=s[x].tag,s[s[x].ch[1]].tag+=s[x].tag;
s[x].tag=0;
if(s[x].rev)
{
swap(s[x].ch[0],s[x].ch[1]);
if(s[x].ch[0]) s[s[x].ch[0]].rev^=1;
if(s[x].ch[1]) s[s[x].ch[1]].rev^=1;
s[x].rev=0;
}
}
void build(int l,int r,int last)
{
if(l>r) return ;
int mid=l+r>>1;
s[mid].fa=last,s[last].ch[mid>last]=mid;
build(l,mid-1,mid),build(mid+1,r,mid);
pushup(mid);
}
void rotate(int x,int &k)
{
int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);
if(z) s[z].ch[y==s[z].ch[1]]=x;
if(y==k) k=x;
s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
int find(int x,int y)
{
pushdown(x);
if(y<=s[s[x].ch[0]].siz) return find(s[x].ch[0],y);
if(y==s[s[x].ch[0]].siz+1) return x;
return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);
}
void splay(int x,int &k)
{
while(x!=k)
{
int y=s[x].fa,z=s[y].fa;
if(y!=k)
{
if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int main()
{
n=rd();
s[0].sm=1<<30;
int i,a,b,c;
for(i=1;i<=n;i++) scanf("%d",&s[i+1].v);
tot=n+2,root=(tot+1)/2;
build(1,root-1,root),build(root+1,n+2,root);
pushup(root);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='A')
{
a=rd()+1,b=rd()+1,c=rd();
splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]);
s[s[s[root].ch[1]].ch[0]].tag+=c;
s[s[s[root].ch[1]].ch[0]].v+=c;
s[s[s[root].ch[1]].ch[0]].sm+=c;
pushup(s[root].ch[1]),pushup(root);
}
if(str[0]=='R'&&str[3]=='E')
{
a=rd()+1,b=rd()+1;
splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]);
s[s[s[root].ch[1]].ch[0]].rev^=1;
}
if(str[0]=='R'&&str[3]=='O')
{
a=rd()+1,b=rd()+1,c=rd()%(b-a+1);
if(c==0) continue;
splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]);
s[s[s[root].ch[1]].ch[0]].rev^=1;
splay(find(root,a-1),root),splay(find(root,a+c),s[root].ch[1]);
s[s[s[root].ch[1]].ch[0]].rev^=1;
splay(find(root,a+c-1),root),splay(find(root,b+1),s[root].ch[1]);
s[s[s[root].ch[1]].ch[0]].rev^=1;
}
if(str[0]=='I')
{
a=rd()+1,b=rd();
splay(find(root,a),root),splay(find(root,a+1),s[root].ch[1]);
s[s[root].ch[1]].ch[0]=++tot;
s[tot].v=s[tot].sm=b,s[tot].siz=1,s[tot].fa=s[root].ch[1];
pushup(s[root].ch[1]),pushup(root);
}
if(str[0]=='D')
{
a=rd()+1;
splay(find(root,a-1),root);
splay(find(root,a+1),s[root].ch[1]);
s[s[root].ch[1]].ch[0]=0;
pushup(s[root].ch[1]),pushup(root);
}
if(str[0]=='M')
{
a=rd()+1,b=rd()+1;
splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]);
printf("%d\n",s[s[s[root].ch[1]].ch[0]].sm);
}
}
return 0;
}
轉載于:https://www.cnblogs.com/CQzhangyu/p/6756310.html