题解：P13983 数列分块入门 8

· · 题解

#6284. 数列分块入门 8 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。

技巧

设一个标记 tag 表示这个块被整体设的值，如果这个块被当成散块修改，那么就把这个标记暴力地打下去。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，加入一开始把 [1,n] 都设成一个值，那么进行一个区间操作最多破坏首尾 2 个块的标记，所以只能使后面的询问至多多 2 个块的暴力时间，所以均摊每次操作复杂度是 T。最优块长为 \sqrt{n}。

注：这题可以用珂朵莉树做。

代码
#include<bits/stdc++.h>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=5e5+5,M=555;
const LL Inf=1e18;
int n,a[N],T,tot,be[M],en[M],bel[N];
LL tag[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        tag[i]=Inf;
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
}
int cover(int l,int r,int val){
    int res=0;
    if(tag[bel[l]]==Inf){
        for(int i=l;i<=r;i++){
            if(a[i]==val) res++;
            a[i]=val;
        }
    }else if(tag[bel[l]]==val){
        res=r-l+1;
    }else{
        for(int i=be[bel[l]];i<=en[bel[r]];i++){
            if(l<=i&&i<=r) a[i]=val;
            else a[i]=tag[bel[l]];
        }
        tag[bel[l]]=Inf;
    }
    return res;
}
int work(int l,int r,int val){
    if(bel[l]==bel[r]){
        return cover(l,r,val);
    }
    int res=cover(l,en[bel[l]],val)+cover(be[bel[r]],r,val);
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        if(tag[i]==Inf){
            for(int j=be[i];j<=en[i];j++){
                if(a[j]==val) res++;
            }
        }else if(tag[i]==val){
            res+=en[i]-be[i]+1;
        }
        tag[i]=val;
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,l,r,c;i<=n;i++){
        cin>>l>>r>>c;
        cout<<work(l,r,c)<<"\n";
    }
    return 0;
}
拓展

如果修改和查询操作分开呢？就无法均摊了。这就是 Paint The Wall - HDU 4391。

设 col_{i,x} 表示块 i 内颜色 x 的数量，标记 tag_i 表示块 i 内的数都被赋值成的数。修改散块下传标记后暴力、整块打标记（这里需要修改 col）；查询散块暴力、整块先看有没有 tag，再看 col。

这里空间不够用，就把 col 开成 map。

const int N=1e5+5,M=320;
int n,m,a[N],T,tot,be[M],en[M],bel[N],tag[M];
map<int,int>col[M];

void init(){
    T=tot=sqrt(n);
    for(int i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(int i=1;i<=tot;i++){
        tag[i]=-1;
        for(int j=be[i];j<=en[i];j++){
            bel[j]=i,col[i][a[j]]++;
        }
    }
}
void pushdown(int bel){
    if(tag[bel]==-1) return;
    for(int i=be[bel];i<=en[bel];i++){
        a[i]=tag[bel];
    }
    tag[bel]=-1;
}
void cover(int l,int r,int val){
    if(~tag[bel[l]]) pushdown(bel[l]);
    for(int i=l;i<=r;i++){
        col[bel[l]][a[i]]--,a[i]=val,col[bel[l]][a[i]]++;
    }
}
int get(int l,int r,int val){
    if(~tag[bel[l]]) pushdown(bel[l]);
    int res=0;
    for(int i=l;i<=r;i++){
        if(a[i]==val){
            res++;
        }
    }
    return res;
}
void update(int l,int r,int val){
    if(bel[l]==bel[r]){
        cover(l,r,val);
        return;
    }
    cover(l,en[bel[l]],val),cover(be[bel[r]],r,val);
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        col[i].clear();
        col[i][val]=en[i]-be[i]+1;
        tag[i]=val;
    }
}
LL query(int l,int r,int val){
    if(bel[l]==bel[r]){
        return get(l,r,val);
    }
    LL res=get(l,en[bel[l]],val)+get(be[bel[r]],r,val);
    for(int i=bel[l]+1;i<=bel[r]-1;i++){
        if(col[i].find(val)!=col[i].end()) res+=col[i][val];
    }
    return res;
}

signed main(){
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        init();
        for(int i=1,op,l,r,z;i<=m;i++){
            cin>>op>>l>>r>>z;
            l++,r++;
            if(op==1){
                update(l,r,z);
            }else{
                cout<<query(l,r,z)<<"\n";
            }
        }
        for(int i=1;i<=tot;i++){
            col[i].clear();
        }
    }
    return 0;
}