从区间数颜色到二维分块

xfrvq · 2022-05-04 12:18:01 · 个人记录

区间数颜色

原题 \to \texttt{P1972 [SDOI2009] HH的项链}。

题意：区间数的种类数（即区间数颜色）。

解法：对每个位置，维护上一个和它颜色相同的位置，记为 pre。

对这个图，我们维护的 pre 为 \{0,0,1,0,3,2\}。

然后你发现，如果区间 [l,r] 中一个颜色的 pre_i\lt l，那么这是这个颜色第一次出现的位置。而区间的颜色总数，就是区间的所有第一次出现的位置的个数和。

于是问题简化为区间小于等于 x 的数的个数。

单点修改区间数颜色

原题 \to \texttt{P1903 [国家集训队] 数颜色 / 维护队列}。

题意略。

解法：考虑一次修改会影响哪些 pre。

这里我们修改了 \tt 3 号节点的颜色为黄色（为了辅助，维护一个 nxt 代表下一个和它颜色相同的位置）。

于是一次修改只会影响三个位置。

考虑怎么动态求一个节点修改后的 pre：维护 n 个 set，记录每个值所有出现的位置，然后在里面 lower_bound，然后回到上一个位置，就是答案了。修改你直接在 set 里面插入删除就行了。

区间修改区间数颜色

原题 \to \texttt{P4690 [Ynoi2016] 镜中的昆虫}。

乍一看，直接弃掉，这个东西没法做了。

但是你注意到一个性质：如果本来有一个区间 [l,r] 颜色相同，我们要把它整体改成另一个颜色，那么只有 prv_l 会发生改变（同样要变的还有这个区间右端第一个同色点），prv_{l+1},\cdots,prv_r 保持不变，它们应该是 l,l+1,\cdots,r-1 的一个等差数列。

既然问题和区间推平有关，这个性质和 颜色相同的区间 有关，那么我们来考虑一个老朋友—— \tt ODT，然后我们 把所有颜色相同的区间看成一个点。

如果我们使用上述方法对一个点进行修改，那么复杂度是不是就正确了呢？考虑证明复杂度正确。

首先可知一开始 \tt ODT 内有 n 个点。
每次修改
1. 把 l 以及 r+1 所在节点断开，一分为二。这一步最坏增加两个节点。
2. 然后删去属于这个区间的所有节点
3. 然后增加一个节点 [l,r]。

注意到两点

每次操作最坏增加三个节点（第一步两个，第三步一个），总量是 O(m) 个。
第二步删去的节点总数是 O(n) 个。

于是所有修改的总数是 O(n+m)。

// P4689 [Ynoi2016] 镜中的昆虫
// 定义一个区间修改为大操作，将其分解为单点修改是小操作。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<set>
#include<vector>
#include<unordered_map>
#include<algorithm>

#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define Rep(i,a,b) for(int i = (a);i >= (b);--i)

int read(){ } // 快读
int max2(),min2(); // max/min加速

const int N = 1e5 + 5; // 开始的数组大小
const int M = 2e5 + 5; // 离散化后值域大小
const int _ = 5e5; // 拆成的小操作总数
const int S = sqrt(N) + 5; // 根号的大小

std::unordered_map<int,int> U; // 辅助离散化的map
int n,m,k,a[N]; // k 是离散化的值域，a 是原来的数组
int prv[N],tmp[M]; // 每个节点的 prv 值，以及辅助算 prv 的数组
int qo[N],ans[N]; // 每个操作的 op，离线后每个询问的答案。
int B,C,st[S],ed[S],V[N],bl[N]; // 分块辅助数组：块长、块数、每块的起点、终点、每个点的值，每个节点对应的块
int c1[S],c2[N]; // 算分块用的，是 O(sqrt) 单点修改 O(1) 查询的辅助数组
int T[M]; // 大修改操作要用的辅助数组（存下所有要修改的点）
int tt; // 拆成的小操作的总数

struct node{ // ODT 节点
    int l,r,v; // 左端点，右断电，值
    bool operator<(const node& p) const { return l < p.l; }
    // ODT 节点按左端点排序
};

std::set<node> s,t[M]; // ODT 与每个值的 ODT

