题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=4408
权限题
题解
首先我们考虑当区间[1..x]全部可以表达出来的时候，假设新加入一个数字K
则如果K<=x+1 就表示从[1..x+K]中所有的数都可以被表示出来
否则就gg了
可是这个东西吧 它有多个区间 多个区间的话复杂度好像有点不对？
考虑设ans=x,表示已经表达了[1..x]的所有数字
y=Σa[i] i∈[l,r]且a[i]<=ans
如果y<=ans 显然存在一个数字 k<=x+1
否则表示其他所有数字都>x+1
这个东西用一个主席树 离散化处理一下就行啦！
#include <bits/stdc++.h> using namespace std; int Size,Siz,N,a[100005],b[100005],c[100005],rt[100005]; struct Node{ int l,r,val; }Tree[20*100005]; int Get_Num(int x){ int l=1,r=Size,ans; while (l<=r){ int mid=(l+r)>>1; if (b[mid]<=x) ans=mid,l=mid+1; else r=mid-1; } return ans; } void Insert(int &rt1,int rt2,int l,int r,int Ned,int val){ int mid=(l+r)>>1; rt1=++Siz; Tree[rt1]=Tree[rt2]; Tree[rt1].val=Tree[rt2].val+val; if (l==r) return; if (Ned<=mid) Insert(Tree[rt1].l,Tree[rt2].l,l,mid,Ned,val); else Insert(Tree[rt1].r,Tree[rt2].r,mid+1,r,Ned,val); } int Query(int rt1,int rt2,int l,int r,int L,int R){ int mid=(l+r)>>1; int ans=0; if (L<=l&&r<=R) return Tree[rt2].val-Tree[rt1].val; if (l<=mid) ans+=Query(Tree[rt1].l,Tree[rt2].l,l,mid,L,R); if (mid<R) ans+=Query(Tree[rt1].r,Tree[rt2].r,mid+1,r,L,R); return ans; } int main(){ scanf("%d",&N); for (int i=1;i<=N;i++){ scanf("%d",&b[i]); c[i]=b[i]; } sort(b+1,b+N+1); Size=unique(b+1,b+N+1)-b-1; for (int i=1;i<=N;i++) a[i]=lower_bound(b+1,b+Size+1,c[i])-b; for (int i=1;i<=N;i++){ rt[i]=rt[i-1]; Insert(rt[i],rt[i-1],1,Size,a[i],c[i]); } int T; scanf("%d",&T); while (T--){ int l,r; scanf("%d%d",&l,&r); int ans=1; while (1){ int Ned=Get_Num(ans); int Sum=Query(rt[l-1],rt[r],1,Size,1,Ned); if (Sum>=ans) ans=Sum+1; else break; } printf("%d ",ans); } return 0; }