1895: Pku3580 supermemo
Time Limit: 15 Sec Memory Limit: 64 MB
Submit: 77 Solved: 47
[Submit][Status]
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。
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行每行描述一个操作。
以下n行每行包含一个整数，描述初始的序列。
接下来一行包含一个整数m，表示操作的数目。
以下m行每行描述一个操作。
Output
对于所有"MIN"操作，输出正确的答案，每行一个。
Sample Input
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 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。
Source
题解：
又被输入坑了。。。
splay裸题。。。T了5.6次，最后把每次的字符串清空然后就A了。。。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 2000000+5
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,q,tot,fa[maxn],c[maxn][],rt,t1,t2,s[maxn],tag[maxn],mi[maxn],v[maxn];
bool rev[maxn];
inline void pushup(int x)
{
if(!x)return;
int l=c[x][],r=c[x][];
s[x]=s[l]+s[r]+;
mi[x]=min(v[x],min(mi[l],mi[r]));
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y!=k)c[z][c[z][]==y]=x;else k=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((c[z][]==y)^(c[y][]==x))rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
inline void add(int x,int z)
{
if(!x)return;
mi[x]+=z;tag[x]+=z;v[x]+=z;
}
inline void rever(int x)
{
if(!x)return;
rev[x]^=;
swap(c[x][],c[x][]);
}
inline void pushdown(int x)
{
if(!x)return;
if(tag[x]){add(c[x][],tag[x]);add(c[x][],tag[x]);tag[x]=;}
if(rev[x]){rever(c[x][]);rever(c[x][]);rev[x]=;}
}
inline int find(int x,int k)
{
pushdown(x);
int l=c[x][],r=c[x][];
if(s[l]+==k)return x;
else if(s[l]>=k)return find(l,k);
else return find(r,k-s[l]-);
}
inline void split(int l,int r)
{
t1=find(rt,l);t2=find(rt,r);
splay(t1,rt);splay(t2,c[rt][]);
}
inline void build(int l,int r,int f)
{
if(l>r)return;
int x=(l+r)>>;
fa[x]=f;c[f][x>f]=x;
if(l==r){mi[x]=v[x];s[x]=;return;}
build(l,x-,x);build(x+,r,x);
pushup(x);
}
int main()
{
n=read();
for2(i,,n+)v[i]=read();
v[]=v[n+]=mi[]=;tot=n+;
build(,n+,);rt=(+n+)>>;
q=read();char ch[];
while(q--)
{
memset(ch,,sizeof(ch));
scanf("%s",ch);int x=read();
if(ch[]=='D')split(x,x+),c[t2][]=;
else if(ch[]=='I')split(x+,x+),fa[c[t2][]=++tot]=t2,s[tot]=,v[tot]=mi[tot]=read();
else if(ch[]=='L')
{
int y=read(),t=read()%(y-x+);if(!t)continue;
split(y+-t-,y+);int tmp=c[t2][];c[t2][]=;
pushup(t2);pushup(t1);
split(x,x+);c[t2][]=tmp;fa[tmp]=t2;
}
else
{
int y=read();split(x,y+);int z=c[t2][];
if(ch[]=='A')add(z,read());
else if(ch[]=='M')printf("%d\n",mi[z]);
else rever(z);
}
pushup(t2);pushup(t1);
}
return ;
}
splay直接暴力往上居然还快了1s233‘
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 2000000+5
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,q,tot,fa[maxn],c[maxn][],rt,t1,t2,s[maxn],tag[maxn],mi[maxn],v[maxn];
bool rev[maxn];
inline void pushup(int x)
{
if(!x)return;
int l=c[x][],r=c[x][];
s[x]=s[l]+s[r]+;
mi[x]=min(v[x],min(mi[l],mi[r]));
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y!=k)c[z][c[z][]==y]=x;else k=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)rotate(x,k);
}
inline void add(int x,int z)
{
if(!x)return;
mi[x]+=z;tag[x]+=z;v[x]+=z;
}
inline void rever(int x)
{
if(!x)return;
rev[x]^=;
swap(c[x][],c[x][]);
}
inline void pushdown(int x)
{
if(!x)return;
if(tag[x]){add(c[x][],tag[x]);add(c[x][],tag[x]);tag[x]=;}
if(rev[x]){rever(c[x][]);rever(c[x][]);rev[x]=;}
}
inline int find(int x,int k)
{
pushdown(x);
int l=c[x][],r=c[x][];
if(s[l]+==k)return x;
else if(s[l]>=k)return find(l,k);
else return find(r,k-s[l]-);
}
inline void split(int l,int r)
{
t1=find(rt,l);t2=find(rt,r);
splay(t1,rt);splay(t2,c[rt][]);
}
inline void build(int l,int r,int f)
{
if(l>r)return;
int x=(l+r)>>;
fa[x]=f;c[f][x>f]=x;
if(l==r){mi[x]=v[x];s[x]=;return;}
build(l,x-,x);build(x+,r,x);
pushup(x);
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();
for2(i,,n+)v[i]=read();
v[]=v[n+]=mi[]=;tot=n+;
build(,n+,);rt=(+n+)>>;
q=read();char ch[];
while(q--)
{
memset(ch,,sizeof(ch));
scanf("%s",ch);int x=read();
if(ch[]=='D')split(x,x+),c[t2][]=;
else if(ch[]=='I')split(x+,x+),fa[c[t2][]=++tot]=t2,s[tot]=,v[tot]=mi[tot]=read();
else if(ch[]=='L')
{
int y=read(),t=read()%(y-x+);if(!t)continue;
split(y+-t-,y+);int tmp=c[t2][];c[t2][]=;
pushup(t2);pushup(t1);
split(x,x+);c[t2][]=tmp;fa[tmp]=t2;
}
else
{
int y=read();split(x,y+);int z=c[t2][];
if(ch[]=='A')add(z,read());
else if(ch[]=='M')printf("%d\n",mi[z]);
else rever(z);
}
pushup(t2);pushup(t1);
}
return ;
}