题解：P5386 [Cnoi2019] 数字游戏

· · 题解

感谢@ljy05提供 n\sqrt{n}\log_2(n) 思路并参与讨论（人太菜不能一个人切黑）。

正文

step1

对于每一个询问 l,r,x,y 我们可以把 (l,r) 这一段区间内符合 x \le \pi_i \le y 的看做 1，反之为0。

那么就有 n\times q 做法，统计区间内每一段连续 1 长度为 len，ans=ans+{{len\times(len+1)}\over{2}}，扫过去求解即可（貌似常数小可以卡过子任务一？）。

时间 O(nq)。

step2

也就是 @ljy05 提出的思路。

一看区间查询、不修改、不强制在线，简单莫队启动！因为是双区间，我们要考虑莫队哪一个区间，但是我们发现如果莫队数组区间，无论是修改还是查询都不好搞的样子，于是考虑莫队值域区间。

当你开始莫队值域区间时，你就会发现豁然开朗。

因为 \pi 是排列，所以在莫队移动区间时，映射修改原数组就很方便。具体修改就这样：我们把值为 i 的数在 \pi 中的位置记为 A_i。在移动区间时，如果加入 i 就把标记数组 vis 的 vis_{A_i} 设为 true ，退出 i 时就把 vis_{A_i} 设为 false。

那现在问题转化为，如何快速单点修改，区间查询。

很容易想到线段树，于是就有了一个 O(q\sqrt {n}\log_2(n)) 的做法，具体维护的话就是每个树节点维护 llen,rlen,ans 即左边、右边连续 1 长度与该区间的答案，在更新与查询时注意边界与整块都是 1 的情况即可。

时间 O(q\sqrt{n}\log_2(n))。

step3

学过莫队的都知道 O(q\sqrt{n}\log_2(n)) 有可能被卡甚至不是正确复杂度，所以我们要优化。而莫队的优化方式大多是通过牺牲询问时间来把修改时间降低（多半是降至 O(1)）。

因为莫队的修改次数为 O(q\sqrt{n}) 而询问次数为 q。而分块通常就是一个很好的选择。

如何维护呢？我这里提出一种只加入不删除的做法（我太懒了，直接把回滚套上去就不想想删除了）。对于每一个下标维护 L,R,vis，对每一个块维护 llen,rlen,ans。L,R 指每一个位置在块中所在 1 区间的左边界、右边界，vis 指该位置是否是 1。llen,rlen,ans 与上文线段树中提到的差不多。

修改时看是否会与其他区间合并，如果可以就更新新区间的 L,R 以及所在块的 ans，如果新区间接触块的左区间或右区间，就更新块内的 llen,rlen。

统计答案时散块整块查就是了，注意块与块间 llen,rlen 衔接与整块都是 1 的情况即可。

时间 O(q\sqrt{n})。

代码

#include<bits/stdc++.h>
#define pl pair<int,int>
#define ll long long
using namespace std;

const int N=2e5+5,M=450;
//k,L,R,vis
int n,m,s,t,k,A[N],id[N];
int L[N],R[N];
ll ans[N];
bool vis[N];
struct nnd {
    int l,lk,r,x,y,idx;
}q[N];
//ls,rs,ans
struct node {
    int l,ls,r,rs,len;
    ll ans;
}D[M];
struct mmb {
    int x,it,lb,rb,L,R,ls,rs;
    ll ans;
}c[N<<1];
inline bool pai(const nnd& x,const nnd& y){
    return (x.lk^y.lk)?(x.lk<y.lk):(x.r<y.r);
}
inline void change(const int& x,const bool& dis){
    vis[x]=1;
    const int it=id[x],l=D[it].l,r=D[it].r;
    const int lb=((x^l)&&vis[x-1])?(L[x-1]):(x);
    const int rb=((x^r)&&vis[x+1])?(R[x+1]):(x);
    if(dis)c[++k]={x,it,lb,rb,L[rb],R[lb],D[it].ls,D[it].rs,D[it].ans};
    D[it].ans-=(ll)(x-lb)*(x-lb+1)/2+(ll)(rb-x)*(rb-x+1)/2;
    R[lb]=rb,L[rb]=lb;
    D[it].ans+=(rb-lb+1)*(rb-lb+2)/2;
    if(lb==l)D[it].ls=rb-lb+1;
    if(rb==r)D[it].rs=rb-lb+1;
}
void cle(){
    k=0;
    for(int i=1;i<=t;i++)
        D[i].ans=D[i].ls=D[i].rs=0;
    for(int i=1;i<=n;i++)
        L[i]=R[i]=vis[i]=0;
}
void ret(){
    for(;k;k--){
        const mmb p=c[k];
        vis[p.x]=0;
        L[p.rb]=p.L;
        R[p.lb]=p.R;
        D[p.it].ls=p.ls;
        D[p.it].rs=p.rs;
        D[p.it].ans=p.ans;
    }
}
inline ll get_ans(const int& l,const int& r){
    const int st=id[l],ed=id[r];
    ll ans=0,sum=0;
    if(st==ed){
        for(int j=l;j<=r;j++){
            if(vis[j]){
                sum++;
                if(j==r||!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
            }
        }
    } else {
        for(int j=l;j<=D[st].r;j++){
            if(vis[j]){
                sum++;
                if(!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
            }
        }
        for(int j=st+1;j<ed;j++){
            const ll l=D[j].ls,r=D[j].rs;
            if(D[j].len==l)
                sum+=l;
            else {
                sum+=l;
                ans+=sum*(sum+1)/2;
                sum=r;
                ans+=D[j].ans-l*(l+1)/2-r*(r+1)/2;
            }
        }
        if(!vis[D[ed].l]){
            ans+=sum*(sum+1)/2;
            sum=0;
        }
        for(int j=D[ed].l;j<=r;j++){
            if(vis[j]){
                sum++;
                if(j==r||!vis[j+1])ans+=sum*(sum+1)/2,sum=0;
            }
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    s=sqrt(n),t=(n-1)/s+1;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        A[x]=i,id[i]=(i-1)/s+1;
    }
    for(int i=1,l,r;i<=t;i++){
        l=(i-1)*s+1,r=min(i*s,n);
        D[i]=(node){l,0,r,0,r-l+1,0};
    }
    for(int i=1,l,r,x,y;i<=m;i++){
        cin>>x>>y>>l>>r;
        q[i]=(nnd){l,id[l],r,x,y,i};
    }
    sort(q+1,q+m+1,pai);    
    for(int i=1,r,R;i<=m;i++){
        r=q[i].lk*s;
        if(q[i].lk^q[i-1].lk)cle(),R=r;
        for(;R<q[i].r;)change(A[++R],0);
        for(int j=min(q[i].r,r);j>=q[i].l;)
            change(A[j--],1);
        ans[q[i].idx]=get_ans(q[i].x,q[i].y);
        ret();
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

码风超抽估计也没入看得懂。