CF848C Goodbye Souvenir

[$\tt Link$](/problem/CF848C) ## 前言 题解清一色的 $\tt CDQ$，树套树，但是有个 $\mathcal O(n^{\frac 53}\log n)$ 是什么鬼？ 这是一个分块做法，复杂度 $\mathcal O(n\sqrt n)$，但是非常阴间，建议谨慎尝试。 如果你真心想写这个做法，建议写完这题就去写 [$\tt rdiq$](/problem/P7448)，[$\tt rcn$](/problem/P7721)。 ## 转化 考虑记下每个位置前一个与它颜色相同的位置 $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)$ 的。  但是我们整块复杂度保证，散块又不行了。于是考虑在现在的灰色部分分块用来辅助原来的散块，分出 + $\bf a\times b$ 个 $\bf c\times b$ 的块 + $\bf b\times a$ 个 $\bf b\times c$ 的块 + $\bf b\times b$ 个 $\bf b\times b$ 的块  现在总共分了 $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$ 坐标都互不相同（如果 $y=0$，这时我们再写一个一维分块做就好了。） **基于性质**，我们把散块拆分为三部分。  对于紫色部分，枚举紫色范围内 $x$ 坐标，然后查看 $y$ 坐标是否也在紫色范围内，如果是就加上贡献。 对于粉色部分，枚举粉色范围内 $y$ 坐标，然后查看 $x$ 坐标是否也在粉色范围内，如果是就加上贡献。 你可以在紫色部分的时候算上蓝色部分，也可以在粉色部分的时候算上蓝色部分，不要算重就行了。 ## Code ```cpp #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; } ```