题目

有一个初始为空的数组，你需要处理q(q<=1e6)次操作，操作分四种：

① + x，数组后面加一个新的数x

② - k，删掉数组最后面的k个值

③ !，回滚最后一次变更（只有①操作和②操作视为变更）

④?，询问当前数组内的不同的数的个数（即数的种类数）

E1允许离线，E2强制在线，需要每次输出答案后刷新缓冲区

思路来源

jjleo代码/jiangly代码/官方题解

心得

这个题赛中一看，这不主席树sb题，结果写了一发喜提MLE

然后以为卡卡空间就卡过去了，结果卡了6个小时空间才卡过去，喜提-200分掉到蓝名成就

画风

3s、256M，可以说是非常极限了（不过还没有加快读）

最后卡过去的提交是，考虑到数字都在，所以，

用三个unsigned char和一位的bitset模拟了下int，

大概把空间大概压到了3/4（感觉纯纯脑瘫）

题解

主席树

朴素

1. 加数时，按照询问动态开点，在主席树上建一条链

2. 查询时，就全局查询数的种类数，实际只需要用到根节点

3. 回滚时，维护一个数组记录一下操作的点号的序列，退到前一个

4. 删除时，倍增往上跳k个

主席树需要维护lson、rson、num三个变量，num从0变1表示新增，其余非新增，

每个空间1e6*20大概2e7，三个6e7，倍增也需要开1e6*20=2e7，

这样做空间总共约8e7，而256M空间只能开下约6e7的数组

优化

不需要num这个变量

当主席树上建一条新链的时候，在进入叶子结点前，

先判断一下叶子结点这个方向的点是否存在，

已经存在就说明种类数没有新增，否则是新增了一个值

而询问只需要全局询问根，所以只需要每个节点记录一下答案

从而将1e6*20的空间优化到了1e6

树状数组

待补

差分+前缀和O(n)

待补

代码

主席树优化

#include <bits/stdc++.h>
#define maxn 1000086using namespace std;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;
}struct Node{int son[2];
}t[maxn * 21];#define ls(x) (t[x].son[0])
#define rs(x) (t[x].son[1])int cnt;int modify(int x, int l, int r, int pos){int tag = 0;while(l < r){int mid = l + r >> 1;if(mid >= pos){if(!ls(x)) tag = 1;t[++cnt] = t[ls(x)], x = ls(x) = cnt, r = mid;}else{if(!rs(x)) tag = 1;t[++cnt] = t[rs(x)], x = rs(x) = cnt, l = mid + 1;} }return tag;
}int q;
int fa[maxn][20];
char s[10];
int tot = 1;
int a[maxn], siz;
int ans[maxn], rt[maxn];int main(){q = read();int now = 1;while(q--){scanf("%s", s);if(s[0] == '+'){int x;x = read();int p = ++tot;fa[p][0] = now;for(int i = 1;i < 20;i++) fa[p][i] = fa[fa[p][i - 1]][i - 1];rt[p] = ++cnt;t[rt[p]] = t[rt[now]];ans[p] = ans[now] + modify(rt[p], 1, 1e6, x);now = p;a[++siz] = now;}else if(s[0] == '-'){int k;k = read();for(int i = 0;i < 20;i++) if(k & (1 << i)) now = fa[now][i];a[++siz] = now;}else if(s[0] == '!'){now = a[--siz];}else{printf("%d\n", ans[now]), fflush(stdout);}}
}

主席树朴素（空间卡常）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10,M=N*22,INF=0x3f3f3f3f,lb=(1<<8)-1,mx=1<<24;
int q,x,y,cur,par[N][10],up=1000000;
int root[N],pos;
int op[N],c;
char s[5];
bitset<M>most[2];
struct node{unsigned char a[3];int g(){int f=0;for(int i=2;i>=0;--i){f=(f<<8)|a[i];}return f;}void s(int x){//assert(x<(1<<20));for(int i=0;i<3;++i){//printf("x&lb:%d\n",x&lb);a[i]=x&lb;x>>=8;}}
}sum[M];
node operator+(node a,node b){int v1=a.g(),v2=b.g();node c;c.s(v1+v2);return c;
}
struct node2{unsigned char a[3];int g(int p,int id){int f=0;for(int i=2;i>=0;--i){f=(f<<8)|a[i];}if(most[id].test(p))f|=mx;return f;}void s(int p,int id,int x){if(x&mx)most[id].set(p);else most[id].reset(p);for(int i=0;i<3;++i){//printf("x&lb:%d\n",x&lb);a[i]=x&lb;x>>=8;}}
}ch[M][2];
int copy(int x){pos++;//if(pos>=M)while(1);ch[pos][0]=ch[x][0];if(most[0].test(x))most[0].set(pos);ch[pos][1]=ch[x][1];if(most[1].test(x))most[1].set(pos);sum[pos]=sum[x];return pos;
}
void add(int k,int l,int r,int x){if (l==r) {if(!sum[k].g())sum[k].s(1);return;}int mid=(l+r)/2,y=ch[k][0].g(k,0),z=ch[k][1].g(k,1);if (x<=mid){y=copy(y);ch[k][0].s(k,0,y);add(y,l,mid,x);}else{z=copy(z);ch[k][1].s(k,1,z);add(z,mid+1,r,x);}sum[k]=sum[y]+sum[z];
}int ask(int k,int l,int r,int a,int b){if (!k) return 0;if (a==l&&b==r) return sum[k].g();int mid=(l+r)/2;if (b<=mid) return ask(ch[k][0].g(k,0),l,mid,a,b);else if (a>mid) return ask(ch[k][1].g(k,1),mid+1,r,a,b);else return ask(ch[k][0].g(k,0),l,mid,a,mid)+ask(ch[k][1].g(k,1),mid+1,r,mid+1,b);
}void op1(int x){int las=cur;cur=++y;par[cur][0]=las;root[cur]=copy(root[las]);rep(i,1,9){int z=cur;for(int j=1;j<=4;++j){z=par[z][i-1];}par[cur][i]=z;}add(root[cur],1,up,x);op[++c]=las;
}
void op2(int k){int las=cur;for(int i=k,x=0;i;i>>=2,x++){int v=i&3;for(int j=1;j<=v;++j){cur=par[cur][x];}}//printf("cur:%d\n",cur);op[++c]=las;
}
void op3(){cur=op[c--];//printf("cur:%d\n",cur);return;
}
void op4(){printf("%d\n",sum[root[cur]].g());fflush(stdout);
}
int main(){//sum[0].s(125);//printf("%d\n",sum[0].g());sci(q);root[0]=pos=1;while(q--){scanf("%s",s);if(s[0]=='+'){sci(x);op1(x);}else if(s[0]=='-'){sci(x);op2(x);}else if(s[0]=='!'){op3();}else{op4();}}return 0;
}