(Zj) a200. APIO2010 1.特别行动队 [dp斜率優化]

http://zerojudge.tw/ShowProblem?problemid=a200

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;

typedef long long LL;
const int MAX_N = 1e6 + 6;

LL p[MAX_N];
LL dp[MAX_N];
int v[MAX_N];

LL a,b,c;

struct line {
    LL m,b;
    LL val(LL x) {
        return m*x+b;
    }
};

deque<line> dq;

LL t(int i) {
    return a*p[i]*p[i] + b*p[i] + c;
}

LL f(int i) {
    return a*p[i]*p[i] - b*p[i] + dp[i];
}

LL g(int i) {
    return p[i];
}

LL h(int i) {
    return -2 * a * p[i];
}

bool check(line x,line y,line z) {
    return (x.b-z.b)*(y.m-x.m)<=(z.m-x.m)*(x.b-y.b);
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        scanf("%lld %lld %lld",&a,&b,&c);
        p[0]=0;
        for (int x=1;n>=x;x++) {
            scanf("%d",&v[x]);
            p[x]=p[x-1]+v[x];
        }
        dp[0] = t(0);
        dq.clear();
        dq.push_back((line){0,0});
        for (int i=1;n>=i;i++) {
            while (dq.size() >= 2 && dq[0].val(g(i)) < dq[1].val(g(i))) dq.pop_front();
            dp[i] = dq[0].val(g(i)) + t(i);
            line newline{h(i),f(i)};
            while (dq.size() >= 2 && check(dq[dq.size()-2],dq[dq.size()-1],newline)) {
                dq.pop_back();
            }
            dq.push_back(newline);
        }
        printf("%lld\n",dp[n]);
    }
}

相似題：http://acm.hdu.edu.cn/showproblem.php?pid=3507

(IOIcamp) 4.區間最大連續和 [Treap版的最大連續區間和，用size取代key的treap]

http://judge.ioicamp.org/problems/4

題目：

區間最大連續和

Time Limit: 3s

Description

連續和，表示一個序列中連續一段的和。最大連續和代表一個序列中所有連續和的最大值。即對於序列 A1,A2,…,AN，其最大連續和定義爲 max{∑i=lrAi∣∀ l,r s.t. 1≤l≤r≤N}

給你一個序列 A$A$包含 N 個整數，你要對這個序列做以下五種操作：

• 插入：在序列中第 x 個數之後，插入 k個相同的數 v
• 刪除：從序列中第 x 個數開始，刪除連續 k個數
• 修改：從序列中第 x 個數開始，將連續 k 個數修改爲 v
• 求和：求序列中第 x 個數開始，連續 k 個數的和
• 求最大連續和：求當前序列的最大連續和

Input Format

第一行包含一個正整數 T ，代表測試資料筆數。
每筆測試資料第一行包含兩個整數 N,M，代表序列長度以及操作次數。
第二行包含 N$N$ 個整數 A1,A2,…,AN，代表最初序列中的數。
接下來共有 M$M$ 行，每行包含若干個數字代表一項操作：
若爲 0 x k v：代表插入操作，在第 x 個數之後，插入 k 個相同的數 v
若爲 1 x k：代表刪除操作，從第 x 個數開始，刪除連續 k 個數
若爲 2 x k v：代表修改操作，從第 x 個數開始，將連續 k 個數修改爲 v
若爲 3 x k：代表求和操作，求第 x 個數開始，連續 k 個數的和
若爲 4：代表求最大連續和：求當前序列的最大連續和

• 1≤T≤5
• 1≤N,M≤105
• k≥1
• 0≤|Ai|,|v|≤1000
• 所有測試資料保證，對於每個操作所包含的區間皆爲合法區間，即對於刪除、修改、求和操作，從第 i 個數開始必定包含至少 k 個數
• 所有測試資料保證，插入序列的數字個數總共不會超過 105 個

Output Format

對於每筆求和或求最大連續和操作，輸出相對應的值。

Sample Input

1
5 10
1 -2 3 -4 5
4
0 1 2 3
4
3 3 3
2 3 2 -4
4
0 4 3 1
4
1 3 3
4

Sample Output

5
9
4
5
7
10

My solution :

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

