文件详细信息

下载本文件

本文件的大小为 1984 字节。

#include<cstdio>
#include<cstring>
#include<queue>
void read(int&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
void write(int a){
	static int ch[20],cnt;
	cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
inline int max(const int a,const int b){
	return a>b?a:b;
}
inline void chkmax(int&a,const int b){
	a<b&&(a=b);
}
const int maxn=200005;
std::priority_queue<int>Q[maxn<<2];
int s[maxn<<2];
void pushup(int u,int mode){
	s[u]=max(Q[u].empty()?-1:Q[u].top(),mode?max(s[u<<1],s[u<<1|1]):-1);
}
void change(int u,int v){
	Q[u].push(v);
	chkmax(s[u],v);
}
void insert(int u,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr)return change(u,v);
	int m=(l+r)>>1;
	if(ql<=m)insert(u<<1,l,m,ql,qr,v);
	if(qr>m)insert(u<<1|1,m+1,r,ql,qr,v);;
	pushup(u,l<r);
}
int ans;
void query(int u,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return chkmax(ans,s[u]);
	chkmax(ans,Q[u].empty()?-1:Q[u].top());
	int m=(l+r)>>1;
	if(ql<=m)query(u<<1,l,m,ql,qr);
	if(qr>m)query(u<<1|1,m+1,r,ql,qr);
}
void del(int u,int l,int r,int ql,int qr,int v){
	if(s[u]<v)return;
	if(ql<=l&&r<=qr){
		if(!Q[u].empty()&&Q[u].top()==v){
			Q[u].pop();
			pushup(u,l<r);
			return;
		}
		if(l==r)return;
		int m=(l+r)>>1;
		del(u<<1,l,m,ql,qr,v);
		del(u<<1|1,m+1,r,ql,qr,v);
		pushup(u,l<r);
		return;
	}
	if(!Q[u].empty()&&Q[u].top()==v){
		Q[u].pop();
		change(u<<1,v);
		change(u<<1|1,v);
	}
	int m=(l+r)>>1;
	if(ql<=m)del(u<<1,l,m,ql,qr,v);
	if(qr>m)del(u<<1|1,m+1,r,ql,qr,v);
	pushup(u,l<r);
}
int n,m,op,l,r,k;
int main(){
	read(n),read(m);
	memset(s+1,-1,sizeof(int)*n*4);
	for(int i=1;i<=m;i++){
		read(op),read(l),read(r);
		if(op==1){
			read(k);
			insert(1,1,n,l,r,k);
		}else if(op==2){
			ans=-1;
			query(1,1,n,l,r);
			if(ans!=-1)del(1,1,n,l,r,ans);
		}else{
			ans=-1;
			query(1,1,n,l,r);
			write(ans),putchar('\n');
		}
	}
	return 0;
}