POJ 3580 SuperMemo (구간 트 리)
12495 단어 데이터 구조
#include
#include
#include
using namespace std;
int n,m,rt,cnt,x,y,z,a[200010],sz[200010],ch[200010][2],fa[200010],v[200010],delta[200010],rev[200010],minum[200010];
char c,op[7];
inline void GET(int &n)
{
int f=1;n=0;
do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
while(c<='9'&&c>='0'){n=n*10+c-'0';c=getchar();}
n*=f;
}
inline void pushdown(int x)
{
if(delta[x])
{
delta[ch[x][0]]+=delta[x];
minum[ch[x][0]]+=delta[x];
v[ch[x][0]]+=delta[x];
delta[ch[x][1]]+=delta[x];
minum[ch[x][1]]+=delta[x];
v[ch[x][1]]+=delta[x];
delta[x]=0;
}
if(rev[x])
{
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
swap(ch[x][0],ch[x][1]);
rev[x]=0;
}
}
inline void pushup(int x)
{
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
minum[x]=v[x];
if(ch[x][0])minum[x]=min(minum[x],minum[ch[x][0]]);
if(ch[x][1])minum[x]=min(minum[x],minum[ch[x][1]]);
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y];
bool flag=(ch[y][1]==x);
ch[y][flag]=ch[x][!flag];
fa[ch[y][flag]]=y;
ch[x][!flag]=y;
fa[ch[x][!flag]]=x;
fa[x]=z;
ch[z][ch[z][1]==y]=x;
pushup(y);
pushup(x);
}
inline void splay(int x,int goal)
{
for(int y;(y=fa[x])!=goal;rotate(x))
{
int z=fa[y];
if(z!=goal)
{
if((ch[z][0]==y)^(ch[y][0]==x))rotate(x);
else rotate(y);
}
}
if(!goal)rt=x;
pushup(x);
}
inline void rotateto(int k,int goal)
{
int x=rt;
while(1)
{
pushdown(x);
if(k0]]+1)x=ch[x][0];
else if(k>sz[ch[x][0]]+1)k-=sz[ch[x][0]]+1,x=ch[x][1];
else break;
}
splay(x,goal);
}
inline void newnode(int &r,int val)
{
r=++cnt;
minum[r]=v[r]=val;
sz[r]=1;
}
void build(int &r,int L,int R,int f)
{
int mid=(L+R)/2;
newnode(r,a[mid]);
fa[r]=f;
if(L==R)return;
if(L0],L,mid-1,r);
if(mid1],mid+1,R,r);
pushup(r);
}
inline void ADD(int L,int R,int d)
{
rotateto(L,0);
rotateto(R+2,rt);
int u=ch[ch[rt][1]][0];
delta[u]+=d,v[u]+=d,minum[u]+=d;
}
inline void REVERSE(int L,int R)
{
rotateto(L,0);
rotateto(R+2,rt);
int u=ch[ch[rt][1]][0];
rev[u]^=1;
}
inline void REVOLVE(int L,int R,int d)
{
int rd=(d%(R-L+1)+(R-L+1))%(R-L+1),u;
if(!rd)return;
rotateto(L,0);
rotateto(R-rd+2,rt);
u=ch[ch[rt][1]][0];
ch[ch[rt][1]][0]=0;
pushup(ch[rt][1]);
pushup(rt);
rotateto(L+rd,0);
rotateto(L+rd+1,rt);
ch[ch[rt][1]][0]=u;
fa[u]=ch[rt][1];
pushup(ch[rt][1]);
pushup(rt);
}
inline void INSERT(int x,int val)
{
rotateto(x+1,0);
rotateto(x+2,rt);
newnode(ch[ch[rt][1]][0],val);
fa[ch[ch[rt][1]][0]]=ch[rt][1];
pushup(ch[rt][1]);
pushup(rt);
}
inline void DELETE(int x)
{
rotateto(x,0);
rotateto(x+2,rt);
ch[ch[rt][1]][0]=0;
pushup(ch[rt][1]);
pushup(rt);
}
inline int MIN(int L,int R)
{
rotateto(L,0);
rotateto(R+2,rt);
return minum[ch[ch[rt][1]][0]];
}
int main()
{
GET(n);
for(int i=1;i<=n;++i)
GET(a[i]);
build(rt,0,n+1,0);
GET(m);
while(m--)
{
memset(op,0,sizeof op);
scanf("%s",op);
if(op[0]=='A')
{
GET(x);
GET(y);
GET(z);
ADD(x,y,z);
}
else if(op[5]=='S')
{
GET(x);
GET(y);
REVERSE(x,y);
}
else if(op[3]=='O')
{
GET(x);
GET(y);
GET(z);
REVOLVE(x,y,z);
}
else if(op[0]=='I')
{
GET(x);
GET(y);
INSERT(x,y);
}
else if(op[0]=='D')
{
GET(x);
DELETE(x);
}
else if(op[0]=='M')
{
GET(x);
GET(y);
printf("%d
",MIN(x,y));
}
}
}