FJWC2016 BZOJ4299 神秘数(CodeChef FRBSUM) 【主席树】
【题目描述】一个可重复数字集合 S 的神秘数定义为最小的不能被 S 的子集的和表示的正整数。例如 S={1,1,1,4,13}，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18 无法表示为集合 S 的子集的和，故集合 S 的神秘数为 8。现给定 n 个正整数 a[1]..a[n]，m 个询问，每次询问给定一个区间[l,r](l<=r)，求由 a[l],a[l+1],…,a[r]所构成的可重复数字集合的神秘数。n<=100000
题解：
首先我们将数据排好序，对于新加进来的一个数$p$，假设我们原来最多能摆到$q$，那么如果$p<=q$，我们就可以摆到$p+q-1$，那么每次插入一个数，我们就可以把它扔到一个线段树中去维护。但是又有区间，所以我们就想到是个二维问题，转化为平面，一维区间，一维数值，做类似于二维偏序的东西，如果再套一个线段树，那么复杂度是$O(nlog_{2}^{3}n)$，所以我们必须用主席树来维护，复杂度$O(nlog_{2}^{2}n)$。
# include <stdio.h>
using namespace std;
const int M=200010;
int n,q,mm;
int ch[M*20][2],s[M*20],root[M],tot=0,a[M];
inline void update(int root1,int &root,int l,int r,int ai) {
if(!root) root=++tot;
s[root]=s[root1]+ai;
if(l==r) return;
int mid=l+r>>1;
if(ai<=mid) ch[root][1]=ch[root1][1],update(ch[root1][0],ch[root][0],l,mid,ai);
else ch[root][0]=ch[root1][0],update(ch[root1][1],ch[root][1],mid+1,r,ai);
}
inline int query(int root1,int root,int l,int r,int ai) {
if(l>ai) return 0;
if(s[root]-s[root1]==0) return 0;
if(r<=ai) return s[root]-s[root1];
int mid=l+r>>1;
int rr=query(ch[root1][0],ch[root][0],l,mid,ai);
if(ai>mid) rr+=query(ch[root1][1],ch[root][1],mid+1,r,ai);
return rr;
}
inline int qu(int l,int r) {
int tt;
for (int t=1;;t=tt+1) {
tt=query(root[l],root[r],1,mm,t);
if(tt<t) return t;
}
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i) {
scanf("%d",&a[i]);
if(a[i]>mm) mm=a[i];
}
for (int i=1;i<=n;++i)
update(root[i-1],root[i],1,mm,a[i]);
scanf("%d",&q);
while(q--) {
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",qu(l-1,r));
}
return 0;
}
2023年4月24日 18:47
Scholarship fellowship works on giving out better service in different forms and we do not sell or give away your personal information other than public info given out by you. We are very conscious about mail spam scholarship-fellowship.com and we try to protect every email as much as possible. In certain cases, your mail may be exposed to the public. Scholarship fellowship works on giving out better service in different forms and we do not sell or give away your personal information other than public info given out by you.