自动搬运

查看原文

来自洛谷，原作者为

	letitdown エミリアたんマジ天使！

搬运于2025-08-24 22:39:05，当前版本为作者最后更新于2022-07-31 09:38:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们考虑使用 std::set 维护每种颜色出现的连续段。

下面对于一个连续段使用 $L,R$ 表示，对于一个询问区间使用 $l,r$ 表示。

对于一次询问，我们钦定一种颜色的贡献由 $[l,r]$ 包含或相交的最左端的 $[L,R]$ 给出。

那么若现在在颜色 $c$ 中有两个相邻的连续段 $[L_1,R_1]$,$[L_2,R_2]$，那么第二个连续段的贡献形式就是对于 $l\in(R_1,R_2],r\in[L_2,n]$ 的询问答案增加 $c$ 。删除一个连续段的贡献形式是类似的。

对于这样的矩形加单点查形式，我们考虑使用树套树或者 KD 树维护，由于颜色段均摊，复杂度是 $O(nlog^2n)$ 或者 $O(n\sqrt{n})$ 的。

但是本题的空间限制不能满足树套树 $O(n\log^2n)$ 的需求，使用 KD 树的常数较大，不能保证通过本题。

但是我们发现本题并没有强制在线，所以把所有操作离线下来进行 CDQ 分治即可。

时间复杂度 $O(n\log^2n)$，空间复杂度 $O(n)$。

Code

#include<set>
#include<cassert>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
namespace EMT{
	typedef long long ll;typedef double db;
	#define pf printf
	#define F(i,a,b) for(int i=a;i<=b;i++)
	#define D(i,a,b) for(int i=a;i>=b;i--)
	inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
	inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}
	inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}
	inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}
	const int N=1e5+10;
	struct qs{int opt,x,l,r,v;friend bool operator <(qs a,qs b){return a.x<b.x;}}q[N*10];
	int n,m,qcnt;
	struct BIT{
		ll t[N];
		inline void add(int x,int v){while(x<=n)t[x]+=v,x+=x&-x;}
		inline void add(int l,int r,int v){add(l,v),add(r+1,-v);}
		inline ll ask(int x){ll ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
	}bit;
	ll ans[N];
	struct dp{int l,r;friend bool operator <(dp a,dp b){return a.l<b.l;}};
	std::set<dp>s[N];
	inline void add(int l,int r,int ql,int qr,int v){
		q[++qcnt]={1,l,ql,qr,v},
		q[++qcnt]={1,r+1,ql,qr,-v};
	}
	inline int ask(std::set<dp> &s,std::set<dp>::iterator it){
		if(it==s.begin())return 1;it--;return it->r+1;
	}
	inline void ins(int v,int l,int r){
		if(1){
			auto it=s[v].upper_bound({r,r});
			if(it!=s[v].begin()){
				it--;
				if(it->r>=r&&it->l<=l)return;
			}
		}
		auto it=s[v].upper_bound({r,r});bool fl=0;
		if(it!=s[v].end()){
			add(ask(s[v],it),it->r,it->l,n,-v);
			if(it->l==r+1){r=it->r;it=s[v].erase(it);fl=1;}
		}
		while(it!=s[v].begin()){
			it--;
			if(l<=it->l&&it->r<=r){add(ask(s[v],it),it->r,it->l,n,-v);it=s[v].erase(it);continue;}
			if(it->r+1<l)break;
			if(it->r+1==l){add(ask(s[v],it),it->r,it->l,n,-v);l=it->l;s[v].erase(it);break;}
			if(it->r>r){add(ask(s[v],it),it->r,it->l,n,-v);r=it->r;it=s[v].erase(it);continue;}
			assert(it->l<=l);l=it->l;add(ask(s[v],it),it->r,it->l,n,-v);it=s[v].erase(it);break;
		}
		if(!fl){
			it=s[v].upper_bound({r,r});
			if(it!=s[v].end())add(r+1,it->r,it->l,n,v);
		}
		it=s[v].insert({l,r}).first;add(ask(s[v],it),r,l,n,v);
	}
	inline void cdq(int l,int r){
		if(l==r)return;
		int mid=(l+r)>>1;
		cdq(l,mid),cdq(mid+1,r);
		std::sort(q+l,q+mid+1),
		std::sort(q+mid+1,q+r+1);
		int j=l;
		F(i,mid+1,r){
			while(q[i].x>=q[j].x&&j<=mid){
				if(q[j].opt==1)bit.add(q[j].l,q[j].r,q[j].v);
				j++;
			}if(q[i].opt==2)ans[q[i].v]+=bit.ask(q[i].r);
		}
		while(j>l){
			j--;
			if(q[j].opt==1)bit.add(q[j].l,q[j].r,-q[j].v);
		}
	}
	inline short main(){
		n=read();m=read();
		memset(ans,-1,sizeof(ans));
		F(i,1,m){
			int opt=read(),l=read(),r=read();
			if(opt==1){ins(read(),l,r);}
			else q[++qcnt]={2,l,r,r,i},ans[i]=0;
		}
		cdq(1,qcnt);
		F(i,1,m)if(~ans[i])pf("%lld\n",ans[i]);
		return 0;
	}
}
signed main(){return EMT::main();}