题解 | #方块 III#

类似湘潭邀请赛的那个dp...
但是湘潭邀请赛的那个dp比这个难,假如赛前做了这个线段树估计那个dp可以秒...
惨...
code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2;
int c[N];
int ls[N],lss[N];
ll w[N];
struct SegTree{
    ll l,r,lz;
    ll mx;
}Tr[N<<3];
void pushup(int u)
{
    Tr[u].mx=max(Tr[u<<1].mx,Tr[u<<1|1].mx);
}

void pushdown(int u)
{
    if(Tr[u].lz)
    {
        Tr[u<<1].mx+=Tr[u].lz;
        Tr[u<<1|1].mx+=Tr[u].lz;
        Tr[u<<1].lz+=Tr[u].lz;
        Tr[u<<1|1].lz+=Tr[u].lz;
        Tr[u].lz=0;
    }
}

void add(int u,int l,int r,ll k)
{
    if(l>r)                     return;
    if(l>Tr[u].r||r<Tr[u].l)    return;
    if(l<=Tr[u].l&&Tr[u].r<=r)
    {
        Tr[u].lz+=k;
        Tr[u].mx+=k;
        return;
    }
    pushdown(u);
    add(u<<1,l,r,k);
    add(u<<1|1,l,r,k);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if(l>r)                     return 0;
    if(l>Tr[u].r||r<Tr[u].l)    return 0;
    if(l<=Tr[u].l&&Tr[u].r<=r)  return Tr[u].mx;
    pushdown(u);
    return max(query(u<<1,l,r),query(u<<1|1,l,r));
}

void build(int u,int l,int r)
{
    Tr[u].l=l,Tr[u].r=r;
    Tr[u].mx=Tr[u].lz=0;
    if(l==r)    return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

void run()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        memset(ls,0,sizeof ls);
        memset(lss,0,sizeof lss);
        for(int i=1;i<=m;i++)
            scanf("%lld",&w[i]);
        build(1,1,n);
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            add(1,ls[c[i]]+1,i,w[c[i]]);
            add(1,lss[c[i]]+1,ls[c[i]],-w[c[i]]);
            ans=max(ans,query(1,1,i));
            lss[c[i]]=ls[c[i]];
            ls[c[i]]=i;
        }
        printf("%lld\n",ans);
    }
}

int main()
{
    int T=1;
    while(T--)
    {
        run();
    }
    return 0;
}