【问题描述】

“南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。

又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”

《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(i,j)。能使他感到最满意，即(i,j)这条路上所有山的喜恶度之和是（c,d）(a≤c≤d≤b)最大值。于是老师便向你请教，你能帮助他吗?值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。

 

【输入】

输入第1行是两个数，n，m，2≤n≤100000，1≤m≤100000，n表示一共有n座山，m表示老师想查询的数目。

第2行是n个整数，代表n座山的喜恶度，绝对值均小于10000。

以下m行每行有a，b两个数，1≤a≤j≤b≤m，表示第a座山到第b座山。

 

【输出】

一共有m行，每行有3个数i，j，s，表示从第i座山到第j座山总的喜恶度为s。显然，对于每个查询，有a≤i≤j≤b，如果有多组解，则输出i最小的，如果i也相等，则输出j最小的解。

 

【输入样例】

5 3

5 -6 3 -1 4

1 3

1 5

5 5

【输出样例】

1 1 5

3 5 6

5 5 4

 

我感觉炒鸡恶心 啊 

线段树维护十个域 

常规 的 l r 代表此区间左右端点

ql qr 代表此区间连续子段最大的区间的左右端点

lr 代表从左端点 最大左子串能到达的位置

rl 代表从右端点 最大右子串能到达的位置

lm rm代表最大左子串和最大右子串

sum 代表区间和 

mx代表区间最大连续子串

 

建树更新，查询也要更新

 

1 #include 
      
         2 #include 
       
          3   4 const int MAXN=100010;  5   6 int n,m;  7   8 struct SegmentTree {  9     int l,r; 10     int ql,qr,lr,rl; 11     int sum,lm,rm,mx; 12 }; 13 SegmentTree t[MAXN<<2]; 14  15 inline void read(int&x) { 16     int f=1;register char c=getchar(); 17     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 18     for(;isdigit(c);x=x*10+c-48,c=getchar()); 19     x=x*f; 20 } 21  22 inline int max(int a,int b) {
    return a
        
         >1; 66     build_tree(now<<1,l,mid); 67     build_tree(now<<1|1,mid+1,r); 68     up(now); 69 } 70  71 SegmentTree query(int now,int l,int r) { 72     if(l==t[now].l&&r==t[now].r) return t[now]; 73     int mid=(t[now].l+t[now].r)>>1; 74     SegmentTree ls,rs,ans; 75     if(r<=mid) return query(now<<1,l,r); 76     else if(l>mid) return query(now<<1|1,l,r); 77     else { 78         ls=query(now<<1,l,mid); 79         rs=query(now<<1|1,mid+1,r); 80         ans.l=ls.l;ans.r=rs.r; 81          82         ans.lm=ls.lm;ans.lr=ls.lr; 83         if(ans.lm
         
          ans.mx) { 97             ans.mx=ls.rm+rs.lm; 98             ans.ql=ls.rl;ans.qr=rs.lr; 99         }100         if(rs.mx>ans.mx) {101             ans.mx=rs.mx;102             ans.ql=rs.ql;ans.qr=rs.qr;103         }104     }105     return ans;106 }107 108 int hh() {109     freopen("hill.in","r",stdin);110     freopen("hill.out","w",stdout);111     read(n);read(m);112     build_tree(1,1,n);113     for(int x,y;m--;) {114         read(x);read(y);115         SegmentTree now=query(1,x,y);116         printf("%d %d %d\n",now.ql,now.qr,now.mx);117     }118     return 0;119 }120 121 int sb=hh();122 int main(int argc,char**argv) {;}