洛谷P3353 【在你窗外闪耀的星星】

题目真的好甜呢QwQ

冲着这题面也要来做

---

满分解法：线段树

我们暴力地把所有点建成一颗线段数

接着在从1到maxx里每个长度为 w的区间中执行区间求和

其实单点修改都不需要，可以在输入的时候统计出每个点上星星的亮度和

另：同一点上可能有多个星星

#include<bits/stdc++.h>

#define inf 0x7fffffff

#define ll long long

using namespace std;

#define maxn 100009

struct node{

    int l,r,val;

}tr[maxn*];

int n;

int a[maxn];

void Buildtree(int x,int l,int r)

{

    tr[x].l=l;

    tr[x].r=r;

    if(l==r)

    {

        tr[x].val=a[l];

        return;

    }

    int mid=(l+r)>>;

    Buildtree(x*,l,mid);

    Buildtree(x*+,mid+,r);

    tr[x].val=tr[x*].val+tr[x*+].val;

}

int Query(int x,int l,int r)

{

    if(l<=tr[x].l&&tr[x].r<=r)

    {

        return tr[x].val;

    }

    int mid=(tr[x].l+tr[x].r)/;

    int ans=;

    if(l<=mid) ans+=Query(x*,l,r);

    if(r>mid) ans+=Query(x*+,l,r);

    return ans;

}

int main()

{

    int maxx=;

    int w;

    scanf("%d%d",&n,&w);

    for(int i=;i<=n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        a[x]+=y;

        maxx=max(maxx,x);

    }

    Buildtree(,,maxx);

    //建树的范围是所有点，从1到最大点的位置

    int ans=;

    for(int i=;i<=maxx;i++)

    {

        ans=max(ans,Query(,i,i+w-));//记得w-1

        /*

        窗框算在W之内

        W=3

                框   星  框

                |    *   |

        ------------------------

        */

    }

    printf("%d\n",ans);

    return ;

}