线段树无输出求大佬看
查看原帖
线段树无输出求大佬看
292069
洋本羊楼主2022/1/24 14:58
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,w,t;
long long tree[400020],x,b,a[100005];
int ans=-1;
void build(int l,int r,int fa)//½¨Ê÷
{
	if(l==r)
	{
		tree[fa]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,fa*2);
	build(mid+1,r,fa*2+1);
	tree[fa]=tree[fa*2]+tree[fa*2+1];
}
int query(int l,int r,int ll,int rr,int fa)
{
    if(ll<=l&&rr>=r)
    {
        return tree[fa];
    }
    int mid=(l+r)/2;
    int ans=0;
    if(ll<=mid)
    {
        ans+=query(l,mid,ll,rr,2*fa);
    }
    if(rr>mid)
    {
        ans+=query(mid+1,r,ll,rr,2*fa+1);
    }
    return ans;
}
int main()
{
	cin>>n>>w;
	if(w==0)
    {
        cout<<0;
        return 0;
    }
	for(int i=1;i<=n;i++)
	{
		cin>>x>>b;
		a[x]+=b;
	}
	build(1,100000,1);
    for(int i=1;i<=100000-w;i++)
    {
        ans=max(ans,query(1,n,i,i+w,1));
    }
    cout<<ans;
	return 0;
}
2022/1/24 14:58
加载中...