黄题爆冷了怎么办在线等挺急的啊。。。

---

题目背景我很认真地看完了。

我哭了，你们呢？

一拳一个泪目怪

---

这道题一眼看上去就是一个前缀和的。然后我就兴致冲冲地写了一发，交上去10pt，WA声一片。

最初的想法很弱智，我以为他给的星星是按x升序给的。

并且还有一点：星星可能会重合。一个点可能会有多个星星。这些都是我没考虑到的。

所以最好的方法是什么？

直接开一个b数组，记录每一个x坐标的星星亮度。

询问的话就先预处理个前缀和，然后进行\(n\)次\(O(1)\)的询问。复杂度\(O(n)\)。

代码：

#include
    
     #include
     
      const int maxn = 100005;int maxx;int b[maxn];int n, w;int main(){    scanf("%d%d", &n, &w);    for(int i = 1; i <= n; i++)    {        int xx, bb; scanf("%d%d", &xx, &bb);        b[xx] += bb;        maxx = std::max(maxx, xx);    }    for(int i = 1; i <= maxx; i++) b[i] += b[i - 1];    int ans = -19260817;    for(int i = 1; i + w - 1 <= maxx; i++)    {        ans = std::max(ans, b[i + w - 1] - b[i - 1]);    }    printf("%d\n", ans);    return 0;}