萌新求条

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,c;
int a[100010],t[400010],t1[400010],t2[400010];
inline void read(int &x){
	char ch;
	while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Node{
	int l,r;
	mutable int c;
	bool operator<(const Node &a)const{
		return l<a.l;
	}
};
set<Node> s;
inline set<Node>::iterator Split(int x){
	set<Node>::iterator it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x){
		return it;
	}
	it--;
	if(it->r<x) return s.end();
	int l=it->l,r=it->r,c=it->c;
	s.erase(it);
	s.insert({l,x-1,c});
	return s.insert({x,r,c}).first;
}
inline void Addign(int l,int r,int c){
	set<Node>::iterator rr=Split(r+1),ll=Split(l);
	s.erase(ll,rr);
	s.insert({l,r,c});
}
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void push_up(int p){t[p]=t[ls(p)]+t[rs(p)];t1[p]=min(t1[ls(p)],t1[rs(p)]);t2[p]=max(t2[ls(p)],t2[rs(p)]);}
inline void build(int p,int l,int r){
	if(l==r){
		t[p]=a[l];
		t1[p]=a[l];
		t2[p]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
inline void Updata(int L,int R,int p,int l,int r,int d){
	if(L<=l&&r<=R){
		t[p]=d;
		t1[p]=d;
		t2[p]=d;
		return;
	}
	int mid=l+r>>1;
	if(L<=mid) Updata(L,R,ls(p),l,mid,d);
	if(R>mid) Updata(L,R,rs(p),mid+1,r,d);
	push_up(p);
}
inline int Query(int L,int R,int p,int l,int r){
	if(L>R) return 0; 
	if(L<=l&&r<=R){
		return t[p];
	}
	int mid=l+r>>1,s=0;
	if(L<=mid) s+=Query(L,R,ls(p),l,mid);
	if(R>mid) s+=Query(L,R,rs(p),mid+1,r);
	return s;
}
inline int query(int L,int R,int p,int l,int r){
	if(L>R) return 0; 
	if(L<=l&&r<=R){
		return t1[p];
	}
	int mid=l+r>>1,s=1e9;
	if(L<=mid) s=min(s,query(L,R,ls(p),l,mid));
	if(R>mid) s=min(s,query(L,R,rs(p),mid+1,r));
	return s;
}
inline int query1(int L,int R,int p,int l,int r){
	if(L>R) return 0; 
	if(L<=l&&r<=R){
		return t2[p];
	}
	int mid=l+r>>1,s=0;
	if(L<=mid) s=max(s,query1(L,R,ls(p),l,mid));
	if(R>mid) s=max(s,query1(L,R,rs(p),mid+1,r));
	return s;
}
int T[110];
signed main(){
//	ios::sync_with_stdio(0);
////	cin.tie(0); cout.tie(0);
//	freopen("ODT.in","r",stdin);
//	freopen("ODT.out","w",stdout);
	read(n);read(m);read(c);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int x;
		read(x);
		s.insert({i,i,x});
	}
	for(int k=1;k<=m;k++){
		int op,l,r,x;
		cin>>op>>l>>r;
		if(op==1){
			Updata(l,l,1,1,n,r);
			a[l]=r;
		}
		if(op==2){
			cin>>x;
			Addign(l,r,x);
		}
		if(op==3){
//			cout<<"3 ";
			if(c==1){
				cout<<query(l,r,1,1,n)<<"\n";
				continue;
			}
			set<Node>::iterator rr=Split(r+1),ll=Split(l);
			set<Node>::iterator li=ll,ri;
			int cnt=0,f=0,ans=1e9,sum=0;
			for(ri=ll;ri!=rr;ri++){
				T[ri->c]++;
				if(T[ri->c]==1) cnt++;
				sum+=Query(ri->l,ri->r,1,1,n);
				if(cnt==c){
					f=1;
					while(cnt==c){
						ans=min(ans,sum-Query(li->l,li->r-1,1,1,n)-Query(ri->l+1,ri->r,1,1,n));
						T[li->c]--;
						if(T[li->c]==0) cnt--;
						sum-=Query(li->l,li->r,1,1,n);
						li++;
					}
				}
			}
			memset(T,0,sizeof(T));
			if(f==0) cout<<"-1\n";
			else cout<<ans<<"\n";
		}
		if(op==4){
//			cout<<"4 ";
			set<Node>::iterator rr=Split(r+1),ll=Split(l);
			set<Node>::iterator li=ll,ri,it;
			int ans=query1(l,r,1,1,n),sum=a[li->r];
			it=ll;it++;
			T[li->c]++;
			for(ri=it;ri!=rr;ri++){
				sum+=a[ri->l];
				T[ri->c]++;
				ans=max(ans,sum);
				if(ri->r!=ri->l){
					while(li!=ri) T[li->c]--,li++;
					sum=a[li->r];
				}
				else if(T[ri->c]>=2){
					while(T[ri->c]>=2){
						T[li->c]--;
						sum-=a[li->r];
						li++;
					}
				}
			}
			cout<<ans<<"\n";
			memset(T,0,sizeof(T)); 
		}
	}
	return 0;
}