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\) 分钟最多能取多少个石子。
第一行正整数 \(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\)
有 \(M\) 行,第 \(i\) 行表示第 \(i\) 分钟最多能取多少石子。
Sample
53 2 4 732 5 2 6 4 92 41 23 5
Output
255
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 #include #include #include #include #include #include