https://codeforces.com/contest/1136

E. Nastya Hasn’t Written a Legend

 

题意：给定长为 nn 的数列 aa，长为 n−1n-1 的数列 kk，两种操作：询问 a[l]+⋯+a[r]a[l]+\cdots +a[r]；a[i]+=xa[i]+=x，若 a[i+1]<a[i]+k[i]a[i+1]<a[i]+k[i]，则 a[i+1]=a[i]+k[i]a[i+1]=a[i]+k[i]，并继续检查 a[i+2]⋯a[i+2]\cdots。

线段树+二分

令 g[i]=∑j=1ik[j]g[i]=\sum_{j=1}^i k[j]，u[i]=a[i]−g[i]u[i]=a[i]-g[i]。

则 ∑i=lra[i]=∑i=lru[i]+∑i=l−1r−1g[i]\sum_{i=l}^{r}a[i]=\sum_{i=l}^r u[i]+\sum_{i=l-1}^{r-1} g[i]。

由于 g[i]g[i] 始终不变，所以可以预处理出前缀和得到。下面只需要维护 u[i]u[i] 的区间和。

假设 a[i]+=xa[i]+=x，则 u′[i]=u[i]+x=a[i]+x−g[i−1]u'[i]=u[i]+x=a[i]+x-g[i-1]，则 u′[i+1]=a[i]+x+k[i]−g[i]=u′[i]u'[i+1]=a[i]+x+k[i]-g[i]=u'[i]。以此类推，所有被进位到的位置的 uu 都变为 u′[i]u'[i]。

模拟发现当 u[j]<u′[i]u[j]<u'[i] 时，jj 会被进位到。

由 u[i]−u[i−1]=a[i]−(a[i−1]+k[i−1])≥0u[i]-u[i-1]=a[i]-(a[i-1]+k[i-1])\ge 0 得 u[i]u[i] 单调递增。所以可以二分得到满足 u[j]<u′[i]u[j]<u'[i] 的位置，这是一个区间，通过线段树维护区间操作。

所以对于询问操作，线段树求 ∑i=lru[i]\sum_{i=l}^r u[i]，再加上前缀和求 ∑i=l−1r−1g[i]\sum_{i=l-1}^{r-1}g[i]。

对于加法操作，二分得到涉及到的区间，线段树区间标记。

注意这里由于懒标记有正负值，所以初始化为 INF。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, q;
ll a[N], k[N];
ll g[N], s[N], u[N];
ll qg(int l, int r) {
	if (l == 0)return s[r];
	else return s[r] - s[l - 1];
}
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll trs[N << 2], laz[N << 2];
void up(int rt) {
	trs[rt] = trs[rt << 1] + trs[rt << 1 | 1];
}
void build(int l, int r, int rt) {
	laz[rt] = INF;
	if (l == r) {
		trs[rt] = u[l];
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
void down(int l, int r, int rt) {
	ll& x = laz[rt];
	if (x != INF) {
		trs[rt << 1] = x * (mid - l + 1);
		trs[rt << 1 | 1] = x * (r - mid);
		laz[rt << 1] = laz[rt << 1 | 1] = x;
		x = INF;
	}
}
void cg(int ql, int qr, ll x, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		laz[rt] = x;
		trs[rt] = x * (r - l + 1);
		return;
	}
	down(l, r, rt);
	if (ql <= mid)cg(ql, qr, x, lson);
	if (qr > mid)cg(ql, qr, x, rson);
	up(rt);
}
ll qry(int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		return trs[rt];
	}
	down(l, r, rt);
	ll res = 0ll;
	if (ql <= mid)res += qry(ql, qr, lson);
	if (qr > mid)res += qry(ql, qr, rson);
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 1; i < n; i++) {
		scanf("%lld", &k[i]);
		g[i] = g[i - 1] + k[i];
	}
	for (int i = 1; i <= n; i++)s[i] = s[i - 1] + g[i];
	for (int i = 1; i <= n; i++)u[i] = a[i] - g[i - 1];
	build(1, n, 1);
	scanf("%d", &q);
	while (q--) {
		char op;
		scanf(" %c", &op);
		int l, r;
		scanf("%d%d", &l, &r);
		if (op == 's') {
			printf("%lld\n", qry(l, r, 1, n, 1) + qg(l - 1, r - 1));
		}
		else {
			ll k = qry(l, l, 1, n, 1);
			k += r;
			int L = l, R = n;
			while (L < R) {
				int m = (L + R + 1) / 2;
				if (qry(m, m, 1, n, 1) < k)L = m;
				else R = m - 1;
			}
			cg(l, L, k, 1, n, 1);
		}
	}
	return 0;
}