4009668_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int sum;
	int parent;
	int l, r;
	int lmin, lmax, max;
	int rmin, rmax, min;
};

Node root[200000];
int cnt, n;
int f[100000], pos[100000];
int neg;

int max(int a, int b)
{
	return a < b ? b : a;
}

int min(int a, int b)
{
	return a < b ? a : b;
}

void creat_seg_tree(int no, int l, int r, int parent)
{
	int mid;

	mid = (l + r) >> 1;
	root[no].parent = parent;
	if(l == r)
	{
		root[no].l = -1;
		root[no].r = -1;
		pos[l] = no;
		root[no].sum = f[l];
		root[no].lmax = root[no].lmin = root[no].max = f[l];
		root[no].rmax = root[no].rmin = root[no].min = f[l];
		return ;
	}
	int L, R;
	L = root[no].l = ++cnt;
	creat_seg_tree(cnt, l, mid, no);
	R = root[no].r = ++cnt;
	creat_seg_tree(cnt, mid+1, r, no);

	root[no].sum = root[L].sum + root[R].sum;

	root[no].lmax = max(root[L].lmax, root[L].sum + root[R].lmax);
	root[no].rmax = max(root[R].rmax, root[R].sum + root[L].rmax);
	root[no].max = max(max(root[no].lmax, root[no].rmax), root[L].rmax + root[R].lmax);

	root[no].lmin = min(root[L].lmin, root[L].sum + root[R].lmin);
	root[no].rmin = min(root[R].rmin, root[R].sum + root[L].rmin);
	root[no].min = min(min(root[no].lmin, root[no].rmin), root[L].rmin + root[R].lmin);
}

void update(int no)
{
	if (no == -1)	return ;
	int L = root[no].l;
	int R = root[no].r;

	root[no].lmax = max(root[L].lmax, root[L].sum + root[R].lmax);
	root[no].rmax = max(root[R].rmax, root[R].sum + root[L].rmax);
	root[no].max = max(max(root[L].max, root[R].max), root[L].rmax + root[R].lmax);

	root[no].lmin = min(root[L].lmin, root[L].sum + root[R].lmin);
	root[no].rmin = min(root[R].rmin, root[R].sum + root[L].rmin);
	root[no].min = min(min(root[L].min, root[R].min), root[L].rmin + root[R].lmin);

	root[no].sum = root[L].sum + root[R].sum;
	update(root[no].parent);
}

int main()
{
	int i, m;
	int a, b;

	neg = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &f[i]);
		neg += f[i] <= 0;
	}
	creat_seg_tree(cnt = 0, 0, n - 1, -1);
	scanf("%d", &m);
	while (m--)
	{
		scanf("%d%d", &a, &b);
		a--;
		if (f[a] <= 0)	neg--;
		if (b <= 0)	neg++;
		root[pos[a]].lmax = root[pos[a]].rmax = root[pos[a]].max = b;
		root[pos[a]].lmin = root[pos[a]].rmin = root[pos[a]].min = b;
		root[pos[a]].sum = b;
		update(root[pos[a]].parent);
		if (neg == 0)
			printf("%d\n", root[0].sum - root[0].min);
		else
			printf("%d\n", max(root[0].sum - root[0].min, root[0].max));
	}
	return 0;
}