关于MLE
查看原帖
关于MLE
178556
Skyjoy楼主2020/4/26 22:57

萌新布吉岛为什么一个正常的线段树维护全部MLE了啊

代码:

#include<bits/stdc++.h>
#define N 100010
#define ls(x) x*2
#define rs(x) x*2+1
using namespace std;
int n,m,maxn[N],minn[N],tree[N*4],mp[N],inf=1e9,t,ans;
struct node{
	int x,y;
	bool operator<(node b){
		if(y==b.y){
			return x<b.x;
		}
		return y>b.y;
	}
}p[N];
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<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void change(int x,int l,int r,int q,int y){
	tree[x]+=y;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	if(q<=mid){
		change(ls(x),l,mid,q,y);
	}
	else{
		change(rs(x),mid+1,r,q,y);
	}
}
int query(int x,int l,int r,int qx,int qy){
	if(qx<=l&&qy<=r){
		return tree[x];
	}
	int res=0,mid=(l+r)/2;
	if(qx<=mid){
		res+=query(ls(x),l,mid,qx,qy);
	}
	if(qy>mid){
		res+=query(rs(x),mid+1,r,qx,qy);
	}
	return res;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		p[i].x=read(),p[i].y=read();
		mp[i]=p[i].x;
		maxn[i]=-inf,minn[i]=inf;
	}
	sort(p+1,p+n+1);
	sort(mp+1,mp+n+1);
	m=unique(mp+1,mp+n+1)-mp-1;
	for(int i=1;i<=n;i++){
		p[i].x=lower_bound(mp+1,mp+m+1,p[i].x)-mp;
		maxn[p[i].x]=max(maxn[p[i].x],p[i].y);
		minn[p[i].x]=min(minn[p[i].x],p[i].y);
	}
	t=p[1].x,p[n+1].y=inf;
	for(int i=1;i<=n;i++){
		if(p[i].y==maxn[p[i].x]){
			change(1,1,m,p[i].x,1);
		}
		if(p[i].y==minn[p[i].x]){
			ans++;
			change(1,1,m,p[i].x,-1);
		}
		if(p[i].y!=p[i+1].y){
			ans+=query(1,1,m,t,p[i].x);
			t=p[i+1].x;
		}
	}
	printf("%d",ans);
	return 0;
}

qwq

2020/4/26 22:57
加载中...