RT，珂朵莉树加CDQ分治

RE 45pts

评测记录

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define xsc return
#define akioi 0
int read()
{
	int x;scanf("%d",&x);
	return x;
}
ll lread()
{
	ll x;scanf("%lld",&x);
	return x;
}
//file head over
#define MaxN 200005
#define mid (l+r>>1)
struct Node{
	int l,r;
	mutable int val;
};
bool operator<(Node i,Node j){return i.l < j.l;}
struct Opt{//操作与修改的结构体 
	int op,x,y,v;
}a[MaxN*10],b[MaxN*10];//每次修改,开始*1 
bool operator<(Opt i,Opt j){return i.x < j.x;}
set<Node>s[MaxN*2];
map<int,int>mp;int cnt;//不讲顺序还是用mp离散化舒服
int n,ans[MaxN],m,q,lst[MaxN];
set<Node>::iterator Split(int pos)
{
	auto it = s[0].lower_bound(Node{pos,0,0});
	it--;Node nd = *it;
	if(nd.r < pos) return it;
	s[0].erase(it);
	s[nd.val].erase(nd);
	Node ndl = nd,ndr = nd;
	ndl.r = pos-1,ndr.l = pos;
	s[0].insert(ndr);
	s[nd.val].insert(ndr);
	s[nd.val].insert(ndl);
	return s[0].insert(ndl).first;
}
void clst(int x,int y)
{
	if(lst[x] == y) return ;
	a[++m] = Opt{0,x,lst[x],-1};
	a[++m] = Opt{0,x,lst[x] = y,1};
}
void Era(Node nd)
{
	s[0].erase(nd);
	s[nd.val].erase(nd);
	auto itl = s[nd.val].upper_bound(nd);
	auto itr = itl;itl--;
	if(itr != s[nd.val].end()) clst(itr->l,itl->r);
	clst(nd.l,nd.l-1);
}
void Ins(Node nd)
{
	s[0].insert(nd);
	auto itl = s[nd.val].upper_bound(nd);
	auto itr = itl;itl--;
	clst(nd.l,itl->r);
	s[nd.val].insert(nd);
	if(itr != s[nd.val].end()) clst(itr->l,nd.r);
}
int tr[MaxN];
int lowbit(int x){return x & (-x);}
void Upd(int x,int y){for(;x <= n;x += lowbit(x)) tr[x] += y;}
int Qry(int x){int res = 0;for(;x;x -= lowbit(x)) res += tr[x];return res;}
void merge(int l,int r)
{
	//cout<<l<<" "<<r<<endl;
	if(l == r) return ;
	merge(l,mid),merge(mid+1,r);
	int pl = l,pr = mid + 1,p = l;
	while(pl <= mid && pr <= r)
	{
		if(a[pl].x <= a[pr].x)
		{
			if(a[pl].op == 0) Upd(a[pl].y+1,a[pl].v);
			b[p++] = a[pl++];
		}
		else
		{
			if(a[pr].op == 1) ans[a[pr].v] += Qry(a[pr].y);
			b[p++] = a[pr++];
		}
	}
	while(pl <= mid)
	{
		if(a[pl].op == 0) Upd(a[pl].y+1,a[pl].v);
		b[p++] = a[pl++];
	}
	while(pr <= r)
	{
		if(a[pr].op == 1) ans[a[pr].v] += Qry(a[pr].y);
		b[p++] = a[pr++];
	}
	for(int i = l;i <= mid;i++) if(a[i].op == 0)Upd(a[i].y+1,-a[i].v);
	for(int i = l;i <= r;i++) a[i] = b[i];
	//for(int i = 1;i <= n;i++) if(tr[i] != 0)puts("Err");
}
int main()
{
	s[0].insert(Node{0,0,0});
	n = read();
	int Q = read(); 
	for(int i = 1;i <= n;i++)
	{
		int x = read();
		if(!mp[x]) mp[x] = ++cnt,s[cnt].insert(Node{0,0,0});x = mp[x];
		s[0].insert(Node{i,i,x});
		auto it = s[x].end();it--;Node t = *it;
		a[++m] = Opt{0,i,lst[i] = t.l,1};
		s[x].insert(Node{i,i,x});
	}
	while(Q--)
	{
		int op = read(),l = read(),r = read();
		if(op == 1)
		{
			int x = read();
			if(!mp[x]) mp[x] = ++cnt;x = mp[x];
			auto itl = Split(l),itr = Split(r+1);
			for(auto itx = itr;itl != itr;)
			{
				itx--;
				Era(*itr);
				itr = itx;
			}
			Ins(Node{l,r,x});
		}
		else a[++m] = Opt{1,r,l,++q},ans[q] = -l+1;
	}
/*	cout<<m<<endl;
	for(int i = 1;i <= m;i++)
	{
		cout<<a[i].op<<" "<<a[i].x<<" "<<a[i].y<<" "<<a[i].v<<endl;
	}*/
	merge(1,m);
	for(int i = 1;i <= q;i++) printf("%d\n",ans[i]);
	xsc akioi;
}