求助线段树动态开点
  • 板块学术版
  • 楼主Adolfo_North
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/7 09:01
  • 上次更新2024/10/7 10:46:32
查看原帖
求助线段树动态开点
616964
Adolfo_North楼主2024/10/7 09:01

为什么 query 中注释掉的那句话不能加上去啊?

#include<bits/stdc++.h>
using namespace std;
const int N=150000,M=1e9;
#define p1 p<<1
#define p2 p<<1|1
int n,m;
struct node{
	int l,r;
	long long w,tag;
}tr[N*60];
int tag[N*60];
int tot=1;
void upd(int &p,int l,int r,int x,int y,long long k){
	if(!p) p=++tot;
	tr[p].w+=(min(r,y)-max(l,x)+1)*k;
	if(l>=x&&r<=y){
		tr[p].tag+=k;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) upd(tr[p].l,l,mid,x,y,k);
	if(y>mid) upd(tr[p].r,mid+1,r,x,y,k);
}
long long query(int p,int l,int r,int x,int y,long long tag){
//	if(!p) return 0;
	if(l>=x&&r<=y) return tr[p].w+tag*(min(r,y)-max(l,x)+1);
	int mid=l+r>>1;
	long long res=0;
	if(x<=mid) res+=query(tr[p].l,l,mid,x,y,tag+tr[p].tag);
	if(y>mid) res+=query(tr[p].r,mid+1,r,x,y,tag+tr[p].tag);
	return res;
}
signed main(){
	freopen("kingdomrush.in","r",stdin);
	freopen("kingdomrush.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,l,r,w;i<=n;i++){
		cin>>l>>r>>w;
		int tmp=1;
		upd(tmp,1,M,l,r,w);
	}
	while(m--){
		int x;
		long long h;
		cin>>x>>h;
		if(query(1,1,M,x+1,M,0)<h){
			cout<<"-1\n";
			continue;
		}
		int l=x+1,r=M,ans=-1,mid;
		while(l<=r){
			mid=l+r>>1;
			if(query(1,1,M,x+1,mid,0)>=h) ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<ans-x<<'\n';
	}
	return 0;
}
2024/10/7 09:01
加载中...