[集训队互测 2018] 完美的队列 题解

· · 题解

发现时限这么大，考虑根号。题目相当于是对于每一个询问，你需要求出往后添加多少个询问之后有每个点的 cnt 数组对应位置超过 a。可以直接序列分块，劈成一段一段后所有答案直接取个 \max 就是原答案。

整块的话考虑离线处理出所有位置的答案，这个答案明显是有单调性的所以可以双指针。直接用线段树比较憨，发现你可以直接用分块的结构，散块的修改暴力做，整块修改直接打标记。

散块考虑对每个位置扫描线，发现是让我们支持加入删除和查询第 k 大，树状树组可以直接做到 O(n\sqrt{n\log n})。

但是插入删除第 k 大这玩意也是可以根号平衡的，具体地我们再维护一个数组 mp 表示第 i 大的数位于哪个块内，发现插入和删除对于这个数组的影响都是 O(\sqrt n) 的，然后再对每个块维护第 k 大的数具体是哪个，这个数组可以暴力重构，于是就做到了 O(n\sqrt n)，空间离线一些东西当然可以做到 O(n)。

#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;
int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=100003,B=320;
int n,m,sq,bn;
int ql[N],qr[N];
vector<int> vec[N],ui[N],ud[N],qi[N],qd[N];
int bel[N],res[N],ans[N];
int a[N],lb[B],rb[B];
int ccbase[N<<1],*cc=ccbase+N,arr[N];
namespace Block{
    int bid[N],mp[N];
    int cnt[B],pre[N];
    int f[B][B],msq;
    int mlb[N],mrb[N];
    inline void init(){
        msq=ceil(sqrt(m));
        for(int i=1;i<=m;++i) bid[i]=(i-1)/msq+1;
        for(int i=1;i<=bid[m];++i){
            mlb[i]=(i-1)*msq+1;
            mrb[i]=i*msq;
        }
        mrb[bid[m]]=m;
    }
    inline void inc(int x){
        int xx=bid[x];
        for(int i=x;i<=mrb[xx];++i) ++pre[i];
        for(int i=mrb[xx];i>=mlb[xx];--i) f[xx][pre[i]]=i;
        for(int i=bid[m];i>=xx;--i) mp[++cnt[i]]=i;
    }
    inline void dec(int x){
        int xx=bid[x];
        for(int i=x;i<=mrb[xx];++i) --pre[i];
        for(int i=mrb[xx];i>=mlb[xx];--i) f[xx][pre[i]]=i;
        for(int i=xx;i<=bid[m];++i) mp[cnt[i]--]=i+1;
        mp[cnt[bid[m]]+1]=0;
    }
    inline int qry(int x){return cnt[bid[x]-1]+pre[x];}
    inline int jump(int x){
        if(x>=N) return m+1;
        if(!mp[x]) return m+1;
        int xx=mp[x];
        x-=cnt[xx-1];
        return f[xx][x];
    }
}
bool exi[N];
int s[N],tp;
int ss[N],stp;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    sq=ceil(sqrt(n));
    for(int i=1;i<=n;++i) bel[i]=(i-1)/sq+1;
    bn=bel[n];
    for(int i=1;i<=bn;++i) lb[i]=(i-1)*sq+1,rb[i]=i*sq;
    rb[bn]=n;
    for(int i=1;i<=m;++i){
        ql[i]=read();qr[i]=read();
        vec[read()].emplace_back(i);
        res[i]=i;
    }
    for(int x=1;x<=bn;++x){
        int tag=0,mn=0x3f3f3f3f;
        for(int i=lb[x];i<=rb[x];++i){
            ++cc[arr[i]=-a[i]];
            if(mn>arr[i]) mn=arr[i];
        }
        for(int i=1,j=0;i<=m;++i){
            while(j<=m&&tag+mn<=0){
                if(++j>m) break;
                if(ql[j]<=lb[x]&&rb[x]<=qr[j]) ++tag;
                else{
                    int l=max(lb[x],ql[j]),r=min(rb[x],qr[j]);
                    for(int t=l;t<=r;++t){
                        --cc[arr[t]];
                        ++cc[++arr[t]];
                    }
                    if(!cc[mn]) ++mn;
                }
            }
            if(ql[i]<=lb[x]&&rb[x]<=qr[i]){
                --tag;
                if(res[i]<j) res[i]=j-1;
            }
            else{
                int l=max(lb[x],ql[i]),r=min(rb[x],qr[i]);
                for(int t=l;t<=r;++t){
                    --cc[arr[t]];
                    ++cc[--arr[t]];
                }
                if(cc[mn-1]) --mn;
            }
        }
        for(int i=lb[x];i<=rb[x];++i) --cc[arr[i]=-a[i]];
    }
    for(int i=1;i<=m;++i){
        int l=ql[i],r=qr[i];
        ui[l].emplace_back(i);
        ud[r+1].emplace_back(i);
        if(bel[r]-bel[l]<=1){
            qi[l].emplace_back(i);
            qd[r+1].emplace_back(i);
        }
        else{
            qi[l].emplace_back(i);
            qd[rb[bel[l]]+1].emplace_back(i);
            qi[lb[bel[r]]].emplace_back(i);
            qd[r+1].emplace_back(i);
        }
    }
    Block::init();
    for(int ps=1;ps<=n;++ps){
        for(int x:qd[ps]) exi[x]=0;
        for(int i=1;i<=tp;++i) if(exi[s[i]]) ss[++stp]=s[i];
        tp=stp;stp=0;
        for(int i=1;i<=tp;++i) s[i]=ss[i];
        for(int x:qi[ps]) exi[x]=1,s[++tp]=x;
        for(int x:ui[ps]) Block::inc(x);
        for(int x:ud[ps]) Block::dec(x);
        for(int i=1;i<=tp;++i){
            int x=s[i];
            int cur=Block::jump(Block::qry(x)+a[ps]);
            if(cur>res[x]) res[x]=cur-1;
        }
    }
    for(int i=0;i<N;++i){
        int mx=0;
        for(int x:vec[i]){
            int l=x,r=res[x];
            if(mx>=l) l=mx+1;
            if(l<=r){++ans[l];--ans[r+1];}
            if(r>mx) mx=r;
        }
    }
    for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

