题解：GSS1 - Can you answer these queries I

weak_in_code · 2024-06-18 17:30:33 · 题解

思路

首先思考一下如何扩展 l 与 r 指针。

对于扩展 l，发现新的 l 指针 l_{new} 可以贡献的答案为 \max\limits_{j=l_{new}}^{r} \sum\limits ^{j}_{k=l_{new}} a_k，形象化一下就是：

对于扩展 r，发现新的 r 指针 r_{new} 可以贡献的答案为 \max\limits _{j=l}^{r_{new}}\sum\limits_{k=j}^{r_{new}} a_k ，形象化一下就是：

~~（画的有点抽象，一点也不形象。）~~

仅仅这样显然无法通过，我们令 s(l,r) = \sum\limits _{i=l}^r a_i，然后将扩展 l 指针的式子提出来看一看：

\max\limits_{j=l_{new}}^{r} s(l_{new},j)

用前缀和思想简化式子：

\max\limits_{j=l_{new}}^{r} (s(1,j)-s(1,l_{new}-1))

然后发现这个 s(1,l_{new}-1) 可以提到外面去，即：

(\max\limits_{j=l_{new}}^{r} s(1,j))-s(1,l_{new}-1)

对于这个问题，显然可以用 ST 表预处理前缀和数组的区间最大值，然后就 O(1) 了。

对于 r 同理，再处理一个后缀和数组的区间最大值。

使用回滚莫队，时间复杂度为 O(n\log n+n\sqrt m)。

Code

#include<bits/stdc++.h>
#define sd std::
//#define int long long
#define inf 0x3f3f3f3f
#define linf 1e18
#define il inline
#define db double
#define ldb long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define f(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
#define umap(x,y) sd unordered_map<x,y>
#define pque(x) sd priority_queue<x>
#define X first
#define Y second
#define kg putchar(' ')
#define Fr(a) for(auto it:a)
#define dbg(x) sd cout<<#x<<": "<<x<<sd endl
il int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
il void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
il void put(int x){print(x);putchar('\n');}
il void printk(int x){print(x);kg;}
const int N=2e5+10,M=25;
int n,q,t,siz,lg[N],las_ma[N][M],fir_ma[N][M],a[N],las[N],fir[N],L[N],R[N],pos[N],ans[N];
struct query
{
    int l,r;
    int id;
}Q[N];
int cmp(query A,query B)
{
    return pos[A.l]==pos[B.l]?A.r<B.r:pos[A.l]<pos[B.l];
}
il void init()//预处理ST表 
{
    f(i,n,1) las[i]=las[i+1]+a[i];
    me(las_ma,-inf),me(fir_ma,-inf);
    F(i,1,n) las_ma[i][0]=las[i],fir_ma[i][0]=fir[i];
    F(i,2,n) lg[i]=lg[i/2]+1;
    F(i,1,20) for(int j=1;j+(1<<i)-1<=n;j++) las_ma[j][i]=MAX(las_ma[j][i-1],las_ma[j+(1<<(i-1))][i-1]),fir_ma[j][i]=MAX(fir_ma[j][i-1],fir_ma[j+(1<<(i-1))][i-1]);
}
int que(int l,int r,int flag)//flag=1:fir,else las
{
    int s=lg[r-l+1];
    return flag?MAX(fir_ma[l][s],fir_ma[r-(1<<s)+1][s]):MAX(las_ma[l][s],las_ma[r-(1<<s)+1][s]);
}
int Ans=-inf,tmp=-inf;
il void add_l(int x,int r){if(x<=r) tmp=MAX(tmp,que(x,r,1)-fir[x-1]);}//伸展左端点 
il void add_r(int x,int l){if(l<=x) Ans=MAX(Ans,que(l,x,0)-las[x+1]);}//伸展右端点 
int main()
{
    n=read();
    F(i,1,n) a[i]=read(),fir[i]=fir[i-1]+a[i];
    init();

    q=read();
    F(i,1,q) Q[i].l=read(),Q[i].r=read(),Q[i].id=i;
    t=sqrt(n);
    siz=n/t;
    F(i,1,siz) L[i]=(i-1)*t+1,R[i]=i*t;
    if(R[siz]<n)
    {
        ++siz;
        L[siz]=R[siz-1]+1;
        R[siz]=n;
    }
    F(i,1,siz) F(j,L[i],R[i]) pos[j]=i;
    sd sort(Q+1,Q+1+q,cmp);
    int l=1,r=0,lb=0,tmpl;
    F(i,1,q)
    {
        if(pos[Q[i].l]==pos[Q[i].r])//一个块，直接处理，用线性做法 
        {
            int ANS=-inf,b=-inf;
            F(j,Q[i].l,Q[i].r)
            {
                if(j==Q[i].l) b=a[j];
                else b=MAX(a[j],a[j]+b);
                ANS=MAX(ANS,b);
            }
            ans[Q[i].id]=ANS;
            continue;
        }
        if(pos[Q[i].l]!=lb)
        {
            while(r>R[pos[Q[i].l]]) --r;
            while(l<R[pos[Q[i].l]]+1) ++l;
            Ans=-inf;
            lb=pos[Q[i].l];
        }
        while(r<Q[i].r) ++r,add_r(r,l);
        tmpl=l;
        tmp=Ans;
        while(tmpl>Q[i].l) --tmpl,add_l(tmpl,r);
        ans[Q[i].id]=tmp;
    }
    F(i,1,q) put(ans[i]);
    return 0;
}