~~前缀和可以做到O(n)~~
吐了,无输出?~~肯定是死循环~~
没想到这么奇怪……
加入``return 0``调试。
发现$query()$ 出锅
结果发现你线段数理解有很大偏差……
build(),query()有多大就多大, build(1,100000,1);不可取
一个小问题:见样例,“边缘取到”意义。
------------
code
```cpp
//注释掉的是错误或无意义的
#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;
long long ans;
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];
}
long long 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;
long long 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);
build(1,n,1);
//for(int i=1;i<=100000-w;i++)
for(int i=1;i<=n-w-1;i++)
{
// ans=max(ans,query(1,n,i,i+w,1));
ans=max(ans,query(1,n,i,i+w-1,1));
}
cout<<ans;
return 0;
}
```
by 龙水流深 @ 2022-01-24 15:28:04
@[洋本羊](/user/292069)
by 龙水流深 @ 2022-01-24 15:28:30
@[龙水流深](/user/231704) 谢谢大佬!刚学线段树和查询,想找题练手,自学可能理解还是不到位qwq继续努力
by 洋本羊 @ 2022-01-24 18:42:03
~~这题难度堪比红题~~
by _buzhidao_ @ 2023-05-04 13:05:24