max answerと牛客多校第四場C

max answer
題意:一組の数を与えて、一つの区間(l,r)の中のすべての数の和とこの区間の最小数の積が最大であることを求める
方法:各数a[i]について、a[i]が最も小数の合法区間である左境界l[i]と右境界r[i]を満たすことを求めることができる.そして各a[i]に対して次は
a[i]を含む範囲l[i]からr[i]の中で最も大きいサブシーケンスとはいくらであるか.
l[i]とr[i]については単調スタックで求めることができ,
1つの要素を追加するたびに、スタックトップ要素以下の場合は、スタックトップ要素を空にするまでポップアップします.
スタックトップ要素は追加する要素より小さく、このときl[i]は最も左の境界1またはスタックトップ要素の位置に1を加える.
r[i]同理は後ろから単調なスタックを1回走り、r[i]最右境界またはスタックトップ要素は1減少する.
case 1.a[i]>=0については、l[i]からr[i]の最小値であるため、区間の各数が0以上であることを示し、最も大きなサブシーケンスとすべての数の和であり、ansは
すべての値の和*a[i]はmaxをとる.
Case 2はa[i]<0の場合、シーケンスが負になる可能性があるため、積を最大にするには、サブシーケンスと最小にするには、セグメントツリーで接頭辞と配列のメンテナンスを行うことができます.
最大最小値は、区間l[i]~i-1で最大接頭辞和を探し、区間i~r[i]で最小接頭辞和を探し、後者から前者を減算するとa[i]を含む
を含む最小子序和.そしてa[i]に乗算した結果ansとmaxをとる.
この問題は、i+1~r[i]の右端点を列挙して接頭辞和を求め続け、次いで最小値m 1をとり、l[i]~i-1の接尾辞を求め続け、最小値m 2をとると最小値m 2をとることもできる.
サブシーケンスとはm 1+m 2+a[i](個人的にはTはデータの負の数が少ないと感じるでしょう)

#include
using namespace std;
typedef  long long ll;
const int maxn=500005;
const ll inf=0xfffffffffff;
ll l[500005], r[500005], a[500005], sum[500005];
int n;
struct segment
{
    int l,r;
    ll mi,mx;
}t[maxn*4];
void pushup(int o)
{
    t[o].mi=min(t[o<<1].mi,t[o<<1|1].mi);
    t[o].mx=max(t[o<<1].mx, t[o<<1|1].mx);
}
void build(int o, int l, int r)
{
    t[o].l=l;
    t[o].r=r;
    if(l==r)
    {
        t[o].mi=t[o].mx=sum[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
}
ll querymi(int o, int l, int r)
{
    if(l<=t[o].l&&t[o].r<=r)
    {
        return t[o].mi;
    }
    int mid=(t[o].l+t[o].r)>>1;
    ll Mi=inf;
    if(l<=mid)Mi=min(Mi,querymi(o<<1,l,r));
    if(r>mid)Mi=min(Mi,querymi(o<<1|1,l,r));
    return Mi;
}
ll querymx(int o,int l, int r)
{
    if(l<=t[o].l&&t[o].r<=r)
    {
        return t[o].mx;
    }
    int mid=(t[o].l+t[o].r)>>1;
    ll Mx=-inf;
    if(l<=mid)Mx=max(Mx,querymx(o<<1,l,r));
    if(r>mid)Mx=max(Mx,querymx(o<<1|1,l,r));
    return Mx;
}
int main()
{
    scanf("%d",&n);
    stackq;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&a[q.top()]>=a[i])
        {
            q.pop();
        }
        if(q.empty())l[i]=1;
        else l[i]=q.top()+1;
        q.push(i);
    }
    while(!q.empty())q.pop();
    for(int i=n;i>=1;i--)
    {
        while(!q.empty()&&a[q.top()]>=a[i])
        {
            q.pop();
        }
        if(q.empty())r[i]=n;
        else r[i]=q.top()-1;
        q.push(i);
    }
    ll ans=-inf;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=0)
        {
            ans=max(ans,(sum[r[i]]-sum[l[i]]+a[l[i]])*a[i]);
        }
        else
        {
            ans=max(ans, (querymi(1,i,r[i])-querymx(1,1,i-1))*a[i]);
        }
    }
    cout<

