2016年10月19日 星期三

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

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

題目:

區間最大連續和

Time Limit: 3s

Description

連續和,表示一個序列中連續一段的和。最大連續和代表一個序列中所有連續和的最大值。即對於序列 ,其最大連續和定義爲 
給你一個序列 A包含  個整數,你要對這個序列做以下五種操作:
  • 插入:在序列中第  個數之後,插入 個相同的數 
  • 刪除:從序列中第  個數開始,刪除連續 個數
  • 修改:從序列中第  個數開始,將連續  個數修改爲 
  • 求和:求序列中第  個數開始,連續  個數的和
  • 求最大連續和:求當前序列的最大連續和

Input Format

第一行包含一個正整數  ,代表測試資料筆數。
每筆測試資料第一行包含兩個整數 ,代表序列長度以及操作次數。
第二行包含 N 個整數 ,代表最初序列中的數。
接下來共有 M 行,每行包含若干個數字代表一項操作:
若爲 :代表插入操作,在第  個數之後,插入  個相同的數 
若爲 :代表刪除操作,從第  個數開始,刪除連續  個數
若爲 :代表修改操作,從第  個數開始,將連續  個數修改爲 
若爲 :代表求和操作,求第  個數開始,連續  個數的和
若爲 :代表求最大連續和:求當前序列的最大連續和
  • 所有測試資料保證,對於每個操作所包含的區間皆爲合法區間,即對於刪除、修改、求和操作,從第  個數開始必定包含至少  個數
  • 所有測試資料保證,插入序列的數字個數總共不會超過  個

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



沒有留言:

張貼留言