【主席树】神秘数

主席树

传送门：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;
}