首页 > 代码库 > 2014 UESTC Training for Data Structures G - 程序设计竞赛

2014 UESTC Training for Data Structures G - 程序设计竞赛

G - 程序设计竞赛

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

“你动规无力,图论不稳,数据结构松散,贪心迟钝,没一样像样的,就你还想和我同台竞技,做你的美梦!今天这场比赛,就是要让你知道你是多么的无能!!”

不训练,无以为战。有n项能力是ACM竞赛要求的,训练则能提升,忽略则会荒废。

m天,你能做到如何。

Input

第一行两个整数nm,分别表示有n项能力要求,共有m天。

第二行n个整数,第i个整数ai表示第i项能力的数值。

接下来m行,每行开始先读入一个整数si,表明这是一次询问还是一次能力变化。

si=0,表明这是一次询问,然后读入两个整数li,ri,表示询问在[liri]区间中任选一段连续序列,这段序列中所有能力值之和最大能是多少。

si=1,表明这是一次能力变化,然后读入两个整数xi,wi,表示第xi项能力变为了wi

1n,m100000,?10000ai10000,1lirin,1xin,?10000wi10000

Output

有多少询问就输出多少行,每行输出一个整数,作为对该询问的回答。

Sample input and output

Sample Input Sample Output
4 4
1 2 3 4
0 1 3
1 3 -3
0 2 4
0 3 3
6
4
-3

 

题意大概是,给定一个序列,要求序列支持修改时间<=o(lgn),区间查询连续序列之和最大值时间<=o(lgn).

要用线段树,记录好多东东。。。。

我是加了4个记录

struct mm{

    int left;

    int right;

    int l;

    int r;

    int data;

    int sum;

}tree[400005]={};

Left,right 是区间范围,

 .l是存当前区间从右开始最大的连续序列之和。

.r是存当前区间从左开始最大的连续序列之和。

.data 是存当前区间的最大的连续序列之和。

.sum是存当前区间的所有元素之和。

然后修改序列时就有

int g=l*2,h=l*2+1;

    tree[l].l=max(tree[g].sum+tree[h].l,tree[g].l);

    tree[l].r=max(tree[h].sum+tree[g].r,tree[h].r);

    tree[l].sum=tree[g].sum+tree[h].sum;

    tree[l].data=http://www.mamicode.com/max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data));

从左开始最大的连续序列之和可以是

 

 

 

 

这两种情况,即max(tree[g].sum+tree[h].l,tree[g].l);

黑色表示该区间的最大的连续序列之和

从右开始同理。

而data就是

 

这三种情况

即max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data));

 

然后查找区间,suan是计算在L区间内从j到k的最大的连续序列之和,先要找到包含[j,k]的最小区间[L.left,L.right],然后就和上图一样了。

int suan(int l,int j,int k)

{

    if (tree[l].left==j && tree[l].right==k) return tree[l].data;

    if ((tree[l].left+tree[l].right)/2<j) return suan(l*2+1,j,k);

    if ((tree[l].left+tree[l].right)/2>=k) return suan(l*2,j,k);

    int g,h;

    g=suanr(l*2,j);

    h=suanl(l*2+1,k);

    int a,s;

    a=suan(l*2,j,(tree[l].left+tree[l].right)/2);

    s=suan(l*2+1,(tree[l].left+tree[l].right)/2+1,k);

    return max(g+h,max(a,s));

}

其中suanr和suanl是计算L区间从右或从左最大的连续序列之和。

int suanr(int l,int j)

{

    if (tree[l].left==j) return tree[l].r;

    if ((tree[l].right+tree[l].left)/2+1<=j) return suanr(l*2+1,j);

    return max(tree[l*2+1].r,tree[l*2+1].sum+suanr(l*2,j));

}

int suanl(int l,int j)

{

    if (tree[l].right==j) return tree[l].l;

    if ((tree[l].right+tree[l].left)/2>=j) return suanl(l*2,j);

    return max(tree[l*2].l,tree[l*2].sum+suanl(l*2+1,j));

}

 

#include <iostream>
#include<cstdio>
using namespace std;
int M;
struct mm{
    int left;
    int right;
    int l;
    int r;
    int data;
    int sum;
}tree[400005]={};
void build(int l,int j,int k)
{
    tree[l].left=j;
    tree[l].right=k;
    if (j==k) return;
    build(l*2,j,(j+k)/2);
    build(l*2+1,(j+k)/2+1,k);
}
void cha(int l,int j,int light)
{
    if (tree[l].right==tree[l].left) {
        tree[l].l=tree[l].r=tree[l].sum=tree[l].data=http://www.mamicode.com/light;
        return;
    }
    if ((tree[l].right+tree[l].left)/2<j)
        cha(l*2+1,j,light);
    else cha(l*2,j,light);
    int g=l*2,h=l*2+1;
    tree[l].l=max(tree[g].sum+tree[h].l,tree[g].l);
    tree[l].r=max(tree[h].sum+tree[g].r,tree[h].r);
    tree[l].sum=tree[g].sum+tree[h].sum;
    tree[l].data=max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data));
}
int suanr(int l,int j)
{
    if (tree[l].left==j) return tree[l].r;
    if ((tree[l].right+tree[l].left)/2+1<=j) return suanr(l*2+1,j);
    return max(tree[l*2+1].r,tree[l*2+1].sum+suanr(l*2,j));
}
int suanl(int l,int j)
{
    if (tree[l].right==j) return tree[l].l;
    if ((tree[l].right+tree[l].left)/2>=j) return suanl(l*2,j);
    return max(tree[l*2].l,tree[l*2].sum+suanl(l*2+1,j));
}
int suan(int l,int j,int k)
{
    if (tree[l].left==j && tree[l].right==k) return tree[l].data;
    if ((tree[l].left+tree[l].right)/2<j) return suan(l*2+1,j,k);
    if ((tree[l].left+tree[l].right)/2>=k) return suan(l*2,j,k);
    int g,h;
    g=suanr(l*2,j);
    h=suanl(l*2+1,k);
    int a,s;
    a=suan(l*2,j,(tree[l].left+tree[l].right)/2);
    s=suan(l*2+1,(tree[l].left+tree[l].right)/2+1,k);
    return max(g+h,max(a,s));
}
int main()
{
    int g,h,j,k,l,n;
    cin>>n>>M;
    build(1,1,n);
    for (j=1;j<=n;j++){
        scanf("%d",&g);
        cha(1,j,g);
    }
    for (j=1;j<=M;j++){
        scanf("%d%d%d",&g,&h,&k);
        if (g==1) cha(1,h,k);
        else {
            printf("%d\n",suan(1,h,k));
        }
    }
    return 0;
}