【BZOJ 2138】stone

浅浅的花香味﹌ 2023-08-17 15:48 35阅读 0赞

# Problem #

## Description ##

话说 \\(Nan\\) 在海边等人，预计还要等上 \\(M\\) 分钟。为了打发时间，他玩起了石子。

\\(Nan\\) 搬来了 \\(N\\) 堆石子，编号为 \\(1\\) 到 \\(N\\)，每堆包含 \\(A\_i\\) 颗石子。

每 \\(1\\) 分钟，\\(Nan\\) 会在编号在 \\(\[L\_i, R\_i\]\\) 之间的石堆中挑出任意 \\(K\_i\\) 颗扔向大海（好疼的玩法），如果 \\(\[L\_i, R\_i\]\\) 剩下石子不够 \\(K\_i\\) 颗，则取尽量地多。为了保留扔石子的新鲜感，\\(Nan\\) 保证任意两个区间 \\(\[L\_i, R\_i\]\\) 和 \\(\[L\_j, R\_j\]\\) ，不会存在 \\(L\_i\\le L\_j \\& R\_j\\le R\_i\\) 的情况，即任意两段区间不存在包含关系。

可是，如果选择不当，可能无法扔出最多的石子，这时 \\(Nan\\) 就会不高兴了。所以他希望制定一个计划，他告诉你他 \\(m\\) 分钟打算扔的区间 \\(\[L\_i, R\_i\]\\) 以及 \\(K\_i\\)。

现在他想你告诉他，在满足前 \\(i-1\\) 分钟都取到你回答的颗数的情况下，第 \\(i\\) 分钟最多能取多少个石子。

## Input Format ##

第一行正整数 \\(N\\)，表示石子的堆数；

第二行正整数 \\(x,y,z,P\\)，(\\(1\\le x,y,z\\le N, P\\le500\\))

有等式 \\(A\_i=\[(i-x)^2+(i-y)^2+(i-z)^2\]\\ mod\\ P\\)；

第三行正整数 \\(M\\) ，表示有 \\(M\\) 分钟；

第四行正整数 \\(K\_1,K\_2,x,y,z,P\\)，(\\(x,y,z\\le1000,P\\le10000\\))

有等式 \\(K\_i=(x\*K\_\{i-1\}+y\*K\_\{i-2\}+z)mod P\\)。

接下来 \\(M\\) 行，每行两个正整数 \\(L\_i,R\_i\\)。

\\(N\\le40000, M\\le N, 1\\le L\_i\\le R\_i\\le N, A\_i\\le500\\)

## Output Format ##

有 \\(M\\) 行，第 \\(i\\) 行表示第 \\(i\\) 分钟最多能取多少石子。

## Sample ##

### Input ###

5
    3 2 4 7
    3
    2 5 2 6 4 9
    2 4
    1 2
    3 5

### Output ###

2
    5
    5

## Explanation ##

石子每堆个数分别为 \\(0,5,2,5,0\\)。

第 \\(1\\) 分钟，从第 \\(2\\) 到第 \\(4\\) 堆中选 \\(2\\) 个；

第 \\(2\\) 分钟，从第 \\(1\\) 到第 \\(2\\) 堆中选 \\(5\\) 个；

第 \\(3\\) 分钟，从第 \\(3\\) 到第 \\(5\\) 堆中选 \\(8\\) 个，但最多只能选 \\(5\\) 个。

# Algorithm #

线段树

# Mentality #

神奇题目。由于它要求的策略不针对整体，只需要局部最优，所以才有了解法。

设当前处理到了第 \\(p\\) 个区间。

设 \\(S\_\{i,j\}\\) 为区间 \\(\[i,j\]\\) 里的石子数之和，设 \\(T\_\{i,j\}\\) 为之前的，严格为 \\(\[i,j\]\\) 子区间的询问区间取的石子数之和。

则在任一时刻，对于任意区间 \\(\[l,r\]\\) 都应该有 \\(T\_\{l,r\}\\le S\_\{l,r\}\\) ，毕竟拿的石子数总不能多于存在的。

设 \\(s\_i\\) 为 \\(\[1,i\]\\) 的石子数和，\\(Tl\_i\\) 为之前的，左端点位于 \\(\[1,i\]\\) 的询问区间取的石子数之和，\\(Tr\_i\\) 为之前的，右端点端点位于 \\(\[1,i\]\\) 的询问区间取的石子数之和。

则可以用它们写成不等式：

