线段树做法绞尽脑汁debug WA 0pts求助
查看原帖
线段树做法绞尽脑汁debug WA 0pts求助
473531
zpw_bth楼主2023/4/6 21:40

求帮助qwq,悬赏关注*1

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,l[200005],r[200005],lsh[200005],len,maxn,id,yr[200005];
int sum[1600005],ltag[1600005];


void pushdown(int o,int l,int r){
	if(ltag[o]){
		ltag[o*2]+=ltag[o];
		ltag[o*2+1]+=ltag[o];
		sum[o*2]+=ltag[o]*l;
		sum[o*2+1]+=ltag[o]*r;
		ltag[o]=0;
	}
	return ;
}


void update(int l,int r,int x,int y,int k,int o){
	if(x<=l&&r<=y){
		sum[o]+=(r-l+1)*k;
		ltag[o]+=k;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(o,mid-l+1,r-mid);
	if(x<=mid){
		update(l,mid,x,y,k,o*2);
	}
	if(y>mid){
		update(mid+1,r,x,y,k,o*2+1);
	}
	sum[o]=sum[o*2]+sum[o*2+1];
}


int query(int l,int r,int x,int y,int o){
	if(x<=l&&r<=y){
		return sum[o];
	}
	int mid=(l+r)>>1;
	pushdown(o,mid-l+1,r-mid);
	int maxn=0;
	if(x<=mid){
		maxn=max(maxn,query(l,mid,x,y,o*2));
	}
	if(y>mid){
		maxn=max(maxn,query(mid+1,r,x,y,o*2+1));
	}
	return maxn;
}


signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		lsh[++len]=l[i];
		lsh[++len]=r[i];
	}
	sort(lsh+1,lsh+len+1);
	len=unique(lsh+1,lsh+len+1)-lsh;
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(lsh,lsh+len+1,l[i])-lsh;
		yr[i]=r[i];
		r[i]=lower_bound(lsh,lsh+len+1,r[i])-lsh;
	}
	for(int i=1;i<=n;i++){
		update(1,400000,l[i],r[i],1,1);
	}
	for(int i=1;i<=n;i++){
		if(query(1,400000,r[i],r[i],1)>=maxn){
			maxn=query(1,400000,r[i],r[i],1);
			id=yr[i];
		}
	}
	cout<<id*maxn;
}
2023/4/6 21:40
加载中...