bzoj3747 [POI2015]Kinoman

　　線段樹，記錄next[i]下一部與當前電影一樣的位置，然后枚舉區間左端點i，詢問線段樹最大值后刪除i到next[i-1]這段區間的觀影值，且增加next[i]到next[next[i]]-1這段區間的觀影值。

　　

　　代碼，跑的有點慢

　　

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5001010;
const int M = 2000010;
int pos[M],a[M],b[M];
int n,m,i,next[M];
long long ans,s[N],v[N];
void clean(int x)
{
    if (v[x])
    {
        s[x]+=v[x];
        v[2*x]+=v[x];
        v[2*x+1]+=v[x];
        v[x]=0;
    }
}
void change(int x,int l,int r,int a,int b,int c)
{
    clean(x);
    if ((a<=l)&&(r<=b))
    {
        v[x]+=c;
        return;
    }
    int m=(l+r)>>1;
    if (a<m) change(2*x,l,m,a,b,c);
    if (m<b) change(2*x+1,m,r,a,b,c);
    clean(2*x);clean(2*x+1);
    s[x]=max(s[2*x],s[2*x+1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (i=1;i<=m;i++)
        scanf("%d",&b[i]);
    for (i=1;i<=n;i++)
    {
        if (pos[a[i]]) next[pos[a[i]]]=i;
        pos[a[i]]=i;
    }
    for (i=1;i<=n;i++) if (next[i]==0) next[i]=n+1;
    
    for (i=1;i<=m;i++) pos[i]=0;
    for (i=1;i<=n;i++)
    {
        if (pos[a[i]]==0) change(1,0,n,i-1,next[i]-1,b[a[i]]);
        pos[a[i]]=1;
    }
    
    for (i=1;i<=n;i++)
    {
        clean(1);ans=max(ans,s[1]);
        change(1,0,n,i-1,next[i]-1,-b[a[i]]);
        if (next[i]!=n+1)
        change(1,0,n,next[i]-1,next[next[i]]-1,b[a[next[i]]]);
    }
    printf("%lld\n",ans);
}

?