\\\[ T\_\{l,r\}\\le S\_\{l,r\}\\\\ Tr\_r-Tl\_\{l-1\}\\le s\_r-s\_\{l-1\}\\\\ s\_\{l-1\}-Tl\_\{l-1\}\\le s\_r-Tr\_r \\\]

设 \\(g\_i = s\_\{i - 1\} - Tl\_\{i - 1\}, f\_i = s\_i - Tr\_i\\) ，则必须有 \\(g\_l\\le f\_r\\) 。对于一个区间而言，最多能取 \\(S\_\{l,r\} - T\_\{l,r\}=f\_r-g\_l\\) 个石子。

考虑对于当前询问 \\(p\\) 而言，\\(\[L\_p,R\_p\]\\) 的决策会影响到所有包含此区间的区间 \\(T\\) 值。为了满足 \\(\\forall T\_\{l,r\}\\le S\_\{l,r\}\\) ，则我们能选择的，最多的石子数应该是 \\(Min\_\{l\\in\[1,L\_p\], r\\in \[R\_p, n\]\} S\_\{l,r\} - T\_\{l,r\}\\) ，然后和询问所需石子数 \\(K\_p\\) 取 \\(Min\\)。

由于 \\(S\_\{l,r\} - T\_\{l,r\}\\) 可以写成 \\(f\_r-g\_l\\) 的形式，所以每个询问的答案就可以写成 \\(Min\_\{i\\in\[R\_p,n\]\}f\_i - Max\_\{i\\in\[1,L\_p\]\}g\_i\\) 。

用线段树维护即可。

# Code #

#include <algorithm> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; long long read() { long long x = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar(); while (isdigit(ch)) { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } return x * w; } #define ls (o << 1) #define rs ((o << 1) + 1) #define mid ((l + r) >> 1) const int Max_n = 4e4 + 5; int n, m, x, y, z, mod, Ans; int s[Max_n]; int f[Max_n << 2], g[Max_n << 2], tagf[Max_n << 2], tagg[Max_n << 2]; int L, R, ans; int ned[Max_n], ln, rn; bool fl; int sqr(int x) { return x * x; } void pushup(int *f, int o) { if (!fl) f[o] = min(f[ls], f[rs]); else f[o] = max(f[ls], f[rs]); } void pushdown(int *f, int *t, int o) { t[ls] += t[o], f[ls] += t[o]; t[rs] += t[o], f[rs] += t[o]; t[o] = 0; } void build(int *f, int o, int l, int r) { if (l == r) { if (!fl) f[o] = s[l]; else if (l) f[o] = s[l - 1]; return; } build(f, ls, l, mid); build(f, rs, mid + 1, r); pushup(f, o); } void query(int *f, int *t, int o, int l, int r) { if (L > R) return; if (l >= L && r <= R) { if (!fl) ans = min(ans, f[o]); else ans = max(ans, f[o]); return; } pushdown(f, t, o); if (mid >= L) query(f, t, ls, l, mid); if (mid < R) query(f, t, rs, mid + 1, r); pushup(f, o); } void add(int *f, int *t, int o, int l, int r) { if (L > R) return; if (l >= L && r <= R) { f[o] += ans, t[o] += ans; return; } pushdown(f, t, o); if (mid >= L) add(f, t, ls, l, mid); if (mid < R) add(f, t, rs, mid + 1, r); pushup(f, o); } int main() { #ifndef ONLINE_JUDGE freopen("2138.in", "r", stdin); freopen("2138.out", "w", stdout); #endif n = read(), x = read(), y = read(), z = read(), mod = read(); for (int i = 1; i <= n; i++) { s[i] = (sqr(x - i) % mod + sqr(y - i) % mod + sqr(z - i) % mod) % mod; s[i] += s[i - 1]; } fl = 0, build(f, 1, 0, n); fl = 1, build(g, 1, 0, n); m = read(); ned[1] = read(), ned[2] = read(); x = read(), y = read(), z = read(), mod = read(); for (int i = 3; i <= m; i++) ned[i] = (x * ned[i - 1] % mod + y * ned[i - 2] % mod + z) % mod; for (int q = 1; q <= m; q++) { ln = read(), rn = read(); ans = -2e9, fl = 1, L = 1, R = ln; query(g, tagg, 1, 0, n); Ans = -ans, ans = 2e9, fl = 0, L = rn, R = n; query(f, tagf, 1, 0, n); Ans = min(Ans + ans, ned[q]); printf("%d\n", Ans); fl = 1, L = ln + 1, ans = -Ans; add(g, tagg, 1, 0, n); fl = 0, L = rn; add(f, tagf, 1, 0, n); } }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11443382.html