// 因为我们要多次同时在两种 ODT 里面插入，删除一个数，所以可以考虑将其简化。

auto Ins(int l,int r,int x){ // 简化后的插入节点 (l,r,x)，返回其迭代器
    t[x].insert((node){l,r,x});
    return s.insert((node){l,r,x}).first;
}

void Ers(int l,int r,int x){ // 简化后的删除节点 (l,r,x)
    s.erase((node){l,r,x});
    t[x].erase((node){l,r,x});
}

auto split(int p){ // 经过了简化的split
    auto it = s.lower_bound((node){p,0,0});
    if(it != s.end() && it->l == p) return it;
    --it; auto[l,r,v] = *it; Ers(l,r,v);
    Ins(l,p - 1,v); return Ins(p,r,v);
}

struct PI{ // 所有操作
    int a,b,c;
    // 如果 c=0，代表是把 a 位置改成 b
    // 否则，代表第 c 个询问是区间 [a,b]
    PI(){ a = b = c = 0; }
    PI(int a,int b,int c) : a(a),b(b),c(c){}
} OPT[_]; // 操作序列

// 这个就是修改函数：我们把所有的小修改、询问按顺序记下来，然后分块
void chg(int x,int y){ OPT[++tt] = PI(x,y + 1,0); }

int pre(int x){ // 通过 s/t 来计算一个点的真正的 prev 值，在修改的最后改 prv 值部分会用到。
    node p = (node){x,0,0};
    auto it = --s.upper_bound(p);
    if(it->l < x) return x - 1;
    auto i = t[it->v].lower_bound(p);
    if(i != t[it->v].begin()) return (--i)->r;
    return 0;
}

void upd(int l,int r,int x){ // 区间推平
    auto ir = split(r + 1),il = split(l); int z = 0;
    for(auto it = il;it != ir;++it){
        T[++z] = it->l; // 记录下所有 ODT 节点的左端点
        auto i = t[it->v].upper_bound(*it);
        if(i != t[it->v].end()) T[++z] = i->l; // 把后面一个同色点也加进去（它也会被影响）
        t[it->v].erase(*it); // 在 t 里删除掉
    }
    s.erase(il,ir); /* 在 s 里删除掉 */ Ins(l,r,x); // 加回去
    rep(i,1,z) if(1 <= T[i] && T[i] <= n) chg(T[i],prv[T[i]] = pre(T[i])); // 最后统一修改
}

void upd(int x,int y){ // 值域分块-单点修改
    rep(i,bl[x],C) c1[i] += y;
    rep(i,x,ed[bl[x]]) c2[i] += y;
}

int qry(int x){ // 值域分块-前缀查询
    return c1[bl[x] - 1] + c2[x];
}

int main(){
    n = read(),m = read();
    rep(i,1,n){ a[i] = read(); if(!U.count(a[i])) U[a[i]] = ++k; a[i] = U[a[i]]; }
    rep(i,1,n) prv[i] = tmp[a[i]],tmp[a[i]] = i; // 计算 prv
    B = sqrt(n); C = (n - 1) / B + 1;
    rep(i,1,C){ // 计算块的辅助数组
        st[i] = (i - 1) * B + 1;
        ed[i] = i == C ? n : i * B;
        rep(j,st[i],ed[i]) bl[j] = i;
    }
    rep(j,1,n) Ins(j,j,a[j]);
    rep(i,1,m){ // 读入询问
        qo[i] = read(); int l = read(),r = read(),x;
        if(qo[i] == 1){
            x = read(); if(!U.count(x)) U[x] = ++k;
            x = U[x]; upd(l,r,x); // 直接修改
        } else OPT[++tt] = PI(l,r,i); // 询问也按顺序记录下来
    }
    memset(tmp,0,sizeof tmp);
    rep(i,1,n) V[i] = tmp[a[i]] + 1,tmp[a[i]] = i; // 这个 V 实际上永远等于 prv+1。+1是为了从 [0,n) 变成 [1,n]
    rep(i,1,C){ // 滚块
        memset(c1,0,sizeof c1); memset(c2,0,sizeof c2); // 辅助数组重置
        rep(j,st[i],ed[i]) upd(V[j],1); // 先加上这块的贡献
        rep(j,1,tt){
            auto[x,y,z] = OPT[j];
            if(z == 0){ // 修改操作
                if(x < st[i] || x > ed[i]) continue; // 修改不在这块，不管
                upd(V[x],-1); upd(V[x] = y,1); // 更改 V[x]，并同时在值域分块里改。
            } else {
                if(y < st[i] || ed[i] < x) continue; // 询问不包含这块，不管
                int l = max2(st[i],x),r = min2(ed[i],y);
                if(x <= st[i] && ed[i] <= y) ans[z] += qry(x); // 全部包含：使用 O(1) 的 qry
                else rep(j,l,r) ans[z] += V[j] <= x; // 部分包含：其实就是散块，暴力即可。
                // 注意因为你值域分块的值整体+1，所以应该是从询问 <x 的个数变成询问 <=x 的个数。
            }
        }
    }
    rep(i,1,m) if(qo[i] == 2) printf("%d\n",ans[i]); // 最后输出 ans 就行了
    return 0;
}

