Codeforces Intel Code Challenge Elimination Round 722C

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://codeforces.com/contest/722/problem/C

题目翻译

给一个序列长度为N的正数序列，一共操作N次每次将序列里的一个位置设置为不可取，在每次删除之后输出序列里的最大连续可取之和。

题解

建一棵区间和最大值线段树，然后每次删除数字的时候，只需要让这个序列最大值断开即可，相当于把当前要删去的位置置为当前最大值的相反数。

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const LL INF=1e14;
const int Maxn=100000;
struct Btree{
    int left,right;
    LL lMax,rMax,max,sum;
};
Btree tree[Maxn*4+5];
int n;
LL num[Maxn+5];
int ord[Maxn+5];
inline void update(int x){
    if (tree[x].left==tree[x].right) return;
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    tree[x].lMax=max(tree[x*2].lMax,tree[x*2].sum+tree[x*2+1].lMax);
    tree[x].rMax=max(tree[x*2+1].rMax,tree[x*2+1].sum+tree[x*2].rMax);
    tree[x].max=max(tree[x*2].max,tree[x*2+1].max);
    tree[x].max=max(tree[x].max,max(tree[x].sum,max(tree[x].lMax,tree[x].rMax)));
    tree[x].max=max(tree[x].max,tree[x*2].rMax+tree[x*2+1].lMax);
    tree[x].lMax=max(tree[x].lMax,0LL);
    tree[x].rMax=max(tree[x].rMax,0LL);
    tree[x].max=max(tree[x].max,0LL);
}
void build(int x,int left,int right){
    tree[x].left=left;
    tree[x].right=right;
    tree[x].max=tree[x].sum=tree[x].lMax=tree[x].rMax=0;
    if (left==right){
        tree[x].max=tree[x].sum=tree[x].lMax=tree[x].rMax=num[left];
    tree[x].lMax=max(tree[x].lMax,0LL);
    tree[x].rMax=max(tree[x].rMax,0LL);
    tree[x].max=max(tree[x].max,0LL);
    }else{
        int mid=(left+right)/2;
        build(x*2,left,mid);
        build(x*2+1,mid+1,right);
        update(x);
    }
}
void modify(int x,int pos,LL val){
    if (tree[x].left==tree[x].right){
        tree[x].lMax=tree[x].rMax=tree[x].sum=tree[x].max=val;
        tree[x].lMax=max(tree[x].lMax,0LL);
    tree[x].rMax=max(tree[x].rMax,0LL);
    tree[x].max=max(tree[x].max,0LL);
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (pos<=mid) modify(x*2,pos,val);
        if (mid+1<=pos) modify(x*2+1,pos,val);
        update(x);
    }
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%I64d",&num[i]);
    for (int i=1;i<=n;i++)
        scanf("%d",&ord[i]);
    build(1,1,n);
    LL lastAns=INF;
    for (int i=1;i<n;i++){
        modify(1,ord[i],-lastAns-1);
        lastAns=tree[1].max;
        printf("%I64d\n",lastAns);
    }
    printf("0\n");
    return 0;
}

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define LL long long

using namespace std;

const LL INF=1e14;

const int Maxn=100000;

struct Btree{

int left,right;

LL lMax,rMax,max,sum;

};

Btree tree[Maxn*4+5];

int n;

LL num[Maxn+5];

int ord[Maxn+5];

inline void update(int x){

if (tree[x].left==tree[x].right) return;

tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;

tree[x].lMax=max(tree[x*2].lMax,tree[x*2].sum+tree[x*2+1].lMax);

tree[x].rMax=max(tree[x*2+1].rMax,tree[x*2+1].sum+tree[x*2].rMax);

tree[x].max=max(tree[x*2].max,tree[x*2+1].max);

tree[x].max=max(tree[x].max,max(tree[x].sum,max(tree[x].lMax,tree[x].rMax)));

tree[x].max=max(tree[x].max,tree[x*2].rMax+tree[x*2+1].lMax);

tree[x].lMax=max(tree[x].lMax,0LL);

tree[x].rMax=max(tree[x].rMax,0LL);

tree[x].max=max(tree[x].max,0LL);

}

void build(int x,int left,int right){

tree[x].left=left;

tree[x].right=right;

tree[x].max=tree[x].sum=tree[x].lMax=tree[x].rMax=0;

if (left==right){

tree[x].max=tree[x].sum=tree[x].lMax=tree[x].rMax=num[left];

tree[x].lMax=max(tree[x].lMax,0LL);

tree[x].rMax=max(tree[x].rMax,0LL);

tree[x].max=max(tree[x].max,0LL);

}else{

int mid=(left+right)/2;

build(x*2,left,mid);

build(x*2+1,mid+1,right);

update(x);

}

void modify(int x,int pos,LL val){

if (tree[x].left==tree[x].right){

tree[x].lMax=tree[x].rMax=tree[x].sum=tree[x].max=val;

tree[x].lMax=max(tree[x].lMax,0LL);

tree[x].rMax=max(tree[x].rMax,0LL);

tree[x].max=max(tree[x].max,0LL);

}else{

int mid=(tree[x].left+tree[x].right)/2;

if (pos<=mid) modify(x*2,pos,val);

if (mid+1<=pos) modify(x*2+1,pos,val);

update(x);

}

int main(){

scanf("%d",&n);

for (int i=1;i<=n;i++)

scanf("%I64d",&num[i]);

for (int i=1;i<=n;i++)

scanf("%d",&ord[i]);

build(1,1,n);

LL lastAns=INF;

for (int i=1;i<n;i++){

modify(1,ord[i],-lastAns-1);

lastAns=tree[1].max;

printf("%I64d\n",lastAns);

}

printf("0\n");

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