orz
by 由希❀ @ 2017-12-09 20:33:58
orz
by zzlzk @ 2017-12-09 20:37:08
orz
by Niko @ 2017-12-09 21:10:49
orz
by λᴉʍ @ 2017-12-09 22:41:37
Mod LGJ
by aiyougege @ 2017-12-10 06:29:17
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ls tree[k].ch[0]
#define rs tree[k].ch[1]
const int MAXN=1e6+10,INF=1e7;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
struct node
{
int pri,v,ch[2],siz;
}tree[MAXN];
int x,y,z,tot=0,root[MAXN];
int new_node(int val)
{
tree[++tot].pri=rand()*rand(),tree[tot].v=val,tree[tot].siz=1;
return tot;
}
void update(int k){ tree[k].siz=tree[ls].siz+tree[rs].siz+1; }
void split(int now,int k,int &x,int &y)
{
if(!now) {x=y=0;return ;}
if(tree[now].v<=k) x=now,split(tree[now].ch[1],k,tree[now].ch[1],y);
else y=now,split(tree[now].ch[0],k,x,tree[now].ch[0]);
update(now);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(tree[x].pri<tree[y].pri) {tree[x].ch[1]=merge(tree[x].ch[1],y),update(x);return x;}
else {tree[y].ch[0]=merge(x,tree[y].ch[0]),update(y);return y;}
}
int kth(int k,int x)// 查询排名
{
if(x<=tree[ls].siz) return kth(ls,x);
else if(x==tree[ls].siz+1) return k;
else return kth(rs,x-tree[ls].siz-1);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
srand((unsigned)time(NULL));
int n=read();
for(int i=1;i<=n;i++)
{
int pre=read(),how=read(),a=read();
root[i]=root[pre];
if(how==1) split(root[i],a,x,y),root[i]=merge(merge(x,new_node(a)),y);
else if(how==2) split(root[i],a,x,z),split(x,a-1,x,y),y=merge(tree[y].ch[0],tree[y].ch[1]),root[i]=merge(merge(x,y),z);
else if(how==3) split(root[i],a-1,x,y),printf("%d\n",tree[x].siz+1),root[i]=merge(x,y);
else if(how==4) printf("%d\n",tree[kth(root[i],a)].v);
else if(how==5) split(root[i],a-1,x,y),printf("%d\n",tree[kth(x,tree[x].siz)].v),root[i]=merge(x,y);
else if(how==6) split(root[i],a,x,y),printf("%d\n",tree[kth(y,1)].v),root[i]=merge(x,y);
}
return 0;
}
```
by attack @ 2017-12-10 07:05:28
我觉得问题没那么简单．．
问题在于你这有持久化？．．
by negiizhao @ 2017-12-17 21:43:20
@[negii](/space/show?uid=5643) 有啊，记录下每次操作的根节点
by attack @ 2017-12-23 07:40:08
got it!
by yjjr @ 2017-12-25 20:48:16