P4587

Aryper · 2021-08-13 23:27:46 · 个人记录

[FJOI2016]神秘数

我们知道：若区间 [l,r]（下标）的数可以表示范围 [1,x]（值域），且 [l,r] 中处在 [lst+1,x+1]（值域，其中 lst 表示用 \le lst 的数可以表示 [1,x]）的数的和 sum>0，就说明值域 [1,x] 可继续扩展到 [1,x+sum]；反之则不可扩展，所求神秘数即为 x+1。

然后根据 \sum a\le10^9 这个条件，可以写一些比较莽的实现。

我们可以用一个主席树维护离散化后的序列，第 i 个版本为 从 a_1 添加数到 a_i 的线段树，维护的信息是每段值域上已经被加入的数的和。

然后我们针对每一次 [l,r] 的询问，借助主席树，用如下方法解决：

1. 首先我们知道，没有数字的数列可以表示 [1,0]（值域，在数学意义上不能这样写，所以意会即可），那么我们利用主席树，求取 [l,r] 中处在 [0,1]（值域）的数的和，如果 sum>0，我们根据上面的原理扩展值域。扩展后的值域是 [1,sum]。

2. 将 [1,sum] 作为新的可表示范围（可看做新的 [1,x]），此时的 lst=1；然后再扩展至某个值域 [1,sum+sum']，此时的 lst=sum+1。

3. 然后重复上文操作，直至不可扩展。

最令人疑惑的就在于这个反复扩展值域的过程，它的复杂度究竟有多高？

我们每次扩展，都令 lst=x_{pre}+1。考虑最坏的情况，倘若我们每次求得的 sum 都只能等于 lst+1，甚至，考虑不可能存在的更坏情况，sum 只能等于 lst-1。那么 [1,x] 扩展到 [1,x+x_{pre}]。以此类推的话，还能扩展到 [1,x+(x+x_{pre})]，然后扩展到 [1,x+(x+x_{pre})+(x+x_{pre})]……

注意到，如果 x_{pre}=1，x=1 ，那么上面的区间的右端的数构成了斐波那契数列。重要的是，斐波那契数列的增长速度很快，为指数式增长，严格地说，大概是 O((\dfrac{1+\sqrt{5}}{2})^n)。所以复杂度就在 O(\log \sum a) 左右，又因为 \sum a\le10^9，这个计算量就非常小了。

加上我们还要在主席树上查询，总的时间复杂度是 O(m\log n\log(\sum a))。

似乎还可以用 ST 表更高效简洁地实现，但是咕咕咕。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e6,inf=1ll<<30;

struct sgt{
    ll l,r,dat;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
}tree[N*4+5];

ll n,tmp,amt,tot,l,r,ans,res,m;

ll uq[N+5],a[N+5],rt[N+5];

ll build(ll l,ll r) {
    ll p=++tot;
    if(l==r) return p;
    ll mid=(l+r)>>1;
    l(p)=build(l,mid);r(p)=build(mid+1,r);
    return p;
}

ll ins(ll cur,ll l,ll r,ll loc) {
    ll p=++tot;
    tree[p]=tree[cur];
    if(l==r) {dat(p)+=uq[loc];return p;}
    ll mid=(l+r)>>1;
    if(loc<=mid) l(p)=ins(l(cur),l,mid,loc);
    else r(p)=ins(r(cur),mid+1,r,loc);
    dat(p)=dat(l(p))+dat(r(p));
    return p;
}

ll query(ll p,ll q,ll l,ll r,ll L,ll R) {
    if(L<=l&&R>=r) return dat(p)-dat(q);
    ll mid=(l+r)>>1,ret=0;
    if(L<=mid) ret+=query(l(p),l(q),l,mid,L,R);
    if(R>mid) ret+=query(r(p),r(q),mid+1,r,L,R);
    return ret;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();uq[++amt]=a[i];
    }

    uq[++amt]=inf;
    sort(uq+1,uq+amt+1);
    amt=unique(uq+1,uq+amt+1)-uq-1;

    rt[0]=build(1,amt);

    for(ll i=1;i<=n;i++) {
        a[i]=lower_bound(uq+1,uq+amt+1,a[i])-uq;
        rt[i]=ins(rt[i-1],1,amt,a[i]);
    }

    m=read();

    for(ll i=1;i<=m;i++) {
        l=read();r=read();
        ans=0;tmp=-1;
        while(1) {
            res=query(rt[r],rt[l-1],1,amt,upper_bound(uq+1,uq+amt+1,tmp+1)-uq,upper_bound(uq+1,uq+amt+1,ans+1)-uq-1);
            if(res>0) {tmp=ans;ans=ans+res;}
            else break;
        }
        write(ans+1);putchar('\n');
    }

    return 0;
}