原题链接：CF848C。
题意：给定一个序列 \(a\)，维护两个操作。
-
操作一：将 \(a_x\) 修改为 \(y\)
-
操作二：对于区间 \(l,r\) 中出现的每一种数 \(x\)，求出 \(\sum f(x)\)。
\(f(x)\) 表示区间 \(l\) 到 \(r\) 内 \(x\) 最后一次出现的位置减去 \(x\) 第一次出现的位置。
注：下文的 cdq 数组维护的三个值分别为上一次出现的位置 \(pre_i\)，当前位置 \(i\)，这段区间的贡献（\(i-pre_i\)）。\(pre\) 和 \(nxt\) 分别表示 \(a_{i}\) 上一次和下一次出现的位置。
有一个比较巧妙的转化：\(f(x)= \sum i-pre_{i}(l \le pre_{i},i \le r,a_{i}=x)\)。
考虑用 cdq 分治来解决这个问题。上述表达式的条件中已经有两个偏序条件了，又因为我们需要把每个操作离线下来，还需要加上时间戳。于是已经有三维偏序了。
我们可以用一个 set 来维护每一个数所有的出现位置，每个 set 中相邻的两个数都要对答案产生贡献（因为相邻两个数一定为 \(pre_i\) 和 \(i\)），要加入 cdq 数组中。
首先对于原数组，我们把所有 \((pre_i,i,i-pre_i)\) 加入 cdq 数组中。
对于每一次操作一，我们既要考虑 \(a_x\) 的贡献，也要考虑 \(y\) 的贡献。
-
\(a_x\) 的贡献：首先要把原先的 \((pre_x,x,x-pre_x)\) 和 \((x,nxt_x,nxt_x-x)\) 删去，因为 \(x\) 的值不再是原来的 \(a_{x}\) 了，所以这两段不存在了。还要把 \((pre_x,nxt_x,nxt_x-pre_x)\) 加入 cdq 数组中，因为 \(a_x\) 不在了，所以 \(pre_x\) 和 \(nxt_x\) 在 set 中就相邻了，需要加上。最终将 \(x\) 从 \(a_x\) 的 set 移到 \(y\) 的 set 中。
-
\(y\) 的贡献：和上述过程相反。
对于每一次操作二，直接将 \((l,r,0)\) 加入 cdq 数组即可，注意还要记录一下哪些是修改操作，哪些是查询操作。
细节较多，时间复杂度 \(O(n \log^2 n)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 10;
set <int> s[MAXN];
multiset <int> :: iterator it;
int n,m,val[MAXN],cnt,tot,ans[MAXN],tree[MAXN],a,b,c,pre,nxt;
struct Node{int l,r,t,val,type;}q[MAXN],w[MAXN];
inline int L(int x){return (x & -x);}
inline void Add(int x,int c){for(;x <= n;x += L(x)) tree[x] += c;}
inline int Query(int x){if(x == 0) return 0;if(x > n) x = n;int r = 0;for(;x;x -= L(x)) r += tree[x];return r;}
inline void Update()
{
if(val[b] == c) return;
pre = 0,nxt = 0;
it = s[val[b]].find(b);
if(it != s[val[b]].begin()) it--,pre = *it,it++;
it++;if(it != s[val[b]].end()) nxt = *it;
if(pre != 0) q[++cnt] = {pre,b,cnt,pre - b,1};
if(nxt != 0) q[++cnt] = {b,nxt,cnt,b - nxt,1};
if(pre != 0 && nxt != 0) q[++cnt] = {pre,nxt,cnt,nxt - pre,1};
s[val[b]].erase(b),s[c].insert(b),val[b] = c;
pre = 0,nxt = 0;
it = s[c].find(b);
if(it != s[c].begin()) it--,pre = *it,it++;
it++;if(it != s[c].end()) nxt = *it;
if(pre != 0) q[++cnt] = {pre,b,cnt,b - pre,1};
if(nxt != 0) q[++cnt] = {b,nxt,cnt,nxt - b,1};
if(pre != 0 && nxt != 0) q[++cnt] = {pre,nxt,cnt,pre - nxt,1};
}
inline void query(){q[++cnt] = {b,c,cnt,++tot,2};}
inline void cdq(int l,int r)
{
if(l >= r) return;
int mid = (l + r) >> 1;
cdq(l,mid),cdq(mid + 1,r);
int i = l,j = mid + 1,k;
while(i <= mid && j <= r)
{
if(q[i].l >= q[j].l){if(q[i].type == 1) Add(q[i].r,q[i].val);w[++k] = q[i++];}
else{if(q[j].type == 2) ans[q[j].val] += Query(q[j].r);w[++k] = q[j++];}
}
while(i <= mid){if(q[i].type == 1) Add(q[i].r,q[i].val);w[++k] = q[i++];}
while(j <= r){if(q[j].type == 2) ans[q[j].val] += Query(q[j].r);w[++k] = q[j++];}
for(i = l;i <= mid;i++) if(q[i].type == 1) Add(q[i].r,-q[i].val);
for(int p = l;p <= r;p++) q[p] = w[p - l + 1];
}
signed main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> val[i];
s[val[i]].insert(i),it = s[val[i]].find(i);
if(it != s[val[i]].begin()) --it,q[++cnt] = (Node){*it,i,cnt,i - *it,1};
}
for(int i = 1;i <= m;i++)
{
cin >> a >> b >> c;
if(a == 1) Update();
if(a == 2) query();
}
cdq(1,cnt);
for(int i = 1;i <= tot;i++) cout << ans[i] << endl;
return 0;
}