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

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

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

题意：给出询问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);
        }
    }
}