95分求助
查看原帖
95分求助
110835
彭天宇楼主2020/9/30 07:58
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],tot,maxn;
struct shuzu{
	int st,pl;//?a¨º?????o¨ªrank
	int op;//xor¦Ì??¦Ì 
}s[N*3];
struct fenkuai{
	int l,r,num,tag;
}f[N];
int belong[N*3],ans[N*3],pl[N*3];
int ask[N][4];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
bool cmp(shuzu x,shuzu y){
	return x.st<y.st;
}
void add(int st,int en,int op){
	int b1=belong[st],b2=belong[en];
	if(b1==b2){
		for(int i=st;i<=en;i++)ans[i]^=op;
		return;
	}
	for(int i=st;i<=f[b1].r;i++)ans[i]^=op;
	for(int i=f[b2].l;i<=en;i++)ans[i]^=op;
	for(int i=b1+1;i<=b2-1;i++)f[i].tag^=op;
}
int main(){
	n=read();
	s[++tot].st=0;
	int mIn=2000000010,mAx=-2000000010;
	for(int i=1;i<=n;i++){
		ask[i][3]=read();
		if(ask[i][3]==1){
			ask[i][0]=read();
			ask[i][1]=read();
			ask[i][2]=read();
			mIn=min(mIn,ask[i][0]);
			mIn=min(mIn,ask[i][1]);
			mAx=max(mAx,ask[i][0]);
			mAx=max(mAx,ask[i][1]);
		}
		else{
			ask[i][0]=read();
			ask[i][1]=read();
			mIn=min(mIn,ask[i][0]);
			mAx=max(mAx,ask[i][0]);
		}
	}
	s[++tot].st=mAx+1;
	s[++tot].st=mIn-1;
	s[++tot].st=-1;
	for(int i=1;i<=n;i++){
		int op=ask[i][3];
		if(op==1){
			int x=ask[i][0],y=ask[i][1],z=ask[i][2];
			s[++tot].st=x;
			s[tot].op=z;
			s[++tot].st=y+1;
			s[tot].op=z;
		}
		if(op==2){
			int x=ask[i][0],y=ask[i][1];
			s[++tot].st=x;
			s[tot].op=y;
			s[++tot].st=x+1;
			s[tot].op=y;
		}
		if(op==3){
			int x=ask[i][0],y=ask[i][1];
			s[++tot].st=mIn-1;//¨¢??¨º 
			s[tot].op=y;
			s[++tot].st=x;
			s[tot].op=y;
			s[++tot].st=x+1;
			s[tot].op=y;
		}
	}//??D¨°1|?¨¹¦Ì????TD?¨¨??¨°???¨¹¨¨¡¤?¡§?a¨ª¡¤???? 
	sort(s+1,s+tot+1,cmp);
	int tmp=0;
	for(int i=1;i<=tot;i++){
		if(s[i].st!=s[i-1].st)tmp++;
		s[i].pl=tmp;
		pl[tmp]=s[i].st;//¨°a?£¤?¨¤???? 
	}
	int num=sqrt(tmp);
	for(int i=1;i<=num;i++){
		f[i].l=(i-1)*num+1;
		f[i].r=i*num;
		for(int j=f[i].l;j<=f[i].r;j++)belong[j]=i;
		f[i].num=i;
	}
	if(num*num<tmp){
		f[num+1].l=num*num+1;
		f[num+1].r=tmp;
		f[num+1].num=num+1;
		for(int j=num*num+1;j<=tmp;j++)belong[j]=num+1;
	}
	for(int i=1;i<=tot;i++){
		add(s[i].pl,tmp,s[i].op);
	}
	int maxpl=-2000000010;
	for(int i=1;i<=tmp;i++){
		ans[i]=(ans[i]^f[belong[i]].tag);
		maxn=max(maxn,ans[i]);
	}
	for(int i=1;i<=tmp;i++)
		if(ans[i]==maxn){
			if(abs(maxpl)>abs(pl[i]))maxpl=pl[i];
			if(abs(maxpl)==abs(pl[i])&&maxpl<pl[i])maxpl=pl[i];
		}
	printf("%d %d\n",maxn,maxpl);
	return 0;
}

第六个点对于0处理不过,其他点有0的能过啊

2020/9/30 07:58
加载中...