\(T4\) 莫队
首先我们需要知道一种统计答案的方法。
我们记 \(R_i\) 表示右边第一个和他相同的位置。
那么我们记 \(a_i=\min(a_{i+1},R_i)\) ，那么贡献就是 \(a_i-i+1\) ，所以我们最后就是要维护 \(a_i\) 就好了。
但是实际上如果你要直接维护 \(a_i\) 没有任何性质是做不了的。
所以我们只能考虑另外一种答案的贡献方式。
考虑一个 \(R_i\) 可以贡献给哪些位置。
显然是他前面一段以他 \(i\) 的后缀 \(\min\) 大于他的数，容易发现这个东西具有单调性，可以使用线段树二分，而对于合并子区间的时候，将右边区间的最小值丢到左边去，看一下能影响多少。对于小于他的数，就用原数，否则改成右区间的最小值。
具体实现，在 \(push\_up\) 的时候改一下就好了。
这样我们每个区间相当于是以当前区间的右端点开始后缀 \(\min\) 的贡献。
总时间复杂度 \(O(n\log^2 n)\)
启示：
关于要我们维护递增或递减关系的信息时，可以先对于每个子区间求出答案，然后在合并区间时再根据单调性用 \(\log\) 的复杂度更新，总复杂度 \(\log^2 n\) 每次操作。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=2e5+10;
int n,m;
int a[MAXN],ys[MAXN];
set<int> s[MAXN];
struct data_structure {
LL x,ans,mi;
}tr[(MAXN<<2)];
void ycl() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
s[i].insert(n+1);
scanf("%d",&a[i]);
s[a[i]].insert(i);
}
for(int i=1;i<=n;++i) {
auto it=s[a[i]].upper_bound(i);
ys[i]=*it;
}
}
LL merge(int u,int l,int r,LL x) {
if(l==r) return min(tr[u].mi,x);
int mid=(l+r)/2;
if(tr[(u<<1|1)].mi<=x) return tr[u].ans-tr[(u<<1|1)].ans+merge((u<<1|1),mid+1,r,x);
return (r-mid)*x+merge((u<<1),l,mid,x);
}
void psup(int u,int l,int mid,int r) {
tr[u].mi=min(tr[(u<<1)].mi,tr[(u<<1|1)].mi);
tr[u].ans=merge((u<<1),l,mid,tr[(u<<1|1)].mi)+tr[(u<<1|1)].ans;
}
void build(int u,int l,int r) {
if(l==r) {
tr[u].x=tr[u].mi=tr[u].ans=ys[l];
return ;
}
int mid=(l+r)/2;
build((u<<1),l,mid);
build((u<<1|1),mid+1,r);
psup(u,l,mid,r);
}
void update(int u,int l,int r,int x,int y) {
if(l==r) {
tr[u].x=tr[u].mi=tr[u].ans=y;
return ;
}
int mid=(l+r)/2;
if(x<=mid) update((u<<1),l,mid,x,y);
else update((u<<1|1),mid+1,r,x,y);
psup(u,l,mid,r);
}
LL ans,lim;
void query(int u,int l,int r,int x,int y) {
if(l>y||r<x) return ;
if(l>=x&&r<=y) {
ans+=merge(u,l,r,lim);
lim=min(lim,tr[u].mi);
return ;
}
int mid=(l+r)/2;
query((u<<1|1),mid+1,r,x,y);
query((u<<1),l,mid,x,y);
}
int main () {
freopen("team.in","r",stdin);
freopen("team.out","w",stdout);
ycl();
build(1,1,n);
for(int i=1;i<=m;++i) {
LL opt,x,y;
scanf("%lld%lld%lld",&opt,&x,&y);
if(opt==1) {
//del a_x
s[a[x]].erase(x);
auto it=s[a[x]].upper_bound(x);
if(it!=s[a[x]].begin()) {
--it;
auto itt=s[a[x]].upper_bound(*it);
update(1,1,n,*it,*itt);
}
//insert y
a[x]=y;
it=s[a[x]].upper_bound(x);
if(it!=s[a[x]].end()) update(1,1,n,x,*it);
if(it!=s[a[x]].begin()) {
--it;
update(1,1,n,*it,x);
}
s[a[x]].insert(x);
}
else {
ans=0;
lim=y+1;
query(1,1,n,x,y);
ans-=(x+y)*(y-x+1)/2;
printf("%lld\n",ans);
}
}
return 0;
}