杭电OJ 1166（C++）

66 阅读 0 评论 44 点赞

我是靠谱客的博主超帅汽车，最近开发中收集的这篇文章主要介绍杭电OJ 1166（C++），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

使用线段树模板即可。由于本题输入数据量极大，所以必须使用 scanf 输入，使用 cin 会超时。

#include <cstdio>
#include <cstring>
const int MAXN = 50005;

int tree[MAXN << 2];
int num[MAXN];
char s[7];
int L, R, C; //L，R为修改的位置，C为修改数

//更新结点信息，rt是此结点在线段树中的索引
void pushup(int rt)
{
	//结点的值等于其左子树的值加上右子树的值
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

//建立线段树
void build_tree(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (l == r) //此结点是叶子结点
	{
		tree[rt] = num[l];
		return;
	}
	int m = (l + r) >> 1;
	build_tree(l, m, rt << 1); //构造左子树
	build_tree(m + 1, r, rt << 1 | 1); //构造右子树
	pushup(rt);
}

//修改单点信息
void update(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (l == r) //叶子结点
	{
		tree[rt] += C;
		if (tree[rt] < 0) //防止减成负数
			tree[rt] = 0;
		return;
	}
	int m = (l + r) >> 1;
	if (L <= m) //在左子树中查找
		update(l, m, rt << 1);
	else //在右子树中查找
		update(m + 1, r, rt << 1 | 1);
	pushup(rt);
}

//区间查询
int query(int l, int r, int rt)
{ //l，r是区间左右端点，rt是此结点在线段树中的索引
	if (L <= l && R >= r) //此区间被完全包含在目标区间中，返回此区间的值
		return tree[rt];
	int sum = 0;
	int m = (l + r) >> 1;
	if (L <= m) //此区间的左子树和目标区间有交集，搜索左子树
		sum += query(l, m, rt << 1);
	if (m < R) //此区间的右子树和目标区间有交集，搜索右子树
		sum += query(m + 1, r, rt << 1 | 1);
	return sum;
}

int main()
{
	int T;
	scanf("%d", &T);
	int n;
	memset(num, 0, sizeof(num));
	for (int Case = 1; Case <= T; Case++)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &num[i]);
		}
		printf("Case %d:n", Case);
		build_tree(1, n, 1);
		while (scanf("%s", s))
		{
			if (s[0] == 'E')
				break;
			else if (s[0] == 'Q') //线段树查询
			{
				scanf("%d%d", &L, &R);
				printf("%dn", query(1, n, 1));
			}
			else if (s[0] == 'A') //线段树点修改增加
			{
				scanf("%d%d", &L, &C);
				update(1, n, 1);
			}
			else if (s[0] == 'S') //线段树点修改减少
			{
				scanf("%d%d", &L, &C);
				C *= -1;
				update(1, n, 1);
			}
		}
	}
	return 0;
}

继续加油。