简要题意
维护一个序列，支持以下操作：
$1 :$ 修改序列的某个值
$2 :$ 查询在区间 $[l,r]$ 内，有多少个子区间，区间内不出现重复的数。
序列长度，操作次数均为 $2 \times 10^5$
思路
这道题叫做“莫队”，题目背景也在介绍莫队，导致咱一直在想带修莫队！非常难受（其实不带修，这道题的莫队也不是那么好写吧），考场最后交了暴力。
首先我们先写出一个 $O(nq)$ 的暴力，如果从前往后考虑（正解会从后往前考虑，只是反过来罢了），预处理出每个位置，它的数字上一次在哪里出现，记为 $pos$，那么对于每一个位置我们实时更新 $lastpos = max(lastpos,pos)$，那么这个位置 $i$ 的贡献为 $i - lastpos$。
考场上咱没注意到的一个转化就是，如果从后往前考虑（注意，从这里开始反过来了哦，$lastpos$ 指的是 右边 最远可以取到哪里，不包含这个点），$nxt_i$ 表示 $i$ 位置上的数后面第一次出现的位置，则有$lastpos_i = min{ nxt_j } (i \le j)$，它是一个后缀最小值，且一个区间 $[l,r]$ 的答案是 $\sum \limits _{i = l} ^{r} (min(r,lastpos_i) - i)$，可以分离出 $i$ 获得 $\sum \limits _{i = l} ^{r} (min(r,lastpos_i)) - \frac {(l + r) \times (r - l + 1)} {2}$ （后者使用等差数列公式转换了）
发现这个 $min(r,lastpos_i)$ 和 $lastpos$ 本身的合并没有任何区别，因为把两个相邻的区间合并，左边的 $lastpos$ 可能会超过右边的 $lastpos$，然而事实上它会被 “砍掉”。可以理解为有一堵墙？右边立下的墙会影响到左边，而询问的 $r$ 本身也可以看做一堵墙。然后我们怎么解决呢？
因为 $lastpos$ 显然是单调的，所以对于一个区间判断它是否会被某一堵墙影响，可以在线段树上二分——左边的部分不会被这堵墙影响，右边的部分会被这堵墙影响，而会被影响的部分，他们的贡献不再是原本的 $lastpos$，而是被砍成了右边这堵墙的位置。根据这个思想，我们可以封装一个 $FindAns$ 函数，在 $\log n$ 的复杂度内求的某个区间被某堵墙影响后的答案。
现在建设线段树。节点维护两个值，$farpos$ 和 $ans$，后者表示的就是 $l$,$r$ 区间内的 $\sum lastpos$（$l$,$r$ 为节点管辖的区间），前者的命名有问题（当时没理解），$farpos$ 维护的是区间所有点中，最小的 $lastpos$ 值（所以它应该叫做 $nearpos$）。它有什么用呢？显然右边区间的 $lastpos$ 会作为“墙”拦住左边区间的答案（单独考虑左边的区间，它的贡献是可能伸出左区间的 $r$ 的），而最左边的墙显然拦下了所有贡献，所以维护最小值。然后我们使用上文封装的 $FindAns$ 函数，将一个区间的右区间的 $farpos$ 作为“墙”，算出左区间的贡献，加上右区间本身的贡献，则是这个区间总的贡献。
上面的 PushUp 函数可能令人疑惑，答案为什么不能直接累加？因为一个维护 $l,r$ 的节点的贡献，意思是考虑以 $l,r$ 内每一个点为起点，也只考虑 $l,r$ 的 $lastpos$ 作为“墙”，造成的贡献。他们可能会伸出右端点 $r$ 直到 $nxt$ 才停止，然而这个过程中实际上他们会被右边大于 $r$ 的墙拦住，不过这并不在该区间考虑的范围内，只有在合并为更大的区间的时候，我们才需要考虑左边区间会被右边拦住带来的影响。
最后 Query 函数则比较简单了，不考虑区间的 $r$ 的话只需要直接普通的合并答案就行了，然而实际上我们新添了一堵墙，也就是询问的 $r$ （因为子区间的右端点不能超过询问右端点嘛），所以说求答案的时候要考虑询问区间 $r$，同时还要先算右区间，然后用右区间的 $farpos$ 更新“墙”（考虑PushUp 时合并的处理，这里询问也是同理）。
因为在线段树的 $\log n$ 次操作中，每次都会调用复杂度为 $\log n$ 的 $FindAns$ 函数，最终复杂度为 $O(q \log ^2 n)$。
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 1018 + 1108;
int nxt[MAXN],a[MAXN],n,q;
set<int> numPos[MAXN];
class SegmentTree{
private:
struct Node{
int farpos;
ll ans;
}node[MAXN * 4];
ll FindAns(int p,int l,int r,int limitpos){
if(l == r)return min(node[p].ans,ll(limitpos));
const int mid = (l + r) >> 1;
if(node[p*2+1].farpos > limitpos){
return FindAns(p*2,l,mid,limitpos) + limitpos * (r - mid);
}else{
return node[p].ans - node[p*2+1].ans + FindAns(p*2+1,mid+1,r,limitpos);
}
return 10181108;
}
inline void PushUp(int p,int l,int r){
node[p].farpos = min(node[p*2].farpos,node[p*2+1].farpos);
const int mid = (l + r) >> 1;
node[p].ans = FindAns(p*2,l,mid,node[p*2+1].farpos) + node[p*2+1].ans;
return ;
}
void Build(int p,int l,int r){
if(l == r){
node[p].farpos = node[p].ans = nxt[l];
return ;
}
const int mid = (l + r) >> 1;
Build(p*2,l,mid),Build(p*2+1,mid+1,r);
PushUp(p,l,r);
return ;
}
void Change(int p,int l,int r,int pos,int _nxt){
if(l == r){
node[p].ans = node[p].farpos = _nxt;
return ;
}
const int mid = (l + r) >> 1;
if(mid >= pos)Change(p*2,l,mid,pos,_nxt);
if(mid < pos)Change(p*2+1,mid+1,r,pos,_nxt);
PushUp(p,l,r);
return ;
}
ll Query(int p,int l,int r,int OBJL,int OBJR,int& limitpos){
if(OBJL <= l && r <= OBJR){
ll res = FindAns(p,l,r,limitpos);
limitpos = min(limitpos,node[p].farpos);
return res;
}
const int mid = (l + r) >> 1;
ll ret = 0;
if(mid < OBJR)ret += Query(p*2+1,mid+1,r,OBJL,OBJR,limitpos);//这个顺序是因为需要用右边的farpos限制左边的右端点
if(mid >= OBJL)ret += Query(p*2,l,mid,OBJL,OBJR,limitpos);
return ret;
}
public:
inline void Build(){
Build(1,1,n);
return ;
}
inline void Change(int pos,int _nxt){
if(not(1 <= pos && pos <= n))return ;
Change(1,1,n,pos,_nxt);
return ;
}
inline ll Query(int l,int r){
int limitpos = r + 1;
return Query(1,1,n,l,r,limitpos);
}
}tr;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i = 1;i <= n;i++){
cin>>a[i];
numPos[a[i]].insert(i);
numPos[i].insert(0),numPos[i].insert(n+1);
}
for(int i = 1;i <= n;i++){
nxt[i] = *(++numPos[a[i]].find(i));
}
tr.Build();
for(int i = 1,opt,x,y;i <= q;i++){
cin>>opt>>x>>y;
if(opt == 1){
int pre = *(--numPos[a[x]].find(x)),_nxt = *(++numPos[a[x]].find(x));
tr.Change(pre,_nxt);
numPos[a[x]].erase(x);
a[x] = y;
numPos[a[x]].insert(x);
pre = *(--numPos[a[x]].find(x)),_nxt = *(++numPos[a[x]].find(x));
tr.Change(pre,x),tr.Change(x,_nxt);
}else if(opt == 2){
cout<<tr.Query(x,y) - 1ll * (x + y) * (y - x + 1) / 2<<'\n';
}
}
return not(Akano loves pure__Elysia);
}据说 P4198 楼房重建 也是同样的套路，可以作为配套练习题
Comments NOTHING