萌新布吉岛为什么一个正常的线段树维护全部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