loj#6029. 「雅礼集训 2017 Day1」市场(线段树)

题意

Sol

势能分析。

除法是不能打标记的，所以只能暴力递归。这里我们加一个剪枝：如果区间内最大最小值的改变量都相同的话，就变成区间减。

这样复杂度是\((n + mlogn) logV\)的。

简单的证明一下：如果没有加的话，每个节点会被除至多log次, 总会除4nlogn次,每次区间加会恢复log个点的势能函数，这样总递归次数就是\(nlog^2n\)。

下传标记的时候别忘了把min和max都更新一下

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#define LL long long

#define ull unsigned long long

#define Fin(x) {freopen(#x".in","r",stdin);}

#define Fout(x) {freopen(#x".out","w",stdout);}

using namespace std;

const int MAXN = 1e6 + 10, INF = 1e9 + 1;

const double eps = 1e-9, pi = acos(-1);

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, Q, a[MAXN];

LL mx[MAXN], mn[MAXN], add[MAXN], sum[MAXN], ll[MAXN], rr[MAXN];

#define ls k << 1

#define rs k << 1 | 1

void update(int k) {

	mx[k] = max(mx[ls], mx[rs]);

	mn[k] = min(mn[ls], mn[rs]);

	sum[k] = sum[ls] + sum[rs];

}

void ps(int k, int v) {

	sum[k] += (rr[k] - ll[k] + 1) * v;

	mn[k] += v; mx[k] += v;

	add[k] += v;

}

void pushdown(int k) {

	if(!add[k]) return ;

	ps(ls, add[k]); ps(rs, add[k]);

	add[k] = 0;

}

void Build(int k, int l, int r) {

	ll[k] = l; rr[k] = r;

	if(l == r) {sum[k] = mx[k] = mn[k] = a[l]; return ;}

	int mid = l + r >> 1;

	Build(ls, l, mid); Build(rs, mid + 1, r);

	update(k);

}

void Add(int k, int l, int r, int ql, int qr, LL v) {

	if(ql <= l && r <= qr) {ps(k, v); return ;}

	int mid = l + r >> 1;

	pushdown(k);

	if(ql <= mid) Add(ls, l, mid, ql, qr, v);

	if(qr  > mid) Add(rs, mid + 1, r, ql, qr, v);

	update(k);

}

LL get(LL x, int d) {

	return (x >= 0 ? x / d : (x - d + 1) / d);

}

void Div(int k, int l, int r, int ql, int qr, LL v) {

	if(ql <= l && r <= qr && (mx[k] - get(mx[k], v) == mn[k] - get(mn[k], v))) {

		ps(k, get(mx[k], v) - mx[k]);

		return ;

	}

	pushdown(k);

	int mid = l + r >> 1;

	if(ql <= mid) Div(ls, l, mid, ql, qr, v);

	if(qr  > mid) Div(rs, mid + 1, r, ql, qr, v);

	update(k);

}

LL Min(int k, int l, int r, int ql, LL qr) {

	if(ql <= l && r <= qr) return mn[k];

	int mid = l + r >> 1;

	pushdown(k);

	if(ql > mid) return Min(rs, mid + 1, r, ql, qr);

	else if(qr <= mid) return Min(ls, l, mid, ql, qr);

	else return min(Min(ls, l, mid, ql, qr), Min(rs, mid + 1, r, ql, qr));

}

LL Sum(int k, int l, int r, int ql, int qr) {

	if(ql <= l && r <= qr) return sum[k];

	int mid = l + r >> 1;

	pushdown(k);

	if(ql > mid) return Sum(rs, mid + 1, r, ql, qr);

	else if(qr <= mid) return Sum(ls, l, mid, ql, qr);

	else return Sum(ls, l, mid, ql, qr) + Sum(rs, mid + 1, r, ql, qr);

}

signed main() {

	N = read(); Q = read();

	for(int i = 1; i <= N; i++) a[i] = read();

	Build(1, 1, N);

	while(Q--) {

		int opt = read(), l = read() + 1, r = read() + 1;

		if(opt == 1) {

			int c = read();

			Add(1, 1, N, l, r, c);

		} else if(opt == 2) {

			int d = read();

			Div(1, 1, N, l, r, d);

		} else if(opt == 3) {

			cout << Min(1, 1, N, l, r) << '\n';

		} else {

			cout << Sum(1, 1, N, l, r) << '\n';

		}

	}

    return 0;

}

巴特西

loj#6029. 「雅礼集训 2017 Day1」市场(线段树)

题意

Sol

最新文章

热门文章