题意：给出询问a,b求出a，b区段内的最大子串

思路：

不难想象，一个区段的最大子串要么为其两个子区段的最大子串，要么第一个子串的最大后缀加上第二个子串的最大前缀。因此我们需要维护每一个串的最大前缀，最大后缀，以及最大子串。但是同时需要考虑到，子串的情况会和坐标有关，因此我们不选择直接维护子串的值，而是选择维护串的起始位置和终止位置，再通过前缀和相减来得到串的值的大小。

AC代码：

#include
    
     #include
     
      #include
      
       #define lson(x) x<<1#define rson(x) x<<1|1using namespace std;const int size=500005;typedef pair
       
         Interval;typedef pair
        
          pii;typedef long long LL;LL Sum[size];struct Tree{	int l,r;	pii max_sub;	int max_perfix;	int max_suffix;}tree[size<<2];inline int md(int l,int r){return (l+r)>>1;}inline LL sum(pii x){	return Sum[x.second]-Sum[x.first-1];}pii Inter_compare(pii a,pii b){	LL x=sum(a),y=sum(b);	if(x!=y) return x>y?a:b;	return a
         
          =tree[k].r) { return tree[k]; } int mid=md(tree[k].l,tree[k].r); if(r<=mid) return query(lson(k),l,r); if(l>mid)return query(rson(k),l,r);//l不能加等于号 return combine(query(lson(k),l,r),query(rson(k),l,r));}int main(){ int n,m; int cnt=0; while(~scanf("%d%d",&n,&m)) { memset(Sum,0,sizeof(Sum)); for(int i=1;i<=n;i++) { int temp; scanf("%d",&temp); Sum[i]=Sum[i-1]+temp; } build(1,1,n); printf("Case %d:\n",++cnt); while(m--) { int l,r; scanf("%d%d",&l,&r); pii ans=query(1,l,r).max_sub; printf("%d %d\n",ans.first,ans.second); } }}