网站如何做更新,网店管家,用层还是表格做网站快,微信如何做模板下载网站也许更好的阅读体验 D e s c r i p t i o n \mathcal{Description} Description n 2 n2 n2个点编号 0 #xff5e; n 1 0#xff5e;n1 0#xff5e;n1#xff0c;每个点有点权#xff0c;要求选若干个点使得总点权最小#xff0c;其中编号为 0 0 0和 n 1 n1 n1的点必…也许更好的阅读体验 D e s c r i p t i o n \mathcal{Description} Description n 2 n2 n2个点编号 0 n 1 0n1 0n1每个点有点权要求选若干个点使得总点权最小其中编号为 0 0 0和 n 1 n1 n1的点必须选且点权为 0 0 0同时满足任意两个被选的点之间的距离不超过 k k k此外还会给一个 01 01 01串表示 1 n 1n 1n这些点是否为必选的点 现在会给 m m m个询问每个询问为如果将编号为 x x x的点权修改为 v v v的答案会是什么 多组数据 n ≤ 5 × 1 0 5 , ∑ n ≤ 2 × 1 0 6 , 1 ≤ m , k ≤ 3 × 1 0 3 ∑ m ∑ k ≤ 1 0 4 n\le 5× 10^5,\sum n\le 2×10^6,1\le m, k\le 3×10^3\sum m\sum k\le10^4 n≤5×105,∑n≤2×106,1≤m,k≤3×103∑m∑k≤104 S o l u t i o n \mathcal{Solution} Solution 最近做做往年 I C P C ICPC ICPC题这题算是个金牌题做的快可以摸金的那种意外地发现很简单 没有修改的话是个很经典的单调栈优化 D P DP DP 设 f i f_i fi表示 [ 0 , i ] [0,i] [0,i]这个区间满足条件且在i选了i的最小花费转移方程为 f i m i n { f j } f_imin\{f_j\} fimin{fj}这个过程单调栈优化可以做到 O ( n ) O(n) O(n)其中 j j j属于 [ i − k , i − 1 ] [i-k,i-1] [i−k,i−1] 对于某个位置必须选择那么就在计算该位置的 d p dp dp值后将单调栈清空再将该位置放进去相当于之后的选择一定有这个位置了 正着做和反着做差不多再设 g [ i ] g[i] g[i]表示满足 [ i , n 1 ] [i,n1] [i,n1]这个区间的最小花费则答案就是 m i n { f i m i n { g j } } min\{f_imin\{g_j\}\} min{fimin{gj}} 考虑修改某个位置的值因为任意一个长度为 k k k的区间一定有一个必须选因此当修改一个位置的值时只要从那个位置开始往后走 k k k步算一次 f i m i n { g j } f_imin\{g_j\} fimin{gj}就可以算出答案这样复杂度是 O ( m k ) O(mk) O(mk)是满足题意的 现在问题就是怎么在修改后 O ( 1 ) O(1) O(1)的算出 f i f_i fi首先考虑到如果把所有到 i i i的单调栈存下来修改了 i i i位置后就从这个单调栈重新做一次但是这样时空都不满足要求为了解决这个问题可以将询问都排序这样就可以共用那个单调栈了 C o d e \mathcal{Code} Code
#include cstdio
#include algorithm
#define ll long long
#define inf 112345678901234567
using namespace std;
const int maxn 5e5 10;
struct IO {template class TIO operator(T res) {res 0;char ch;bool flag false;while ((ch getchar()) 9 || ch 0) flag | ch -;while (ch 0 ch 9) res (res 3) (res 1) (ch ^ 0), ch getchar();if (flag) res ~res 1;return *this;}
} cin;
int T, n, m, k, hd, ed;
int a[maxn], q[maxn], q2[maxn], fr[maxn], x[maxn], v[maxn], id[maxn];
ll f[maxn], tf[maxn], g[maxn], ans[maxn];
char s[maxn];
bool cmp (int a, int b) { return x[a] x[b]; }
int main ()
{cin T;while (T--) {cin n k;for (int i 1; i n; i) cin a[i];scanf(%s, s 1);a[0] a[n 1] f[0] 0;q[hd ed 1] 0;for (int i 1; i n 1; i) {while (q[hd] i - k) hd;f[i] f[q[hd]] a[i];if (s[i] 1) q[hd ed 1] i;else {while (ed hd f[q[ed]] f[i]) --ed;q[ed] i;}}q[hd ed 1] n 1, fr[n 1] n 1, g[n 1] 0;for (int i n; i 0; --i) {while (q[hd] i k) hd;g[i] g[q[hd]] a[i];fr[i] q[hd];if (s[i] 1) q[hd ed 1] i;else {while (ed hd g[q[ed]] g[i]) --ed;q[ed] i;}}cin m;for (int i 1; i m; i) scanf(%d%d, x[i], v[i]), id[i] i, ans[i] inf;sort(id 1, id m 1, cmp);q[hd ed 1] 0;int cur 1;for (int i 1; i n; i) {while (q[hd] i - k) hd;while (x[id[cur]] i cur m) {int hd2 hd, ed2 ed, t a[i];a[i] v[id[cur]];for (int j hd; j ed; j) q2[j] q[j];int mx min(i k, n 1);for (int j i; j mx; j) {while (q2[hd2] j - k) hd2;tf[j] tf[q2[hd2]] a[j];ans[id[cur]] min(ans[id[cur]], tf[j] g[fr[j]]);if (s[j] 1) q2[hd2 ed2 1] j;else {while (ed2 hd2 tf[q2[ed2]] tf[j]) --ed2;q2[ed2] j;}}a[i] t;cur;}tf[i] tf[q[hd]] a[i];if (s[i] 1) q[hd ed 1] i;else {while (ed hd f[q[ed]] f[i]) --ed;q[ed] i;}}for (int i 1; i m; i) printf(%lld\n, ans[i]);}return 0;
} 如有哪里讲得不是很明白或是有错误欢迎指正 如您喜欢的话不妨点个赞收藏一下吧
