题目链接
题解
这题有毒&&bzojAC100祭
我们需要在最大\log_2级别的复杂度内解决4个问题：
- 插入一个元素
- 删除集合中值等于X（输入的值）的所有元素
- 对于整个集合的所有元素值增加X
- 查询集合内元素二进制下第K位为1的个数
数据范围N\leq 500000,X\leq 10^{16}
X在10^{16}，所以如果我们不能开权值线段树去维护这4个操作，首先我们没办法在\log的复杂度内实现第四个操作，其次空间难以承受。
我们考虑一个与线段树功能类似的数据结构。
树状数组。
我们将权值作为下标，开16个权值树状数组，分别表示考虑后i位的小于等于x的数的个数。
所以我们通过作差可以求出第K位为1的数的个数。
显然易见：ans=c[k][2^{k+1}-1]-c[k][2^k-1]
至于ADD操作的lazy标记可以通过标记永久化来解决。
写个博客表示我还在水题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<set> using namespace std; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } const int maxn=3e5+10; multiset<int>s; int n,sum; long long c[20][maxn]; char op[30]; inline int lowbit(int x){ return x&-x; } inline void add(int x,int pos,long long num){ for(;pos<=(1<<16);pos+=lowbit(pos))c[x][pos]+=num; } inline int query(int t,int x){ int tot=0; for(;x;x-=lowbit(x)) tot+=c[t][x]; return tot; } int main() { #ifndef ONLINE_JUDGE freopen("2568.in","r",stdin); freopen("2568.out","w",stdout); #endif read(n); for(int j=1,x;j<=n;j++){ scanf(" %s %d",op+1,&x); if(op[1]=='A')sum+=x; if(op[1]=='I'){ s.insert(x-sum); for(int i=1;i<=18;i++) add(i-1,(((1<<i)-1)&(x-sum))+1,1); } if(op[1]=='D'){ int tot=s.count(x-sum);s.erase(x-sum); for(int i=1;i<=18;i++)add(i-1,(((1<<i)-1)&(x-sum))+1,-tot); } if(op[1]=='Q'){ int l=1<<x;int r=(1<<(x+1))-1; int ans=0; ans+=query(x,min(max(r-(sum&((1<<(x+1))-1))+1,0),1<<16)); ans-=query(x,min(max(l-(sum&((1<<(x+1))-1)),0),1<<16)); l+=1<<(x+1),r+=1<<(x+1); ans+=query(x,min(max(r-(sum&((1<<(x+1))-1))+1,0),1<<16)); ans-=query(x,min(max(l-(sum&((1<<(x+1))-1)),0),1<<16)); printf("%d\n",ans); } } return 0; } |
By:Wahacer
2018.06.19
16:54