闲话
好今日得到最让人感到奇妙的一件事是松鼠加入 ps_p live 力
虽然但是……比较地奇妙
……不知道该评价什么（
连步玎都不是 ps_p 的（
所以给了一天自由练习的时间就是刷数据结构的是吗（
然后看了一半的 Lycoris Recoil
强推！下次要看完（
今日推的原创番就是莉可丽丝了！
就先写到这罢
白鸟过河滩好听的！
数据结构……杂题？
这是五道题。明天似乎还有五道。
也是比较的水，所以题解写得短点（
给定长为 \(n\) 的序列 \(a\)。\(q\) 次询问 \((l,r)\)，你需要输出
\[\mathop{\operatorname{lcm}}\limits_{i=l}^r \{a_i\} \]对 \(10^9 + 7\) 取模的值。强制在线。
\(1\le n, q\le 10^5, 1\le a_i \le 2\times 10^5\)。
Muel的常数怎么那么小啊啊啊啊
考虑将每个数质因子分解。对每个 \(n\) 有 \(O(\log n)\) 个状态。注意这里的状态不一定是质因子 \(p\) 和其最大指数的组合，非最大指数也可以。我们发现，我们需要的是 \([l,r]\) 区间内元素对应 \(p^k\) 状态中满足 \(k\) 最大的状态的积。
考虑对每个元素维护一个前缀版本，当一个元素可以贡献 \(p^k\) 时将其前面所有可以贡献 \(p^k\) 的元素的贡献删除。容易发现可以让每个元素只删除直接前驱做到这一点。
对每个贡献开桶，维护存在该贡献的直接前驱。当出现新的元素可以产生贡献时，在该元素版本中删除前驱并加入当前节点。这点可以使用主席树，根维开在下标上维护前缀版本，值维同样开在下标上维护某个前缀版本中特定位置的信息。
时空复杂度 \(O(n\log^2 n)\)。
通过对质因子进行根号分治也可以做到。空间复杂度有些问题。
code
#include <bits/stdc++.h>
using namespace std;
template<typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, q, a[N], mx, l, r, ret, inv[N], lpf[N], pref[N];
struct SegmentCitrus {
int rt[N], mlc;
int & operator [] (const int & p) { return rt[p]; }
const int operator [] (const int & p) const { return rt[p]; }
struct node {
int ls, rs, sum;
#define ls(p) seg[p].ls
#define rs(p) seg[p].rs
#define sum(p) seg[p].sum
} seg[N * 200];
int add(int p, int l, int r, int pos, int val) {
int ptr = ++mlc;
if (l == r) {
sum(ptr) = 1ll * sum(p) * val % mod;
return ptr;
} int mid = l + r >> 1;
if (pos <= mid) ls(ptr) = add(ls(p), l, mid, pos, val), rs(ptr) = rs(p);
else ls(ptr) = ls(p), rs(ptr) = add(rs(p), mid + 1, r, pos, val);
sum(ptr) = 1ll * sum(ls(ptr)) * sum(rs(ptr)) % mod;
return ptr;
}
void add(int id, int pos, int val) {
rt[id] = add(rt[id], 1, n, pos, val);
}
int qry(int p, int l, int r, int bnd) {
if (l >= bnd) return sum(p);
if (r < bnd) return 1;
int mid = l + r >> 1;
return 1ll * qry(ls(p), l, mid, bnd) * qry(rs(p), mid + 1, r, bnd) % mod;
}
int qry(int l, int r) { return qry(rt[r], 1, n, l); }
} Tr;
signed main() {
get(n); rep(i,1,n) get(a[i]), mx = max(mx, a[i]);
inv[0] = inv[1] = 1;
rep(i,2,mx) {
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
if (!lpf[i]) for (int j = i; j <= mx; j += i) lpf[j] = i;
}
Tr.seg[0].sum = 1;
rep(i,1,n) {
int tmp = a[i]; Tr[i] = Tr[i-1];
while (lpf[tmp]) {
int k = lpf[tmp], t = 1;
while (tmp % k == 0) {
t *= k; tmp /= k;
if (pref[t]) Tr.add(i, pref[t], inv[k]);
pref[t] = i;
}
Tr.add(i, i, t);
}
}
get(q); rep(i,1,q) {
get(l, r);
l = (l + ret) % n + 1, r = (r + ret) % n + 1;
if (l > r) swap(l, r);
cout << (ret = Tr.qry(l, r)) << '\n';
}
}
给出 \(n\) 个点， \(m\) 条边的不带权连通无向图， \(q\) 次询问至少要加完编号前多少的边，才能使得 \([l,r]\) 中的所有点两两连通。
\(1\le n, m, q \le 2\times 10^5\)。
考虑一条边的边权为编号。记 \(f(u,v)\) 为 \(u,v\) 在最小生成树上路径中边权最大值。容易发现答案即为
\[\max_{i=l}^{r-1} \{ f(i,i+1) \} \]如果我们可以求得 \(f\)，那就可以通过 st 表等结构快速得到答案。问题来到了如何求得 \(f\)。
这是很容易的。使用 Kruskal 重构树可以做到 \(O(n\log n)\) 求解。
总时间复杂度 \(O(n\log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
template<typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 1e5 + 10;
int T, n, m, q, l, r;
int dsu[N], ele[N];
void init(int n) { rep(i,1,n) dsu[i] = ele[i] = i; }
int find(int u) { return u == dsu[u] ? u : dsu[u] = find(dsu[u]); }
int dfn[N << 1], stp, dep[N << 1], a[N << 1], fa[N << 1], cnt, f[N], lgv[N << 1], st[20][N << 1];
vector <int> g[N << 1];
void dfs(int u, int f) {
dfn[u] = ++ stp, fa[u] = f; dep[u] = dep[f] + 1;
for (auto v : g[u]) if (v != f) dfs(v, u);
}
void init() {
rep(i,2,stp) lgv[i] = lgv[i >> 1] + 1;
rep(i,1,stp) st[0][dfn[i]] = fa[i];
rep(i,1,lgv[stp]) for (int j = 1, u, v; j + (1 << i) - 1 <= stp; ++ j)
u = st[i-1][j], v = st[i-1][j + (1 << i - 1)], st[i][j] = dep[u] < dep[v] ? u : v;
}
int qry(int u, int v) {
if (u == v) return u;
u = dfn[u], v = dfn[v];
if (u > v) swap(u, v); u ++;
int d = lgv[v - u + 1];
u = st[d][u], v = st[d][v - (1 << d) + 1];
return dep[u] < dep[v] ? u : v;
}
void init2() {
rep(i,1,n-1) st[0][i] = f[i];
rep(i,1,lgv[n-1]) for (int j = 1; j + (1 << i) <= n; ++ j)
st[i][j] = max(st[i-1][j], st[i-1][j + (1 << i - 1)]);
}
int query(int l, int r) {
if (l > r) return 0;
int d = lgv[r - l + 1];
return max(st[d][l], st[d][r - (1 << d) + 1]);
}
signed main() {
get(T);
while (T--) {
get(n, m, q); cnt = n;
rep(i,1,(n<<1) - 1) g[i].clear();
init(n);
rep(i,1,m) {
get(l, r);
l = find(l), r = find(r);
if (l == r) continue;
++ cnt;
g[cnt].push_back(ele[l]), g[cnt].push_back(ele[r]);
g[ele[l]].push_back(cnt), g[ele[r]].push_back(cnt);
dsu[l] = r, a[cnt] = i, ele[r] = cnt;
}
dfs(cnt, 0); init();
rep(i,1,n-1) f[i] = a[qry(i, i + 1)];
init2();
rep(i,1,q) {
get(l, r);
cout << query(l, r - 1) << ' ';
} cout << '\n';
}
}
给定序列 \(a\)，保证 \(a_i\) 两两不同。每个 \(i\)会向序列中满足 \(a_i\oplus a_j\)（\(\oplus\) 代表异或）最小的 \(j\) 连双向边，并且如果 \(j\) 也向 \(i\) 连了边，只算一条边。现在要删去序列中的一些数，使得最后形成的图是一棵树，输出最少删除数。
\(1\le n\le 2\times 10^5, 1\le a_i \le 10^9\)。
转化成最大保留数计算，答案转为 $n - $ 答案即可。
考虑异或最小才连边的性质，我们将所有数插入一棵 trie。容易发现只有最深层节点才会和他的兄弟连边，这就组成了一系列长度不超过 \(2\) 的环。
设 \(f_i\) 为 \(i\) 节点子树内元素两两有边的最大保留数。容易发现当 \(i\) 的孩子数小于 \(2\) 时直接继承儿子即可。考虑两个儿子的情况。由于一边剩余超过两个节点的话一定会在内部连边，因此定有一边需要删除节点到只剩一个。取两边较小的删除即可。
在 trie 上进行一遍搜索即可得到答案。复杂度 \(O(n\log a)\)。
code
#include <bits/stdc++.h>
using namespace std;
template<typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 2e5 + 10;
int n, a[N], mx, lgmx;
int trie[N << 5][2], mlc;
void insert(int u) {
int ptr = 0, ztr;
pre(i,lgmx,0) {
ztr = u >> i & 1;
if (trie[ptr][ztr] == 0) trie[ptr][ztr] = ++ mlc;
ptr = trie[ptr][ztr];
}
}
int dfs(int u) {
if (!trie[u][0] and !trie[u][1]) return 1;
if (!trie[u][0] and trie[u][1]) return dfs(trie[u][1]);
if (trie[u][0] and !trie[u][1]) return dfs(trie[u][0]);
return max(dfs(trie[u][0]), dfs(trie[u][1])) + 1;
}
signed main() {
get(n); rep(i,1,n) get(a[i]), mx = max(mx, a[i]); lgmx = __lg(mx);
rep(i,1,n) insert(a[i]);
cout << n - dfs(0);
}
给定长度为 \(n\) 的序列 \(a\)，共有 \(q\) 个询问，支持两种操作：
1 l r将区间 \([l,r]\) 依次向右移动一位，其中 \(a_r\) 移动到 \(a_l\)。
2 l r k询问区间 \([l,r]\) 中 \(k\) 出现次数。强制在线。
\(1\le n,q\le 10^5,1\le a_i\le n\)。
这题我没打正解。
首先考虑静态情况怎么写。
这是简单的，我们开 \(n\) 个 vector，第 \(i\) 个 vector 维护值为 \(i\) 的元素的编号集合，每次查询时找到落在前缀区间内的元素个数后差分得到答案。
由于每次只会移动一个元素，考虑动态为元素重编号。
具体地，我们维护一个平衡树表示当前所有元素的编号。假设要插入的位置前面的元素的编号为 \(l\)，位置后面的元素的编号为 \(r\)，则为更改元素重编号为 \(\frac{l+r}2\)。
询问时找到第 \(l,r\) 个编号，仍然在对应值的集合中寻找前缀后差分即可。
这引发了一个问题：若数据是特殊构造的，则连续向一个位置插入会导致两个点的编号以指数速度趋近，最后精度丢失成为相同点。
这显然无法再使用平衡树维护了。
怎么办呢？
答案是遇到困难睡大觉。
当产生这种情况时我们直接退出程序就能过这题的 hack 数据了。因为这题的 hack 完全没有一次询问。
当然这也是可以解决的。可能的方案有采取不同的重编号策略多次重复尝试或 \(O(\frac{\sqrt{n}} {\log {n}})\) 次插入后暴力重构等。
不想写。
正解是平衡树维护这个相对顺序，或者分块。
不想写。
因为不想写 \(n+1\) 棵平衡树所以仍然是 vector 维护编号集合。
因为不想写 \(1\) 棵平衡树所以仍然是 pb_ds 的平衡树。
所以码很短。
code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
template<typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 2e5 + 10;
int n, q, typ, l, r, x, ans;
vector <double> bv[N];
__gnu_pbds :: tree <pair<double, int>, __gnu_pbds :: null_type, less<pair<double,int> >,
__gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update> T;
signed main() {
get(n); rep(i,1,n) get(x), bv[x].push_back(i * 1e18), T.insert( { i * 1e18, x } );
get(q); while ( q-- ) {
get(typ, l, r); l = (l + ans - 1) % n + 1; r = (r + ans - 1) % n + 1; if (l > r) swap(l, r);
if (typ == 1) {
auto lft = prev(T.find_by_order(l - 1)), rgt = T.find_by_order(l - 1), rpos = T.find_by_order(r - 1);
bv[rpos->second].erase(lower_bound(bv[rpos->second].begin(), bv[rpos->second].end(), rpos->first));
bv[rpos->second].insert(upper_bound(bv[rpos->second].begin(), bv[rpos->second].end(), (lft->first + rgt->first) / 2), (lft->first + rgt->first) / 2);
int tmp = rpos->second;
T.erase(rpos);
if ((T.find( {(lft->first + rgt->first) / 2, tmp} ) != T.end())) return 0;
T.insert( {(lft->first + rgt->first) / 2, tmp} );
} else {
auto lft = T.find_by_order(l - 1), rgt = T.find_by_order(r - 1);
get(x); x = (x + ans - 1) % n + 1;
cout << ( ans = (upper_bound(bv[x].begin(), bv[x].end(), rgt->first) - bv[x].begin()) -
(lower_bound(bv[x].begin(), bv[x].end(), lft->first) - bv[x].begin()) ) << '\n';
}
}
}
给定 \(n\) 个二元组 \((x_i,w_i)\)，按照 \(x_i\) 严格递增排序给出。给出 \(q\) 次询问，每次询问给出 \(l,r\)，你需要输出：
\[\min_{l\le i<j\le r} |x_i-x_j| \times (w_i+w_j) \]\(2\le n,q \le 3\times 10^5, |x_i|\le 10^9, 1\le w_i \le 10^9\)。
性质题。
我们从左右两边对 \(w\) 做单调栈，栈内维护小于 \(w_i\) 的值中 \(x\) 最接近 \(x_i\) 的元素。设 \(l_i\) 为从左边做到 \(i\) 位置时 \(i\) 入栈前的栈顶，\(r_i\) 为从右边做时的栈顶。我们需要证明只有 \((i,l_i)\) 和 \((i,r_i)\) 可能对答案造成贡献。
证明：
假设 \((i,j)\) 是更优的答案且 \(j\neq l_i, j\neq r_i\)，则我们知道 \(w_{l_i} \le w_j, |x_{l_i} - x_i| < |x_j - x_i|\)。因此 \(j\) 的答案一定不更优。
\(r_i\) 的情况同理。
于是我们就只需要维护 \(O(n)\) 对元素对答案的贡献了。容易发现每对元素是一个带权区间，需要询问区间完全包含才能贡献权值，最终答案是权值最小值。
这个直接树状数组倒着扫一遍就行了。在区间结束时以区间开始位置作为下标插入区间权值即可。
答案最大 \(4\times 10^{18}\)，记得 \(\inf\) 设大点。
code
#include <bits/stdc++.h>
using namespace std;
template<typename T> void get(T & x) {
x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x);
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 3e5 + 10; typedef long long ll;
int n, q, x[N], w[N], t1, t2;
vector <tuple<int, int, ll> > vec[N];
int stk[N], top;
ll ans[N];
#define calc(i, j) (1ll * abs(x[i] - x[j]) * (w[i] + w[j]))
struct BIT {
ll Index[N];
void add(int p, ll v) { for (; p <= n; p += p & -p) Index[p] = min(Index[p], v); }
ll qry(int p) { ll ret = 4e18 + 10; for (; p; p ^= p & -p) ret = min(ret, Index[p]); return ret; }
} B;
signed main() {
get(n, q); rep(i,1,n) get(x[i], w[i]), B.Index[i] = 4e18 + 10;
stk[++top] = 0;
rep(i,1,n) {
while (stk[top] and w[stk[top]] > w[i]) -- top;
if (stk[top]) vec[stk[top]].emplace_back(0, i, calc(stk[top], i));
stk[++top] = i;
}
stk[top = 1] = 0;
pre(i,n,1) {
while (stk[top] and w[stk[top]] > w[i]) -- top;
if (stk[top]) vec[i].emplace_back(0, stk[top], calc(stk[top], i));
stk[++top] = i;
}
rep(i,1,q) get(t1, t2), vec[t1].emplace_back(i, t2, 0);
pre(i,n,1) {
for (auto [id, pos, val] : vec[i])
if (id == 0) {
B.add(pos, val);
} else {
ans[id] = B.qry(pos);
}
} rep(i,1,q) cout << ans[i] << '\n';
}