CF1172F 题解

First Post:

Last Update:

这题还是想岔了一些，也有可能是图画错了，有些性质观察得并不是很彻底。和题解无限接近了属于是（

对于一个区间 ，显然，对于初始数 ，设 表示最终值那么 是一个关于 的分段函数，且最多 段，因为只会减 个 。

对于一段数列，设 表示初始数最少是多少，使得做完这个数列之后减去了 个 。

在序列上的问题， 又高达 ，当然首选线段树。

考虑怎么合并 和 的 数组。

当然是用左边的 和右边的 来更新 。

下文设 的和为 。

考虑更新的条件，我们要确保对于一个在 中的数，其在做完左边之后还大于等于 。

那么就有条件 。

那么更新的时候，从 反推回 ，就得到转移式 。

直接这么做的话，合并两个区间的复杂度是平方的，不如暴力。

事实上，对于这种 的转移，是可以考虑双指针优化的。（当然，要求 均单调）

考察双指针的可行性，首先， 肯定是单调递增的。

我们再说明，对于 相同的转移，我们取 最小的一定不劣。

即证明 不劣于 。

首先有 ，即 。

且有 。

所以 。

显然会有 。

但有这点还是不够，为了能够用指针维护决策点，我们还需说明， 是关于 单调递增的，也就是 。

由于 表示最小的初始值，所以 经过一段区间后，最大值必定是 ，否则我们可以将初始值调小一点，所以我们需要再增加至少 才可以再减掉一个 。

那么，我们只需维护一个指针 ，表示当前最大的满足条件的 ，在 自增时， 对应移动，用走到的那些 转移即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,Sz = N << 2;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
template<typename T> inline void ckmin(T &x,const T &y) { if(x > y) x = y;}
template<typename T> inline void ckmax(T &x,const T &y) { if(x < y) x = y;}
int n,m,p,a[N];

struct node{
	int l,r,len;
	ll sum;
	vector<ll> c;
};
node tr[Sz];
#define ls k << 1
#define rs k << 1 | 1
inline void pushup(int k)
{
	tr[k].sum = tr[ls].sum + tr[rs].sum;
	for(int x = 0,y = 0;x <= tr[ls].len;x++)
	{
		if(y > tr[rs].len) --y;
		for(;y <= tr[rs].len;++y)
		{
			ll val = tr[rs].c[y] + 1ll * x * p - tr[ls].sum;
			ll lim = tr[ls].c[x + 1] - 1 - 1ll * x * p + tr[ls].sum;
			if(lim < tr[rs].c[y]) {if(y) --y;break; /* 当前 y 不合法，要回退一个*/}
			ckmin(tr[k].c[x + y],max(tr[ls].c[x],val));
		}
	}
}
void build(int k,int l,int r)
{
	tr[k].l = l;tr[k].r = r;
	tr[k].len = r - l + 1;
	for(int i = 1;i <= tr[k].len + 2;i++) tr[k].c.push_back(INF);
	tr[k].c[0] = -INF;
	if(l == r) { tr[k].sum = a[l];tr[k].c[1] = p - a[l];return;}
	int mid = l + r >> 1;
	build(k << 1,l,mid);
	build(k << 1 | 1,mid + 1,r);
	pushup(k);
	// printf("[%d,%d]: ",l,r);
	// for(auto i : tr[k].c) printf("%d ",i);
	// printf("\n");
}
ll Now; // 全局变量，初始时为 0,遇到一个区间，就让 now = f(l,r,now)，最后拼凑出询问区间的答案。
void Query(int k,int l,int r,int x,int y)
{
	if(l > y || r < x) return;
	if(x <= l && r <= y) 
	{
		int pos = upper_bound(tr[k].c.begin(),tr[k].c.end(),Now) - tr[k].c.begin() - 1;
		Now = Now - 1ll * pos * p + tr[k].sum;
		return;
	}
	int mid = l + r >> 1;
	Query(k << 1,l,mid,x,y);
	Query(k << 1 | 1,mid + 1,r,x,y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> p;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	build(1,1,n);
	for(int i = 1;i <= m;i++)
	{
		int l,r;
		cin >> l >> r;
		Now = 0;
		Query(1,1,n,l,r);
		cout << Now << endl;
	}
	return 0;
}
≡