P5386题解

· · 题解

这题和第十分块神似。

题目大意

在指定区间内有多少子区间的值域在 [x,y] 内。

思路

这题我就讲讲怎样用回滚莫队做，具体维护方法请参考我的第十分块的题解。

这题也不好像第十分块一样将查询的值域排序（因为有 y 当上限），所以我们考虑在值域上用回滚莫队，即在值域上分块。这题有个非常妙的地方就是 a 序列是 1 到 n 的序列，所以值域分块可以和序列分块混在一起。题打 O(1) 修改，O(\sqrt n)查询的分块，这样时间复杂度就可以降到 O(n\sqrt n)，我看出题人将时间跳的这么高就是为了适应 O(n\sqrt n \log n) 的时间复杂度，所以也就不用像第十分块一样大力卡常了 qwq。

给给代码吧。

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005,sn=1505;
int n,m,s,l=1,r,a[maxn],idx[maxn],L[sn],R[sn],head[maxn],nxt[maxn],to[maxn],cnt,block;
int pos[maxn],sum[sn],top;
bool flag[maxn];
long long ans[maxn],gx[maxn];
struct query{
    int l,r,x,y,id;
}p[maxn];
struct node{
    int ll,lr,rr,rl,x;
    bool type;
    long long val;
}sta[maxn],tmp;
bool cmp(query x,query y){
    return idx[x.x]==idx[y.x]?x.y<y.y:x.x<y.x;
}
void add(int u,int v){
    nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v;
}
void modify(int x,bool type){
    pos[x]=x,flag[x]=1,tmp.x=x;
    int last=x-1,next=x+1,Tmp=pos[last];
    bool flag1=(flag[last]&&L[idx[x]]!=x),flag2=(flag[next]&&R[idx[x]]!=x);
    if(!flag1&&!flag2) tmp.type=tmp.ll=tmp.rr=tmp.lr=tmp.rl=0,tmp.val=1;
    else{
        tmp.type=1;
        if(flag1&&flag2) {
            tmp.val=(next-pos[last])*(pos[next]-last);
            tmp.ll=pos[last],tmp.lr=last,pos[pos[last]]=pos[next];
            tmp.rr=pos[next],tmp.rl=next,pos[pos[next]]=Tmp;
        }else{
            if(flag1){
                tmp.val=next-pos[last];
                tmp.ll=x,tmp.lr=x,pos[x]=pos[last];
                tmp.rr=pos[last],tmp.rl=last,pos[pos[last]]=x;
            }else{
                tmp.val=pos[next]-last;
                tmp.ll=x,tmp.lr=pos[x],pos[x]=pos[next]; 
                tmp.rr=pos[next],tmp.rl=next,pos[pos[next]]=x;
            }
        }
    }
    sum[idx[x]]+=tmp.val;
    if(type) sta[++top]=tmp;
}
long long Q(int l,int r){
    long long tot=0,len=0;
    if(idx[l]==idx[r]){
        for(int i=l;i<=r;++i){
            if(flag[i]) ++len;
            else tot+=gx[len],len=0;
        }
        return tot+gx[len];
    }
    for(int i=l;i<=R[idx[l]];++i){
        if(flag[i]) ++len;
        else tot+=gx[len],len=0;
    }
    for(int i=idx[l]+1;i<idx[r];++i){
        if(pos[L[i]]==R[i]) len+=R[i]-L[i]+1;
        else{
            if(flag[L[i]]) len+=pos[L[i]]-L[i]+1,tot-=gx[pos[L[i]]-L[i]+1];
            tot+=gx[len]+sum[i],len=0;
            if(flag[R[i]]) len+=R[i]-pos[R[i]]+1,tot-=gx[R[i]-pos[R[i]]+1];
        }
    }
    for(int i=L[idx[r]];i<=r;++i){
        if(flag[i]) ++len;
        else tot+=gx[len],len=0;
    }
    return tot+gx[len];
}
int main() {
    scanf("%d%d",&n,&m);
    s=sqrt(n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        add(a[i],i);
        idx[i]=(i+s-1)/s,gx[i]=1ll*i*(i+1)/2;
        if(idx[i]!=idx[i-1]){
            R[idx[i-1]]=i-1;
            L[idx[i]]=i;
        }
    }
    R[idx[n]]=n;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&p[i].l,&p[i].r,&p[i].x,&p[i].y);
        p[i].id=i;
    }
    sort(p+1,p+m+1,cmp);
    block=0;
    for(int i=1;i<=m;++i){
        if(idx[p[i].x]==idx[p[i].y]){
            memset(flag,0,sizeof(flag));
            memset(sum,0,sizeof(sum));
            memset(pos,0,sizeof(pos));
            for(int j=p[i].x;j<=p[i].y;++j) for(int k=head[j];k;k=nxt[k]) modify(to[k],0);
            ans[p[i].id]=Q(p[i].l,p[i].r);
            continue;
        }
        l=R[idx[p[i].x]];
        if(idx[p[i].x]!=block){
            memset(flag,0,sizeof(flag));
            memset(sum,0,sizeof(sum));
            memset(pos,0,sizeof(pos));
            r=l-1,block=idx[p[i].x];
        }
        while(r<p[i].y) for(int j=head[++r];j;j=nxt[j]) modify(to[j],0);
        while(l>p[i].x) for(int j=head[--l];j;j=nxt[j]) modify(to[j],1);
        ans[p[i].id]=Q(p[i].l,p[i].r);
        while(top){ 
            tmp=sta[top--],sum[idx[tmp.x]]-=tmp.val,flag[tmp.x]=0;
            if(tmp.type) pos[tmp.rr]=tmp.rl,pos[tmp.ll]=tmp.lr;
        }
    }
    for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}