CF848C Goodbye Souvenir 题解
Creeper_l
·
·
个人记录
原题链接：CF848C。
题意：给定一个序列 a，维护两个操作。
注：下文的 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)$。
```cpp
#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;
}
```