但是这个题似乎并不能规约到一些经典根号题，所以说我们可以去思考一下 \text{polylog} 咋做。我们分块做法散块的根号平衡看起来做得很不优美，所以我们考虑只将整块的做法扩展到 \text{polylog}。我们改为用线段树划分整个区间，每个询问在 O(\log) 个节点处被处理，每个节点处理的询问答案同样具有单调性。我们依旧考虑在每个线段树节点上双指针。

但是会影响到某个线段树节点的修改看起来很多？考虑我们刚才分块是怎么优化的：注意绝大部分修改都是整块修改，于是直接打标记。线段树同样有这个性质，除开完全包含某个区间的修改，剩下的与该区间有交的修改的量级是 O(n\log n) 的。考虑线段树每次区间操作只会访问 O(\log) 个节点所以这个性质是显然的。

完全包含某个区间的修改的贡献我们可以拿个数据结构（比如树状数组）维护出每次修改的时间。我们发现我们只需要直接从父亲继承这些修改，每次继承之后的变化量之和是 O(n\log n) 的，所以我们需要按 dfs 序处理这些区间并且动态维护这个树状数组就行了。

剩下的就和分块差不多，直接对与该区间有交的修改双指针。整块修改的贡献就从树状数组里查一下。求答案时就在树状数组上倍增一下。时间复杂度 O(n\log^2 n)。在本题的数据范围下不如单根号快。

#include <cstdio>
#include <vector>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=100003;
int n,m;
int ql[N],qr[N],res[N];
vector<int> vec[N];
int ans[N],a[N];
vector<int> qry[N<<2],upd[N<<2];
void hang(int x,int p=1,int l=1,int r=n){
    if(ql[x]<=l&&r<=qr[x]){
        qry[p].emplace_back(x);
        return;
    }
    upd[p].emplace_back(x);
    int mid=(l+r)>>1;
    if(ql[x]<=mid) hang(x,lc,l,mid);
    if(qr[x]>mid) hang(x,rc,mid+1,r);
}
int mn[N<<2],tg[N<<2];
inline void proc(int p,int v){mn[p]+=v;tg[p]+=v;}
inline void pushdown(int p){
    if(tg[p]){
        proc(lc,tg[p]);
        proc(rc,tg[p]);
        tg[p]=0;
    }
}
void build(int p,int l,int r){
    tg[p]=0;
    if(l==r){mn[p]=-a[l];return;}
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    mn[p]=min(mn[lc],mn[rc]);
}
void update(int x,int v,int p,int l,int r){
    if(ql[x]<=l&&r<=qr[x]) return proc(p,v);
    pushdown(p);
    int mid=(l+r)>>1;
    if(ql[x]<=mid) update(x,v,lc,l,mid);
    if(qr[x]>mid) update(x,v,rc,mid+1,r);
    mn[p]=min(mn[lc],mn[rc]);
}
int tr[N];
inline void mdf(int x,int v){for(int i=x;i<=m;i+=(i&-i)) tr[i]+=v;}
inline int ask(int x){
    int res=0;
    for(int i=x;i;i^=(i&-i)) res+=tr[i];
    return res;
}
inline int jump(int v){
    if(!v) return 0;
    int x=0;
    for(int i=16;~i;--i)
        if(x+(1<<i)<=m&&tr[x+(1<<i)]<v) v-=tr[x+=(1<<i)];
    return x+1;
}
void dfs(int p=1,int l=1,int r=n){
    build(p,l,r);
    for(int x:qry[p]) mdf(x,1);
    int len=upd[p].size(),t=0,o=0;
    for(int x:qry[p]){
        int cur=ask(x);
        while(o<len&&upd[p][o]<x) update(upd[p][o++],-1,p,l,r);
        while(t<len&&ask(upd[p][t])-cur+mn[p]<0) update(upd[p][t++],1,p,l,r);
        int pos=jump(cur-mn[p])-1;
        if(t&&pos<upd[p][t-1]) pos=upd[p][t-1]-1;
        if(pos>res[x]) res[x]=pos;
    }
    if(l<r){
        int mid=(l+r)>>1;
        dfs(lc,l,mid);
        dfs(rc,mid+1,r);
    }
    for(int x:qry[p]) mdf(x,-1);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i){
        ql[i]=read();qr[i]=read();
        vec[read()].emplace_back(i);
        res[i]=i;hang(i);
    }
    dfs();
    for(int i=0;i<N;++i){
        int mx=0;
        for(int x:vec[i]){
            int l=x,r=res[x];
            if(mx>=l) l=mx+1;
            if(l<=r){++ans[l];--ans[r+1];}
            if(r>mx) mx=r;
        }
    }
    for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}