leetcode 3165. 不包含相邻元素的子序列的最大和

思路

题目中不相邻子序列和的最大值是满足加和性质的，考虑使用线段树，这里我用了4颗线段树，sum[o][l][r]中l=0和l=1分别表示当前区间是否选取左端点作为子序列的一部分，r=0和r=1分别表示当前区间是否选取右端点作为子序列的一部分。接下来就是线段树单点更新。

  1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  2 #define bug(x) cout<<#x<<" is "<<x<<endl
  3 #include <bits/stdc++.h>
  4 #define iter ::iterator
  5 using namespace  std;
  6 typedef long long ll;
  7 typedef pair<int,int>P;
  8 #define pb push_back
  9 #define mk make_pair
 10 #define se second
 11 #define fi first
 12 #define rs o*2+1
 13 #define ls o*2
 14 const int N=1e5+5;
 15 const int mod=1e9+7;
 16 ll sum[N*4][2][2];
 17 vector<int>a;
 18 void up(int o,int l,int r,int pos,int val){
 19     if(l==r){
 20         //printf("o=%d  l=%d  val=%d\n",o,l,val);
 21         if(val<=0)sum[o][1][0]=0;
 22         else sum[o][1][0]=val;
 23         return;
 24     }
 25     int m=(l+r)/2;
 26     if(pos<=m)up(ls,l,m,pos,val);
 27     else up(rs,m+1,r,pos,val);
 28     
 29 
 30     if(l==m&&r==m+1){
 31         sum[o][0][0]=0;
 32         sum[o][0][1]=sum[rs][1][0];
 33         sum[o][1][0]=sum[ls][1][0];
 34         sum[o][1][1]=0;
 35     }
 36     else if(l==m){
 37         sum[o][0][0]=max(sum[rs][0][0],sum[rs][1][0]);
 38         sum[o][0][1]=max(sum[rs][0][1],sum[rs][1][1]);
 39         sum[o][1][0]=sum[ls][1][0]+sum[rs][0][0];
 40         sum[o][1][1]=sum[ls][1][0]+sum[rs][0][1];
 41     }
 42     else if(r==m+1){
 43         sum[o][0][0]=max(sum[ls][0][0],sum[ls][0][1]);
 44         sum[o][0][1]=sum[ls][0][0]+sum[rs][1][0];
 45         sum[o][1][0]=max(sum[ls][1][0],sum[ls][1][1]);
 46         sum[o][1][1]=sum[ls][1][0]+sum[rs][1][0];
 47     }
 48     else{
 49         ll res=sum[ls][0][0]+sum[rs][0][0];
 50 
 51 
 52 
 53         sum[o][0][0]=res;
 54         res=sum[ls][0][1]+sum[rs][0][0];
 55         sum[o][0][0]=max(sum[o][0][0],res);
 56         res=sum[ls][0][0]+sum[rs][1][0];
 57         sum[o][0][0]=max(sum[o][0][0],res);
 58 
 59 
 60         res=sum[ls][1][0]+sum[rs][0][0];
 61         sum[o][1][0]=res;
 62         res=sum[ls][1][0]+sum[rs][1][0];
 63         sum[o][1][0]=max(sum[o][1][0],res);
 64         res=sum[ls][1][1]+sum[rs][0][0];
 65         sum[o][1][0]=max(sum[o][1][0],res);
 66 
 67 
 68         res=sum[ls][0][0]+sum[rs][0][1];
 69         sum[o][0][1]=res;
 70 
 71         res=sum[ls][0][0]+sum[rs][1][1];
 72         sum[o][0][1]=max(sum[o][0][1],res);
 73 
 74         res=sum[ls][0][1]+sum[rs][0][1];
 75         sum[o][0][1]=max(sum[o][0][1],res);
 76 
 77 
 78 
 79         res=sum[ls][1][0]+sum[rs][0][1];
 80         sum[o][1][1]=res;
 81 
 82         res=sum[ls][1][0]+sum[rs][1][1];
 83         sum[o][1][1]=max(sum[o][1][1],res);
 84 
 85         res=sum[ls][1][1]+sum[rs][0][1];
 86         sum[o][1][1]=max(sum[o][1][1],res);
 87     }
 88 }
 89 class Solution {
 90 public:
 91     int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
 92         a=nums;
 93         int n=nums.size();
 94         for(int i=1;i<=n;i++){
 95             sum[i][0][0]=0;
 96             sum[i][0][1]=0;
 97             sum[i][1][0]=0;
 98             sum[i][1][1]=0;
 99         }
100         for(int i=0;i<n;i++){
101             int x=nums[i];
102             up(1,1,n,i+1,x);
103         }
104         //printf("\n\n");
105         ll ans=0;
106         int cnt=0;
107         for(auto v:queries){
108             cnt++;
109             int x=v[0];
110             int y=v[1];
111             up(1,1,n,x+1,y);
112             ll res=0;
113             res=max(res,sum[1][0][0]);
114             res=max(res,sum[1][0][1]);
115             res=max(res,sum[1][1][0]);
116             res=max(res,sum[1][1][1]);
117             //bug(res);
118             ans=(ans+res)%mod;
119             // for(int i=1;i<=n;i++){
120             //     printf("i=%d \n",i);
121             //     printf("sum[i]=%d\n",sum[i][0][0]);
122             //     printf("sum[i]=%d\n",sum[i][0][1]);
123             //     printf("sum[i]=%d\n",sum[i][1][0]);
124             //     printf("sum[i]=%d\n",sum[i][1][1]);
125             // }
126             //if(cnt==1)break;
127         }
128 
129         
130         return ans;
131     }
132 };
133 
134 int main(){
135 
136 
137     Solution A;
138 
139     // vector<int>nums={3,5,9};
140 
141     // vector<vector<int>>queries={{1,-2},{0,-3}};
142 
143     vector<int>nums={4,0,-1,-2,3,1,-1};
144 
145     vector<vector<int>>queries={{3,1},{0,-2},{1,-1},{0,-2},{5,4},{6,-3},{6,-2},{2,-1}};
146 
147     cout<<A.maximumSumSubsequence(nums,queries);
148 
149 
150 }