848C - Goodbye Souvenir - CodeForces Solution

#include<bits/stdc++.h>
#define gt() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
#define pt(ch) (Top<1000000?St[Top++]=ch:(Out(),St[(Top=0)++]=ch))
#define Out() (fwrite(St,1,Top,stdout))
#define LL unsigned int
using namespace std;
int Top;static char St[1000000],buf[1000000],*p1=buf,*p2=buf;
const int maxn=(1e5)+5;
int N,M,T,Q,P[maxn],cnt;LL Ans[maxn],c[maxn];
set<int>S[maxn];
struct ff{
	int x,y,o,f;
	inline int val(){return (~f)?(x-y):(y-x);}
}A[maxn<<3],C[maxn<<3];
int Re(){
	int ret=0;char ch=gt();
	while(ch<'0'||ch>'9') ch=gt();
	while(ch>='0'&&ch<='9') ret=ret*10+(ch^'0'),ch=gt();
	return ret;
}
void Wri(LL x){if(x>9) Wri(x/10);pt(x%10+'0');}
void Add(int i,int x){while(i<=N) c[i]+=x,i+=i&-i;}
int Get(int i){int Res=0;while(i) Res+=c[i],i^=i&-i;return Res;}
void Merge(int L,int mid,int R){
	for(int k=L,i=L,j=mid+1;k<=R;k++) C[k]=(j>R||(i<=mid&&A[i].x<=A[j].x))?A[i++]:A[j++];
	for(int k=L;k<=R;k++) A[k]=C[k];
}
void Solve(int L,int R){
	if(L>=R) return;
	int mid=L+R>>1,i,j;Solve(L,mid),Solve(mid+1,R);
	for(i=mid+1,j=L;i<=R;i++)if(A[i].o){
		while(j<=mid&&A[j].x<=A[i].x){if(!A[j].o) Add(A[j].y,A[j].val());j++;}
		Ans[A[i].o]+=Get(N)-Get(A[i].y-1);
	}
	for(i=L;i<j;i++) if(!A[i].o) Add(A[i].y,-A[i].val());
	Merge(L,mid,R);
}
int main(){
	#ifdef hhh
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	#endif
	N=Re(),Q=Re();
	for(int i=1;i<=N;i++){
		S[P[i]=Re()].insert(i);
		if(S[P[i]].size()>1) 
		A[++M]=(ff){i,*(--S[P[i]].rbegin()),0,1}; 
	}
	while(Q--){
		int opt=Re(),x=Re(),y=Re();++T;
		if(opt==2){A[++M]=(ff){y,x,++cnt,0};continue;}
		
		auto i=S[P[x]].find(x);int L=0,R=0;
		if(i!=S[P[x]].begin()) A[++M]=(ff){x,L=*--i,0,-1},i++;
		if(++i!=S[P[x]].end()) A[++M]=(ff){R=*i,x,0,-1};
		if(L&&R) A[++M]=(ff){R,L,0,1};
		S[P[x]].erase(x);//Del
		
		S[P[x]=y].insert(x),i=S[y].find(x),L=R=0;
		if(i!=S[y].begin()) A[++M]=(ff){x,L=*--i,0,1},i++;
		if(++i!=S[y].end()) A[++M]=(ff){R=*i,x,0,1};
		if(L&&R) A[++M]=(ff){R,L,0,-1};//Insert
	}
	Solve(1,M);
	for(int i=1;i<=cnt;i++) Wri(Ans[i]),pt('\n');
    return Out(),0;
}