题解：P13983 数列分块入门 8

zhoujiefu · 2025-09-07 15:53:24 · 题解

做法

对于每一个块，开一个桶记录某个值出现的数量。对于修改操作，散块直接下放标记暴力修改，整块直接打 tag。查询时，散块直接下放标记暴力修改，整块直接查询 tag，如果有 tag 说明这一段已经被覆盖了，否则直接查询桶数组里的值。下放标记时，要定点清除桶数组，需要清空的值只有块内出现过的值。因为值域很大，所以要先离线下来离散化一下。时间复杂的 O(n\sqrt n)。

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=3e5+5,BB=700;
int n,tot;
int a[N],b[N<<1],tag[N/BB+3],L[N/BB+3],R[N/BB+3],bel[N];
short cnt[N/BB+3][N<<1];
struct Query{
    int l,r,c;
}q[N];
inline void pushdown(int i){
    if(!tag[i]) return;
    rep(j,L[i],R[i]) cnt[i][a[j]]=0,a[j]=tag[i];
    cnt[i][tag[i]]=R[i]-L[i]+1,tag[i]=0;
}
inline void update(int l,int r,int x){
    if(bel[l]==bel[r]){
        pushdown(bel[l]);
        rep(i,l,r) cnt[bel[i]][a[i]]--,cnt[bel[i]][x]++,a[i]=x;
        return;
    }
    pushdown(bel[l]),pushdown(bel[r]);
    rep(i,l,R[bel[l]]) cnt[bel[i]][a[i]]--,cnt[bel[i]][x]++,a[i]=x;
    rep(i,L[bel[r]],r) cnt[bel[i]][a[i]]--,cnt[bel[i]][x]++,a[i]=x;
    rep(i,bel[l]+1,bel[r]-1) tag[i]=x;
}
inline int query(int l,int r,int x){
    int ans=0;
    if(bel[l]==bel[r]){
        pushdown(bel[l]);
        rep(i,l,r) ans+=(a[i]==x);
        return ans;
    }
    pushdown(bel[l]),pushdown(bel[r]);
    rep(i,l,R[bel[l]]) ans+=(a[i]==x);
    rep(i,L[bel[r]],r) ans+=(a[i]==x);
    rep(i,bel[l]+1,bel[r]-1){
        if(!tag[i]) ans+=cnt[i][x];
        else if(tag[i]==x) ans+=(R[i]-L[i]+1);
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rep(i,1,n) cin>>a[i],b[++tot]=a[i],bel[i]=i/BB;
    rep(i,1,n){
        cin>>q[i].l>>q[i].r>>q[i].c;
        b[++tot]=q[i].c;
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    rep(i,1,n) a[i]=lower_bound(b+1,b+tot+1,a[i])-b,q[i].c=lower_bound(b+1,b+tot+1,q[i].c)-b,cnt[bel[i]][a[i]]++;
    rep(i,1,n) if(!L[bel[i]]) L[bel[i]]=i;
    for(int i=n;i>=1;--i) if(!R[bel[i]]) R[bel[i]]=i;
    rep(i,1,n){
        cout<<query(q[i].l,q[i].r,q[i].c)<<'\n';
        update(q[i].l,q[i].r,q[i].c);
    }
    return 0;
}