{"problem":{"name":"[POI 2020/2021 R3] 扫雪波特 / Surowa zima","description":{"content":"有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。 有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。 简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\\bold{\\frac1k}$，需要一秒；扫雪必须移动。** 给出每天机器的初始","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9404"},"statements":[{"statement_type":"Markdown","content":"有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。\n\n有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。\n\n简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\\bold{\\frac1k}$，需要一秒；扫雪必须移动。**\n\n给出每天机器的初始位置，机器初始没电，问每天清除所有雪的最少时间。终点任意。\n\n带修，即充电站可能损坏或修好（第一天之前都是好的），但保证每天都至少有一个好的充电站（所以不会无解）。\n\n## Input\n\n第一行四个整数 $n,l,k,d$。\n\n第二行 $n$ 个整数 $x_1,x_2,\\dots,x_n$，表示充电站的位置，保证 $0\\leq x_1<x_2<\\dots<x_n\\leq l$。\n\n接下来 $3d$ 行，描述 $d$ 天的事件：\n\n- 第一行三个整数 $z,u,p$，分别表示昨晚修好的充电站数量，损坏的数量，和机器的初始位置。\n- 第二行 $z$ 个整数，表示被修好的充电站编号。\n- 第三行 $u$ 个整数，表示损坏的充电站编号。\n\n## Output\n\n$d$ 行，每行一个整数，表示每天的答案。\n\n[samples]\n\n## Background\n\n译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Surowa zima](https://szkopul.edu.pl/problemset/problem/QCCQf92wAoWAOoJ3tHoypvp3/statement/)。\n\nd1t3。\n\n## Note\n\n样例解释：$3\\rightarrow2_{充电}\\Rightarrow0\\rightarrow2_{充电}\\Rightarrow4\\rightarrow5_{充电}\\Rightarrow4$。$\\rightarrow$ 表示移动，$\\Rightarrow$ 表示移动并扫雪。\n\n对于所有数据，$1\\leq n\\leq 250000$，$1\\leq l\\leq 10^9$，$1\\leq k\\leq l$，$1\\leq d\\leq 250000$，$\\sum z,\\sum u\\leq 500000$。\n\n| 子任务编号 | 附加限制 | 分数 |\n| :----------: | :----------: | :----------: |\n| 1 | $l\\leq 12$，$d\\leq 50$ | 10 |\n| 2 | $l\\leq 500$，$d\\leq 50$，$k=1$ | 12 |\n| 3 | $l\\leq 5000000$，$d\\leq 20$ | 8 |\n| 4 | $z=u=0$ | 8 |\n| 5 | $z,u\\leq 100$，$k\\leq 50$ | 20 |\n| 6 | $k=1$ | 18 |\n| 7 |  | 24 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9404","tags":["模拟","贪心","2020","平衡树","POI（波兰）","构造","分类讨论"],"sample_group":[["3 5 2 1\n2 3 5\n0 1 3\n\n2\n","9\n"],["5 12 1 5\n1 3 6 9 11\n0 1 1\n\n1\n1 1 3\n1\n2\n1 1 6\n2\n3\n1 1 9\n3\n4\n1 1 11\n4\n5\n","33\n33\n36\n33\n33\n"],["11 100 1 26\n0 10 20 30 40 50 60 70 80 90 100\n0 5 0\n\n2 4 6 8 10\n5 6 4\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 8\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 12\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 16\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 20\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 24\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 28\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 32\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 36\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 40\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 44\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 48\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 52\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 56\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 60\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 64\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 68\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 72\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 76\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 80\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 84\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 88\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 92\n2 4 6 8 10\n1 3 5 7 9 11\n6 5 96\n1 3 5 7 9 11\n2 4 6 8 10\n5 6 100\n2 4 6 8 10\n1 3 5 7 9 11\n","1090\n1096\n1098\n1092\n1094\n1100\n1094\n1092\n1098\n1096\n1090\n1096\n1098\n1092\n1094\n1100\n1094\n1092\n1098\n1096\n1090\n1096\n1098\n1092\n1094\n1100\n"],["见附件","见附件"],["见附件","1000000000000000000\n2001007996000\n"]],"created_at":"2026-03-03 11:09:25"}}