T1 游戏
标签
尺取 线段树 单调队列
线段树进阶
思路
抽象题意，相当于有 \(t\) 个点，有 \(n\) 个下接 \(x\) 轴的矩形。
首先明显可以按照 \(c\) 排序，然后尺取。
写法
线段树记录每区间内未被覆盖的最大高度。
因为插入和删除的顺序相对不变，一个单调队列维护该区间内矩形高度即可，若有删除操作则向儿子取 \(\max\) 重新计算 \(mx\)。
代码
常数极大，可使用内存池优化。
code
ci N = 1e6 + 9;
ci inf = 2e9;
int t, n, ans(inf);
int a[N], b[N], c[N], v[N], h[N], id[N];
bool cmp(int x, int y) {return c[x] < c[y];}
struct SGT {
#define lc ((u) << 1)
#define rc ((u) << 1 | 1)
int mx[N << 2], buf[N * 40];
unsigned int head[N << 2], tail[N << 2];
il void pushup_mx(int u) {
if(head[u] > tail[u]) return;
if(v[q[u][head[u]]] >= mx[u]) mx[u] = 0;
}
il void pushup(int u) {
mx[u] = max(mx[lc], mx[rc]);
pushup_mx(u);
}
il void build(int u, int l, int r) {
if(l == r) return mx[u] = h[l], void();
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(u);
}
il void insert(int u, int l, int r, int a, int b, int i) {
if(a <= l && r <= b) {
while(head[u] < q[u].size() && v[*(-- q[u].end())] <= v[i]) q[u].pop_back();
q[u].eb(i);
if(v[q[u][head[u]]] >= mx[u]) mx[u] = 0;
return;
}
if(b < l || r < a) return;
int mid = (l + r) >> 1;
insert(lc, l, mid, a, b, i);
insert(rc, mid + 1, r, a, b, i);
pushup(u);
}
il void erase(int u, int l, int r, int a, int b, int i) {
if(a <= l && r <= b) {
if(q[u][head[u]] == i) {
++ head[u];
if(l == r) {
mx[u] = h[l];
pushup_mx(u);
}
else {
pushup(u);
}
}
return;
}
if(b < l || r < a) return;
int mid = (l + r) >> 1;
erase(lc, l, mid, a, b, i);
erase(rc, mid + 1, r, a, b, i);
pushup(u);
}
} tree;
il void ins(int i) {
tree.insert(1, 1, t, a[i], b[i], i);
}
il void ers(int i) {
tree.erase(1, 1, t, a[i], b[i], i);
}
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
rd(t); rd(n);
rep(i, 1, n) {
rd(a[i], b[i], c[i], v[i]);
id[i] = i;
}
sort(id + 1, id + n + 1, cmp);
rep(i, 1, t) rd(h[i]);
tree.build(1, 1, t);
int L = 1;
rep(_i, 1, n) {
int i = id[_i];
ins(i);
while(tree.mx[1] == 0) {
cmin(ans, c[i] - c[id[L]]);
ers(id[L]); ++ L;
}
}
pt("%d\n", ans);
return 0;
}
T2 驻军
标签
长链剖分，树上前缀和进阶
思路
订正的时候没有对答案取模再乘，dfs 时没有判长链。
考虑将找链转化为对端点处理，发现可以通过处理将答案变为只与 \(lca(x, y), x, y\) 有关的形式，这样才能进行长链剖分。
约定
\(f_u\) 表示 \(u\) 子树内所有点到 \(u\) 的距离和。
\(e_{u, v}\) 表示 \((u\to v)\) 的边权。
\(h_u\) 表示 \(u\) 子树外所有点到 \(u\) 的距离和。
\(sz_u\) 表示 \(u\) 子树的大小。
\(w_v\) 表示 \((fa_v\to v)\) 的贡献，等于 \(sz_v\cdot e_{fa_v, v}\)。
\(s_u\) 表示从 \(u\) 到根（可设为 \(1\)）的简单路径上的边的 \(w\) 之和，等于 \(w_u + w_{fa_u} + \cdots\)
转移
若路径为 \(x, y\)，设 \(lca(x, y) = u\) 则答案为 \(h_u + f_u - (s_x - s_u) - (s_y - s_u)\)。
这个比较难，可对每条边快速统计多算的贡献，减去即可。
\(f_u = \sum\limits_{u\to v} (f_v + w_v)\)
\(s_v = s_u + w_v\)
\(h_v = (n - sz_v)\cdot e_{u, v} + h_u + f_u - f_v - w_v\)
代码
code
ci N = 2e6 + 9;
const ll INF = 1e18;
int n, k;
ll sz[N], f[N], s[N], h[N], w[N];
vector<pii> A[N];
void dfs1(int u, int la) {
sz[u] = 1;
for(pii e : A[u]) {
int v = e.fi;
if(v == la) continue;
dfs1(v, u);
sz[u] += sz[v];
w[v] = sz[v] * e.se;
f[u] += f[v] + w[v];
}
}
int depth[N], son[N];
void dfs2(int u, int la) {
depth[u] = 1;
for(pii e : A[u]) {
int v = e.fi;
if(v == la) continue;
s[v] = s[u] + w[v];
h[v] = 1LL * (n - sz[v]) * e.se + h[u] + (f[u] - f[v] - w[v]);
dfs2(v, u);
cmax(depth[u], depth[v] + 1);
if(depth[v] + 1 == depth[u]) son[u] = v;
}
}
ll buc[N], *mx[N], ans(INF);
void dfs(int u, int la) {
mx[u][1] = s[u];
if(son[u]) {
mx[son[u]] = mx[u] + 1;
dfs(son[u], u);
for(pii e : A[u]) {
int v = e.fi;
if(v == la || v == son[u]) continue;
mx[v] = mx[u] + depth[u];
dfs(v, u);
rep(i, 1, depth[v]) {
if(i > 0 && k - i > 1 && i <= depth[v] && k - i <= depth[u]) {
cmin(ans, h[u] + f[u] + 2 * s[u] - mx[u][k - i] - mx[v][i]);
if(ans < 0) {
printf("%lld %lld %lld\n", h[u], f[u], s[u]);
printf("u-road = %d v = %d\n", u, v), exit(0);
}
}
}
rep(i, 1, depth[v]) cmax(mx[u][i + 1], mx[v][i]), mx[v][i] = 0;
}
}
if(depth[u] >= k) {
cmin(ans, h[u] + f[u] + s[u] - mx[u][k]);
if(ans < 0) printf("u-list = %d\n", u),exit(0);
}
}
ci mod = 998244353;
ll fpow(ll a, ll x) {
ll res = 1;
while(x) {
if(x & 1) res = res * a % mod;
a = a * a % mod;
x >>= 1;
}
return res;
}
int dis[N];
void _dfs(int u, int la) {
dis[u] = dis[la] + 1;
for(pii e : A[u]) {
if(e.fi == la) continue;
_dfs(e.fi, u);
}
}
int main() {
// freopen("barrack.in", "r", stdin);
// freopen("barrack.out", "w", stdout);
freopen("a.in", "r", stdin);
rd(n, k);
rep(i, 2, n) {
int x, y, z;
rd(x, y, z);
A[x].eb(mp(y, z));
A[y].eb(mp(x, z));
}
int st = 1;
_dfs(1, 0);
rep(i, 2, n) {
if(dis[i] > dis[st]) {
st = i;
}
}
_dfs(st, 0);
rep(i, 1, n) {
if(dis[i] > dis[st]) {
st = i;
}
}
if(dis[st] < k) return puts("-1"), 0;
dfs1(1, 0);
dfs2(1, 0);
mx[1] = buc;
dfs(1, 0);
printf("%lld\n", ans % mod * fpow(n, mod - 2) % mod);
return 0;
}
T3 序列
标签
离线
线段树入门
思路
考虑将所有操作离线，对于每一个位置 \(i\) 处理询问。
第 \(j\) 次询问 \(p,k\) 相当于将 \(0\to k - 1\) 的前缀和与 \(k\sim j\) 的 \(\gcd\) 求一个 \(\gcd\)，开个线段树维护一下区间和和区间 \(\gcd\) 即可。
感觉比 T2 简单。
代码
代码好写。
code
ci N = 2.5e5 + 9;
int n, q;
int a0[N], qval[N], op[N];
ll ans[N];
vector<int> ins[N], ers[N];
vector<int> qry[N];
ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b);}
struct SGT {
#define lc ((u) << 1)
#define rc ((u) << 1 | 1)
int tr_gcd[N << 2];
ll tr_sum[N << 2];
void push_up(int u) {
tr_sum[u] = tr_sum[lc] + tr_sum[rc];
tr_gcd[u] = gcd(tr_gcd[lc], tr_gcd[rc]);
}
void modify(int u, int l, int r, int loc, int var) {
if(l == r) {
tr_gcd[u] = tr_sum[u] = var;
return;
}
int mid = (l + r) >> 1;
if(loc <= mid) modify(lc, l, mid, loc, var);
else modify(rc, mid + 1, r, loc, var);
push_up(u);
}
ll querysum(int u, int l, int r, int a, int b) {
if(a <= l && r <= b) return tr_sum[u];
if(b < l || r < a) return 0;
int mid = (l + r) >> 1;
return querysum(lc, l, mid, a, b) + querysum(rc, mid + 1, r, a, b);
}
int querygcd(int u, int l, int r, int a, int b) {
if(a <= l && r <= b) return tr_gcd[u];
if(b < l || r < a) return 0;
int mid = (l + r) >> 1;
return gcd(querygcd(lc, l, mid, a, b), querygcd(rc, mid + 1, r, a, b));
}
} tree;
int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
rd(n, q);
rep(i, 1, n) rd(a0[i]);
rep(i, 1, q) {
rd(op[i]);
if(op[i] == 1) {
int l, r; rd(l, r, qval[i]);
ins[l].eb(i);
ers[r + 1].eb(i);
}
else {
int p; rd(p, qval[i]);
qry[p].eb(i);
}
}
rep(i, 1, n) {
for(int j : ins[i]) {
tree.modify(1, 1, q, j, qval[j]);
}
for(int j : ers[i]) {
tree.modify(1, 1, q, j, 0);
}
for(int j : qry[i]) {
ans[j] = gcd(a0[i] + tree.querysum(1, 1, q, 1, qval[j] - 1), tree.querygcd(1, 1, q, qval[j], j));
}
}
rep(i, 1, q) {
if(op[i] == 2) {
printf("%lld\n", abs(ans[i]));
}
}
return 0;
}