首页 > 代码库 > CodeForces 52C Circular RMQ（区间循环线段树，区间更新，区间求和）

CodeForces 52C Circular RMQ（区间循环线段树，区间更新，区间求和）

2024-07-10 05:40:33   221人阅读

转载请注明出处：http://blog.csdn.net/u012860063

题目链接：http://codeforces.com/problemset/problem/52/C

You are given circular array a0,?a1,?...,?an?-?1. There are two types of operations with it:

  • inc(lf,?rg,?v) — this operation increases each element on the segment [lf,?rg] (inclusively) by v;
  • rmq(lf,?rg) — this operation returns minimal value on the segment [lf,?rg] (inclusively).

Assume segments to be circular, so if n?=?5 and lf?=?3,?rg?=?1, it means the index sequence: 3,?4,?0,?1.

Write program to process given sequence of operations.

Input

The first line contains integer n (1?≤?n?≤?200000). The next line contains initial state of the array: a0,?a1,?...,?an?-?1 (?-?106?≤?ai?≤?106),ai are integer. The third line contains integer m (0?≤?m?≤?200000), m — the number of operartons. Next m lines contain one operation each. If line contains two integer lf,?rg (0?≤?lf,?rg?≤?n?-?1) it means rmq operation, it contains three integers lf,?rg,?v (0?≤?lf,?rg?≤?n?-?1;?-?106?≤?v?≤?106) — inc operation.

Output

For each rmq operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Sample test(s)
input
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1
output
1
0
0

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
//lson和rson分辨表示结点的左儿子和右儿子
//rt表示当前子树的根(root),也就是当前所在的结点
#define INF 0x3fffffff
__int64 mmin[5000047];
__int64 col[5000047];
__int64 MIN(__int64 a, __int64 b)
{
	if( a < b)
		return a;
	return b;
}
void pushup(int rt)
{
	//sum[rt] = sum[rt<<1] + sum[rt<<1|1];
	mmin[rt]=MIN(mmin[rt<<1], mmin[rt<<1|1]);
}
void pushdown(int rt, int m)
{
	if(col[rt])
	{
		col[rt<<1]+=col[rt];
		col[rt<<1|1]+=col[rt];
		mmin[rt<<1]+=col[rt];
		mmin[rt<<1|1]+=col[rt];
		col[rt]=0;
	}
}
void build(int l, int r, int rt)
{
	col[rt]=0;
	if(l==r)
	{
		scanf("%I64d", &mmin[rt]);
		return ;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int L, int R, int v, int l, int r, int rt)
{
	if(L<=l && r<=R)
	{
		col[rt]+=v;
		mmin[rt]+=v;
		return ;
	}
	pushdown(rt, r-l+1);
	int m=(l+r)>>1;
	if(L<=m)
		update(L, R, v, lson);
	if(R>m)
		update(L, R, v, rson);
	pushup(rt);
}
__int64 query(int L, int R, int l, int r, int rt)
{//查询区间[L，R]中的最小值
	if(L<=l && r<=R)//当前结点完全包含在查询区间内
		return mmin[rt];
	pushdown(rt, r-l+1);
	int m=(l+r)>>1;
	__int64 ret=INF;
	if(L<=m)//往左走
		ret=MIN(ret, query(L, R, lson));
	if(R>m)//往右走
		ret=MIN(ret, query(L, R, rson));
	return ret;
}

int main()
{
	int n, m, a, b, c;
	char op;
	scanf("%d", &n);
	build(1, n, 1);
	scanf("%d", &m);
	while(m--)
	{
		scanf("%d%d%c", &a, &b, &op);
		a++;//将区间转换为是1到n
		b++;
		if(a<=b)
		{
			if(op==' ')//意味着是输入三个数的操作
			{
				scanf("%d", &c);
				if(c==0)
					continue;
				update(a, b, c, 1, n, 1);
			}
			else
				printf("%I64d\n", query(a, b, 1, n, 1));
		}
		else
		{
			if(op==' ')
			{
				scanf("%d", &c);
				if(c==0)
					continue;
				update(a, n, c, 1, n, 1);//拆分区间为a到n和1到b
				update(1, b, c, 1, n, 1);
			}
			else
				printf("%I64d\n", MIN(query(a, n, 1, n, 1), query(1, b, 1, n, 1)));
		}
	}
	return 0;
}


联系
我们