题目
AtCoder Beginner Contest 294 E - 2xN Grid
AtCoder Beginner Contest 294 G - Sugar Water 2
做题记录
AtCoder Beginner Contest 294 E - 2xN Grid
因为长度有\(10^12\)不能暴力匹配，但考虑到两个数组的切割点（就是二元组数量）只有 \(O(10^5)\)，因此我们就以切割点，每块每块考虑就可以了。
感觉非常暴力啊。（不是我说的，是Lanely大佬说的）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans, idxa, idxb;
int l, n, m;
int read()
{
int x = 0, w = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * w;
}
signed main()
{
l = read(), n = read(), m = read();
vector<array<int, 2> > a(n), b(m);
for (int i = 0; i < n; i++)
a[i][0] = read(), a[i][1] = read();
for (int i = 0; i < m; i++)
b[i][0] = read(), b[i][1] = read();
while (1)
{
int minn = min(a[idxa][1], b[idxb][1]);
if (a[idxa][0] == b[idxb][0])
ans += minn;
a[idxa][1] -= minn;
b[idxb][1] -= minn;
if (a[idxa][1] == 0)
idxa++;
if (b[idxb][1] == 0)
idxb++;
if (idxa == n || idxb == m)
break;
}
printf("%lld\n", ans);
return 0;
}
AtCoder Beginner Contest 294 G - Sugar Water 2
这个题就是个DFS序+LCA+线段树维护操作的模板题。
只是在修改update和query的时候有一点区别要注意。
#include<bits/stdc++.h>
#define lson l, mid, root << 1
#define rson mid + 1, r, root << 1 | 1
#define lroot root << 1
#define rroot root << 1 | 1
#define int long long
using namespace std;
const int N = 5e5 + 10;
int read()
{
int x = 0, w = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * w;
}
int dep[N], p[N][50];
int a[N], in[N], out[N], cnt;
int indx[N];
int sum[N << 2], lazy[N << 2];
int u[N], v[N], w[N];
int h[N], e[N], ne[N], ww[N], idx;
int n;
void add(int a, int b, int c)
{
e[++idx] = b;
ww[idx] = c;
ne[idx] = h[a];
h[a] = idx;
}
void dfs(int u, int fa)
{
in[u] = ++cnt;
indx[cnt] = u;
dep[u] = dep[fa] + 1;
p[u][0] = fa;
for (int i = 1; (1 << i) <= dep[u]; i++)
p[u][i] = p[p[u][i - 1]][i - 1];
for (int i = h[u]; i; i = ne[i])
{
int v = e[i];
if (v == fa)
continue;
a[v] = a[u] + ww[i];
dfs(v, u);
}
out[u] = cnt;
}
int lca(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
{
if (dep[p[x][i]] >= dep[y])
x = p[x][i];
if (x == y)
return x;
}
for (int i = 20; i >= 0; i--)
if (p[x][i] != p[y][i])
{
x = p[x][i];
y = p[y][i];
}
return p[x][0];
}
void push_up(int root)
{
sum[root] = sum[lroot] + sum[rroot];
}
void build(int l, int r, int root)
{
if (l == r)
{
sum[root] = a[indx[l]];
return ;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
push_up(root);
}
inline void push_down(int root, int l, int r) {
if (lazy[root] != 0) {
int mid = (l + r) >> 1;
lazy[lroot] += lazy[root];
lazy[rroot] += lazy[root];
sum[lroot] = sum[lroot] + (mid - l + 1) * lazy[root];
sum[rroot] = sum[rroot] + (r - mid) * lazy[root];
lazy[root] = 0;
return ;
}
}
void update(int l, int r, int root, int ll, int rr, int k)
{
if (ll <= l && r <= rr)
{
sum[root] += (r - l + 1) * k;
lazy[root] += k;
return ;
}
push_down(root, l, r);
int mid = (l + r) >> 1;
if (ll <= mid)
update(lson, ll, rr, k);
if (rr > mid)
update(rson, ll, rr, k);
push_up(root);
}
int query(int l, int r, int root, int aim)
{
if (l == r && r == aim)
return sum[root];
int res = 0;
push_down(root, l, r);
int mid = (l + r) >> 1;
if (aim <= mid)
res += query(lson, aim);
if (aim > mid)
res += query(rson, aim);
return res;
}
signed main()
{
n = read();
for (int i = 1; i < n; i++)
{
u[i] = read(), v[i] = read(), w[i] = read();
add(u[i], v[i], w[i]);
add(v[i], u[i], w[i]);
}
dfs(1, 0);
for (int i = 1; i < n; i++)
if (in[u[i]] > in[v[i]])
swap(u[i], v[i]);
build(1, n, 1);
int q = read();
while (q--)
{
int opt = read(), x = read(), y = read();
if (opt == 1)
{
update(1, n, 1, in[v[x]], out[v[x]], y - w[x]);
w[x] = y;
}
else
{
int fa = lca(x, y);
printf("%lld\n", query(1, n, 1, in[x]) + query(1, n, 1, in[y]) - 2 * query(1, n, 1, in[fa]));
}
}
return 0;
}