Magician（线段树+dp）

题目链接：点击打开链接

题目大意：给出n个数，m次操作，有两种操作，0 l r 询问[l,r]内的一个序列最大和为多少，要求该序列的相邻的位置奇偶性不同，可以不连续；1 k x将第k个位置的数换位x

因为只要求奇偶性不同，所以一个序列的最大值有四种情况，偶数开始偶数结束，偶数开始奇数结束，，奇数开始偶数奇数，奇数开始奇数结束。可以用一个数组表示，0表示偶数，1表示奇数，那么a[0][0],a[0][1],a[1][0],a[1][1]就能表示这四种情况了，查询[l,r]用线段树维护一下这四个值，注意在合并的时候的全部情况

dp[rt].a[i][j] = max(dp[rt<<1].a[i][j],dp[rt<<1|1].a[i][j])

dp[rt].a[i][j] = max(dp[rt].a[i][j],dp[rt<<1].a[i][0]+dp[rt<<1|1].a[1][j]) ;dp[rt].a[i][j] = max(dp[rt].a[i][j],dp[rt<<1].a[i][1]+dp[rt<<1|1].a[0][j]) ;

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std ;#define LL __int64#define root 1,n,1#define int_rt int l,int r,int rt#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define maxn 100010struct node{LL a[2][2] ;}dp[maxn<<2] , p , q ;void push_up(int rt) {int i , j ;for(i = 0 ; i < 2 ; i++){for(j = 0 ; j < 2 ; j++) {dp[rt].a[i][j] = max(dp[rt<<1].a[i][j],dp[rt<<1|1].a[i][j]) ;dp[rt].a[i][j] = max(dp[rt].a[i][j],dp[rt<<1].a[i][0]+dp[rt<<1|1].a[1][j]) ;dp[rt].a[i][j] = max(dp[rt].a[i][j],dp[rt<<1].a[i][1]+dp[rt<<1|1].a[0][j]) ;}}return ;}void create(int_rt) {if( l == r ) {LL x ;scanf("%I64d", &x) ;dp[rt].a[0][0] = dp[rt].a[0][1] = dp[rt].a[1][0] = dp[rt].a[1][1] = -(LL)1e16 ;dp[rt].a[l%2][l%2] = x ;return ;}create(lson) ;create(rson) ;push_up(rt) ;}void update(int k,LL x,int_rt) {if( l == r ) {dp[rt].a[0][0] = dp[rt].a[0][1] = dp[rt].a[1][0] = dp[rt].a[1][1] = -(LL)1e16 ;dp[rt].a[l%2][l%2] = x ;return ;}int mid = (l+r)/2 ;if(k <= mid) update(k,x,lson) ;else update(k,x,rson) ;push_up(rt) ;}node query(int ll,int rr,int_rt) {if( ll <= l && rr >= r ){return dp[rt] ;}int i , j , mid = (l+r)/2 ;node s1 , s2 , temp ;s1.a[0][0] = s1.a[0][1] = s1.a[1][0] = s1.a[1][1] = -(LL)1e16 ;s2.a[0][0] = s2.a[0][1] = s2.a[1][0] = s2.a[1][1] = -(LL)1e16 ;if( ll <= mid ) s1 = query(ll,rr,lson) ;if( rr > mid ) s2 = query(ll,rr,rson) ;for(i = 0 ; i < 2 ; i++){for(j = 0 ; j < 2 ; j++) {temp.a[i][j] = max(s1.a[i][j],s2.a[i][j]) ;temp.a[i][j] = max(temp.a[i][j],s1.a[i][0]+s2.a[1][j]) ;temp.a[i][j] = max(temp.a[i][j],s1.a[i][1]+s2.a[0][j]) ;}}return temp ;}int main() {int t , n , m , i , j ;int k , l , r ;LL max1 , x ;scanf("%d", &t) ;while( t– ) {scanf("%d %d", &n, &m) ;create(root) ;while( m– ) {scanf("%d", &k) ;if( !k ) {scanf("%d %d", &l,&r) ;p = query(l,r,root) ;max1 = -(LL)1e16 ;for(i = 0 ; i < 2 ; i++)for(j = 0 ; j < 2 ; j++)max1 = max(max1,p.a[i][j]) ;printf("%I64d\n", max1) ;}else {scanf("%d %I64d", &k, &x) ;update(k,x,root) ;}}}return 0 ;}

你并不一定会从此拥有更美好的人生，

相关文章：

你感兴趣的文章：

标签云：