C++ 解法, 执行用时: 193ms, 内存消耗: 9048K, 提交时间: 2021-12-11 12:35:13

#include<bits/stdc++.h>
using namespace std;
int mk[100010];
struct tup{
	int l,r,w,p;
	bool operator<(tup x)const{
		return l<x.l;
	}
};
set<tup>st;
set<tup>::iterator it;
int ans[100010],a[100010],fa[100010],sk[100010];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	int n,m,t;
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		mk[a[i]]=i;fa[i]=i;
	}
	for(int i=1;i<=m;++i)st.insert((tup){i,i,0,mk[i]});
	while(t--){
		int f;
		scanf("%d",&f);
		if(f==1){
			int x,l,r,p,cnt=0;
			scanf("%d%d%d%d",&x,&l,&r,&p);
			it=st.upper_bound((tup){r,0,0,0});
			int ans1=(r-l+1)*p,ans2=0,ans3=0;
			--it;
			while(1){
				int l1=it->l,r1=it->r,w1=it->w,p1=it->p;
				if(r1<l)break;
				--it;
				st.erase((tup){l1,r1,w1,p1});
				p1=find(p1);
				int l2=max(l1,l),r2=min(r1,r);
				if(p1==x)ans2+=w1*(r2-l2+1);
				else{
					ans3+=w1*(r2-l2+1);
					ans[p1]-=w1*(r2-l2+1);
					if(l2<=a[p1]&&r2>=a[p1])sk[++cnt]=p1;
				}
				if(l1<l)st.insert((tup){l1,l-1,w1,p1});
				if(r1>r)st.insert((tup){r+1,r1,w1,p1});
			}
			st.insert((tup){l,r,p,x});
			ans[x]+=ans1-ans2;
			printf("%d\n",ans1-ans2+ans3);
			for(int i=1;i<=cnt;++i)fa[sk[i]]=x,ans[x]+=ans[sk[i]];
		}
		else{
			int x;
			scanf("%d",&x);
			printf("%d\n",ans[x]);
		}
	}
	for(int i=1;i<=n;++i)if(fa[i]==i)printf("%d\n",i);
}