"Ray, Pass me the dishes!" UVALive - 3938 （线段树）

灰太狼 2021-03-28 14:42 348阅读 0赞

![70][]

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

思路：

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

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define lson(x) x<<1
    #define rson(x) x<<1|1
    using namespace std;
    const int size=500005;
    typedef pair<int,int> Interval;
    typedef pair<int,int> 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<b?a:b;
    }
    inline Tree combine(Tree a,Tree b)
    {
    	Tree temp;
    	temp.l=a.l;
    	temp.r=b.r;
    	temp.max_perfix=Inter_compare(Interval(a.l,a.max_perfix),Interval(a.l,b.max_perfix)).second;
    	temp.max_suffix=Inter_compare(Interval(a.max_suffix,b.r),Interval(b.max_suffix,b.r)).first;
    	temp.max_sub=Inter_compare(Interval(a.max_suffix,b.max_perfix),Inter_compare(a.max_sub,b.max_sub));
    	return temp;
    }
    void build(int k,int l,int r)
    {
    	if(l==r)
    	{
    		tree[k].l=l;
    		tree[k].r=r;
    		tree[k].max_suffix=l;
    		tree[k].max_perfix=l;
    		tree[k].max_sub=Interval(l,r);
    		return ;
    	}
    	int mid=md(l,r);
    	build(lson(k),l,mid);
    	build(rson(k),mid+1,r);
    	tree[k]=combine(tree[lson(k)],tree[rson(k)]);
    }
    Tree query(int k,int l,int r)
    {
    	if(l<=tree[k].l&&r>=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);
    		}
    	}
    
    }

[70]: /images/20210328/1616942508297.png