带权区间数颜色

首先，区间数颜色是可以转换为二维数点问题的，即视为有 n 个点 (i,pre_i)，然后我们要求 [l,r][0,l) 矩形里有几个点。

例题 \to \texttt{CF848C Goodbye Souvenir}。

题意：求区间每种颜色最后出现位置减去第一次出现位置之和。

考虑把这个贡献从每种颜色转化到每个位置。

方法是定义每个位置的贡献为 i-pre_i，当然要 pre_i_i\ge 询问左端点。

假如一个颜色所有出现的位置为 b_1,\cdots,b_k，那么总贡献为：

\begin{aligned} Sum&=(b_k-pre_{b_k})+\cdots+(b_2-pre_{b_2})\\ &=(b_k-b_{k-1})+\cdots+(b_2-b_1)\\ &=b_k-b_1 \end{aligned}

可以看出最后就是我们想求的。

转化完后，我们把这个问题换成一个二维数点的形式，即有 n 个点 (i,pre_i)，其权值为 i-pre_i。询问就相当于求 [l,r][l,n] 这一段的和。

这个东西很自然的可以用 \tt CDQ，\tt KDT，树套树等东西来做。但是有的时候需要平衡复杂度，我们就会使用这样一种东西——二维分块。

二维分块

二维分块功能：

O(1)-O(\sqrt n) 单点修改矩阵查询
O(1)-O(\sqrt n) 矩阵修改单点查询
O(1)-O(\sqrt n) 矩阵查询单点修改
O(1)-O(\sqrt n) 单点查询矩阵修改

二维分块需要利用到一种性质：所有 x 坐标互不相同，所有 y 坐标互不相同。

因为这个性质，二维分块不好出模板题（要出也很容易被其他 DS 艹过）。

举个例子，假设我们要加的是这么一个矩形（左下角是原点，右上角是询问点）。

为了方便，以下记 \mathbf a=n^{0.25},\mathbf b=n^{0.5},\mathbf c=n^{0.75}。

首先因为整块复杂度要保证，所以块数是 O(\sqrt n) 的，于是你就应该用 \bf c\times c 来分块，这样总块数就是 O(\mathbf{a\times a}=\sqrt n) 的。

但是我们整块复杂度保证，散块又不行了。于是考虑在现在的灰色部分分块用来辅助原来的散块，分出

现在总共分了 4 种块，对于每种块我们都维护块和。

现在来算一下复杂度。

对于红色块而言，它一定不超过 \sqrt n 个。
对于橙色块而言，它一行最多只有 n\div\mathbf c=n^{0.25} 个，一列最多只有 \mathbf{c\div b}=n^{0.25} 个，乘起来不超过 \sqrt n 个。
对于蓝色块而言，它一行最多只有 \mathbf{c\div b}=n^{0.25} 个，一列最多只有 n\div\mathbf c=n^{0.25} 个，乘起来不超过 \sqrt n 个。
对于绿色块而言，它一行/一列最多只有 \mathbf{c\div b}=n^{0.25} 个，乘起来也不超过 \sqrt n 个。

那散块如何做呢？

