AcWing,第108场周赛T3 拼接数组-526互联

AcWing,第108场周赛T3

前置知识：P1115 最大子段和的dp和线段树作法

分析：对于一个数组，可以直接求出最大字段和，但由于多个数组拼接在一起，没有办法直接求得拼接数组的最大字段和。求最大字段和我已知有两种方法：

dp
线段树

先对每一个数组用线段树求出最大前缀和，最大字段和，最大后缀和，再才用Dp的思路求出拼接后数组的最大字段和，和P1115 最大子段和的dp作法差不多

\[res = \max (seg_{b_{i}ms}, dp_{i - 1} + seg_{b_{i}ls},dp_{i - 1} + seg_{b_{i}s}, seg_{b_{i}rs}) \\ dp_i = \max (dp_{i - 1} + seg_{b_{i}s}, seg_{b_{i}rs},0) \]

\(i\) 代表拼接数组的第 \(i\) 个数组，\(\texttt{seg}\) 代表线段树处理的最大前缀和，最大字段和，最大后缀和，数组值分别为\(\texttt{ls,ms,rs,s}\) ， \(b_i\) 是要拼接的数组

//  AC one more times

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int N = 3e5 + 10;


int n, m, a[60][5010], l[N];
ll f[N];

struct info
{
    ll ms,ls,rs,s;
};
info operator + (const info t1,const info t2)
{
    info t;
    t.s=t1.s+t2.s;
    t.ls=max(t1.ls,t1.s+t2.ls);
    t.rs=max(t2.rs,t2.s+t1.rs);
    t.ms=max({t.ls,t.rs,t1.ms,t2.ms,t1.rs+t2.ls});
    return t;
}

struct segtree
{
    info t;
}seg[60][N];

void update(int x, int id)
{
    seg[x][id].t=seg[x][id*2].t+seg[x][id*2+1].t;
}

void buildtree(int x, int id,int l,int r)
{   
    if(l==r)
    {
        seg[x][id].t={a[x][l],a[x][l],a[x][l],a[x][l]};
        return;
    }
    int mid=(l+r)>>1;
    buildtree(x, id*2,l,mid);
    buildtree(x, id*2+1,mid+1,r);
    update(x, id);
}

void solve()
{       
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>l[i];
        for(int j = 1; j <= l[i]; j++)
            cin>>a[i][j];
        buildtree(i, 1, 1, l[i]);
    }
    ll res = -(1ll << 60ll);
    for(int i = 1; i <= m; i++)
    {
        int id; cin>>id;
        res = max({res, seg[id][1].t.ls + f[i - 1], seg[id][1].t.ms, f[i - 1] + seg[id][1].t.s, seg[id][1].t.rs});
        f[i] = max({f[i - 1] + seg[id][1].t.s, seg[id][1].t.rs, 0ll});
    }
    cout<<res<<'\n';
    return;
}


  
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}