权值线段树+整体二分,样例不过求调
查看原帖
权值线段树+整体二分,样例不过求调
616964
Adolfo_North楼主2024/4/13 22:11

疑似是线段树的sb问题

#include <bits/stdc++.h>
using namespace std;
#define p2 p<<1
#define p3 p<<1|1
const int N=1e5+7;
int n,m;
struct Juice{
	int d,p,l;
	bool operator <(Juice x) {
		return d>x.d;
	}
}a[N];
struct kids{
	long long g,l;
	int id;
}q[N],q1[N],q2[N];
int vol[N<<2],mon[N<<2],idx;
int ans[N];
void pushup(int p){
	vol[p]=vol[p2]+vol[p3];
	mon[p]=mon[p2]+mon[p3];
}
void add(int p,int l,int r,int Jp,int Jl){
	if(l==r){
		vol[p]+=Jp;
		mon[p]=vol[p]*Jl;
		return;
	}
	int mid=l+r>>1;
	if(Jp<=mid) add(p2,l,mid,Jp,Jl);
	else add(p3,mid+1,r,Jp,Jl);
	pushup(p);
}
long long query(int p,int l,int r,int v){
	if(!v) return 0;
	if(l==r) return l*v;
	int mid=l+r>>1;
	if(vol[mid]>=v) return query(p2,l,mid,v);
	else return mon[p2]+query(p3,mid+1,r,v);
}
void Work(int l,int r,int L,int R){
//	cout<<l<<' '<<r<<' '<<L<<' '<<R<<'\n';;;
	if(l>r) return;
	if(L==R){
		for(int i=l;i<=r;i++) ans[q[i].id]=a[L].d;
		return;
	}
	int mid=L+R>>1,p0=0,p1=0;
	while(idx<mid) idx++,add(1,1,N,a[idx].p,a[idx].l);
	while(idx>mid) add(1,1,N,a[idx].p,-a[idx].l),idx--;
	for(int i=l;i<=r;i++){
		int lin=query(1,1,N,q[i].l);
//		cout<<lin<<' ';
		if(vol[1]>=q[i].l&&query(1,1,N,q[i].l)<=q[i].g) q1[++p0]=q[i];
		else q2[++p1]=q[i];
	}
//	cout<<'\n';
	for(int i=1;i<=p0;i++) q[l+i-1]=q1[i];
	for(int i=1;i<=p1;i++) q[l+p0+i-1]=q2[i];
	Work(l,l+p0-1,L,mid);
	Work(l+p0,r,mid+1,R);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i].d>>a[i].p>>a[i].l;
	a[++n]={-1,0,0};
	sort(a+1,a+1+n);
	for(int i=1;i<=m;i++){
		cin>>q[i].g>>q[i].l;
		q[i].id=i;
	}
	Work(1,m,1,n);
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}
2024/4/13 22:11
加载中...