2018.08.15 bzoj3747: [POI2015]Kinoman（線段樹）

傳送門

簡單題。

先不管時間複雜度看看怎麼做。

對于一段區間[l,r]，如果從右端加入一個數a[r+1]，對這個區間有什麼影響？顯然如果區間中已經有了a[r+1]這個數就會産生-a[i+1]的影響，否則就會産生a[i+1]的影響。

于是對于每個數維護一個pred[i]表示上一個a[i]這個數值的下标。

如果我們枚舉右端點i，對于每一個i維護一個[j,i]的最大值。這樣每次相當于對[pred[i]+1,i]這段區間做一個區間加，對[pred[pred[i]]+1,pred[i]]有一個區間減的效果。

直接搞是O(n^2)的，無法接受。

是以果斷線段樹優化一波就行了。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
inline ll read(){
    ll ans=;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<)+(ans<<)+(ch^),ch=getchar();
    return ans;
}
int n,m,f[N],pred[N],last[N];
ll w[N];
struct node{int l,r;ll add,mx;}T[N<<];
inline ll max(ll a,ll b){return a>b?a:b;}
inline void pushup(int p){T[p].mx=max(T[lc].mx,T[rc].mx);}
inline void pushnow(int p,ll v){T[p].add+=v,T[p].mx+=v;}
inline void pushdown(int p){if(T[p].add)pushnow(lc,T[p].add),pushnow(rc,T[p].add),T[p].add=;}
inline void build(int p,int l,int r){
    T[p].l=l,T[p].r=r,T[p].add=;
    if(l==r)return;
    build(lc,l,mid),build(rc,mid+,r);
}
inline void update(int p,int ql,int qr,ll v){
    if(ql>T[p].r||qr<T[p].l)return;
    if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
    pushdown(p);
    if(qr<=mid)update(lc,ql,qr,v);
    else if(ql>mid)update(rc,ql,qr,v);
    else update(lc,ql,mid,v),update(rc,mid+,qr,v);
    pushup(p);
}
inline ll query(int p,int ql,int qr){
    if(ql>T[p].r||qr<T[p].l)return ;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx;
    pushdown(p);
    if(qr<=mid)return query(lc,ql,qr);
    if(ql>mid)return query(rc,ql,qr);
    return max(query(lc,ql,mid),query(rc,mid+,qr));
}
int main(){
    n=read(),m=read();
    for(int i=;i<=n;++i)f[i]=read();
    for(int i=;i<=m;++i)w[i]=read();
    for(int i=;i<=n;++i)pred[i]=last[f[i]],last[f[i]]=i;
    ll ans=;
    build(,,n);
    for(int i=;i<=n;++i){
        update(,pred[i]+,i,w[f[i]]);
        if(pred[i])update(,pred[pred[i]]+,pred[i],-w[f[i]]);
        ans=max(ans,query(,,i));
    }
    cout<<ans;
    return ;
}