Luogu

BZOJ权限题

分析

有两条比较显然的性质:

  • 若有$n$个$1$,则$1\sim n$都能被表示出来,即答案是$n+1$。
  • 如果新加进来一个大于$n+1$的数,则答案还是$n+1$。

假设已经表示出了$[1,x]$。查询一下区间$[l,r]$中所有小于等于$x+1$的数的和$s$,若$s\geq x+1$,说明此时必定还存在更大的组合方案,可以表示的区间变为$[1,s]$,继续做这个过程即可。

可以用主席树来维护区间小于等于某个数的数的和,复杂度大概是$O(n\log^2n)$?

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
int a[N],b[N];

struct node {
    int lc,rc,sum;
} t[N*30];

int rt[N],tot=0;
inline int build(int l,int r) {
    int p=++tot;
    if (l==r) return p;
    int mid=(l+r)>>1;
    t[p].lc=build(l,mid),t[p].rc=build(mid+1,r);
    return p;
}
inline int insert(int now,int l,int r,int x,int dlt) {
    int p=++tot; t[p]=t[now],t[p].sum+=dlt;
    if (l==r) return p;
    int mid=(l+r)>>1;
    if (x<=mid) t[p].lc=insert(t[now].lc,l,mid,x,dlt);
    else t[p].rc=insert(t[now].rc,mid+1,r,x,dlt);
    return p;
}
inline int query(int p,int q,int l,int r,int st,int ed) {
    int mid=(l+r)>>1,ans=0;
    if (l>=st&&r<=ed) return t[q].sum-t[p].sum;
    if (st<=mid) ans+=query(t[p].lc,t[q].lc,l,mid,st,ed);
    if (ed>mid) ans+=query(t[p].rc,t[q].rc,mid+1,r,st,ed);
    return ans;
}

inline int find(int x,int tot) {
    int L=1,R=tot,ans;
    while (L<=R) {
        int mid=(L+R)>>1;
        if (b[mid]<=x) ans=mid,L=mid+1;
        else R=mid-1;
    }
    return ans;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=b[i]=read();
    sort(b+1,b+n+1); int tot=unique(b+1,b+n+1)-b-1;
    rt[0]=build(1,tot);
    for (re int i=1;i<=n;++i) {
        int x=find(a[i],tot);
        rt[i]=insert(rt[i-1],1,tot,x,a[i]);
    }
    m=read();
    while (m--) {
        int l=read(),r=read(),ans=1;
        while (233) {
            int x=find(ans,tot);
            int s=query(rt[l-1],rt[r],1,tot,1,x);
            if (s>=ans) ans=s+1;
            else break;
        }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 04 PM