简要题意
有 $m$ 个人要去健身房健身, 健身房总共开放 $n$ 天, 第 $i$ 天的票价为 $a_i$ , 每个人可以在任意一天买任意张票, 若一张票在第 $t$ 天生效, 则它只会在 $[t,t+k-1]$ 的时间内有效.
第 $i$ 个人, 想在第 $l_i$ 到第 $r_i$ 天的每一天来健身房, 且从第 $l_i$ 天开始选票, 问最小要多少花多少钱能满足 $l_i$ 到 $r_i$ 都可以进入健身房.
$n,q \leqslant 3 \times 10^5$ .
题解
显然是贪心的选择买哪种票, 设 $b_i = \min\limits_{j=i-k}^{i}{\{ a_j \}}$ , 则询问区间 $[l,r]$ 的答案为 $a_i+b_{l+k}+min{\{b_{l+k},b_{l+2k}\}}+\dots + min{\{b_{l+k},\dots ,b_{l+tk}\}}$ , 其中 $t$ 为最大的满足 $l+tk \leqslant r$ 的整数, 可以直接把 $r$ 变成 $l+\frac{r-l}{k}\times k$ .
考虑后面前缀 $min$ 的前缀和形式的式子, 设有序列 $c$ , 求 $f_i = \sum\limits_{j=i}^{n}{min{\{c_{i \dots j}\}}}$ .
这部分可以单调栈处理. 设 $nxt_i$ 表示在 $i$ 之后第一个值小于 $c_i$ 的位置, 则 $f_i = f_{nxt_i}+c_i \times (nxt_i-i)$ .
题目中的形式是求 $\sum\limits_{i=l}^{r}{\{c_{l \dots i}\}}$ 求这个可以找到 $c_p = min{\{c_{l \dots r}\}}$ , 则前面的式子就等于 $f_l-f_p+c_p \times(r-p+1)$ .
用 $ST$ 表维护区间最小值, 再要注意是 $k$ 个一组的处理.
代码
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << endl
template <typename T>
inline bool read(T &x) {
int f = 1,c = getchar();x = 0;
while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
return read(x) && read(args...);
}
namespace run {
const int maxn = 6e5+10,maxlg = 24;
pii g[maxn][maxlg];
int lg[maxn];
int f[maxn],nxt[maxn],b[maxn];
int stk[maxn],top;
int n,m,k;
inline pii query(int l,int r) {
if (l > r)return pii(0,0);
int tmp = lg[r-l+1];
return min(g[l][tmp],g[r-(1<<tmp)+1][tmp]);
}
inline int calc(int l,int r) {
int p = query(l-k,r).second;
if (p == l-k)p += k;
p = p+(r-p)%k;
return f[l]-f[p]+b[p]*(r/k-p/k+1);
}
inline int main() {
read(n,m,k);
lg[0] = -1;
for (register int i = 1;i <= n;++i)lg[i] = lg[i>>1]+1,read(g[i][0].first),g[i][0].second = i;
for (register int i = 1;i < maxlg;++i)
for (register int j = 1;j+(1<<i)-1 <= n;++j)
g[j][i] = min(g[j][i-1],g[j+(1<<(i-1))][i-1]);
for (register int i = k+1;i <= n;++i)b[i] = query(i-k,i).first;
stk[++top] = n+1;
for (register int l = k+1;l+k <= n && l <= (k<<1);++l) {
int r = l+(n-l)/k*k;top = 1;
for (register int i = r;i >= l;i -= k) {
while (top > 1 && b[i] <= b[stk[top]])--top;
nxt[i] = stk[top];
f[i] = f[nxt[i]]+b[i]*(nxt[i]/k-i/k);
stk[++top] = i;
}
}
for (register int i = 1,l,r;i <= m;++i) {
read(l,r);r = l+(r-l)/k*k;
int ans = g[l][0].first+(l+k <= r ? calc(l+k,r) : 0);
printf("%lld\n",ans);
}
cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
}
#undef int
#define demonlover
int main() {
#ifdef demonlover
freopen("CF1601E.in","r",stdin);
freopen("CF1601E.out","w",stdout);
#endif
return run :: main();
}
|