pku 2750 线段树 最大连续区间.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
using namespace std;

#define NMAX 100005
//PKU 2750 线段树 最大连续区间

typedef struct optree
{
    int left;
    int right;
    int value;
    int min;//无限制的区间最小值
    int max;
    int lisum;//从左边起的区间最小值
    int risum;
    int lxsum;
    int rxsum;
    int sum;
	int mm;
}optree;

optree tree[NMAX*3];
int pa[NMAX];

int gmax(int a,int b) {return a>b?a:b;}
int gmax(int a,int b,int c) 
{
	if(a>b) return a>c?a:c;
	else return b>c?b:c;
}

int gmin(int a,int b) {return a<b?a:b;}
int gmin(int a,int b,int c)
{
	if(a<b) return a<c?a:c;
	else return b<c?b:c;
}

void update(int p)
{
    int t;
 while(p>=1)
 {
    tree[p].sum=tree[2*p].sum+tree[2*p+1].sum;
	tree[p].max=gmax(tree[2*p].max,tree[2*p+1].max,tree[2*p].rxsum+tree[2*p+1].lxsum);
	tree[p].lxsum=gmax(tree[2*p].lxsum,tree[2*p].sum+tree[2*p+1].lxsum);
	tree[p].rxsum=gmax(tree[2*p+1].rxsum,tree[2*p].rxsum+tree[2*p+1].sum);
	tree[p].min=gmin(tree[2*p].min,tree[2*p+1].min,tree[2*p].risum+tree[2*p+1].lisum);
	tree[p].lisum=gmin(tree[2*p].lisum,tree[2*p].sum+tree[2*p+1].lisum);
	tree[p].risum=gmin(tree[2*p+1].risum,tree[2*p].risum+tree[2*p+1].sum);
    p=p/2;
 }
}

void build(int p,int l,int r)
{
 tree[p].left=l;
 tree[p].right=r;
 tree[p].sum=tree[p].mm=tree[p].lisum=tree[p].risum=tree[p].lxsum=tree[p].rxsum=0;
 if(r!=l)
 {
     tree[p].value=-1;
     build(2*p,l,(l+r)/2);
     build(2*p+1,(l+r)/2+1,r);
 }
 else
 {
     tree[p].value=l;
 }
}

void solve(int key,int v)
{
    int p,mid;
    p=1;
    while(tree[p].value==-1)
    {
        mid=(tree[p].left+tree[p].right)/2;
        if(key<=mid) p=p*2;
        else p=p*2+1;
    }
    tree[p].sum=tree[p].mm=v;
	tree[p].max=tree[p].min=tree[p].lisum=tree[p].risum=tree[p].lxsum=tree[p].rxsum=v;
    update(p/2);
}

void init(int num)
{
    int i;
    build(1,1,num);
    for(i=1;i<=num;i++)
        solve(i,pa[i]);
}

int main()
{
    int i,num,qnum,qa,qb,ans;
    scanf("%d",&num);
    for(i=1;i<=num;i++) scanf("%d",&pa[i]);
    scanf("%d",&qnum);
    init(num);
    for(i=1;i<=qnum;i++)
    {
        scanf("%d %d",&qa,&qb);
        solve(qa,qb);
 		if(tree[1].min>0) 	
			ans=tree[1].sum-tree[1].min;		
		else ans=gmax(tree[1].max,tree[1].sum-tree[1].min);
		printf("%d\n",ans);		
    }
    return 0;
}