题目描述

Description

约翰有N 台挤奶机器，这些机器排成了一条直线，其中第i台机器工作效率是Ai，也就是说工作一天可以产出Ai。约翰将会开动这些机器工作Q 天。每天一早，约翰一定会维修一台机器。在第i 天早上，他维修的是第Ti 台机器，经过维修之后，这台机器的工作效率将会变成Di。在任何时候，位置相邻的两台机器都不能同时工作。请问约翰每天应该选择开动哪些机器，才能让这Q 天的总产出之和最大？

题目分析

类似小白逛公园的线段树
维护 max_l,max_r,max_all,max_none,max_maxx
分别代表 只选左端点，只选右端点，左右端点都选，左右端点都不选，以上四个值的最大值
我们来推公式辣！注意区间中的任意两个端点不能相邻

a[num].all=max(a[num<<1].l+a[num<<1|1].r,a[num<<1].all+a[num<<1|1].r,a[num<<1].l+a[num<<1|1].all);
a[num].none=max(a[num<<1].none+a[num<<1|1].none,a[num<<1].r+a[num<<1|1].none,a[num<<1].none+a[num<<1|1].l);
a[num].l=max(a[num<<1].l+a[num<<1|1].l,a[num<<1].all+a[num<<1|1].none,a[num<<1].l+a[num<<1|1].none);
a[num].r=max(a[num<<1].r+a[num<<1|1].r,a[num<<1].none+a[num<<1|1].all,a[num<<1].none+a[num<<1|1].r);
a[num].max=max(a[num].all,a[num].none,a[num].l,a[num].r);

最终累计a[1].max_maxx就是答案辣！记得开long long！

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int c[40100];
struct your
{
    long long l;
    long long r;
    long long none;
    long long all;
    long long max;
    int x,y;
}a[200000];
void push_up(int num)
{
    a[num].all=max(a[num<<1].l+a[num<<1|1].r,max(a[num<<1].all+a[num<<1|1].r,a[num<<1].l+a[num<<1|1].all));
    a[num].none=max(a[num<<1].none+a[num<<1|1].none,max(a[num<<1].r+a[num<<1|1].none,a[num<<1].none+a[num<<1|1].l));
    a[num].l=max(a[num<<1].l+a[num<<1|1].l,max(a[num<<1].all+a[num<<1|1].none,a[num<<1].l+a[num<<1|1].none));
    a[num].r=max(a[num<<1].r+a[num<<1|1].r,max(a[num<<1].none+a[num<<1|1].all,a[num<<1].none+a[num<<1|1].r));
    a[num].max=max(max(a[num].all,a[num].none),max(a[num].l,a[num].r));
    return ;
}
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy)
    {
        a[num].all=c[dx];
        return ;
    }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1);
    build(mid+1,dy,num<<1|1);
    push_up(num);
}
void update(int x,int tmp,int num)
{
    if(a[num].x==x&&a[num].y==x)
    {
        a[num].all=tmp;
        return ;
    }
    int mid=(a[num].x+a[num].y)>>1;
    if(x<=mid) update(x,tmp,num<<1);
    else update(x,tmp,num<<1|1);
    push_up(num);
}
long long ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int x,tmp;
        scanf("%d%d",&x,&tmp);
        update(x,tmp,1);
        ans+=a[1].max;
    }
    printf("%lld",ans);
}