本文主要是介绍Circular RMQ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 1
| Input | Output |
|---|---|
4 1 2 3 4 4 3 0 3 0 -1 0 1 2 1 | 1 0 0 |
思路：
树形结构。
数据较大时可以使用位运算。
以及注意命令的判断。
#include<iostream>
using namespace std;
typedef long long LL;
const LL INF = 0x3fffffff;
struct ss
{LL v,tag;
}a[200000 << 2];
LL Min(LL a,LL b)
{return a < b ? a:b;
}void pushup(int cur)
{a[cur].v = Min(a[cur<<1].v,a[cur<<1|1].v);
}void built(int l,int r,int cur)
{a[cur].v = 0;a[cur].tag = 0;if(l == r){scanf("%I64d", &a[cur].v);return ;}int mid = (l + r) >> 1;built(l, mid,cur << 1);built(mid + 1,r,cur << 1|1);pushup(cur);
}void pushdown(int cur)
{if(a[cur].tag != 0){a[cur<<1].tag += a[cur].tag;a[cur<<1|1].tag += a[cur].tag;a[cur<<1].v += a[cur].tag;a[cur<<1|1].v += a[cur].tag;a[cur].tag = 0;}
}void update(int l,int r,int ll,int rr,int cur,LL v)
{if(l<=ll&&r>=rr){a[cur].v += v;a[cur].tag += v;return ;}pushdown(cur);int mid = (ll +rr)>>1;if(mid < r) update(l,r,mid + 1,rr,cur<<1|1,v);if(mid >= l) update(l,r,ll,mid,cur<<1,v);pushup(cur);
}LL quiry(int l,int r,int ll,int rr,int cur)
{if(l<=ll&&r>=rr){return a[cur].v;} pushdown(cur);int mid = (ll + rr) >> 1;LL t1 =INF;LL t2 = INF;if(mid < r) t1 = quiry(l,r,mid + 1,rr,cur<<1|1);if(mid >= l) t2 = quiry(l,r,ll,mid,cur<<1);return Min(t1,t2);
}int main()
{int n;scanf("%d", &n);built(1,n,1);int m;scanf("%d", &m);while(m--){int a,b,c;char ch;scanf("%d%d%c", &a, &b, &ch);a++,b++;if(ch != ' '){if(a>b){LL t1=quiry(a,n,1,n,1);LL t2 = quiry(1,b,1,n,1);printf("%I64d\n",Min(t1,t2));}elseprintf("%I64d\n",quiry(a,b,1,n,1));}else {scanf("%d", &c);if(a>b){update(a,n,1,n,1,c);update(1,b,1,n,1,c);}else update(a,b,1,n,1,c);}}return 0;
}这篇关于Circular RMQ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
