题目大意：
给定n个数，再给q个区间询问，希望在区间s,t中找到一段连续的子序列使其和最大
因为询问上万，节点数50000，明显是用线段树去做，这里很明显的区间更新，唯一写起来有点恶心的是询问
每一个区间的最大都要跟左右区间的左最大右最大有关系
反正时要注意细节了，查询的时候同时要查询其左右连续最大
自己的错误在于左右连续最大的更新出问题，这个希望自己以后要注意
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <set> 6 #include <map> 7 using namespace std; 8 9 const int INF = 0x3fffffff; 10 #define N 50010 11 #define MOD 100007 12 #define ls o<<1 13 #define rs o<<1|1 14 #define define_m int m=(l+r)>>1 15 16 int ml[N*3] , mr[N*3] , mx[N*3] , sum[N*3]; 17 int a[N] , pre[N] , n; 18 19 void push_up(int o) 20 { 21 mx[o] = max(mx[ls] , mx[rs]); 22 mx[o] = max(mx[o] , ml[rs]+mr[ls]); 23 ml[o] = max(ml[ls],sum[ls]+ml[rs]) , mr[o] = max(mr[rs],sum[rs]+mr[ls]); 24 sum[o] = sum[ls]+sum[rs]; 25 } 26 27 void build(int o , int l , int r) 28 { 29 if(l==r){ 30 sum[o]=ml[o]=mr[o]=mx[o]=a[l]; 31 return; 32 } 33 define_m; 34 build(ls , l , m); 35 build(rs , m+1 , r); 36 push_up(o); 37 } 38 39 void query(int o , int l , int r , int s , int t , int &ansl , int &ansr , int &ans) 40 { 41 if(l>=s && r<=t){ 42 ans = mx[o]; 43 ansl = ml[o]; 44 ansr = mr[o]; 45 return ; 46 } 47 define_m; 48 if(m>=t) query(ls , l , m , s , t , ansl , ansr , ans); 49 else if(m<s) query(rs , m+1 , r , s , t , ansl , ansr ,ans); 50 else{ 51 int t1,t2,t3,t4,t5,t6; 52 query(ls , l , m , s , m , t1 , t2 , t3); 53 query(rs , m+1 , r , m+1 , t , t4 , t5 , t6); 54 ansl = max(t1 , pre[m]-pre[s-1]+t4) , ansr = max(t5 , pre[t]-pre[m]+t2); 55 ans = max(t3 , t6); 56 ans = max(ans , t2+t4); 57 } 58 //cout<<o<<" "<<l<<" "<<r<<" "<<s<<" "<<t<<" "<<ansl<<" "<<ansr<<" "<<ans<<endl; 59 } 60 61 int main() 62 { 63 #ifndef ONLINE_JUDGE 64 freopen("a.in" , "r" , stdin); 65 #endif // ONLINE_JUDGE 66 while(~scanf("%d" , &n)) 67 { 68 for(int i=1 ; i<=n ; i++){ 69 scanf("%d" , a+i); 70 pre[i] = pre[i-1]+a[i]; 71 } 72 build(1 , 1 , n); 73 int m; 74 scanf("%d" , &m); 75 for(int i=0 ; i<m ; i++){ 76 int s , t; 77 scanf("%d%d" , &s , &t); 78 int t1,t2,t3; 79 query(1,1,n,s,t,t1,t2,t3); 80 printf("%d\n" , t3); 81 } 82 } 83 return 0; 84 }