P3097 [USACO13DEC]最优挤奶Optimal Milking

题意简述：给定n个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案

感谢@zht467 提供翻译

---

错误日志： 又双叒叕没开long long

---

Solution

考虑线段树维护

只有四种情况， 选择左端点与否 \(*\) 选择右端点与否

共四种情况

维护这四个便可以上推了

void pushup(LL id){    tree[id].ans[0][0] = max(tree[lid].ans[0][0] + tree[rid].ans[1][0], tree[lid].ans[0][1] + tree[rid].ans[0][0]);    tree[id].ans[0][1] = max(tree[lid].ans[0][0] + tree[rid].ans[1][1], tree[lid].ans[0][1] + tree[rid].ans[0][1]);    tree[id].ans[1][0] = max(tree[lid].ans[1][0] + tree[rid].ans[1][0], tree[lid].ans[1][1] + tree[rid].ans[0][0]);    tree[id].ans[1][1] = max(tree[lid].ans[1][0] + tree[rid].ans[1][1], tree[lid].ans[1][1] + tree[rid].ans[0][1]);    }

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 80019;LL num, na, a[maxn];#define lid (id << 1)#define rid (id << 1) | 1struct seg_tree{ LL l, r; LL ans[2][2];//0为选，1为不选 }tree[maxn << 2];void pushup(LL id){ tree[id].ans[0][0] = max(tree[lid].ans[0][0] + tree[rid].ans[1][0], tree[lid].ans[0][1] + tree[rid].ans[0][0]); tree[id].ans[0][1] = max(tree[lid].ans[0][0] + tree[rid].ans[1][1], tree[lid].ans[0][1] + tree[rid].ans[0][1]); tree[id].ans[1][0] = max(tree[lid].ans[1][0] + tree[rid].ans[1][0], tree[lid].ans[1][1] + tree[rid].ans[0][0]); tree[id].ans[1][1] = max(tree[lid].ans[1][0] + tree[rid].ans[1][1], tree[lid].ans[1][1] + tree[rid].ans[0][1]); }void build(LL id, LL l, LL r){ tree[id].l = l, tree[id].r = r; if(l == r){ tree[id].ans[1][1] = a[l]; return ; } LL mid = (l + r) >> 1; build(lid, l, mid), build(rid, mid + 1, r); pushup(id); }void update(LL id, LL val, LL l, LL r){ if(tree[id].l == l && tree[id].r == r){ tree[id].ans[1][1] = val; return ; } LL mid = (tree[id].l + tree[id].r) >> 1; if(mid < l)update(rid, val, l, r); else if(mid >= r)update(lid, val, l, r); pushup(id); }LL sum;int main(){ num = RD(), na = RD(); for(LL i = 1;i <= num;i++)a[i] = RD(); build(1, 1, num); for(LL i = 1;i <= na;i++){ LL p = RD(), val = RD(); update(1, val, p, p); LL ans = max(tree[1].ans[0][0], tree[1].ans[0][1]); ans = max(ans, tree[1].ans[1][0]); ans = max(ans, tree[1].ans[1][1]); sum += ans; } printf("%lld\n", sum); return 0; }