难度在最近遇到的题里相对较高，在这里写一篇珂学题解。
（以下是学校给的部分分）
\(20\%\)：直接暴力枚举。
另外 \(20\%\)：假如我们取 \(pre\)，对于 \(pre<l\) 的，\(ans++\)，明显二维偏序，树状数组或 \(cdq\) 即可，时间复杂度 \(O(n\log n)\)。
另外 \(40\%\)：相当于多加一个时间维，三维偏序，\(cdq\) 典中典，时间复杂度 \(O(n\log^2n)\)。
这是正解向的，实际上第二个部分分还可以莫队，第三个部分分还可以分块或带修莫队。
\(100\%\)：这里引入珂朵莉树：
模板题 \(CF896C\)，也是普遍认为的算法来源。
实际上就是将相同的数合到一个区间，对于区间赋值（珂朵莉树中通常称为推平），直接将这些区间全部并到一块，合成一个区间（珂朵莉树精髓，\(assign\)）。时间复杂度在随机数据下，可证明为 \(O(n\log n)\) 级别的，可以自己上网搜。
我们用珂朵莉树维护 \(pre\)，就可以保证时间维变成 \(n+m\) 个。
时间复杂度 \(O(n\log^2n)\)。
//中国珂学院 SNGXYZ 分院 OI 科第三办公室研究员 LYH
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5,M=2e6+5;
int n,m,cnm,cnq,pr[N];
int a[N],lst[N],ans[N],cna;
struct node{
int x,y,t,v,id;
}q[M];map<int,int>mp;
int cmp1(node x,node y){
return x.t!=y.t?x.t<y.t:x.id<y.id;
}int cmp2(node x,node y){
return x.x!=y.x?x.x<y.x:x.id<y.id;
}struct chtholly{
struct odt{
int l,r;
mutable int v;
bool operator<(const odt &c)const{
return l<c.l;
}
};set<odt>st,cl[N];
#define iter set<odt>::iterator
iter ins(int l,int r,int v){
cl[v].insert({l,r,v});
return st.insert({l,r,v}).first;
}void del(int l,int r,int v){
cl[v].erase({l,r,v});
st.erase({l,r,v});
}iter spilt(int x){
iter it=st.lower_bound({x,0,0});
if(it!=st.end()&&(*it).l==x) return it;
it--;int l=(*it).l,r=(*it).r,v=(*it).v;
del(l,r,v),ins(l,x-1,v);
return ins(x,r,v);
}int pre(int x){
iter it=--st.upper_bound({x,0,0});
if((*it).l<x) return x-1;
iter ch=cl[(*it).v].lower_bound({x,0,0});
return (ch!=cl[(*it).v].begin())*(*(--ch)).r;
}void assign(int l,int r,int v,int t){
iter tr=spilt(r+1),tl=spilt(l);
vector<int>ps;
for(iter it=tl;it!=tr;it++){
if(it!=tl) ps.emplace_back((*it).l);
iter nxt=cl[(*it).v].upper_bound(*it);
if(nxt!=cl[(*it).v].end()) ps.emplace_back((*nxt).l);
cl[(*it).v].erase(*it);
}st.erase(tl,tr);ins(l,r,v);
ps.emplace_back(l);
iter nxt=cl[v].upper_bound({l,r,v});
if(nxt!=cl[v].end()) ps.emplace_back((*nxt).l);
for(int i=0;i<ps.size();i++){
q[++cnq]=(node){ps[i],pr[ps[i]],t,-1,0};
pr[ps[i]]=pre(ps[i]);
q[++cnq]=(node){ps[i],pr[ps[i]],t,1,0};
}
}
}seniorious;
struct BIT{
int c[N];
void add(int x,int y){
for(;x<N;x+=x&-x)
c[x]+=y;
}int ans(int x){
int re=0;
for(;x;x-=x&-x)
re+=c[x];
return re;
}
}bit;
void cdq(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
cdq(l,mid),cdq(mid+1,r);
int i=l,j=mid+1;
while(j<=r){
while(i<=mid&&q[i].x<=q[j].x){
if(!q[i].id) bit.add(q[i].y+1,q[i].v);
i++;
}if(q[j].id) ans[q[j].id]+=bit.ans(q[j].y+1)*q[j].v;
j++;
}for(int k=l;k<i;k++)
if(!q[k].id) bit.add(q[k].y+1,-q[k].v);
inplace_merge(q+l,q+mid+1,q+r+1,cmp2);
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
if(!mp[a[i]])
mp[a[i]]=++cnm;
a[i]=mp[a[i]];
pr[i]=lst[a[i]];
lst[a[i]]=i;
q[++cnq]={i,pr[i],0,1,0};
seniorious.ins(i,i,a[i]);
}for(int i=1;i<=m;i++){
int x;cin>>x;
if(x==1){
int l,r,v;cin>>l>>r>>v;
if(!mp[v]) mp[v]=++cnm;
seniorious.assign(l,r,mp[v],i);
}else{
int l,r;cin>>l>>r;
q[++cnq]={r,l-1,i,1,++cna};
q[++cnq]={l-1,l-1,i,-1,cna};
}
}sort(q+1,q+cnq+1,cmp1);
cdq(1,cnq);
for(int i=1;i<=cna;i++)
cout<<ans[i]<<"\n";
return 0;
}/*
在太阳西斜的这个世界里，置身天上之森。
等这场战争结束之后，不归之人与望眼欲穿的众人。
人人本着正义之名，长存不灭的过去、逐渐消逝的未来。
我回来了，纵使日薄西山，即便看不到未来。
此时此刻的光辉，盼君勿忘。
————世界上最幸福的女孩
*/