首先，散块本身的定义是：一个询问覆盖了一个点但没有完全覆盖这个点所在的 \bf b\times b 块，就是上图中的黄色部分。

上文提到的性质，可以理解为：保证所有的 x 坐标或 y 坐标互不相同。

基于性质，我们把散块拆分为三部分。

对于紫色部分，枚举紫色范围内 x 坐标，然后查看 y 坐标是否也在紫色范围内，如果是就加上贡献。

对于粉色部分，枚举粉色范围内 y 坐标，然后查看 x 坐标是否也在粉色范围内，如果是就加上贡献。

你可以在紫色部分的时候算上蓝色部分，也可以在粉色部分的时候算上蓝色部分，不要算重就行了。

namespace blk2d{
    const int B1 = 18,B2 = 324,B3 = 5832;
    const int S1 = 25,S2 = 335,S3 = 5835;

    #define F1(i,z) rep(i,1,bl3[z] - 1)
    #define F2(i,z) rep(i,s3[bl3[z]],bl2[z] - 1)
    #define F3(i,z) rep(i,s2[bl2[z]],z - 1)

    int s2[S2],bl2[N],s3[S1],bl3[N];
    int c1[S1][S1],c2[S2][S1],c3[S1][S2],c4[S2][S2],c5[N];

    void init(){
        rep(i,1,n) bl2[i] = bl(i,B2),bl3[i] = bl(i,B3);
        Rep(i,n,1) s2[bl2[i]] = i,s3[bl3[i]] = bl2[i];
    }

    void upd(int x,int t){
        int y = u[x];
        F1(i,x) F1(j,y) c1[i][j] += t;
        F2(i,x) F1(j,y) c2[i][j] += t;
        F1(i,x) F2(j,y) c3[i][j] += t;
        F2(i,x) F2(j,y) c4[i][j] += t;
        F3(i,x) if(u[i] < s2[bl2[y]]) c5[i] += t;
        F3(i,y) if(v[i] < x) c5[v[i]] += t;
    }

    int qry(int x){
        int y = u[x],a = bl3[x],b = bl2[x],c = bl3[y],d = bl2[y];
        return c1[a][c] + c2[b][c] + c3[a][d] + c4[b][d] + c5[x];
    }
}

例题

\texttt{CF848C Goodbye Souvenir}

首先，带权数颜色部分我已经讲了。剩下是二维分块。

对于 (i,pre_i) 这种类型的点，x 坐标绝对是互不相同了，y 坐标除了有些会等于 0，其它都互不相同。所以对于 y=0 的情况，写一个一维分块维护就行了。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<set>

#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define Rep(i,a,b) for(int i = (a);i >= (b);--i)
#define clr(M) memset(M,0,sizeof M)

const int N = 1e5 + 5;

typedef long long ll;

int n,m,a[N],p[N],q[N];

namespace blk2d{
    const int B1 = 18,B2 = 324,B3 = 5832;
    const int S1 = 25,S2 = 330,S3 = 5840;

    int st2[S2],bl2[N],st3[S1],bl3[N]; ll c0[N],s0[S2];
    ll c1[S1][S1],c2[S2][S1],c3[S1][S2],c4[S2][S2],c5[N],c6[N];

    #define F1(i,z) rep(i,1,bl3[z] - 1)
    #define F2(i,z) rep(i,st3[bl3[z]],bl2[z] - 1)
    #define F3(i,z) rep(i,st2[bl2[z]],z)
    #define bl(i,t) (i - 1) / t + 1

    void init(){
        rep(i,1,n) bl2[i] = bl(i,B2),bl3[i] = bl(i,B3);
        Rep(i,n,1) st2[bl2[i]] = i,st3[bl3[i]] = bl2[i];
    }

    void upd(int x,int y,ll t){
        p[x] = y; q[y] = x;
        if(y == 0) return c0[x] += t,void(s0[bl2[x]] += t);
        int a = bl3[x],b = bl2[x],c = bl3[y],d = bl2[y];
        c1[a][c] += t; c2[b][c] += t; c3[a][d] += t; c4[b][d] += t;
        c5[x] += t; c6[y] += t;
    }

