功在不舍 @ 2020-02-29 23:38:22
怎么搞都只有70
#define FASTER
#ifdef FASTER
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#endif
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,inf=0x7fffffff,last,ans;
struct Splay{
int all,root,father[1500001],ch[1500001][2],size[1500001],val[1500001],cnt[1500010];
int identify(int x){return ch[father[x]][0]==x?0:1;}
void updata(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];}
void connect(int x,int fa,int son){father[x]=fa;ch[fa][son]=x;}
void rotate(int x){
register int y=father[x],r=father[y];
register int yson=identify(x),rson=identify(y);
register int b=ch[x][yson^1];
connect(b,y,yson);connect(y,x,yson^1);connect(x,r,rson);
updata(y);
}
void splay(int x,int to){
while(father[x]!=to)
{
register int y=father[x],z=father[y];
if(z!=to)
(identify(x)^identify(y))?rotate(x):rotate(y);
rotate(x);
}updata(x);if(to==0)root=x;
}
void search(int x){
int now=root;
while(val[now]!=x&&ch[now][x>val[now]]!=0)
now=ch[now][x>val[now]];
splay(now,0);
}
int find(int x){
int now=root;
while(1){
if(x<=size[ch[now][0]])now=ch[now][0];
else{
x-=(size[ch[now][0]]+cnt[now]);
if(x<=0){splay(now,0);return val[now];}
now=ch[now][1];
}
}
}
int prefix(int x){
search(x);
int now=ch[root][0];
while(ch[now][1])now=ch[now][1];
return now;
}
int suffix(int x){
search(x);
int now=ch[root][1];
while(ch[now][0])now=ch[now][0];
return now;
}
void insert(int x){
int now=root,fa=0;
while(val[now]!=x&&now!=0)
fa=now,now=ch[now][x>val[now]];
if(now!=0)cnt[now]++;
else {
now=++all;
if(fa)ch[fa][x>val[fa]]=now;
size[now]=cnt[now]=1;
val[now]=x;father[now]=fa;
}
splay(now,0);
}
void del(int x){
int suf=suffix(x),pre=prefix(x);
splay(pre,0);splay(suf,pre);
int now=ch[suf][0];
if(cnt[now]>1)cnt[now]--,splay(now,0);
else ch[suf][0]=0,splay(suf,0);
}
int rank(int x){
search(x);
return size[ch[root][0]];
}
}tree;
int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
int main()
{
// freopen("t1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=n;i++)
{
int x=read();
tree.insert(x);
}
tree.insert(-inf);tree.insert(inf);
for(int i=1;i<=m;i++)
{
int opt=read(),x=read();
x^=last;
// cout<<opt<<" "<<x<<endl;
// cout<<last<<endl;
if(opt==1)tree.insert(x);
if(opt==2)tree.del(x);
if(opt==3)
{
tree.insert(x);
last=tree.rank(x);
ans^=last;
tree.del(x);
}
if(opt==4)
{
last=tree.find(x+1);
ans^=last;
}
if(opt==5)
{
tree.insert(x);
last=tree.val[tree.prefix(x)];
ans^=last;
tree.del(x);
}
if(opt==6)
{
tree.insert(x);
last=tree.val[tree.suffix(x)];
ans^=last;
tree.del(x);
}
}
cout<<ans<<endl;
return 0;
}by momo5440 @ 2020-03-01 00:05:30
从巨佬那copy过来的
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")by xiejinhao @ 2020-03-01 00:43:27
@功在不舍
没人告诉你结构体很慢吗……
by SSerxhs @ 2020-03-01 02:06:18
connect都封装还不inline能不慢吗。。
by 功在不舍 @ 2020-03-01 10:32:38
@xiejinhao
我拆了结构体，把小函数写进去了，第一个点数据本地还是2.9s
求大佬帮帮
#define FASTER
#ifdef FASTER
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#endif
#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int n,m,inf=0x7fffffff,last,ans;
int all,root,father[1500001],ch[1500001][2],size[1500001],val[1500001],cnt[1500010];
inline void rotate(int x){
register int y=father[x],r=father[y];
register int yson=ch[y][1]==x,rson=ch[r][1]==y;
register int b=ch[x][yson^1];
father[b]=y;ch[y][yson]=b;father[y]=x;ch[x][yson^1]=y;father[x]=r;ch[r][rson]=x;
size[y]=size[ch[y][0]]+size[ch[y][1]]+cnt[y];
}
inline void splay(int x,int to){
while(father[x]!=to)
{
register int y=father[x],z=father[y];
if(z!=to)
((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y);
rotate(x);
}
size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
if(to==0)root=x;
}
inline void search(int x){
int now=root;
while(val[now]!=x&&ch[now][x>val[now]]!=0)
now=ch[now][x>val[now]];
splay(now,0);
}
inline int find(int x){
int now=root;
while(1){
if(x<=size[ch[now][0]])now=ch[now][0];
else{
x-=(size[ch[now][0]]+cnt[now]);
if(x<=0)return now;
now=ch[now][1];
}
}
}
inline int prefix(int x){
search(x);
int now=ch[root][0];
while(ch[now][1])now=ch[now][1];
return now;
}
inline int suffix(int x){
search(x);
int now=ch[root][1];
while(ch[now][0])now=ch[now][0];
return now;
}
inline void insert(int x){
if(!root)
{
root=++all;
size[root]=1;cnt[root]=1;val[root]=x;return ;
}
int now=root,fa=0;
while(val[now]!=x&&now!=0)
fa=now,now=ch[now][x>val[now]];
if(now!=0)cnt[now]++,size[now]++;
else {
now=++all;
ch[fa][x>val[fa]]=now;
size[now]=cnt[now]=1;
val[now]=x;father[now]=fa;
}
splay(now,0);
}
inline void del(int x){
int suf=suffix(x),pre=prefix(x);
splay(pre,0);splay(suf,pre);
int now=ch[suf][0];
if(cnt[now]>1)cnt[now]--,splay(now,0);
else ch[suf][0]=0,splay(suf,0);
}
inline int rank(int x){
search(x);
return size[ch[root][0]];
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
int main()
{
freopen("t1.in","r",stdin);
n=read();m=read();
for(register int i=1;i<=n;i++)
{
register int x=read();
insert(x);
}
insert(-inf);insert(inf);
for(register int i=1;i<=m;i++)
{
register int opt=read(),x=read();
x^=last;
// cout<<opt<<" "<<x<<endl;
// cout<<last<<endl;
if(opt==1)insert(x);
else if(opt==2)del(x);
else if(opt==3)
{
insert(x);
last=rank(x);
ans^=last;
del(x);
}
else if(opt==4)
{
last=val[find(x+1)];
ans^=last;
}
else if(opt==5)
{
insert(x);
last=val[prefix(x)];
ans^=last;
del(x);
}
else if(opt==6)
{
insert(x);
last=val[suffix(x)];
ans^=last;
del(x);
}
}
cout<<ans<<endl;
return 0;
}by 谋事在人 @ 2020-03-01 19:48:20
写spaly（雾）
by 功在不舍 @ 2020-03-02 17:26:41
splay已死此贴终结
FHQ Treap
#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];
int newnode(int v){val[++all]=v;size[all]=1;pri[all]=rand();return all;}
void updata(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}
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;
}
}
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);
}
}
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];
}
}
}
void insert(int v){
split(root,v,x,y);
root=merge(merge(x,newnode(v)),y);
}
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);
}
void rank1(int v){
split(root,v-1,x,y);
last=size[x]+1;
root=merge(x,y);
ans^=last;
}
void prefix(int v){
split(root,v-1,x,y);
last=val[kth(x,size[x])];
root=merge(x,y);
ans^=last;
}
void suffix(int v){
split(root,v,x,y);
last=val[kth(y,1)];
root=merge(x,y);
ans^=last;
}
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)rank1(q);
else if(p==4)last=val[kth(root,q)],ans^=last;
else if(p==5)prefix(q);
else if(p==6)suffix(q);
}
cout<<ans<<endl;
return 0;
}