ryp 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-28 20:34:30
赛时真脑瘫了。。
每个点只有两种选择：要么单独搞个雷达，代价是 $c$；要么和上一个连起来，代价是它们之间的距离，因为雷达修在点上肯定优于不在点上。
于是我们记录一下差，排序然后直接做就可以了。不想写二分，写的离线，决策点单调不左。
对于每一位，如果有奇数个一，那么分奇数组能保证这一位是 1（最优），否则选偶数个。
优先保证最高位。发现对于奇数的情况，选整体不劣；对于偶数的情况，只选一个不劣。奇数直接全局异或和，偶数直接枚举分割点。
分讨即可。
有点毒瘤但是挺有意思的分讨 + DS。晚点补。
p.s. 立绘好看捏
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-28 20:41:01
原题是 P3514
比较简单但是感觉比较有意思的构造。
发现对于所有 $k \gt 2$ ，只要 $k$ 能被凑出，$k - 2$ 就能凑出。
于是我们分奇数偶数讨论，记录奇偶情况下和的最大值，然后倒推出其他所有 $k$ 的。
具体实现有点压
#include <iostream>
using namespace std;
const int N = 1e6 + 10, K = 2 * N;
int f[2], z[N], sum[N], l[K], r[K];
void dfs (int x)
{
if (x <= 2) return;
if (z[l[x]] == 1 && z[r[x]] == 1) l[x - 2] = l[x] + 1, r[x - 2] = r[x] - 1, dfs (x - 2);
else if (z[l[x]] == 2) l[x - 2] = l[x] + 1, r[x - 2] = r[x], dfs (x - 2);
else l[x - 2] = l[x], r[x - 2] = r[x] - 1, dfs (x - 2);
}
int main (void)
{
int n, q, lfi, rfi;
ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> z[i];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + z[i];
for (lfi = 1; lfi <= n && z[lfi] == 2; lfi++);
for (rfi = n; rfi >= 0 && z[rfi] == 2; rfi--);
f[sum[n] & 1] = sum[n], l[sum[n]] = 1, r[sum[n]] = n;
if (sum[n] - sum[lfi] > sum[rfi]) l[f[sum[n] & 1 ^ 1] = sum[n] - sum[lfi]] = lfi + 1, r[f[sum[n] & 1 ^ 1]] = n;
else l[f[sum[n] & 1 ^ 1] = sum[rfi - 1]] = 1, r[f[sum[n] & 1 ^ 1]] = rfi - 1;
dfs (f[0]), dfs (f[1]);
while (q--) {
int k;
cin >> k;
if (k > f[k & 1]) cout << "-1 -1\n";
else cout << l[k] << ' ' << r[k] << '\n';
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-03 20:05:34
结论就是 $n \lt m$ 无解，$n\ge m$ 有解。
$n\lt m$，那么构造全 $1$ 序列即可，无解。
设 $S$ 为某个长度为 $n$ 的序列的前缀和，有 $\lvert S\rvert = n \ge m$，那么根据抽屉原理显然存在 $S_i \equiv S_j \pmod m, i \lt j$，于是我们取 $[i + 1, j]$ 即可。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 11:19:27
转换器：
Usage: .\/online raw.in raw.ans dst.in
dst.out 和 raw.ans 自然是一样的。
#include <iostream>
using namespace std;
int main (int argc, const char **argv)
{
FILE *in, *out, *ans;
int n, q, last = 0;
in = fopen (argv[1], "r"), out = fopen (argv[2], "r"), ans = fopen (argv[3], "w");
fscanf (in, "%d %d", &n, &q);
fprintf (ans, "%d %d\n", n, q);
for (int i = 0, v; i < n; i++) fscanf (in, "%d", &v), fprintf (ans, "%d ", v);
fprintf (ans, "\n");
while (q--) {
int l, r;
fscanf (in, "%d %d", &l, &r);
if (l > r) swap (l, r);
fprintf (ans, "%d %d\n", l ^ last, r ^ last);
fscanf (out, "%d", &last);
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 14:43:58
非常毒瘤的分桃题。
维护每个数的补后继，记作 $s(x)$；再设 $Q(x)$ 表示与 $x$ 相同的数组成的下标集合。
对 $Q(x)$，只有最大的那个下标能得到 $s(x)$，其他的 $s(x)$ 都是零，显然是正确的。
我们用 set 维护 $Q(x)$ 即可。然后考虑点修。
点修 $x$ 为 $y$ 后会导致什么？设 $x$ 上原来为 $u$，那么 $Q(u)$ 中要删去 $x$，$Q(y)$ 中加上 $x$。
如果 $x$ 是原来 $Q$ 中最小的，那么将以 $x$ 为补后继的数的补后继更新为 $x$ 的等后继
如果 $x$ 原来是 $Q$ 中最大的，那么更新其等前驱的补后继
如果 $x$ 是现在 $Q$ 中最小的，那么将以 $y$ 为补后继的数的补后继更新为 $x$
如果 $x$ 是现在 $Q$ 中最大的，那么从其等前驱抢来补后继
上面那几把东西假了。
$x$ 原来的后继？要给比 $x$ 大的且比 $x$ 原来后继小的，即最大的小于 $x$ 原后继的在 $Q$ 中的。
原来以 $x$ 为后继的？给 $Q(x)$ 中最小的大于原来以 $x$ 为后继的。
$x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ $x$ 现在的后继？ 是最小的大于 $x$ 的。
以 $y$ 为后继的？找第一个大于其的。
-- upd 7.29
这个题看起来并没有那么难。
我们设一个数 $x$ 的前驱，为 $w - x$ 的位置，那么问题就转化为求区间前驱的最大值，看它是不是不小于 $l$。
我们考虑点修带来的变化。首先发现，对于两个有相同前驱的数，下标大的那个的前驱是不需要维护的。
那么这样，我们就只保留一堆数字中最靠前的那个数的前驱位置，其他的就扔掉不管。
现在考虑点修。
首先，如果有 $y$ 使得 $p(y) \ne x$ 且 $y \ne p(x)$ 的，那么 $y$ 是不会变的。
对于以 $x$ 为前驱的数，我们找和 $x$ 相同的，且最靠右的那个来替换。
然后，我们把 $x$ 原来的前驱让给和他相等的最靠左的那个。
这样，$x$ 就能大胆得变成别的数了。设 $x$ 变成了 $y$，那么如果 $x$ 的位置比 $y$ 里头最靠前的还要靠前（同时肯定要在它的前驱后头），那么就把原来 $y$ 的前驱抢过来；
如果以 $y$ 为前驱的数，这时候如果 $x$ 是最大的，我们就把原来前驱替换成 $x$。
这样之后，我们做区间最大值就可以了。线段树搞定。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-10 20:12:11
const int N = 1e5 + 10, oo = 2147483647;
int fa[N << 6], son[N << 6][2], siz[N << 6], cntq[N << 6], val[N << 6], rt[4 * N], cnt = 1, z[N], n;
namespace splay {
static inline void maintain (int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
static inline int get (int x) { return x == son[fa[x]][1]; }
static inline int compare (int f, int k) { return k > val[f]; }
static inline void rotate (int x)
{
int y = fa[x], z = fa[y], p = get (x);
son[y][p] = son[x][p ^ 1];
if (son[x][p ^ 1]) fa[son[x][p ^ 1]] = y;
fa[fa[son[x][p ^ 1] = y] = x] = z;
if (z) son[z][y == son[z][1]] = x;
maintain (y), maintain (x);
}
static inline int splay (int &rt, int x, int t = 0)
{
for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
return t ? x : rt = x;
}
static inline int insert_at (int f, int k)
{
siz[cnt] = cntq[cnt] = 1, val[cnt] = k, fa[cnt] = f;
if (f) son[f][compare (f, k)] = cnt;
return cnt++;
}
static inline int insert (int &rt, int k)
{
int f = rt, last = 0;
if (!f) return rt = insert_at (0, k);
while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
if (f && val[f] == k) return cntq[f]++, splay (rt, f);
else return f = insert_at (last, k), maintain (last), splay (rt, f);
}
static inline int find (int &rt, int k)
{
int f = rt;
if (!f) return 0;
while (val[f] != k && son[f][compare (f, k)]) f = son[f][compare (f, k)];
return splay (rt, f);
}
static inline int merge (int &rt, int x, int y)
{
int f = x;
if (!x || !y) return x + y;
while (son[f][1]) f = son[f][1];
son[splay (rt, f, fa[x])][1] = y;
if (y) fa[y] = f;
return f;
}
static inline int remove (int &rt, int k)
{
int f = find (rt, k), x;
if (cntq[f] > 1) return cntq[f]--, splay (rt, f);
if ((x = merge (rt, son[f][0], son[f][1]))) fa[x] = 0;
return rt = x;
}
static inline int qnxt (int &rt, int k)
{
int f = son[find (rt, k)][1];
if (val[rt] > k) return rt;
while (son[f][0]) f = son[f][0];
return splay (rt, f);
}
static inline int qpre (int &rt, int k)
{
int f = son[find (rt, k)][0];
if (val[rt] < k) return rt;
while (son[f][1]) f = son[f][1];
return splay (rt, f);
}
static inline int qrank (int &rt, int k) { return siz[son[find (rt, k)][0]] + (val[rt] < k ? cntq[rt] : 0); }
}
namespace segtree {
static inline void build (int i, int x, int y)
{
int mid = (x + y) \/ 2;
splay::insert (rt[i], oo), splay::insert (rt[i], -oo);
if (x != y) build (i * 2, x, mid), build (i * 2 + 1, mid + 1, y);
}
static inline void insert (int i, int x, int y, int p, int k)
{
int mid = (x + y) \/ 2;
splay::insert (rt[i], k);
if (x == y) return;
if (p <= mid) insert (i * 2, x, mid, p, k);
else insert (i * 2 + 1, mid + 1, y, p, k);
}
static inline int qrank (int i, int x, int y, int l, int r, int k)
{
int mid = (x + y) \/ 2, res = 0;
if (l <= x && y <= r) return splay::qrank (rt[i], k) - 1;
if (l <= mid) res = qrank (i * 2, x, mid, l, r, k);
if (r > mid) res += qrank (i * 2 + 1, mid + 1, y, l, r, k);
return res;
}
static inline void upd (int i, int x, int y, int p, int k)
{
int mid = (x + y) \/ 2;
splay::remove (rt[i], z[p]), splay::insert (rt[i], k);
if (x == y) return z[p] = k, void ();
if (p <= mid) upd (i * 2, x, mid, p, k);
else upd (i * 2 + 1, mid + 1, y, p, k);
}
static inline int qpre (int i, int x, int y, int l, int r, int k)
{
int mid = (x + y) \/ 2, res = -oo;
if (l <= x && y <= r) return val[splay::qpre (rt[i], k)];
if (l <= mid) res = qpre (i * 2, x, mid, l, r, k);
if (r > mid) res = max (res, qpre (i * 2 + 1, mid + 1, y, l, r, k));
return res;
}
static inline int qnxt (int i, int x, int y, int l, int r, int k)
{
int mid = (x + y) \/ 2, res = oo;
if (l <= x && y <= r) return val[splay::qnxt (rt[i], k)];
if (l <= mid) res = qnxt (i * 2, x, mid, l, r, k);
if (r > mid) res = min (res, qnxt (i * 2 + 1, mid + 1, y, l, r, k));
return res;
}
static inline void build (void) { build (1, 1, n); }
static inline void insert (int p, int k) { insert (1, 1, n, p, k); }
static inline int qrank (int l, int r, int k) { return qrank (1, 1, n, l, r, k); }
static inline void upd (int p, int k) { upd (1, 1, n, p, k); }
static inline int qpre (int l, int r, int k) { return qpre (1, 1, n, l, r, k); }
static inline int qnxt (int l, int r, int k) { return qnxt (1, 1, n, l, r, k); }
static inline int kth (int x, int y, int k)
{
int l = 0, r = 1e9, mid, ans = -1;
while (l <= r) {
mid = (l + r) \/ 2;
if (qrank (x, y, mid) + 1 <= k) l = (ans = mid) + 1;
else r = mid - 1;
}
return ans;
}
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-12 12:21:14
void add (int x, int k) { while (x <= n && k > f[x]) f[x] = k, x += lowbit (x); }
int qry (int x, int y)
{
int res = -1e9;
while (y >= x) {
if (y - lowbit (y) > x) res = max (res, f[y]), y -= lowbit (y);
else res = max (res, z[y]), y--;
}
return res;
}
即树状数组求区间最值。
点加的复杂度是显然的。考虑区间查。
$y$ 有两种变化：
不难发现 $y$ 的减量是不小于一的。然后发现对于情况二，$y$ 的低 $\text{highbit(x)}$ 位一定全都是 $0$，那么这种情况出现次数是 $\log$ 级别的。情况二后紧跟的一定是操作一（因为 $\text{lowbit}(y) \gets 1$），这之后是连续 $\log$ 次的操作一。所以粗略复杂度是 $O(\log^2 n)$。
感性上这个上界有点松了。但我不太会势能分析。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-18 11:04:43
设 $f(u, k)$ 代表在 $u$ 的子树上，需要删掉多少条边才能得到一个大小为 $k$ 的子树。初始地，$f(u, 1) = 0$，$f(u,k) = \infty \space \text{s.t.} \space k \neq 1$。
那么对于每一个孩子，我们如果不用它，那么就是 $f(u, k) + 1$，因为需要删掉这条边。
否则，如果用这个孩子 $v$ 来更新 $u$，我们就有：
$f(u, k) = f(u, j) + f(v, k - j), \space 0 \le j \le k - 1$
所以总的方程：
$$ f(u, k) = \min\limits_{v} f(u, k) + 1, f(u, j) + f(v, k - j) $$
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-20 21:52:17
主席树就是可持久化权值线段树。因为线段树本身就比平衡树常数小，并且它是严格 $\Theta(\lg n)$ 而不是摊下来的，所以说 “能离线的都用线段树” —— 崔神语。
主席树板子是区间的第 $k$ 小问题，P3834。读一下题，你会发现这题甚至都没有在不在线的区别。
我们先考虑怎么维护 $[1, r]$ 内的第 $k$ 小。这就和平衡树的 kth 差不多。建一个值域线段树，对区间维护一个 sum，表示区间内有多少个数。那么显然，我们只需要根据当前区间数的数量来判断走左还是右子树即可，单查询 $\Theta(\lg n)$，总复杂度 $O(n\lg n + q\lg n)$，因为带了一个离散化。
再考虑 $[l, r]$ 的第 $k$ 小。这玩意儿一般人按说是没法忍住不继续看下文的情况下能自己想出来的。我们用可持久化线段树维护每一个历史版本，然后 $[l, r]$ 的查询就变成了个前缀和，同样复杂度可做，但是空间从 $O(n)$ 到了 $O(n + q\lg n)$。
模板懒得写了，随便抄个题解就过了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 10:03:14
我们保存每一个点开始搜集情报的时间 $t_i$，那么操作二就是显然的设置，操作一就是问区间有多少个小于 $t - c$ 的 $t_i$，主席树即可，而且不用离散化。
这么一看这题也太简单了，裸树剖套了个主席树板子 + LCA，亏我昨晚上想一晚上。
鲁ICP备2025150228号