一个序列，定义无重区间为没有重复的数的区间。两种操作：
- 将(a_x)改为(y)。
- 询问区间([x,y])中有多少个无重子区间。
(n,mle 2*10^5)
按照套路求出每个位置前面第一个相同的位置，记为(lst_i)，对于一个询问([L,R])，答案为(sum_{i=L}^R i-max(max_{j=L}^{i}lst_j,L-1))。
相当于要求([L,R])的前缀(max)的和。
可以规定(lst_L=L-1)，这样就不用特别考虑(L-1)的影响，甚至可以直接写作(sum_{i=L}^R i-max_{j=1}^ilst_j)。
考虑暴力，相当于一个数(x)，初始为(L-1)，从(L)做到(R)，每次(x o max(x,a_i))（ll称之为复合），并且做一次加(x)的贡献。记这个东西为(query(L,R,x))。
先说个(O(nlg^2n))的做法：
用线段树维护。考虑(query(L,R,x))，如果(x>mx(L,mid))，则((mid-l+1)*x+query(mid+1,R,x))；否则(query(l,mid,x)+query(mid+1,R,mx(L,mid)))。可以发现(query(mid+1,R,mx(L,mid)))已经和(x)无关了，所以可以预处理(f(L,R)=query(mid+1,R,mx(L,mid)))。
在update的时候花(O(lg ))时间维护每一个有影响的(f(L,R))，于是一次修改时间复杂度(O(lg^2))。
询问的时候需要找出(O(lg))子区间然后进行(query)操作，(query)执行一次是(O(lg))，所以查询一次时间复杂度(O(lg^2))。
再说ll的(O(nlg n))爆标做法：
对于每个时间，按照序列从前往后做，一路取前缀(max)。（如果是询问时间可以将(lst_{L})变为(L-1)，变成从(1)开始的前缀max）
把时间变成要维护的维度，枚举序列的位置，维护所有时间的前缀(max)及其贡献历史和。
可以用吉司机线段树解决。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define N 200005
#define ll long long
int n,m;
int a[N],lst[N];
set<int> buc[N];
int mx[N*4];
ll f[N*4];
ll tquery(int k,int l,int r,int x){
if (l==r)
return max(x,mx[k]);
int mid=l+r>>1;
if (x>mx[k<<1]) return (ll)x*(mid-l+1)+tquery(k<<1|1,mid+1,r,x);
return tquery(k<<1,l,mid,x)+f[k];
}
void build(int k,int l,int r){
if (l==r){
mx[k]=lst[l];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
mx[k]=max(mx[k<<1],mx[k<<1|1]);
f[k]=tquery(k<<1|1,mid+1,r,mx[k<<1]);
}
void modify(int x,int c,int k=1,int l=1,int r=n){
if (l==r){
mx[k]=c;
return;
}
int mid=l+r>>1;
if (x<=mid) modify(x,c,k<<1,l,mid);
else modify(x,c,k<<1|1,mid+1,r);
mx[k]=max(mx[k<<1],mx[k<<1|1]);
f[k]=tquery(k<<1|1,mid+1,r,mx[k<<1]);
}
ll ans;
void query(int st,int en,int &x,int k=1,int l=1,int r=n){
if (st<=l && r<=en){
ans+=tquery(k,l,r,x);
x=max(x,mx[k]);
return;
}
int mid=l+r>>1;
if (st<=mid) query(st,en,x,k<<1,l,mid);
if (mid<en) query(st,en,x,k<<1|1,mid+1,r);
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
freopen("team.in","r",stdin);
freopen("team.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
if (!buc[a[i]].empty())
lst[i]=*buc[a[i]].rbegin();
buc[a[i]].insert(i);
}
build(1,1,n);
for (int i=1;i<=m;++i){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if (op==1){
buc[a[x]].erase(x);
auto p=buc[a[x]].upper_bound(x);
if (p!=buc[a[x]].end()){
if (p==buc[a[x]].begin())
lst[*p]=0;
else{
auto q=p;
lst[*p]=*(--q);
}
modify(*p,lst[*p]);
}
a[x]=y;
p=buc[y].upper_bound(x);
if (p!=buc[y].end()){
lst[*p]=x;
modify(*p,lst[*p]);
}
if (p==buc[y].begin())
lst[x]=0;
else
lst[x]=*(--p);
modify(x,lst[x]);
buc[y].insert(x);
}
else{
ans=0;
int z=x-1;
query(x,y,z);
printf("%lld
",(ll)(x+y)*(y-x+1)/2-ans);
}
}
return 0;
}