【主席树】神秘数

传送门:LOJ2174


思路:

  • 先来撕烤一些性质;
  • 将数组排序以后,如果前$i$个数的前缀和$tmp$比第$i+1$个数少$2$或更多,那么$tmp+1$即为答案;
  • 然后可以推出如果小于等于$i$的数的答案为$ans$,且整个序列中小于等于$ans$的数的和$tmp$小于$ans$,那么答案即为$ans$;
  • 否则答案不小于$tmp+1$,因为$[1,ans]$可以与后面的数组造出$[ans+1,tmp]$的所有数。

代码如下:

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 120000
#define MAX 1000000005
int n,m,x,cnt,l,r,ans,tmp,root[N],sum[N*30],ls[N*30],rs[N*30];
int getint(){
char ch; int sum=0;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
return sum;
}
void ins(int &rt,int rt2,int l,int r,int k){
if (!rt) sum[rt=++cnt]=sum[rt2];
if (l==r){sum[rt]+=k; return;}
int mid=(l+r)>>1;
if (k<=mid){rs[rt]=rs[rt2]; ins(ls[rt],ls[rt2],l,mid,k);}
if (k>mid){ls[rt]=ls[rt2]; ins(rs[rt],rs[rt2],mid+1,r,k);}
sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
int query(int rt,int l,int r,int L,int R){
if (!rt) return 0;
if (l>=L && r<=R) return sum[rt];
int mid=(l+r)>>1,ret=0;
if (L<=mid) ret+=query(ls[rt],l,mid,L,R);
if (R>mid) ret+=query(rs[rt],mid+1,r,L,R);
return ret;
}
int main(){
n=getint();
for (int i=1;i<=n;i++){x=getint(); ins(root[i],root[i-1],1,MAX,x);}
m=getint();
for (int i=1;i<=m;i++){
l=getint(); r=getint();
ans=1;
while ((tmp=query(root[r],1,MAX,1,ans)-query(root[l-1],1,MAX,1,ans))>=ans) ans=tmp+1;
printf("%d\n",ans);
}
return 0;
}