rt,萌新刚学FHQTreap,你可以看见WAon#4,但是就在我下载#4数据的时候我发现一个很奇怪的问题:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N,A,B;
struct Treap{
LL cnt,root;
struct node
{LL key,val,size=0,ls=0,rs=0;}tree[200005];
#define ls(p) (tree[p].ls)
#define rs(p) (tree[p].rs)
void pushup(LL p)
{tree[p].size=tree[ls(p)].size+tree[rs(p)].size+1;}
LL New(LL X){
tree[++cnt].key=X;tree[cnt].val=rand();
tree[cnt].size=1;ls(cnt)=rs(cnt)=0;
return cnt;
}
LL Merge(LL X,LL Y){
if(!X||!Y)return X|Y;
if(tree[X].val<=tree[Y].val){
rs(X)=Merge(rs(X),Y);
pushup(X);return X;
}
else{
ls(Y)=Merge(X,ls(Y));
pushup(Y);return Y;
}
}
void Split(LL p,LL X,LL& L,LL& R){
if(!p){L=R=0;return;}
if(tree[p].key<=X)
{L=p;Split(rs(p),X,rs(p),R);}
else
{R=p,Split(ls(p),X,L,ls(p));}
pushup(p);
}
void insert(LL X){
Split(root,X-1,A,B);
root=Merge(Merge(A,New(X)),B);
}
void del(LL X){
LL T;
Split(root,X-1,A,B);
Split(B,X,T,B);
T=Merge(ls(T),rs(T));
root=Merge(Merge(A,B),T);
}
LL rank(LL X){
Split(root,X-1,A,B);
LL ret=tree[A].size+1;
root=Merge(A,B);
return ret;
}
LL get(LL p,LL inx){
LL mid=tree[ls(p)].size+1;
if(mid==inx)return tree[p].key;
if(mid<inx)return get(rs(p),inx-mid);
else return get(ls(p),inx);
}
}FHQ;
int main(){
freopen("P3369_4.in","r",stdin);
freopen("ans.txt","w",stdout);
scanf("%lld",&N);
while(N--){
LL op,X;
scanf("%lld%lld",&op,&X);
if(op==1)FHQ.insert(X);
else if(op==2)FHQ.del(X);
else if(op==3)printf("%lld\n",FHQ.rank(X));
else if(op==4)printf("%lld\n",FHQ.get(1,X));
else if(op==5){
FHQ.Split(FHQ.root,X-1,A,B);
printf("%lld\n",FHQ.get(A,FHQ.tree[A].size));
FHQ.root=FHQ.Merge(A,B);
}else{
FHQ.Split(FHQ.root,X,A,B);
printf("%lld\n",FHQ.get(B,1));
FHQ.root=FHQ.Merge(A,B);
}
}
return 0;
}
这段代码读入"P3369_4.in",也就是本题的测试点#4,但是ans.txt却和"P3369_4.out"一模一样!

大佬们不信可以下个数据试试QAQ