#include
#define ll long long
using namespace std;
ll l[500005], r[500005], a[500005], sum[500005];
int n;
struct segment
{
    int l,r;
    ll mi,mx;
}t[maxn*4];
void pushup(int o)
{
    t[o].mi=min(t[o<<1].mi,t[o<<1|1].mi);
    t[o].mx=max(t[o<<1].mx, t[o<<1|1].mx);
}
void build(int o, int l, int r)
{
    t[o].l=l;
    t[o].r=r;
    if(l==r)
    {
        t[o].mi=t[o].mx=sum[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
}
ll querymi(int o, int l, int r)
{
    if(l<=t[o].l&&t[o].r<=r)
    {
        return t[o].mi;
    }
    int mid=(t[o].l+t[o].r)>>1;
    ll Mi=inf;
    if(l<=mid)Mi=min(Mi,querymi(o<<1,l,r));
    if(r>mid)Mi=min(Mi,querymi(o<<1|1,l,r));
    return Mi;
}

int getnum(int n,int x,int y)
{
    int r=0;
    if(x<=y & x+y <= n+1)
    {
        r = x;
        return  4*(r-1)*n - 4*(r-1)*(r-1) +1 + y-r;
    }
    if(x<=y & x+y >= n+1)
    {
        r = n- y + 1;
        return 4*(r-1)*n - 4*(r-1)*(r-1) + 1 + n-2*r + 1 + x - r;
    }
    if(x>=y & x+y >= n+1)
    {
        r = n - x +1;
        return 4*(r-1)*n - 4*(r-1)*(r-1) + 1 + 3*n-6*r + 3 - y + r;
    }
    if(x>=y & x+y <= n+1)
    {
        r = y;
        return 4*(r-1)*n - 4*(r-1)*(r-1) + 1 + 4*n-8*r + 4  - x + r;
    }
    return 0;
}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d %d %d
",i,j,getnum(n,i,j));
        }
    }
    return 0;
}

牛客多校第四場C
題意はあなたに2つのシーケンスAをあげて、Bは1つの区間(l,r)内のa[i]の最小値とb[i]のシーケンスの和の積を求めます
上記の方法とほぼ同様に、aの合法区間l[i],r[i]を単調スタックで求め、a[i]>=0とa[i]<0の2つの場合についてそれぞれ最大サブシーケンスと最小サブシーケンスとを求め、b配列の接頭辞和の最大最小値をセグメントツリーで維持すると、最大サブシーケンスとi~r[i]における最大接頭辞とl[i]-1~i-1における最小接頭辞和を減算し、最小サブシーケンスは、i~r[i]における最小接頭辞と、l[i]-1~i-1における最大接頭辞の和を減算.答えを別々に更新
接頭辞の和を探す時0点を探し当てることができるため、線分の木は0から建てて、しかもこの問題は比較的に複雑で、構造体の中の左右の境界l,rを関数のパラメータの中で書くことができて、ノードのメンテナンスの情報の個数を減らします

#include
using namespace std;
typedef  long long ll;
const int maxn=3000006;
const ll inf=0xfffffffffff;
ll l[maxn], r[maxn], a[maxn], sum[maxn],b[maxn];
int n;
struct segment
{
    ll mi,mx;
}t[maxn*4];
void pushup(int o)
{
    t[o].mi=min(t[o<<1].mi,t[o<<1|1].mi);
    t[o].mx=max(t[o<<1].mx, t[o<<1|1].mx);
}
void build(int o, int l, int r)
{
    //t[o].l=l;
    //t[o].r=r;
    if(l==r)
    {
        t[o].mi=t[o].mx=sum[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
}
ll querymi(int o, int l, int r,int L,int R)
{
    if(l<=L&&R<=r)
    {
        return t[o].mi;
    }
    int mid=(L+R)>>1;
    ll Mi=inf;
    if(l<=mid)Mi=min(Mi,querymi(o<<1,l,r,L,mid));
    if(r>mid)Mi=min(Mi,querymi(o<<1|1,l,r,mid+1,R));
    return Mi;
}
ll querymx(int o,int l, int r,int L,int R)
{
    if(l<=L&&R<=r)
    {
        return t[o].mx;
    }
    int mid=(L+R)>>1;
    ll Mx=-inf;
    if(l<=mid)Mx=max(Mx,querymx(o<<1,l,r,L,mid));
    if(r>mid)Mx=max(Mx,querymx(o<<1|1,l,r,mid+1,R));
    return Mx;
}
int main()
{
    scanf("%d",&n);
    stackq;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
    sum[0]=0;
    build(1,0,n);
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&a[q.top()]>=a[i])
        {
            q.pop();
        }
        if(q.empty())l[i]=1;
        else l[i]=q.top()+1;
        q.push(i);
    }
    while(!q.empty())q.pop();
    for(int i=n;i>=1;i--)
    {
        while(!q.empty()&&a[q.top()]>=a[i])
        {
            q.pop();
        }
        if(q.empty())r[i]=n;
        else r[i]=q.top()-1;
        q.push(i);
    }
    ll ans=-inf;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=0)
        {
            //cout<