    ll qry(int x,int y){
        ll sum = 0;
        F1(i,x) F1(j,y) sum += c1[i][j];
        F2(i,x) F1(j,y) sum += c2[i][j];
        F1(i,x) F2(j,y) sum += c3[i][j];
        F2(i,x) F2(j,y) sum += c4[i][j];
        F3(i,x) if(p[i] <= y) sum += c5[i];
        F3(i,y) if(q[i] < st2[bl2[x]]) sum += c6[i];
        rep(i,1,bl2[x] - 1) sum += s0[i];
        rep(i,st2[bl2[x]],x) sum += c0[i];
        return sum;
    }
}

using namespace blk2d;

std::set<int> P[N];

int pre(int x){
    auto i = P[a[x]].lower_bound(x);
    return i == begin(P[a[x]]) ? 0 : *--i;
}

int nxt(int x){
    auto i = P[a[x]].upper_bound(x);
    return i == end(P[a[x]]) ? 0 : *i;
}

void cpre(int u){
    if(!u) return;
    int v = pre(u);
    upd(u,p[u],p[u] - u);
    upd(u,v,u - v);
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",a + i),P[a[i]].insert(i);
    init();
    rep(u,1,n) p[u] = pre(u),upd(u,p[u],u - p[u]);
    while(m--){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1){
            int w = nxt(x);
            P[a[x]].erase(x); P[a[x] = y].insert(x);
            cpre(x); cpre(w); int v = nxt(x); cpre(v);
            q[p[x]] = x; q[p[w]] = w; q[p[v]] = v;
        } else printf("%lld\n",qry(y,n) - qry(y,x - 1) - qry(x - 1,n) + qry(x - 1,x - 1));
    }
    return 0;
}

\texttt{P7448 [Ynoi2007] rdiq}

题意：多次求区间逆序对，但是如果多个逆序对满足分别位置的值相等，那我们就只算一次。

#### 选择方法&拆贡献首先发现这个问题严格难于 [区间逆序对](/problem/P5047) 问题。区间逆序对的常见做法是 **分块** 或者 **二次离线莫队**，这里选择更好写且常数小的 **二次离线莫队**。标识：记 $P_i,N_i$ 分别为与 $i$ 位置颜色相同的上一个/下一个位置。假如我们莫队，那么从 $[l,r-1]$ 变成 $[l,r]$，答案会增加 $[P_r,r]$ 新出现的 $\gt a_r$ 的数的种类数。拆一下，就是 $[l,r]$ 中 $\gt a_r$ 的数的种类数，减去 $[l,P_r]$ 中 $\gt a_r$ 的数的种类数。 #### 二次离线转化问题即使经过转化，我们要求的东西还是和 **种类数** 有关而非**总数**。所以我们对数组做一次扫描线，在扫到 $i$ 时，计算有关 $i$ 的贡献，同时**把 $P_i$ 的贡献消除**就行了。于是现在的问题就是 **总数**，要求 **单点加，区间大于 $x$ 的数的个数**，考虑将其转化为二维形式，第一维是下标，第二维是值域，那么原问题就是一个 **带权二维数点**。鉴于莫队二次离线的原理，我们把问题转换为： + 扫描线过程中，拆出 $O(n)$ 个修改（包括插入 $i$ 以及删去 $P_i$） + 给每个询问计算贡献，总共会有 $O(n\sqrt m)$ 次二维的查询。于是你要合理的平衡复杂度，做到 $O(\sqrt n)$ 修改 $O(1)$ 查询。别漏了几个性质。 + 所有有值的点，$x$ 坐标互不相同，$y$ 坐标可能相同（因为是值域）。 + 我们有一种方法让 $y$ 坐标也互不相同，即对于相同的 $y$ 坐标值，让 $x$ 坐标越小的 $y$ 坐标越小。有了性质，二维分块做就行了。 $\tt Cautions:

以下代码马蜂阴间（指任何函数之间都有空行，两条同行的分号分割的语句直接也打空格，但是又压行、简化代码极其严重）。
以下代码使用了很多高等的 \texttt{c++} 的功能。如果您想尝试提交，需要至少加 \texttt{c++17}。
莫队块长要调 n\div\sqrt m，因为我们不能让复杂度带 m（这题 n,m 不是一个级别的）。

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<tuple>
#include<algorithm>

