[C/C++] Codeforce 52C - Circular RMQ

C. Circular RMQ

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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).

 

 

 

<코드>

#include<bits/stdc++.h>

using namespace std;
struct node
{
	long long l, r, w, tag;
}tree[800005];
long long n, m, q, x, y, k, ans;
void build(long long l, long long r, long long k)
{
	tree[k].l = l; tree[k].r = r;
	if (l == r)
	{
		scanf("%lld", &tree[k].w);
		return;
	}
	long long mid = (l + r) / 2;
	build(l, mid, k * 2);
	build(mid + 1, r, k * 2 + 1);
	tree[k].w = min(tree[k * 2].w, tree[k * 2 + 1].w);
}
void add(long long k, long long w, long long ll, long long rr)
{
	long long l = tree[k].l, r = tree[k].r;
	if (l >= ll && r <= rr)
	{
		tree[k].tag += w;
		return;
	}
	//cout<<k<<" "<<l<<" "<<r<<endl;
	long long mid = (l + r) / 2;
	//cout<<x<<" "<<y<<endl;
	if (ll <= mid)add(k * 2, w, ll, rr);
	if (rr > mid)add(k * 2 + 1, w, ll, rr);
	tree[k].w = min(tree[k * 2].w + tree[k * 2].tag, tree[k * 2 + 1].w + tree[k * 2 + 1].tag);
	return;
}
long long query(long long k, long long ll, long long rr)
{
	if (tree[k].l >= ll && tree[k].r <= rr)
	{
		return tree[k].w + tree[k].tag;
	}
	if (tree[k].l > rr || tree[k].r < ll)
	{
		return 213704440000;
	}
	long long mid = (tree[k].l + tree[k].r) / 2, lc, rc;
	lc = query(k * 2, ll, rr);
	rc = query(k * 2 + 1, ll, rr);
	return min(lc, rc) + tree[k].tag;
}
int main()
{
	cin >> n;
	build(1, n, 1);
	cin >> m;
	for (long long i = 1; i <= m; i++)
	{
		cin >> x >> y;
		x++; y++;
		char c = getchar();
		if (c == '\n')
		{
			//4 1
			ans = 213744040000;
			if (x > y)cout << min(query(1, x, n), query(1, 1, y));
			else cout << query(1, x, y);
			cout << endl;
		}
		else
		{
			cin >> q;
			if (x > y)add(1, q, x, n), add(1, q, 1, y);
			else add(1, q, x, y);
		}
	}
	return 0;
}

 

 

https://codeforces.com/problemset/problem/52/C

Problem - 52C - Codeforces