《P4587 [FJOI2016] 神秘数》

题目描述

一个可重复数字集合 S 的神秘数定义为最小的不能被 S 的子集的和表示的正整数。例如 S={1,1,1,4,13}，有：1=1，2=1+1，3=1+1+1，4=4，5=4+1，6=4+1+1，7=4+1+1+1。

8 无法表示为集合 S 的子集的和，故集合 S 的神秘数为 8。

现给定长度为 n 的正整数序列 a，m 次询问，每次询问包含两个参数 l,r，你需要求出由 al​,al+1​,⋯,ar​ 所组成的可重集合的神秘数。

输入格式

第一行一个整数 n，表示数字个数。

第二行 n 个正整数，从 1 编号。

第三行一个整数 m，表示询问个数。

输出格式

对于每个询问，输出一行对应的答案。

输入输出样例

输入 #1复制

5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5

输出 #1复制

2 4 8 8 8

说明/提示

对于 100% 的数据点，1≤n,m≤105，∑a≤109。

代码实现：

#include<bits/stdc++.h> using namespace std; #define il inline #define rg register #define ll long long il int rd() { int res=0,k=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();} while(ch<='9'&&ch>='0'){res=res*10+ch-48;ch=getchar();} return res*k; } il void wt(int x) { if(x<0)return putchar('-'),wt(-x),void(); if(x<=9)return putchar(x+48),void(); return wt(x/10),wt(x%10),void(); } int lg[100005], a[100005], n, m; struct st { int st[100005][17]; ll sum[100005]; void init(int llim, int rlim) { sum[0]=0; for(rg int i=1;i<=n;i++) if(a[i]>=llim&&a[i]<=rlim)st[i][0]=a[i],sum[i]=sum[i-1]+a[i]; else st[i][0]=0x3f3f3f3f,sum[i]=sum[i-1]; for(rg int j=1;(1<<j)<=n;j++) for(rg int i=1;i+(1<<j)<=n+1;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } ll qry_min(int l, int r) { int d=lg[r-l]; return min(st[l][d],st[r-(1<<d)+1][d]); } ll qry_sum(int l, int r) { return sum[r]-sum[l-1]; } } b[30]; signed main() { n=rd(); for(rg int i=1;i<=n;i++) a[i]=rd(); m=rd(); for(rg int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; b[0].init(1,1); for(rg int i=1,t=2;i<=29;i++,t<<=1ll) b[i].init(t,t+t-1); for(rg int i=1,l,r;i<=m;i++) { l=rd();r=rd(); ll ans=0; int t=0; while(t<=29) { if(ans+1ll<min(b[t].qry_min(l,r),(1ll<<(t+1))-1)) break; ans+=b[t].qry_sum(l,r); t++; } wt(ans+1ll); puts(""); } return 0; }