(Solution:) 当 (a) 在下面时，(ans = size[a] \times min(K,dep[a]))，当 (a) 在上面时，观察到合法的 (b) 有两个限制，(1:) (dep_b ∈[dep_a + 1,dep_a+k]), (2:dfn_b∈[dfn_a,dfn_a+size_a -1])。树状数组二维数点即可。另有在线主席树或长剖做法。
const int N = 3e6 + 10;
int n, m, h[N], e[N << 1], ne[N << 1], idx; int size[N], dfn[N], dep[N], tot, tr[N], ans[N];
inline void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
inline void dfs(int u, int fa){
dfn[u] = ++ tot; size[u] = 1; for(int i = h[u]; ~ i; i = ne[i]){
int v = e[i]; if(v == fa) continue;
dep[v] = dep[u] + 1; dfs(v, u); size[u] += size[v];
}
}
struct point{ int u, v, w; friend bool operator 0) ans[q[i].id] += ask(q[i].x2) - ask(q[i].x1);
else ans[q[i].id] -= ask(q[i].x2) - ask(q[i].x1);
} for(int i = 1; i
(Solution:) 设当前表示的值域为 ([1,x])，(ans = x + 1)，属于值域 ([1,x+1]) 的数和为 (res)，若 (res >= ans) 则存在未选择的小于等于 (ans) 的数，(ans = res + 1)，否则 (break)。
const int N = 1e5 + 10, inf = 1e9;
int n, m, a[N], rt[N], cnt;
struct node{ int ls, rs, v; }t[N << 5];
inline void insert(int &now, int pre, int l, int r, int pos, int v){
now = ++ cnt; t[now] = t[pre], t[now].v += v; if(l == r){ return; } int mid = (l + r) >> 1;
if(pos > 1, res = 0;
if(ql mid) res += query(t[v].rs, t[u].rs, mid + 1, r, ql, qr);
return res;
}
signed main(){
read(n); for(int i = 1; i = ans) ans = res + 1; else break;
} print(ans), puts("");
} return 0;
}
(Solution:) 两种操作，(1:) 查询两点路径上第 (k) 小，(2:) 连接两棵树。第二种操作启发式合并，第 (k) 小使用主席树。合并时 (dfs) 暴力修改，用父节点重建每个节点的主席树，并且更新每个节点的倍增数组（(st) 表）。
const int N = 8e4 + 10;
int testcase, T, n, m, size; int st[N][17], son[N], dep[N], fa[N], vis[N], a[N], b[N], root[N];
int h[N], ne[N << 2], e[N << 2], idx, cnt; struct node{ int size, ls, rs; }t[N * 600];
inline void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
inline void insert(int &now, int pre, int l, int r, int u){
now = ++ cnt; t[now] = t[pre]; t[now].size ++;
if(l == r) return; int mid = (l + r) >> 1;
if(u > 1;
build(t[now].ls, l, mid); build(t[now].rs, mid + 1, r);
}
inline int query(int x, int y, int pre1, int pre2, int l, int r, int k){
if(l == r){ return b[l]; } int mid = (l + r) >> 1;
int lsz = t[t[x].ls].size + t[t[y].ls].size - t[t[pre1].ls].size - t[t[pre2].ls].size;
if(k dep[y]) swap(x, y);
for(int k = 16; k >= 0; k --){
if(dep[st[y][k]] >= dep[x]) y = st[y][k];
}
if(x == y) return x;
for(int k = 16; k >= 0; k --){
if(st[x][k] != st[y][k]){ x = st[x][k], y = st[y][k]; }
} return st[x][0];
}
signed main(){
memset(h, -1, sizeof h); read(testcase), read(n), read(m), read(T);
for(int i = 1; i > ch;
read(x), read(y); x ^= lastans; y ^= lastans;
if(ch == 'Q'){
read(k); k ^= lastans;
int L = lca(x, y);
lastans = query(root[x], root[y], root[L], root[st[L][0]], 1, size, k);
print(lastans), puts("");
}else{
add(x, y), add(y, x); int u = find(x), v = find(y);
if(son[u] < son[v]) swap(u, v), swap(x, y);
dfs(y, x, u);
}
} return 0;
}
(Solution:) 发现 (\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60)，把 (t) 在(\mod 60) 意义下进行不会影响结果的正确性。接下来继续考虑线段树，对于每个区间 ([l, r])，再对于每个可能的时间(\mod 60) 意义下的结果，我们维护如果在达到 (l) 的时候 (t\mod 60 = i)，那么达到 (r + 1) 需要花费多少时间。(O(60)) 的 (pushup)。(O(n {\log} n×60))。
const int N = 1e5 + 10;
#define ls u << 1
#define rs u << 1 | 1
struct node{ int l, r, f[61]; }tr[N << 2];
int n, m, a[N];
inline void pushup(int u){
for(int i = 0; i = 0; i --){ tr[u].f[i] = 1 + (i % a[l] == 0); } return; }
int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u);
}
inline void modify(int u, int x, int c){
if(tr[u].l == tr[u].r){ a[x] = c; for(int i = 59; i >= 0; i --) tr[u].f[i] = 1 + (i % a[x] == 0); return; }
if(x r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r > op; if(op == 'C'){
int x, c; read(x), read(c); modify(1, x, c);
}else{
int l, r; read(l), read(r); r --; print(query(1, l, r, 0)), puts("");
}
}
}
Original: https://www.cnblogs.com/William-Sg/p/16595032.html
Author: Altwilio
Title: 数据结构做题记录
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605145/
转载文章受原作者版权保护。转载请注明原作者出处！