2016-08-23

Codeforces 52C Circular RMQ【zkw线段树】

题目链接：

http://codeforces.com/contest/52/problem/C

题意：

区间可以加或者减去一个数，求区间最小值

分析：

参考zkw线段树解决区间rmq
一个很重要的思想就是利用差分

差分是化绝对为相对的重要手段

标记永久化后就是值，只不过这种值是相对的

计算答案时可以利用从节点到根部的信息

采用差分的方式，每个结点保存其与父结点的差值，即$T[i] = T[i] - T[i <<1]$，区间更新的时候最多只修改左右两个边界的点和其父节点，每层最多只修改$4$个结点。区间查询的姿势就是从叶子结点一层一层往上爬，每次取最大或最小把答案累加起来即可。
注意几点：

更新要更新到根结点，不然面对多次更新的情况会出错
while(l > 1){tmp = min(T[l], T[l ^ 1]), T[l] -= tmp, T[l ^ 1] -= tmp, T[l >>= 1] += tmp;}
查询区间为闭区间。因为每个结点存的内容都依赖于他的父亲，而如果采用开区间的话，边界结点的父亲也被算作开区间而不会算到答案中，这样就会影响该父节点另一个在闭区间内的儿子，所以对于这种差分的情况查询的时候要采用闭区间。


/*************************************************************************
    > File Name: 52c.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/23 10:23:31
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 5;
int M;
ll T[maxn << 2];
void build(int n)
{
	for(M = 1; M <= n + 1; M <<= 1);
	for(int i = M + 1; i <= M + n; i++) scanf("%I64d", &T[i]);
	for(int i = M - 1; i; i--){
		T[i] = min(T[i << 1], T[i << 1 | 1]);
	}
	for(int i = M + n; i; i--){
		T[i] = T[i] - T[i >> 1];
	}
}
void update(int l, int r, int x)
{
	l = l + M - 1, r = r + M + 1;
	ll tmp;
	for(; l^r^1; l >>= 1, r >>= 1){
		if(~l & 1) T[l ^ 1] += x;
		if(r & 1) T[r ^ 1] += x;
		tmp = min(T[l], T[l ^ 1]), T[l] -= tmp, T[l ^ 1] -= tmp, T[l >> 1] += tmp;
		tmp = min(T[r], T[r ^ 1]), T[r] -= tmp, T[r ^ 1] -= tmp, T[r >> 1] += tmp;
	}
	while(l > 1){
		tmp = min(T[l], T[l ^ 1]), T[l] -= tmp, T[l ^ 1] -= tmp, T[l >>= 1] += tmp;
	}
}
ll query(int l, int r)
{
	l = l + M, r = r + M;//闭区间
	ll lans = 0, rans = 0;
	if(l != r){
		for(; l^r^1; l >>= 1, r >>= 1){
			lans += T[l], rans += T[r];
			if(~l & 1) lans = min(lans, T[l ^ 1]);
			if(r & 1) rans = min(rans, T[r ^ 1]);
		}
	}
	ll ans = min(lans + T[l], rans + T[r]);
	while(l > 1) ans += T[l >>= 1];
	return ans;
}
int main (void)
{
	int n;scanf("%d", &n);
	build(n);
	int m;scanf("%d", &m);
	int x, y, z;
	ll ans;
	for(int i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		if(getchar() == '\n'){
			if(x > y) ans = min(query(x + 1, n), query(1, y + 1));
			else ans = query(x + 1, y + 1);
			printf("%I64d\n", ans);
		}else{
			scanf("%d", &z);
			if(x > y){
				update(x + 1, n, z); update(1, y + 1, z);
			}else update(x + 1, y + 1, z);
		}
	}
	return 0;
}