JimmyFlower @ 2020-03-05 18:48:14
就#6被卡了，但是我这个总耗时好像比其他的splay快。而且别的splay的#6都很快，在1s之内。？？？
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<cctype>
#include<cstdio>
#define ri register int
using namespace std;
int n,m,opt,x,ans=0,la=0;
int root=0,len=0;
struct splay{int d,n,s,f,son[2];}tr[1110000];
inline char gc()
{
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
ri x=0; register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);x=(x<<3)+(x<<1)+(c&15),c=gc());
return x;
}
inline int get(int x){return tr[tr[x].f].son[1]==x;}
inline void update(int x)
{
int lc=tr[x].son[0],rc=tr[x].son[1];
tr[x].s=tr[lc].s+tr[rc].s+tr[x].n;
}
inline void add(int d,int f)
{
len++;
tr[len].d=d,tr[len].n=tr[len].s=1,tr[len].f=f,tr[len].son[0]=tr[len].son[1]=0;
if(d<tr[f].d) tr[f].son[0]=len; else tr[f].son[1]=len;
}
inline void connect(int r,int R,int w)
{
if(r) tr[r].f=R;
tr[R].son[w]=r;
}
inline void rotate(int x)
{
int w=get(x)^1;
int f=tr[x].f,ff=tr[f].f;
connect(tr[x].son[w],f,w^1);
connect(x,ff,get(f));
connect(f,x,w);
update(f),update(x);
}
inline void splay(int x,int rt)
{
for(ri f;(f=tr[x].f)!=rt;rotate(x))
if(tr[f].f!=rt) rotate(get(x)==get(f)?f:x);
if(rt==0) root=x;
}
inline int getip(int d)
{
int x=root;
while(tr[x].d!=d)
{
if(d<tr[x].d)
{
if(!tr[x].son[0]) break;
x=tr[x].son[0];
}
else
{
if(!tr[x].son[1]) break;
x=tr[x].son[1];
}
}
return x;
}
inline void ins(int d)
{
if(root==0){add(d,0),root=len;return;}
int x=getip(d);
if(tr[x].d==d) tr[x].n++,splay(x,0);
else add(d,x),splay(len,0);
}
inline void del(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].n>1){tr[x].n--,update(x);return;}
if(!tr[x].son[0]&&!tr[x].son[1]) root=len=0;
else if(!tr[x].son[0]&&tr[x].son[1]) root=tr[x].son[1],tr[root].f=0;
else if(tr[x].son[0]&&!tr[x].son[1]) root=tr[x].son[0],tr[root].f=0;
else
{
int p=tr[x].son[0];
while(tr[p].son[1]) p=tr[p].son[1];
splay(p,x);
connect(tr[x].son[1],p,1);
root=p,tr[p].f=0,update(p);
}
}
inline int getrk(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].d<d) return tr[tr[x].son[0]].s+tr[x].n+1;
else return tr[tr[x].son[0]].s+1;
}
inline int kth(int k)
{
int x=root;
while(1)
{
int lc=tr[x].son[0],rc=tr[x].son[1];
if(k<=tr[lc].s) x=lc;
else if(k>tr[lc].s+tr[x].n) k=k-(tr[lc].s+tr[x].n),x=rc;
else break;
}
splay(x,0);
return tr[x].d;
}
inline int pre(int d)
{
int x=getip(d); splay(x,0);
if(d<=tr[x].d&&tr[x].son[0])
for(x=tr[x].son[0];tr[x].son[1];x=tr[x].son[1]);
return tr[x].d;
}
inline int nxt(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].d<=d&&tr[x].son[1])
for(x=tr[x].son[1];tr[x].son[0];x=tr[x].son[0]);
return tr[x].d;
}
int main()
{
n=read(),m=read();
for(ri i=1;i<=n;i++) x=read(),ins(x);
for(ri i=1;i<=m;i++)
{
opt=read(),x=read()^la;
if(opt==1) ins(x);
else if(opt==2) del(x);
else if(opt==3) ans^=(la=getrk(x));
else if(opt==4) ans^=(la=kth(x));
else if(opt==5) ans^=(la=pre(x));
else if(opt==6) ans^=(la=nxt(x));
}
printf("%d",ans);
return 0;
}by Smile_Cindy @ 2020-03-05 19:26:50
@JimmyFlower 好了，给你3,5,6操作时加了一个先插后删的操作，过了
#include<cctype>
#include<cstdio>
#define ri int
using namespace std;
int n,m,opt,x,ans=0,la=0;
int root=0,len=0;
struct splay{int d,n,s,f,son[2];}tr[1110000];
inline char gc()
{
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
ri x=0; register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);x=(x<<3)+(x<<1)+(c&15),c=gc());
return x;
}
inline int get(int x){return tr[tr[x].f].son[1]==x;}
inline void update(int x)
{
int lc=tr[x].son[0],rc=tr[x].son[1];
tr[x].s=tr[lc].s+tr[rc].s+tr[x].n;
}
inline void add(int d,int f)
{
len++;
tr[len].d=d,tr[len].n=tr[len].s=1,tr[len].f=f,tr[len].son[0]=tr[len].son[1]=0;
if(d<tr[f].d) tr[f].son[0]=len; else tr[f].son[1]=len;
}
inline void connect(int r,int R,int w)
{
if(r) tr[r].f=R;
tr[R].son[w]=r;
}
inline void rotate(int x)
{
int w=get(x)^1;
int f=tr[x].f,ff=tr[f].f;
connect(tr[x].son[w],f,w^1);
connect(x,ff,get(f));
connect(f,x,w);
update(f),update(x);
}
inline void splay(int x,int rt)
{
for(ri f;(f=tr[x].f)!=rt;rotate(x))
if(tr[f].f!=rt) rotate(get(x)==get(f)?f:x);
if(rt==0) root=x;
}
inline int getip(int d)
{
int x=root;
while(tr[x].d!=d)
{
if(d<tr[x].d)
{
if(!tr[x].son[0]) break;
x=tr[x].son[0];
}
else
{
if(!tr[x].son[1]) break;
x=tr[x].son[1];
}
}
return x;
}
inline void ins(int d)
{
if(root==0){add(d,0),root=len;return;}
int x=getip(d);
if(tr[x].d==d) tr[x].n++,splay(x,0);
else add(d,x),splay(len,0);
}
inline void del(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].n>1){tr[x].n--,update(x);return;}
if(!tr[x].son[0]&&!tr[x].son[1]) root=len=0;
else if(!tr[x].son[0]&&tr[x].son[1]) root=tr[x].son[1],tr[root].f=0;
else if(tr[x].son[0]&&!tr[x].son[1]) root=tr[x].son[0],tr[root].f=0;
else
{
int p=tr[x].son[0];
while(tr[p].son[1]) p=tr[p].son[1];
splay(p,x);
connect(tr[x].son[1],p,1);
root=p,tr[p].f=0,update(p);
}
}
inline int getrk(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].d<d) return tr[tr[x].son[0]].s+tr[x].n+1;
else return tr[tr[x].son[0]].s+1;
}
inline int kth(int k)
{
int x=root;
while(1)
{
int lc=tr[x].son[0],rc=tr[x].son[1];
if(k<=tr[lc].s) x=lc;
else if(k>tr[lc].s+tr[x].n) k=k-(tr[lc].s+tr[x].n),x=rc;
else break;
}
splay(x,0);
return tr[x].d;
}
inline int pre(int d)
{
int x=getip(d); splay(x,0);
if(d<=tr[x].d&&tr[x].son[0])
for(x=tr[x].son[0];tr[x].son[1];x=tr[x].son[1]);
splay(x,0);
return tr[x].d;
}
inline int nxt(int d)
{
int x=getip(d); splay(x,0);
if(tr[x].d<=d&&tr[x].son[1])
for(x=tr[x].son[1];tr[x].son[0];x=tr[x].son[0]);
splay(x,0);
return tr[x].d;
}
int main()
{
n=read(),m=read();
for(ri i=1;i<=n;i++) x=read(),ins(x);
for(ri i=1;i<=m;i++)
{
opt=read(),x=read()^la;
if(opt==3 || opt==5 || opt==6)ins(x);
if(opt==1) ins(x);
else if(opt==2) del(x);
else if(opt==3) ans^=(la=getrk(x));
else if(opt==4) ans^=(la=kth(x));
else if(opt==5) ans^=(la=pre(x));
else if(opt==6) ans^=(la=nxt(x));
if(opt==3 || opt==5 || opt==6)del(x);
}
printf("%d",ans);
return 0;
}by JimmyFlower @ 2020-03-05 20:36:31
@Alpha 谢谢，但是为什么这样可以过呢
by JimmyFlower @ 2020-03-05 20:44:41
?好玄学，getip加了splay#4竟然只有70ms?跑的比最优解还要快3,4倍
by Smile_Cindy @ 2020-03-05 20:44:42
@JimmyFlower 你的getip每次并不一定能保证找到x，可能找到x的前驱或者后继，如果实现得比较精细，也可以不用插入删除。
by JimmyFlower @ 2020-03-05 20:49:39
@Alpha 噢谢谢。话说这是第一次有人帮我看这么长的代码
by JimmyFlower @ 2020-03-05 20:51:17
确实挺巧妙，不过没想到常数影响会这么大
by JimmyFlower @ 2020-03-05 20:56:29
@Alpha 那个getip的函数怎么实现的更精细的一点？我感觉循环里这样判断太丑了。能给我一个那个部分的代码我自己看一下吗，如果有的话，谢谢。抱歉打扰您
by Smile_Cindy @ 2020-03-05 20:59:21
@JimmyFlower 这份代码因为卡常实现得比较精细，不过也因为卡常所以很丑。
#include <bits/stdc++.h>
#define prev aljflwehfe
#define next alaledhel
#define rank flsjlfelfe
using namespace std;
const int MAX_N=1100005;
struct node
{
int ch[2],fa,siz,cnt,val;
node()
{
ch[0]=ch[1]=0;
fa=0;
siz=0;
cnt=0;
val=0;
}
}T[MAX_N];
int n,m,num,rt;
bool idenify(int x)
{
return T[T[x].fa].ch[1]==x;
}
void update(int x)
{
T[x].siz=T[T[x].ch[0]].siz+T[x].cnt+T[T[x].ch[1]].siz;
}
void connect(int x,int y,bool flag)
{
T[x].fa=y;
T[y].ch[flag]=x;
}
void rotate(int x)
{
int y=T[x].fa,z=T[y].fa;
bool kx=idenify(x),ky=idenify(y);
int w=T[x].ch[!kx];
connect(w,y,kx);
connect(x,z,ky);
connect(y,x,!kx);
update(y);
update(x);
}
void splay(int x,int to=0)
{
while(T[x].fa!=to)
{
int y=T[x].fa,z=T[y].fa;
if(z!=to)
{
bool kx=idenify(x),ky=idenify(y);
if(kx==ky)rotate(y);
else rotate(x);
}
rotate(x);
}
if(!to)rt=x;
}
int kth(int k)
{
int cur=rt;
while(true)
{
if(k<=T[T[cur].ch[0]].siz)cur=T[cur].ch[0];
else if(k>T[cur].cnt+T[T[cur].ch[0]].siz)
{
k-=T[cur].cnt+T[T[cur].ch[0]].siz;
cur=T[cur].ch[1];
}
else
{
splay(cur);
return cur;
}
}
}
void insert(int x)
{
int cur=rt,p=0;
while(cur && T[cur].val!=x)
{
p=cur;
cur=T[cur].ch[x>T[cur].val];
}
if(cur)T[cur].cnt++;
else
{
cur=++num;
T[cur].val=x;
T[cur].siz=T[cur].cnt=1;
connect(cur,p,x>T[p].val);
}
splay(cur);
}
void find(int x)
{
int cur=rt;
if(!cur)return;
while(T[cur].ch[x>T[cur].val] && T[cur].val!=x)cur=T[cur].ch[x>T[cur].val];
splay(cur);
}
int prev(int x)
{
find(x);
int cur=rt;
if(T[cur].val<x)return cur;
cur=T[cur].ch[0];
while(T[cur].ch[1])cur=T[cur].ch[1];
splay(cur);
return cur;
}
int next(int x)
{
find(x);
int cur=rt;
if(T[cur].val>x)return cur;
cur=T[cur].ch[1];
while(T[cur].ch[0])cur=T[cur].ch[0];
splay(cur);
return cur;
}
void erase(int x)
{
int pre=prev(x),nxt=next(x);
splay(pre);
splay(nxt,pre);
int &t=T[nxt].ch[0];
if(T[t].cnt>1)
{
T[t].cnt--;
splay(t);
}
else t=0;
}
int rank(int x)
{
find(x);
if(T[rt].val<x)return T[T[rt].ch[0]].siz+T[rt].cnt;
else return T[T[rt].ch[0]].siz;
}
void init()
{
T[1].siz=1,T[2].siz=2;
T[1].val=INT_MIN,T[2].val=INT_MAX;
T[1].cnt=T[2].cnt=1;
connect(1,2,0);
rt=2;
num=2;
splay(1);
}
int A[MAX_N],B[MAX_N];
int newnode(int x)
{
num++;
T[num].val=x;
T[num].cnt=1;
T[num].siz=1;
return num;
}
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
template <class I>
inline void gi (I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
// print a signed integer
template <class I>
inline void print (I x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: putc;
using io :: print;
int main()
{
init();
gi(n);
gi(m);
for(int i=1;i<=n;i++)gi(A[i]);
static int L[256];
for(int i=0;i<32;i+=8)
{
memset(L,0,sizeof(L));
for(int j=1;j<=n;j++)L[A[j]>>i&255]++;
for(int j=1;j<256;j++)L[j]+=L[j-1];
for(int j=n;j>=1;j--)B[L[A[j]>>i&255]--]=A[j];
for(int j=1;j<=n;j++)A[j]=B[j];
}
int pre=2;
for(int i=n;i>=1;i--)
{
if(i==n || A[i]!=A[i+1])
{
int t=newnode(A[i]);
connect(t,pre,0);
pre=t;
}
else
{
T[pre].cnt++;
T[pre].siz++;
}
}
splay(pre);
int last=0,ans=0;
while(m--)
{
int op,x;
gi(op);
gi(x);
x=x xor last;
if(op==1)insert(x);
else if(op==2)erase(x);
else if(op==3)ans=ans xor (last=rank(x));
else if(op==4)ans=ans xor (last=T[kth(x+1)].val);
else if(op==5)ans=ans xor (last=T[prev(x)].val);
else ans=ans xor (last=T[next(x)].val);
}
print(ans);
return 0;
}by JimmyFlower @ 2020-03-05 21:00:03
谢了
by JimmyFlower @ 2020-03-05 21:02:02
hh其实我也不必在此纠结太多的