功在不舍 @ 2020-03-02 17:11:22
FHQ Treap全部RE
然而本地能够运行得到正确结果
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<time.h>
using namespace std;
int n,m,last,p,q,ans,x,y,tmp,z;
int all,root,size[2000000],pri[2000000],val[2000000],ch[2000000][2];
inline int newnode(int v){val[++all]=v;size[all]=1;pri[all]=rand();return all;}
inline int updata(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(pri[x]>pri[y]){
ch[x][1]=merge(ch[x][1],y);
updata(x);return x;
}else{
ch[y][0]=merge(x,ch[y][0]);
updata(y);return y;
}
}
inline void split(int now,int k,int &x,int &y){
if(!now)x=y=0;
else{
if(val[now]<=k)x=now,split(ch[now][1],k,ch[now][1],y);
else y=now,split(ch[now][0],k,x,ch[now][0]);
updata(now);
}
}
inline int kth(int now,int k){
while(now){
if(k<=size[ch[now][0]])now=ch[now][0];
else {
k-=(size[ch[now][0]]+1);
if(k<=0)return now;
now=ch[now][1];
}
}
}
inline void insert(int v){
split(root,v,x,y);
root=merge(merge(x,newnode(v)),y);
}
inline void del(int v){
split(root,v,x,z);
split(x,v-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(merge(x,y),z);
}
inline int rank(int v){
split(root,v-1,x,y);
tmp=size[x]+1;
root=merge(x,y);
return tmp;
}
inline int prefix(int v){
split(root,v-1,x,y);
tmp=val[kth(x,size[x])];
root=merge(x,y);
return tmp;
}
inline int suffix(int v){
split(root,v,x,y);
tmp=val[kth(y,1)];
root=merge(x,y);
return tmp;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
// freopen("t1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=n;i++)p=read(),insert(p);
for(int i=1;i<=m;i++)
{
p=read();q=read();q^=last;
if(p==1)insert(q);
else if(p==2)del(q);
else if(p==3)last=rank(q),ans^=last;
else if(p==4)last=val[kth(root,q)],ans^=last;
else if(p==5)last=prefix(q),ans^=last;
else if(p==6)last=suffix(q),ans^=last;
}
cout<<ans<<endl;
return 0;
}
by xhQYm @ 2020-03-02 17:12:08
Orz
by liqingyang @ 2020-03-02 17:13:09
看看我的？
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cstdio>
using namespace std;
struct node
{
int l,r,v,s,ss;
};
node a[1100010];
const int oo=2147483647;
int xx=0,root=0,last=0,anss=0,ans,t;
inline void update(int p)
{
a[p].ss=a[a[p].l].ss+a[a[p].r].ss+1;
}
void insert(int &p,int vv)
{
if(!p)
{
p=++xx;
a[p].v=vv;
a[p].s=rand();
update(p);
return;
}
if(vv<a[p].v)
{
insert(a[p].l,vv);
if(a[p].s>a[a[p].l].s&&a[a[p].l].s)
{
int b=a[p].l;
a[p].l=a[b].r;
a[b].r=p;
update(p);
p=b;
}
}
else
{
insert(a[p].r,vv);
if(a[p].s>a[a[p].r].s&&a[a[p].r].s)
{
int b=a[p].r;
a[p].r=a[b].l;
a[b].l=p;
update(p);
p=b;
}
}
update(p);
}
int merge(int ll,int rr)
{
if(!ll)
{
return rr;
}
if(!rr)
{
return ll;
}
if(a[ll].s>a[rr].s)
{
a[ll].r=merge(a[ll].r,rr);
update(ll);
return ll;
}
else
{
a[rr].l=merge(ll,a[rr].l);
update(rr);
return rr;
}
}
void shanchu(int &p,int x)
{
if(!p)
{
return;
}
if(x<a[p].v)
{
shanchu(a[p].l,x);
}
else if(x==a[p].v)
{
p=merge(a[p].l,a[p].r);
}
else
{
shanchu(a[p].r,x);
}
if(p)
{
update(p);
}
}
void find3(int p,int x)
{
if(!p)
{
return;
}
if(x<=a[p].v)
{
find3(a[p].l,x);
}
else
{
ans+=a[a[p].l].ss+1;
find3(a[p].r,x);
}
}
void find4(int p,int x)
{
if(!p||a[p].ss+t<x)
{
return;
}
if(x<=a[a[p].l].ss+t)
{
find4(a[p].l,x);
}
if(x==t+a[a[p].l].ss+1)
{
ans=a[p].v;
}
if(x>t+a[a[p].l].ss+1)
{
t+=a[a[p].l].ss+1;
find4(a[p].r,x);
}
}
void find5(int p,int x)
{
if(!p)
{
return;
}
if(a[p].v<x)
{
ans=max(ans,a[p].v);
}
if(x<=a[p].v)
{
find5(a[p].l,x);
}
else
{
find5(a[p].r,x);
}
}
void find6(int p,int x)
{
if(!p)
{
return;
}
if(a[p].v>x)
{
ans=min(ans,a[p].v);
}
if(x>=a[p].v)
{
find6(a[p].r,x);
}
else
{
find6(a[p].l,x);
}
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
ios::sync_with_stdio(false);
srand(time(0));
int n=read(),m=read();
for(int i=1;i<=n;i++)
{
insert(root,read());
}
for(int i=1;i<=m;i++)
{
int s=read(),x=read()^last;
if(s==1)
{
insert(root,x);
}
if(s==2)
{
shanchu(root,x);
}
if(s==3)
{
ans=1;
find3(root,x);
}
if(s==4)
{
ans=0,t=0;
find4(root,x);
}
if(s==5)
{
ans=-oo;
find5(root,x);
}
if(s==6)
{
ans=oo;
find6(root,x);
}
if(s>=3)
{
last=ans;
anss^=ans;
}
}
cout<<anss<<endl;
return 0;
}by hanzhongtlx @ 2020-03-02 17:13:18
数组大点
by liqingyang @ 2020-03-02 17:13:39
@功在不舍 加油！
by hanzhongtlx @ 2020-03-02 17:13:59
加上5之类的
by hanzhongtlx @ 2020-03-02 17:14:05
@功在不舍
by 功在不舍 @ 2020-03-02 17:14:12
@hanzhongtlx 数组够大了吧
by hanzhongtlx @ 2020-03-02 17:15:05
行办
by 功在不舍 @ 2020-03-02 17:16:34
为什么我本地能正常运行，第一个点100000的数据答案也是对的
by dengyaotriangle @ 2020-03-02 17:18:30
update函数是int类型却没有返回值