线段树，前缀和

刚入手这道题，发现是道差分和前缀和的构造题。

看了数据范围，马上就意识到时间复杂度被卡在了 O(n*log n)。

再看题目，虽然有线段树的味道，但是并未有方法。

支持 单点修改，区间查询 ，但是在查询的时候便发现这个方法是没有意义的。

用常规的方法，时间复杂度是 O(n^2* m) 的，所以思考构造线段树的方式

唯一的方法就是将区间和存入线段树，线段树中的区间 l~r 的value表示以k（l~r）开头往后的m长度的区间和集合中的最大值。

这样问题迎刃而解

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define in inline
#define rint register int
typedef long long LL;
typedef pair<int,int> PII;

in int read()
{
    rint x=0,f=0; register char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}

/*----------code----------*/
const int N=1e5+10;
int a[N],s[N]; //亮度和前缀和 
int n,m,k;

struct Node{
    int l,r;
    int v,tav; //当前懒标记不包含该结点 
}tr[N*4];

void pushup(int u)
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}

void pushdown(int u)
{   
    tr[u<<1].tav+=tr[u].tav,tr[u<<1|1].tav+=tr[u].tav;
    tr[u<<1].v+=tr[u].tav,tr[u<<1|1].v+=tr[u].tav;
    tr[u].tav=0;
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]={l,r,s[l+m]-s[l-1],0};
        return;
    }
    
    tr[u]={l,r};
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int x)
{
    pushdown(u);
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].tav+=x;
        tr[u].v+=x; 
        pushdown(u);
        return;
    }
    
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
}

void output()
{
    for(int i=1;i<=4*n;i++)
        if(tr[i].l==tr[i].r&&tr[i].l)
            cout<<i<<' '<<tr[i].l<<' '<<tr[i].l+m<<' '<<tr[i].v<<' '<<tr[i].tav<<endl;
}

int main()
{
    s[0]=0;
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
    build(1,1,n-m);
    cout<<tr[1].v<<endl;
    
    k=read();
    while(k--)
    {
        int x,y; x=read(),y=read();
        
        modify(1,max(x-m,1),x,y-a[x]);
        a[x]=y;
        
        cout<<tr[1].v<<endl;
    }
    
    return 0;
}

对于第一组数据，取数组最大值即可。
对于前5组数据，和上周的倒数第二题一样，只要将连续\(w+1\)个数的和记录在sum数组里，求sum数组的最大值即可。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,w; cin>>n>>w; w++;
    int a[n+1]; for(int i=1;i<=n;i++) cin>>a[i];
    int sum[n-w+2];
    for(int i=1;i<=n-w+1;i++) sum[i]=0; 
    for(int i=1;i<=w;i++) sum[1] += a[i];
    int maxv = sum[1];
    for(int i=w+1;i<=n;i++) sum[i-w+1] = sum[i-w] + a[i] - a[i-w], maxv = max(maxv, sum[i-w+1]);
    cout<<maxv<<endl;
    return 0;
}

重点是正解的做法。我们其实是在维护sum数组的最大值。
一次单点修改a[i]其实是对\(w\)个连续sum元素进行区间修改，查询是对区间最大值进行查询。
所以想到用 线段树(区间修改，最值查询)。
emmmm 在这里放350分，肯定是一般方法过不了的啦~~~

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100005;
struct Segment_Tree{
    #define lc(x) (x<<1)
    #define rc(x) (x<<1|1)  
    
    struct node{
        int value;
        int lazy;
        int left,right; 
    }T[maxn*4];
    
    void pushup(int x)
    {
        T[x].value = max(T[lc(x)].value, T[rc(x)].value);
    }
    void pushdown(int x)
    {
        T[x].value += T[x].lazy;
        if(T[x].left != T[x].right) 
        {
            T[lc(x)].lazy += T[x].lazy; T[rc(x)].lazy += T[x].lazy;     
        }
        T[x].lazy = 0;
    }
    
    void build(int a[], int n, int now, int l, int r)
    {
        if(l == r)
        {
            T[now] = (node){a[l], 0, l, r};
            return;
        }
        int mid = (l+r)/2;
        build(a, n, lc(now), l, mid);
        build(a, n, rc(now), mid+1, r);
        
        T[now] = (node){
            max(T[lc(now)].value, T[rc(now)].value) ,0, l, r
        };
    }
    
    void modify(int now, int l, int r, int w)
    {
        pushdown(now);
        if(T[now].left > r || T[now].right < l) return;
        if(T[now].left >= l && T[now]. right <= r) 
        {
            T[now].lazy += w;
            pushdown(now);
            return;
        }  
        modify(lc(now), l, r, w);
        modify(rc(now), l, r, w);
        pushup(now);
    }
    int query()
    {
        return T[1].value;
    }
}T;

int main()
{
    int n,w; cin>>n>>w; w++;
    int a[n+1]; for(int i=1;i<=n;i++) cin>>a[i];
    
    int sum[n-w+2];
    for(int i=1;i<=n-w+1;i++) sum[i]=0; 
    for(int i=1;i<=w;i++) sum[1] += a[i];
    for(int i=w+1;i<=n;i++) sum[i-w+1] = sum[i-w] + a[i] - a[i-w];
    
    T.build(sum, n-w+1, 1, 1, n-w+1);
    cout<<T.query()<<endl;
    
    int m;cin>>m; while(m--)
    {
        int x,y; cin>>x>>y;
        T.modify(1, max(1, x-w+1), x, y - a[x]);
        a[x] = y;
        cout<<T.query()<<endl;
    }
    return 0;
}