CF848C Goodbye Souvenir

· · 题解

\tt Link

前言

题解清一色的 \tt CDQ，树套树，但是有个 \mathcal O(n^{\frac 53}\log n) 是什么鬼？

这是一个分块做法，复杂度 \mathcal O(n\sqrt n)，但是非常阴间，建议谨慎尝试。

如果你真心想写这个做法，建议写完这题就去写 \tt rdiq，\tt rcn。

转化

考虑记下每个位置前一个与它颜色相同的位置 P_i。

那么我们可以把这个贡献从每种颜色转化到每个位置。

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

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

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

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

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

关于点的性质：所有点的 x 坐标互不相同，y 坐标除了可能有多个 0 之外，互不相同.

修改操作

很平凡。你维护每个点出现位置的 set，然后就可以 O(\log n) 计算每个位置的上一个/下一个颜色相同位置。

二维分块

这个题用这玩意确实大材小用了，但是还是想说说。

注意：下面介绍的是一种 O(\sqrt n) 前缀矩形加 O(1) 单点查询的数据结构。转化一下可以得到适合原问题的单点加矩形查

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

为了方便，以下记 \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 种块，对于每种块我们都维护块和。

现在来算一下复杂度。

那散块如何做呢？

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

上文所说的性质，就是说 x,y 坐标都互不相同（如果 y=0，这时我们再写一个一维分块做就好了。）

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

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

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

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

Code

#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;
}