#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define Rep(i,a,b) for(int i = (a);i >= (b);--i)
#define clr(_M) memset(_M,0,sizeof _M)
#define eb emplace_back

typedef long long ll;

const int N = 1e5 + 5,M = 5e5 + 5;
const int S1 = 25,S2 = 335,S3 = 5835;

int B1 = 18,B2 = 324,B3 = 5832;
int s2[S2],bl2[N],s3[S1],bl3[N];

#define F1(i,z) rep(i,1,bl3[z] - 1)
#define F2(i,z) rep(i,s3[bl3[z]],bl2[z] - 1)
#define F3(i,z) rep(i,s2[bl2[z]],z - 1)
#define _ n + 1 -
#define bl(x,t) (x - 1) / t + 1

struct qry{
    int l,r,i,b;
    bool operator<(const qry& q) const { return b ^ q.b ? b < q.b : r < q.r; }
} q[M];

std::vector<std::tuple<int,int,int> > P[N],Q[N];

int n,m,Bl,a[N],u[N],v[N],t[N],pv[N],nx[N]; ll A[M];
int c1[S1][S1],c2[S2][S1],c3[S1][S2],c4[S2][S2],c5[N];

void upd(int x,int t){
    int y = u[x];
    F1(i,x) F1(j,y) c1[i][j] += t;
    F2(i,x) F1(j,y) c2[i][j] += t;
    F1(i,x) F2(j,y) c3[i][j] += t;
    F2(i,x) F2(j,y) c4[i][j] += t;
    F3(i,x) if(u[i] < s2[bl2[y]]) c5[i] += t;
    F3(i,y) if(v[i] < x) c5[v[i]] += t;
}

int qry(int x){
    int y = u[x],a = bl3[x],b = bl2[x],c = bl3[y],d = bl2[y];
    return c1[a][c] + c2[b][c] + c3[a][d] + c4[b][d] + c5[x];
}

void sol(int ty){
    clr(t); rep(i,1,n) ++t[a[i]];
    rep(i,1,n) t[i] += t[i - 1];
    rep(i,1,n) v[u[i] = t[a[i]]--] = i;
    clr(t); rep(i,1,n) pv[i] = t[a[i]],t[a[i]] = i;
    clr(t); Rep(i,n,1) nx[i] = t[a[i]],t[a[i]] = i;
    clr(c1); clr(c2); clr(c3); clr(c4); clr(c5);
    rep(i,1,n){
        upd(i,1); if(pv[i]) upd(pv[i],-1);
        auto& v = ty == 1 ? Q[i] : P[i];
        for(auto[l,r,k] : v){
            ll c = 0;
            rep(j,l,r){
                if(nx[j] < i) c -= qry(nx[j]);
                c += qry(j);
            }
            k > 0 ? A[k] += c : A[-k] -= c;
        }
    }
}

signed main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",a + i),a[i] = _ a[i];
    scanf("%d",&m); Bl = sqrt(n);
    rep(i,1,m){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].i = i; q[i].b = bl(q[i].l,Bl);
    }
    std::sort(q + 1,q + m + 1);
    rep(i,1,n) bl2[i] = bl(i,B2),bl3[i] = bl(i,B3);
    Rep(i,n,1) s2[bl2[i]] = i,s3[bl3[i]] = bl2[i];
    int l = 1,r = 0;
    rep(i,1,m){
        int L = q[i].l,R = q[i].r,I = q[i].i;
        if(r < R) P[_ l].eb(_ R,n - r,I),r = R;
        if(r > R) P[_ l].eb(_ r,n - R,-I),r = R;
        if(l > L) Q[r].eb(L,l - 1,I),l = L;
        if(l < L) Q[r].eb(l,L - 1,-I),l = L;
    }
    sol(1); 
    std::reverse(a + 1,a + n + 1);
    rep(i,1,n) a[i] = _ a[i];
    sol(2);
    rep(i,2,m) A[q[i].i] += A[q[i - 1].i];
    rep(i,1,m) printf("%lld\n",A[i]);
    return 0;
}