BZOJ 3747 POI 2015 Kinoman 線段樹

BZOJ 3747 POI 2015 Kinoman 線段樹

題目大意：給出電影院的放映電影順序，一個電影只有看過一次的時候會獲得電影的權值。沒看過或者看兩次或以上都不能獲得權值。問看連續區間的電影能夠獲得的最大權值是多少。

思路：利用線段樹維護前綴和。將出現第一次的地方的權值加上那部電影的權值，第二次出現的時候權值減去那部電影的權值。枚舉起點，先更新答案，然後在當前節點減去權值的二倍，然後再在下一次出現的地方加上權值（我感覺我沒說明白，總之看代碼吧。。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1000010
using namespace std;
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)
 
struct SegTree{
    long long _max,c;
}tree[MAX << 2];
 
int total,cnt;
int src[MAX],value[MAX];
int first[MAX],last[MAX],next[MAX];
 
inline void PushDown(int pos)
{
    if(tree[pos].c) {
        tree[LEFT]._max += tree[pos].c;
        tree[RIGHT]._max += tree[pos].c;
        tree[LEFT].c += tree[pos].c;
        tree[RIGHT].c += tree[pos].c;
        tree[pos].c = 0;
    }
}
 
inline void Modify(int l,int r,int x,int y,int c,int pos)
{
    if(l == x && y == r) {
        tree[pos]._max += c;
        tree[pos].c += c;
        return ;
    }
    PushDown(pos);
    int mid = (l + r) >> 1;
    if(y <= mid) Modify(l,mid,x,y,c,LEFT);
    else if(x > mid) Modify(mid + 1,r,x,y,c,RIGHT);
    else {
        Modify(l,mid,x,mid,c,LEFT);
        Modify(mid + 1,r,mid + 1,y,c,RIGHT);
    }
    tree[pos]._max = max(tree[LEFT]._max,tree[RIGHT]._max);
}
 
inline long long Ask(int l,int r,int x,int y,int pos)
{
    if(l == x && y == r)
        return tree[pos]._max;
    PushDown(pos);
    int mid = (l + r) >> 1;
    if(y <= mid) return Ask(l,mid,x,y,LEFT);
    if(x > mid)      return Ask(mid + 1,r,x,y,RIGHT);
    long long left = Ask(l,mid,x,mid,LEFT);
    long long right = Ask(mid + 1,r,mid + 1,y,RIGHT);
    return max(left,right);
}
 
int main()
{
    cin >> total >> cnt;
    for(int i = 0; i < MAX; ++i) next[i] = total + 1;
    for(int i = 1; i <= total; ++i) {
        scanf("%d",&src[i]);
        if(!first[src[i]]) {
            first[src[i]] = i;
            last[src[i]] = i;
        }
        else {
            next[last[src[i]]] = i;
            last[src[i]] = i;
        }
    }
    for(int i = 1; i <= cnt; ++i)
        scanf("%d",&value[i]);
    for(int i = 1; i <= cnt; ++i)
        if(first[i]) {
            Modify(1,total + 1,first[i],total + 1,value[i],1);
            Modify(1,total + 1,next[first[i]],total + 1,-value[i],1);
        }
    long long ans = 0;
    for(int i = 1; i <= total; ++i) {
        ans = max(ans,Ask(1,total,i,total,1));
        Modify(1,total + 1,i,total + 1,-value[src[i]],1);
        Modify(1,total + 1,next[i],total + 1,value[src[i]] << 1,1);
        Modify(1,total + 1,next[next[i]],total + 1,-value[src[i]],1);
    }
    cout << ans << endl;
    return 0;
}