题解 CF1354D 【Multiset】

## 题目大意 有一串$n$个正整数的数列$\{A_i\}$，它们的值域为$[1,n]$。现在有$q$个操作，共有两类： - $1.$删除排名为$k$的数字。若没有，则忽略这次操作。 - $2.$加入数字$k$，满足$k\in[1,n]$。 $n,q\le 1\times 10^6$。空间限制：$\rm 28MB$。 最后输出任意一个数列中存在的数字即可。 ## 题解 $10^6$个$\rm int$占用的内存是$\rm 4MB$，因此我们只需要用空间复杂度常数较小的结构就可以轻松地过去了…… 由于值域在$[1,n]$内，考虑值域树状数组维护一个桶。 ### 操作$2$ 加入一个数字$k$，显然直接在桶的下标$k$处加一就可以了。 ### 操作$1$ 查询$k$大，可以用值域树状数组来写。我们可以用值域树状数组查询到大小在$[1,x]$中所有数字出现过的次数之和。显然，这个值单调不减。用树状数组查询$k$大，有一个好处，就是$C_{p+2^q}$的值，就是$[p,p+2^q]$的值。具体证明可以参照树状数组的定义。于是，我们从大到小枚举$q$，然后判断是否要让当前的$p$加上$2^q$即可。 ### 关于空间限制 这题有$\rm 28MB$的限制。虽然他卡不动树状数组，但是这里还是提供一个简单的卡空间的办法。由于桶中每个数字不超过$2^{21}$，因此我们可以将一个$\rm unsigned\_long\_long$类型的数据存储三个元素。这样，可以节省$\frac{1}{3}$的空间。 具体而言，我们开一个存放数据的内存数组$M$。当查询下标$x$时，我们根据$\left\lfloor\frac{x}{3}\right\rfloor$定位出$x$存放在了$M$的哪一位；再根据$x$除以$3$的余数，得出在这一位的哪一段；再使用位运算取出这一段即可。 ## 参考代码 ``` #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } const int MAXN =1e6+3; typedef unsigned long long u64; typedef unsigned int u32; u64 M[MAXN/3]; u32 get(int idx){ int p=idx/3; switch(idx%3){ case 0: return (M[p]&0b111111111111111111111000000000000000000000000000000000000000000)>>42; case 1: return (M[p]&0b000000000000000000000111111111111111111111000000000000000000000)>>21; default: return M[p]&0b000000000000000000000000000000000000000000111111111111111111111; } } void add(int idx,int w){ int p=idx/3; if(w>0) switch(idx%3){ case 0: M[p]+=(LL)w<<42; break; case 1: M[p]+=(LL)w<<21; break; case 2: M[p]+=(LL)w; break; } else{ w=-w; switch(idx%3){ case 0: M[p]-=(LL)w<<42; break; case 1: M[p]-=(LL)w<<21; break; case 2: M[p]-=(LL)w; break; } } } #define C(x) (x&-x) int n,q,tot; void inc(int idx){ while(idx<=n) add(idx,1),idx+=C(idx); } void dec(int idx){ while(idx<=n) add(idx,-1),idx+=C(idx); } int kth(int x){ int p=0,k=1<<21; for(;k;k>>=1){ if((p|k)<=n&&get(p|k)<x) x-=get(p|k),p|=k; } return p+1; } int main(){ n=qread(),q=qread(),tot=n; up(1,n,i) inc(qread()); up(1,q,i){ int w=qread(); if(w<0){ if(-w>tot) continue; else dec(kth(-w)),--tot; }else inc(w),++tot; } if(tot==0) puts("0"),exit(0); printf("%d\n",kth(1)); return 0; } ```