蒟蒻刚学线段树，求调

Reverse_Sword_Six @ 2021-04-27 13:08:21

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <math.h>

using namespace std ;

typedef long long ll ;

const int N = 1000005 ;
struct node {
  int l , r ; 
  ll sum , lazy ;//左端点、右端点、区间和、懒标记
  ll pre,suf,maxsum;//最大前缀和，最大后缀和
}tree[N<<2] ;
int n , m , a[N] ;

node merge (node left,node right) {
  node rt ;
  rt.pre = max(left.pre,left.sum+right.pre) ;
  rt.suf = max(right.suf,right.sum+left.suf) ;
  rt.maxsum = max(right.maxsum,max(left.maxsum,left.suf+right.pre)) ;
  rt.sum = left.sum+right.sum ;
  return rt;
}

void build (int root,int l,int r) {
  tree[root].l = l ;
  tree[root].r = r ;
  if(l==r) {
    tree[root].sum = a[l] ;
    tree[root].maxsum = a[l] ;
    tree[root].suf = a[l] ;
    tree[root].pre = a[l] ;
    return ;
  }
  int mid = l + r >> 1 ;
  build(root<<1,l,mid) ;
  build(root<<1|1,mid+1,r) ;
  tree[root] = merge(tree[root<<1],tree[root<<1|1]) ;
}

void add (int root , int id , int k ) {
  if(tree[root].l == tree[root].r) {
    tree[root].sum = tree[root].maxsum = tree[root].suf = tree[root].pre = k ;
    return ;
  }
  int mid = tree[root].l + tree[root].r >> 1 ;
  if(id<=mid) add ( root<<1 , id , k );
  else add ( root<<1|1 , id , k ) ;
  tree[root] = merge(tree[root<<1],tree[root<<1|1]) ;
}

node query ( int root , int l , int r ) {
  node res,lres,rres ;
  if(l<=tree[root].l && r >= tree[root].r ) {
    return tree[root] ; 
  }
  int mid = tree[root].l + tree[root].r >> 1 ;
  int flag1=0 ,flag2=0 ;
  if(l<=m) {lres=query(root<<1,l,r);flag1=1;}
  if(r> m) {rres=query(root<<1|1,l,r);flag2=1;}
  if(flag1&&flag2) res=merge(lres,rres);//合并
  else if(flag1) res=lres;
  else if(flag2) res=rres;
  return res ;
}

int main ( ) {
  ios::sync_with_stdio(false) ;
  cin >> n >> m ;
  for ( int i = 1 ; i <= n ; i ++ ) {
    cin >> a[i] ;
  }
  build(1,1,n) ;
  while(m--) {
    int o , x , y , k ;
    cin >> o ;
    if(o==2) {
      cin >> x >> k ;
      add ( 1 , x , k ) ;
    }
    else {
      cin >> x >> y ;
      if(x>y) swap(x,y) ;
      cout << query(1,x,y).maxsum << endl ;
    }
  }
  //system("pause") ;
}

by Reverse_Sword_Six @ 2021-04-27 13:27:19

啊啊啊

by Reverse_Sword_Six @ 2021-04-27 13:28:27

啊我会了

by chen_qian @ 2021-04-27 13:28:54

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <math.h>

using namespace std ;

typedef long long ll ;

const int N = 1000005 ;
struct node {
  int l , r ; 
  ll sum , lazy ;//左端点、右端点、区间和、懒标记
  ll pre,suf,maxsum;//最大前缀和，最大后缀和
}tree[N<<2] ;
int n , m , a[N] ;

node merge (node left,node right) {
  node rt ;
  rt.pre = max(left.pre,left.sum+right.pre) ;
  rt.suf = max(right.suf,right.sum+left.suf) ;
  rt.maxsum = max(right.maxsum,max(left.maxsum,left.suf+right.pre)) ;
  rt.sum = left.sum+right.sum ;
  return rt;
}
void build (int root,int l,int r) {
  tree[root].l = l ;
  tree[root].r = r ;
  if(l==r) {
    tree[root].sum = a[l] ;
    tree[root].maxsum = a[l] ;
    tree[root].suf = a[l] ;
    tree[root].pre = a[l] ;
    return ;
  }
  int mid = l + r >> 1 ;
  build(root<<1,l,mid) ;
  build(root<<1|1,mid+1,r) ;
  tree[root] = merge(tree[root<<1],tree[root<<1|1]) ;
}

void add (int root , int id , int k ) {
  if(tree[root].l == tree[root].r) {
    tree[root].sum = tree[root].maxsum = tree[root].suf = tree[root].pre = k ;
    return ;
  }
  int mid = tree[root].l + tree[root].r >> 1 ;
  if(id<=mid) add ( root<<1 , id , k );
  else add ( root<<1|1 , id , k ) ;
  tree[root] = merge(tree[root<<1],tree[root<<1|1]) ;
}

node query ( int root , int l , int r ) {
  node res,lres,rres ;
  //cout<<root<<endl;
  if(l<=tree[root].l && r >= tree[root].r ) {
    cout<<tree[root].l<<' '<<tree[root].r<<endl;//加上这句话，自己看成什么样了
    return tree[root] ; 
  }
  int mid = tree[root].l + tree[root].r >> 1 ;
  int flag1=0 ,flag2=0 ;
  if(r<=mid) {return query(root<<1,l,r);}
  if(l>mid) {return query(root<<1|1,l,r);}
  return merge(query(root<<1,l,r),query(root<<1|1,l,r));
}

int main ( ) {
  ios::sync_with_stdio(false) ;
  cin >> n >> m ;
  for ( int i = 1 ; i <= n ; i ++ ) {
    cin >> a[i] ;
  }
  build(1,1,n) ;
  while(m--) {
    int o , x , y , k ;
    cin >> o ;
    if(o==2) {
      cin >> x >> k ;
      add ( 1 , x , k ) ;
    }
    else {
      cin >> x >> y ;
      if(x>y) swap(x,y) ;
      cout << query(1,x,y).maxsum << endl ;
    }
  }
  //system("pause") ;
}