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

題目：

區間最大連續和

Time Limit: 3s

Description

連續和，表示一個序列中連續一段的和。最大連續和代表一個序列中所有連續和的最大值。即對於序列

A_{1}, A_{2}, \dots, A_{N}

，其最大連續和定義爲

max {\sum_{i = l}^{r} A_{i} ∣ \forall l, r s.t. 1 \leq l \leq r \leq N}

給你一個序列

A

包含

N

個整數，你要對這個序列做以下五種操作：

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

Input Format

第一行包含一個正整數

T

，代表測試資料筆數。
每筆測試資料第一行包含兩個整數

N, M

，代表序列長度以及操作次數。
第二行包含

N

個整數

A_{1}, A_{2}, \dots, A_{N}

，代表最初序列中的數。
接下來共有

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 \leq T \leq 5$
$1 \leq N, M \leq 10^{5}$
$k \geq 1$
$0 \leq | A_{i} |, | v | \leq 1000$
所有測試資料保證，對於每個操作所包含的區間皆爲合法區間，即對於刪除、修改、求和操作，從第 $i$ 個數開始必定包含至少 $k$ 個數
所有測試資料保證，插入序列的數字個數總共不會超過 $10^{5}$ 個

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

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());
            }
        }
    }
}

yp155136 coding area

2016年10月19日星期三

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

區間最大連續和

Description

Input Format

Output Format

Sample Input

Sample Output

沒有留言:

張貼留言

2016年10月19日 星期三

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

區間最大連續和

Description

Input Format

Output Format

Sample Input

Sample Output

沒有留言:

張貼留言

2016年10月19日星期三