P13983 数列分块入门 8

_JF_ · 2025-09-09 15:08:33 · 题解

区间查询等于 x 数的数量，同时区间推平。

就是这个“同时”，太厉害了。

我好像只会一个 n\sqrt n \log n 的/xk。

正解是，对于每个块，我们维护块内的数是否相同，如果不同，我们暴力统计，如果相同我们直接判断。

这样为什么能保证时间复杂度呢。因为一个块查询的次数 \le 一个块内的数是不同的次数 \le n。

所以总的时间复杂度是 O(n \sqrt n)。

#include<bits/stdc++.h>
using namespace std;
const int N =3e5+10;
#define int long long 
int l[N],r[N],pos[N],lzy[N],n,tot,a[N];
void Devide(){
    int len=sqrt(n),tot=n/len;
    if(len*len!=n)  tot++;
    for(int i=1;i<=tot;i++) l[i]=(i-1)*len+1,r[i]=l[i]+len-1;
    r[tot]=n;
    for(int i=1;i<=tot;i++){
        bool f=true; int lst=a[l[i]];
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i; if(a[j]!=lst) f=false;
        }
        if(f==false)    lzy[i]=LLONG_MAX;
        else    lzy[i]=lst;
    }
}
void update(int L,int R,int c){
    bool f=true;
    if(pos[L]==pos[R]){
        for(int i=L;i<=R;i++)   a[i]=c;
        for(int i=l[pos[L]];i<=r[pos[L]];i++)   if(a[i]!=c) f=false;
        if(f)   lzy[pos[L]]=c; else lzy[pos[L]]=LLONG_MAX;
        return ;
    }

    for(int i=L;i<=r[pos[L]];i++)   a[i]=c;
    f=true;
    for(int i=l[pos[L]];i<=r[pos[L]];i++)   if(a[i]!=c) f=false;
    if(f)   lzy[pos[L]]=c; else lzy[pos[L]]=LLONG_MAX;

    for(int i=l[pos[R]];i<=R;i++)   a[i]=c;
    f=true;
    for(int i=l[pos[R]];i<=r[pos[R]];i++)   if(a[i]!=c) f=false;
    if(f)   lzy[pos[R]]=c; else lzy[pos[R]]=LLONG_MAX;

    for(int i=pos[L]+1;i<=pos[R]-1;i++) lzy[i]=c;
}
int Query(int L,int R,int c){
    int Num=0;
    if(pos[L]==pos[R]){
        if(lzy[pos[L]]!=LLONG_MAX){
            for(int i=l[pos[L]];i<=r[pos[L]];i++)   a[i]=lzy[pos[L]];
        }
        for(int i=L;i<=R;i++)   if(a[i]==c) Num++;

        return Num;
    }
    if(lzy[pos[L]]!=LLONG_MAX){
        for(int i=l[pos[L]];i<=r[pos[L]];i++)   a[i]=lzy[pos[L]];
    }
    for(int i=L;i<=r[pos[L]];i++)   if(a[i]==c) Num++;

    if(lzy[pos[R]]!=LLONG_MAX){
        for(int i=l[pos[R]];i<=r[pos[R]];i++)   a[i]=lzy[pos[R]];
    }
    for(int i=l[pos[R]];i<=R;i++)   if(a[i]==c) Num++;
    for(int i=pos[L]+1;i<=pos[R]-1;i++){
        if(lzy[i]==LLONG_MAX){
            for(int j=l[i];j<=r[i];j++) if(a[j]==c) Num++;
        }
        else{
            if(lzy[i]==c)   Num+=(r[i]-l[i]+1);
        }
    }
    return Num;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i];
    Devide();
    for(int i=1,L,R,c;i<=n;i++){
        cin>>L>>R>>c;
        cout<<Query(L,R,c)<<endl;
        update(L,R,c);
    }
    return 0;
}