一些沒什麼技巧的數據結構
數據結構
自古不會數據結構，只會瞎寫。/kk
CF1039D You Are Given a Tree
題目大意
給定一棵樹，對於 \(k \in [1,n]\) 求出，樹中最多有多少不相交的路徑，每條路徑恰好包含 \(k\) 個點。
題解
首先假設只有一個給定的 \(k\) ，那麼可以 \(O(n)\) 求出答案，然而要對 \(n\) 個 \(k\) 求解， \(O(n^2)\) 顯然不行。不難發現，當 \(k > \sqrt(n)\) 時，答案一定不會超過 \(\sqrt(n)\) ，因此對於 \(k > \sqrt(n)\) 時的 \(O(n)\) 種情況，一共只有 \(O(\sqrt(n))\) 種可能的答案，於是可以相對於前 \(\sqrt(n)\) 暴力 \(O(n)\) 求出答案，大於 \(\sqrt(n)\) 的部分對於每個答案進行二分，求哪些 \(k\) 的答案均相同，時間複雜度 \(O(n \sqrt(n) \log n)\)。
直接做需要奇怪的卡常科技，不知道為什麼整體二分會快這麼多。。而且好寫。。不會分析複雜度。。
code
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int read(void){
int f = 1, x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
return f * x;
}
int n, ans[N], f[N];
int head[N], nxt[N << 1], to[N << 1], cnt;
void add(int u, int v)
{ nxt[++cnt] = head[u], to[cnt] = v, head[u] = cnt; }
int dfn[N], num[N], fa[N], ind;
void dfs(int u, int f){
dfn[u] = ++ind, fa[num[ind] = u] = f;
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(v ^ f) dfs(v, u);
}
}
int calc(int x){
int res = 0;
for(int i = n; i; --i){
int u = num[i], a = 0, b = 0;
for(int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(v == fa[u]) continue;
if(f[v] >= a) b = a, a = f[v];
else if(f[v] > b) b = f[v];
}
if(a + b + 1 >= x) ++res, f[u] = 0;
else f[u] = a + 1;
}
return res;
}
void solve(int l, int r, int L, int R){
if(l > r || L > R) return;
if(l == r){
for(int i = L; i <= R; ++i) ans[i] = l;
return;
}
int mid = (L + R) >> 1; ans[mid] = calc(mid);
solve(ans[mid], r, L, mid - 1); solve(l, ans[mid], mid + 1, R);
}
signed main(void){
n = read();
for(int i = 1, x, y; i < n; ++i){
x = read(), y = read();
add(x, y), add(y, x);
}
dfs(1, 0); ans[1] = n;
solve(0, n / 2, 2, n);
for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
return 0;
}
CF983E NN country
題目大意
有一棵樹，樹上有若干條路徑，每條路徑 \(x, y\) 包含路徑上所有的點，有 \(q\) 次詢問，每次詢問 \(u,v\) 表示從 \(u\) 走到 \(v\) 至少經過多少條路徑。
題解
首先不難求出對於每個點經過一條路徑所能到達的最靠上的點在哪裡，於是可以考慮對其進行倍增，每次詢問 \((u, v)\) 時，直接倍增到 \(lca\) 下方，恰好下一次能到達 \(lca\) 的地方，此時問題變為是否存在一條路徑包含路徑 \((u, v)\) ，使得 \(u\) 恰好一次能到 \(v\) ，這本質上是一個二維偏序問題，即是否存在一條路徑一個端點在 \(u\) 子樹內，另一個端點在 \(v\) 子樹內，通過主席樹解決即可。
沒啥細節就不放程式碼了。。。
CF1422F Boring Queries
題目大意
給定一個長度為 \(n\) 的序列 \(a\)，有 \(q\) 次詢問，每次給定 \(l, r\) ，求這個區間的 \(lcm\) 。
題解
考慮 \(lcm\) 的本質是什麼，對於一些數形如 \(x = p_1^{c_1}p_2^{c_2}…p_k^{c_k}\) ，取 \(lcm\) 的本質就是對所有的 \(c_i\) 取 \(\max\) ，考慮從左到右枚舉 \(r\) 回答，不難發現，若 \(i \le r\) ，存在一個質因子在 \(a_r\) 中的次數大於在 \(a_i\) 中的次數，那麼 \(a_i\) 就沒用了，這類似一個單調棧，於是可以對每個質數單獨維護一個單調棧，在用線段樹維護每個位置的答案即可，由於題目強制在線，所以將線段樹可持久化一下就行了。。
code
#include <bits/stdc++.h>
#define fi first
#define se second
const int N = 2e5 + 10, mod = 1e9 + 7;
int read(void) {
int f = 1, x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
return f * x;
}
using std::pair;
using std::make_pair;
int inv[N], pri[N], cnt;
bool vis[N];
std::unordered_map<int, int> mp[N];
void pre(void) {
inv[0] = inv[1] = 1;
for(int i = 2; i < N; ++i) {
if(!vis[i]) pri[++cnt] = i;
for(int j = 1; j <= cnt && pri[j] * i < N; ++j)
{ vis[i * pri[j]] = 1; if(!(i % pri[j])) break; }
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}
for(int i = 1; i <= cnt; ++i) for(int j = 1; j * pri[i] < N; ++j)
mp[j * pri[i]][i] = j % pri[i] ? pri[i] : mp[j][i] * pri[i];
}
struct range { int l, r, w; };
std::vector<range> pos[N];
int n, q, a[N], rt[N], tot;
struct Tree { int ls, rs, mul; } t[N << 7];
void add(int& p, int lst, int l, int r, int w, int L = 1, int R = n) {
t[p = ++tot] = t[lst]; int mid = (L + R) >> 1;
if(l <= L && r >= R) { return void(t[p].mul = 1ll * t[p].mul * w % mod); }
if(l <= mid) add(t[p].ls, t[lst].ls, l, r, w, L, mid);
if(r > mid) add(t[p].rs, t[lst].rs, l, r, w, mid + 1, R);
}
int que(int p, int x, int L = 1, int R = n) {
if(L == R) return t[p].mul; int mid = (L + R) >> 1;
if(x <= mid) return 1ll * t[p].mul * que(t[p].ls, x, L, mid) % mod;
else return 1ll * t[p].mul * que(t[p].rs, x, mid + 1, R) % mod;
}
signed main(void) {
n = read(), t[0].mul = 1, pre();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) {
rt[i] = rt[i - 1];
for(pair<int, int> x : mp[a[i]]) {
while(!pos[x.fi].empty() && pos[x.fi].back().w <= x.se) {
range ul = pos[x.fi].back(); pos[x.fi].pop_back();
add(rt[i], rt[i], ul.l, ul.r, inv[ul.w]);
}
int p = pos[x.fi].empty() ? 1 : pos[x.fi].back().r + 1;
pos[x.fi].push_back( { p, i, x.se } );
add(rt[i], rt[i], p, i, x.se);
}
} q = read();
for(int i = 1, l, r, lst = 0; i <= q; ++i) {
l = (read() + lst) % n + 1, r = (read() + lst) % n + 1;
if(l > r) l ^= r, r ^= l, l ^= r;
printf("%d\n", lst = que(rt[r], l));
}
return 0;
}
CF503E Pastoral Oddities
題目大意
給定一張 \(n\) 個點 \(m\) 條邊的圖，初始時沒有邊，每次往裡加一條邊，邊有邊權，求是否存在一個邊集滿足每個點的度數均為奇數，若存在，輸出邊集中最大邊權的最小值。
題解
乍一看像是神仙題，果然是神仙題。。
有一個很強的結論，每個點的度數為奇數的充要條件為所有聯通塊的大小均為偶數。
必要性證明：考慮反證法，大小為奇數的連通塊內所有點的度數為奇數，則一定有連通塊內度數和為奇數，而一個無向圖連通塊度數和一定為偶數，相悖。
充分性證明：考慮有一個偶數大小的連通塊，我們一定可以通過以下方法構造出一種合法解，從葉子開始向上走，一個點若有奇數個兒子，就刪掉它和父親之間的邊，最終除了根節點和被斷開的節點，所有點都有偶數個兒子。
這樣，我們可以考慮維護這張圖的最小生成森林，維護每棵樹的大小，同時在 \(link\) 和 \(cut\) 時維護奇連通塊的數量，這裡可以用 \(LCT\) 維護子樹資訊實現。考慮每次新加入一條邊奇連通塊數量肯定不會變多，因此每一條新邊能加入就加入，此時有一些邊可能對奇聯通塊數沒有影響，刪除最大的對奇連通塊數沒有影響的邊，可以用一個堆來維護森林中的所有邊，不能刪除的最大的邊便是答案。
code
//How I wish, how I wish you were here.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const int N = 5e5 + 10;
int read(void) {
int f = 1, x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
return f * x;
}
using std::pair; using std::make_pair;
int n, m, u[N], v[N], w[N];
bool Cut[N];
std::priority_queue<pair<int, int> > q;
struct Link_Cut_Tree {
int fa[N], siz[N], son[N][2], inv[N], stk[N], top, cnt;
std::pair<int, int> mx[N], a[N];
bool lz[N];
bool right(int p) { return son[fa[p]][1] == p; }
bool nroot(int p) { return son[fa[p]][0] == p || son[fa[p]][1] == p; }
void update(int p) {
mx[p] = std::max(std::max(mx[son[p][0]], mx[son[p][1]]), a[p]);
siz[p] = inv[p] + siz[son[p][0]] + siz[son[p][1]] + (p <= n);
}
void pushrev(int p) { lz[p] ^= 1, std::swap(son[p][0], son[p][1]); }
void pushdown(int p) {
if(!lz[p]) return; lz[p] = 0;
if(son[p][0]) pushrev(son[p][0]);
if(son[p][1]) pushrev(son[p][1]);
}
void rotate(int p) {
int f1 = fa[p], f2 = fa[f1], id = right(p), w = son[p][id ^ 1];
if(nroot(f1)) son[f2][right(f1)] = p; son[p][id ^ 1] = f1, son[f1][id] = w;
if(w) fa[w] = f1; fa[f1] = p, fa[p] = f2; update(f1);
}
void splay(int p) {
int u = p; stk[top = 1] = u;
while(nroot(u)) stk[++top] = u = fa[u];
while(top) pushdown(stk[top--]);
while(nroot(p)) {
if(nroot(fa[p]))
rotate(right(p) == right(fa[p]) ? fa[p] : p);
rotate(p);
} update(p);
}
void access(int p) {
for(int x = 0; p; p = fa[x = p]) {
splay(p), inv[p] += siz[son[p][1]];
inv[p] -= siz[son[p][1] = x], update(p);
}
}
void makert(int p)
{ access(p), splay(p), pushrev(p); }
int findrt(int p) {
access(p), splay(p), pushdown(p);
while(son[p][0]) pushdown(p = son[p][0]);
return splay(p), p;
}
void link(int u, int v) {
makert(u), access(v), splay(v);
cnt -= siz[u] & 1, cnt -= siz[v] & 1;
fa[u] = v, inv[v] += siz[u], update(v);
cnt += siz[v] & 1;
}
void cut(int u, int v) {
makert(u), access(v), splay(v), cnt -= siz[v] & 1;
son[v][0] = fa[u] = 0, update(v);
cnt += siz[u] & 1, cnt += siz[v] & 1;
}
int add(int id) {
int u = ::u[id], v = ::v[id], w = ::w[id];
bool flag = 1;
if(findrt(u) == findrt(v)) {
makert(u), access(v), splay(v);
int ul = mx[v].se;
if(w < mx[v].fi)
cut(ul, ::u[ul - n]), cut(ul, ::v[ul - n]), Cut[ul - n] = 1;
else flag = 0;
}
if(flag) {
a[id + n] = mx[id + n] = make_pair(w, id + n);
link(id + n, u), link(id + n, v), q.push(make_pair(w, id));
}
if(cnt) return -1;
while(!q.empty()) {
int id = q.top().se; q.pop();
if(Cut[id]) continue;
cut(id + n, ::u[id]), cut(id + n, ::v[id]);
if(cnt) {
link(id + n, ::u[id]), link(id + n, ::v[id]);
q.push(make_pair(::w[id], id)); return ::w[id];
}
}
}
} t;
signed main(void) {
t.cnt = n = read(), m = read();
for(int i = 1; i <= n; ++i) t.siz[i] = 1;
for(int i = 1; i <= m; ++i) {
u[i] = read(), v[i] = read(), w[i] = read();
printf("%d\n", t.add(i));
}
return 0;
}
605菜市場
改編自模擬賽的水題，太水所以沒有題解，歡迎大家爆切。
code
#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 10;
int read(void) {
int f = 1, x = 0; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
return f * x;
}
int n, q, g, r, op, mod;
int tot, rt[N], d[N], f[N], stp[N][20];
struct TRE { int ls, rs, mn; } t[N << 7];
void cover(int &p, int lst, int l, int r, int w, int L = 0, int R = mod - 1) {
t[p = ++tot] = t[lst]; if(!lst) t[p].mn = n;
if(l <= L && r >= R) return void(t[p].mn = w);
int mid = (L + R) >> 1;
if(l <= mid) cover(t[p].ls, t[lst].ls, l, r, w, L, mid);
if(r > mid) cover(t[p].rs, t[lst].rs, l, r, w, mid + 1, R);
}
int que(int p, int x, int L = 0, int R = mod - 1) {
if(!p) return n;
if(L == R) return t[p].mn; int mid = (L + R) >> 1;
if(x <= mid) return std::min(t[p].mn, que(t[p].ls, x, L, mid));
else return std::min(t[p].mn, que(t[p].rs, x, mid + 1, R));
}
signed main(void) {
n = read(), q = read(), g = read(), r = read(), op = read(), mod = r + g;
for(int i = 1; i <= n; ++i) d[i] = d[i - 1] + read();
for(int i = n - 1, p, L, R; i; --i) {
stp[i][0] = p = que(rt[i + 1], d[i] % mod);
f[i] = f[p] + d[p] - d[i];
if(p ^ n) f[i] += mod - (d[p] - d[i]) % mod;
for(int j = 1; j < 20; ++j)
stp[i][j] = stp[stp[i][j - 1]][j - 1];
R = (d[i] - g + mod) % mod, L = (d[i] - g - r + 1 + mod) % mod;
if(L <= R) cover(rt[i], rt[i + 1], L, R, i);
else cover(rt[i], rt[i + 1], L, mod - 1, i), cover(rt[i], rt[i], 0, R, i);
}
for(int i = 1, t, l, r, res = 0, p; i <= q; ++i) {
t = read(), l = (read() ^ (op * res)) % (n + 1), r = (read() ^ (op * res)) % (n + 1);
if(l > r) l ^= r, r ^= l, l ^= r;
p = que(rt[l + 1], (mod + d[l] % mod - t % mod) % mod);
if(p >= r) { printf("%lld\n", res = d[r] - d[l] + t); continue; }
res = d[p] - d[l] + t + mod - (d[p] - d[l] + t) % mod + f[p];
for(int j = 19; ~j; --j) if(stp[p][j] && stp[p][j] < r) p = stp[p][j];
res += d[r] - d[p] - f[p]; printf("%lld\n", res);
}
return 0;
}
