F Components
考虑树形 \(DP\) 。
有 \(f_{i, j, 0/1}\) 为以 \(i\) 为根的子树，一共有 \(j\) 个连通块，选/不选的方案数。
\[pre_{x, 0/1} \leftarrow f_{u, x, 0/1} \]\[f_{u, i, 0} = f_{u, i, 0} + pref_{i-j,0} \times (f_{v, j, 0} + f_{v, j, 1}) \]\[f_{u, i, 1} = f_{u, i, 1} + pref_{i-j,1} \times(f_{v, j, 0} + f_{v, j+1, 1}) \]#include <bits/stdc++.h>
#define _for(i, a, b) for(I i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(I i = (a); i < (b); i ++)
#define _rof(i, a, b) for(I i = (a); i >= (b); i --)
#define _pre(i, a, b) for(I i = (a); i > (b); i --)
#define inl inline
#define I int
#define ll long long
inl I read(){
static I bo, x; bo = x = 0;
static char c; c = getchar();
while(c < '0' || c > '9') {if(c == '-')bo = 1; c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<3) + (x<<1) + c - '0'; c = getchar();}
return bo ? -x : x;
}
inl void out(ll x, bool bo = true){
if(x < 0) putchar('-'), x = -x;
if(x == 0){if(bo)putchar('0'); return;}
out(x/10, false), putchar('0' + x%10);
}
using namespace std;
const int N = 5e3+1;
const ll mod = 998244353;
int n;
int h[N], nt[N<<1], to[N<<1], cnt;
void link(int u, int v){
nt[++cnt] = h[u], h[u] = cnt, to[cnt] = v;
nt[++cnt] = h[v], h[v] = cnt, to[cnt] = u;
}
ll f[N][N][2], sz[N];
ll pref[N][2];
void dp(int u, int fa){
sz[u] = 1ll, f[u][1][1] = f[u][0][0] = 1ll;
for(int i = h[u], v; i; i = nt[i]){
if((v = to[i]) == fa) continue;
dp(v, u);
_for(i, 0, sz[u] + sz[v]){pref[i][0] = f[u][i][0], pref[i][1] = f[u][i][1], f[u][i][0] = f[u][i][1] = 0;}
_rof(i, sz[u]+sz[v], 0){
_for(j, max(0ll, i - sz[u]), min((ll) i, sz[v])){
(f[u][i][0] += pref[i-j][0] * (f[v][j][0] + f[v][j][1]) % mod) %= mod;
(f[u][i][1] += pref[i-j][1] * (f[v][j][0] + f[v][j+1][1]) % mod) %= mod;
}
}
sz[u] += sz[v];
}
}
int main(){
n = read();
_rep(i, 1, n) {
static int u, v;
u = read(), v = read();
link(u, v);
}
dp(1, 0);
_for(i, 1, n)
out((f[1][i][0] + f[1][i][1]) % mod), puts("");
return 0;
}
G Balance Update Query
整体区间前 \(x\) 大和。
值域很大，而 \(n\) 很小，考虑离线 \(a_i\) 和询问 \(1\) 的 \(y\)，离散化，值域线段树上修改/查询。
#include <bits/stdc++.h>
#define _for(i, a, b) for(I i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(I i = (a); i < (b); i ++)
#define _rof(i, a, b) for(I i = (a); i >= (b); i --)
#define _pre(i, a, b) for(I i = (a); i > (b); i --)
#define inl inline
#define I int
#define L long long
#define LL 1ll
inl I read(){
static I bo, x; bo = x = 0;
static char c; c = getchar();
while(c < '0' || c > '9') {if(c == '-')bo = 1; c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<3) + (x<<1) + c - '0'; c = getchar();}
return bo ? -x : x;
}
inl void out(L x, bool bo = true){
if(x < 0) putchar('-'), x = -x;
if(x == 0){if(bo)putchar('0'); return;}
out(x/10, false), putchar('0' + x%10);
}
using namespace std;
const int N = 4e5;
const int LEN = 4e5+11;
struct opt{int op, x, y;};
vector<opt> op;
int n, a[N], b[N], total, ls[N*3], q;
namespace sgt{
#define lc ((k)<<(1))
#define rc ((k)<<(1)|(1))
#define mid ((l) + (r) >> (1))
L sum[LEN<<2], cnt[LEN<<2];
void pushup(int k){
cnt[k] = cnt[lc] + cnt[rc];
sum[k] = sum[lc] + sum[rc];
}
void modify(int x, int y, int k = 1, int l = 1, int r = total){
if(x > r || x < l) return;
if(l == r){
cnt[k] += y, sum[k] += LL * ls[x] * y;
return;
}
modify(x, y, lc, l, mid), modify(x, y, rc, mid+1, r);
pushup(k);
}
L query(int x, int k = 1, int l = 1, int r = total){
if(cnt[k] < x) return -1;
if(l == r) return LL * ls[l] * x;
if(x > cnt[rc]) return sum[rc] + query(x-cnt[rc], lc, l, mid);
else return query(x, rc, mid+1, r);
}
}
int main(){
n = read();
_for(i, 1, n) a[i] = read(), b[i] = read(), ls[++total] = a[i];
q = read();
_for(i, 1, q){
int opts = read(), x = read(), y = 0;
if(opts <= 2){
y = read();
if(opts == 1) ls[++total] = y;
}
op.push_back((opt){opts, x, y});
}
sort(ls+1, ls+total+1);
total = unique(ls+1, ls+total+1)-ls-1;
_for(i, 1, n) a[i] = lower_bound(ls+1, ls+total+1, a[i])-ls;
_for(i, 0, q-1) if(op[i].op == 1)
op[i].y = lower_bound(ls+1, ls+total+1, op[i].y)-ls;
_for(i, 1, n) sgt::modify(a[i], b[i]);
_for(i, 0, q-1){
if(op[i].op == 3) out(sgt::query(op[i].x)), puts("");
else{
sgt::modify(a[op[i].x], -b[op[i].x]);
if(op[i].op == 1) a[op[i].x] = op[i].y;
else b[op[i].x] = op[i].y;
sgt::modify(a[op[i].x], b[op[i].x]);
}
}
return 0;
}
H Directed Graph and Query
考虑 \(Floyd\) 的性质，第一个枚举的 \(k\) 的意义是只经过 \(1\) 至 \(k\) 的节点的最短距离。
考虑离线枚举答案看是否有解（ \(u\) 可以到达 \(v\) ）。
\(bitset\) 优化 \(Floyd\) 传递闭包,时间复杂度 \(O(\dfrac{n^3}{w} + nq)\)。
#include <bits/stdc++.h>
#define _for(i, a, b) for(I i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(I i = (a); i < (b); i ++)
#define _rof(i, a, b) for(I i = (a); i >= (b); i --)
#define _pre(i, a, b) for(I i = (a); i > (b); i --)
#define inl inline
#define I int
inl I read(){
static I bo, x; bo = x = 0;
static char c; c = getchar();
while(c < '0' || c > '9') {if(c == '-')bo = 1; c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<3) + (x<<1) + c - '0'; c = getchar();}
return bo ? -x : x;
}
inl void out(I x, bool bo = true){
if(x < 0) putchar('-'), x = -x;
if(x == 0){if(bo)putchar('0'); return;}
out(x/10, false), putchar('0' + x%10);
}
using namespace std;
const int N = 2001;
bitset<2001> e[N];
int n, m, q, qa[N*10], qb[N*10], ans[N*10];
int main(){
n = read(), m = read();
_for(i, 1, m){
static int u, v;
u = read(), v = read();
e[u][v] = 1;
}
q = read();
_for(i, 1, q) qa[i] = read(), qb[i] = read(), ans[i] = -1;
_for(i, 1, n){
_for(u, 1, n) if(e[u][i]) e[u] |= e[i];
_for(qt, 1, q) if(ans[qt] == -1 && e[qa[qt]][qb[qt]] == 1) ans[qt] = max(i, max(qa[qt], qb[qt]));
}
_for(i, 1, q) out(ans[i]), puts("");
return 0;
}