typedef long long LL;
const LL INF = 1e15 + 7;
const int MAX_N = 1e5 + 6;

struct Treap {
    Treap* lc;
    Treap* rc;
    LL val;
    LL lmax,rmax,midmax,sum;
    LL tag;
    int pri;
    int sz;
    Treap(int _key) {
        lc=rc=NULL;
        tag=INF;
        lmax=rmax=midmax=sum=val=_key;
        sz = 1;
        pri=rand();
    }
};

LL Lmax(Treap* t) {
    return t?t->lmax:-INF;
}

LL Rmax(Treap* t) {
    return t?t->rmax:-INF;
}

LL Midmax(Treap* t) {
    return t?t->midmax:-INF;
}

LL Sum(Treap* t) {
    return t?t->sum:0;
}

LL Val(Treap* t) {
    return t?t->val:0;
}

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    t->lmax = max(Sum(t->lc)+(t->val),max(Lmax(t->lc),Sum(t->lc)+t->val+Lmax(t->rc)));
    t->rmax = max(Sum(t->rc)+(t->val),max(Rmax(t->rc),Sum(t->rc)+t->val+Rmax(t->lc)));
    t->midmax = max(max(Rmax(t->lc)+t->val,max(max(Midmax(t->lc),Midmax(t->rc)),t->val)),max(t->val+Lmax(t->rc),Rmax(t->lc)+t->val+Lmax(t->rc)));
    t->sum = Sum(t->lc) + Sum(t->rc) + t->val;
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

void push(Treap* t) {
    if (t->tag == INF) return;
    if (t->lc) {
        t->lc->sum = t->tag * t->lc->sz;
        t->lc->rmax = t->lc->midmax = t->lc->lmax = max(t->tag,t->tag*t->lc->sz);
        t->lc->tag = t->tag;
        t->lc->val = t->tag;
    }
    if (t->rc) {
        t->rc->sum = t->tag * t->rc->sz;
        t->rc->rmax = t->rc->midmax = t->rc->lmax = max(t->tag,t->tag*t->rc->sz);
        t->rc->tag = t->tag;
        t->rc->val = t->tag;
    }
    t->tag = INF;
}

Treap* merge(Treap* a,Treap* b){
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        push(a);
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        push(b);
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (Sz(t->lc)+1 <= k) {
        a=t;
        push(a);
        split(t->rc,k-Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        push(b);
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

Treap* root;

void add(int x,int k,int v) {
    Treap* tl;
    split(root,x,tl,root);
    while (k--) tl=merge(tl,new Treap(v));
    root = merge(tl,root);
}

void deleted(int x,int k) {
    Treap *tl,*tr;
    split(root,x-1,tl,root);
    split(root,k,root,tr);
    root = merge(tl,tr);
}

void modify(int x,int k,int v) {
    Treap *tl,*tr;
    split(root,x-1,tl,root);
    split(root,k,root,tr);
    root->tag=v;
    root->val=v;
    root->lmax=root->rmax=root->midmax = max(v,v*Sz(root));
    root->sum = v*Sz(root);
    push(root);
    root = merge(merge(tl,root),tr);
}

LL Q1(int x,int k) {
    Treap *tl,*tr;
    split(root,x-1,tl,root);
    split(root,k,root,tr);
    push(root);
    pull(root);
    LL ret=Sum(root);
    root=merge(merge(tl,root),tr);
    return ret;
}

LL Q2() {
    push(root);
    pull(root);
    return root->midmax;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        root = NULL;
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;n>=x;x++) {
            int a;
            scanf("%d",&a);
            root = merge(root,new Treap(a));
        }
        while (m--) {
            int i;
            scanf("%d",&i);
            if (i==0) {
                int x,k,v;
                scanf("%d %d %d",&x,&k,&v);
                add(x,k,v);
            }
            else if (i==1) {
                int x,k;
                scanf("%d %d",&x,&k);
                deleted(x,k);
            }
            else if (i==2) {
                int x,k,v;
                scanf("%d %d %d",&x,&k,&v);
                modify(x,k,v);
            }
            else if (i==3) {
                int x,k;
                scanf("%d %d",&x,&k);
                printf("%lld\n",Q1(x,k));
            }
            else {
                printf("%lld\n",Q2());
            }
        }
    }
}