挑战
最后发现就是分块大暴力，要是有更有意思的解法就好了（不过这个信息本来就没有优秀的合并方式，或者用一种二位在线偏序结构倒是可以解决这个问题）。
// challenge.cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 200;
const unsigned MAGIC_NUM = 4294967295u;
ll ai[MAX_N], wi[MAX_N], n, q, block_siz, block_tot, lft[MAX_N];
pair<ll, int> tmp[MAX_N];
ll pre[MAX_N], tree[MAX_N];
int lowbit(int x) { return x & (-x); }
void update(int x, ll d)
{
for (; x <= n; x += lowbit(x))
tree[x] += d;
}
ll query(int x)
{
ll ans = 0;
for (; x; x -= lowbit(x))
ans += tree[x];
return ans;
}
unsigned xnor(unsigned a, unsigned b) { return ~((a & MAGIC_NUM) ^ (b & MAGIC_NUM)); }
void rebuild(int id)
{
for (int i = lft[id]; i <= lft[id + 1] - 1; i++)
tmp[i] = make_pair(wi[i], i);
sort(tmp + lft[id], tmp + lft[id + 1]);
pre[lft[id]] = wi[tmp[lft[id]].second] * ai[tmp[lft[id]].second];
for (int i = lft[id] + 1; i <= lft[id + 1] - 1; i++)
pre[i] = pre[i - 1] + wi[tmp[i].second] * ai[tmp[i].second];
}
int main()
{
scanf("%lld%lld", &n, &q);
block_siz = sqrt(n), block_tot = (n + block_siz - 1) / block_siz;
lft[1] = 1, lft[block_tot + 1] = n + 1;
for (int i = 2; i <= block_tot; i++)
lft[i] = lft[i - 1] + block_siz;
for (int i = 1; i <= n; i++)
scanf("%lld", &ai[i]), update(i, ai[i]);
for (int i = 1; i <= n; i++)
scanf("%lld", &wi[i]);
for (int i = 1; i <= block_tot; i++)
rebuild(i);
while (q--)
{
ll op, x, y, z;
scanf("%lld%lld%lld", &op, &x, &y);
if (op == 1)
{
scanf("%lld", &z);
unsigned ans = 0, pans = query(y) - query(x - 1);
int xid = (x + block_siz - 1) / block_siz, yid = (y + block_siz - 1) / block_siz;
if (xid != yid)
{
for (int i = xid + 1; i <= yid - 1; i++)
{
int pos = lower_bound(tmp + lft[i], tmp + lft[i + 1], make_pair(z + 1, 0)) - tmp - 1;
ans += pos >= lft[i] ? pre[pos] : 0;
}
for (int i = x; i <= lft[xid + 1] - 1; i++)
if (wi[i] <= z)
ans += wi[i] * ai[i];
for (int i = lft[yid]; i <= y; i++)
if (wi[i] <= z)
ans += wi[i] * ai[i];
}
else
for (int i = x; i <= y; i++)
if (wi[i] <= z)
ans += wi[i] * ai[i];
printf("%u\n", xnor(ans, pans));
}
else if (op == 2)
{
update(x, -ai[x]), ai[x] = y;
rebuild((x + block_siz - 1) / block_siz);
update(x, ai[x]);
}
else
{
wi[x] = y;
rebuild((x + block_siz - 1) / block_siz);
}
}
return 0;
}
CF9E
真的暴力，本来以为是\(O(n^2 \log n)\)的大暴力，忘记了 BFS 可以做到更优（因为队列中的距离单调）。
@@ -0,0 +1,82 @@
// CF59E.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>
using namespace std;
const int MAX_N = 3010, MAX_M = 20202;
int head[MAX_N], current, n, m, k;
int upward[MAX_N][MAX_N], dist[MAX_N][MAX_N], tmp[MAX_N];
vector<int> vecs[MAX_N][MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_M << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
bool check(int a, int b, int c)
{
for (int i = 0, siz = vecs[a][b].size(); i < siz; i++)
if (vecs[a][b][i] == c)
return false;
return true;
}
void writeAns(int pre)
{
printf("%d\n1 ", dist[pre][n]);
int pt = n, tot = 0;
int fat = n;
/*
while (pt != 1)
{
tmp[++tot] = pt;
int tp = pre, pre = upward[pre][pt], pt = tp;
}
*/
while (fat != 1)
{
tmp[++tot] = fat;
int tp = pre;
pre = upward[pre][fat];
fat = tp;
}
for (int i = tot; i >= 1; i--)
printf("%d ", tmp[i]);
}
void bfs()
{
queue<pr> q;
q.push(make_pair(0, 1));
while (!q.empty())
{
int pre = q.front().first, u = q.front().second;
q.pop();
if (u == n)
writeAns(pre), exit(0);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (!dist[u][edges[i].to] && check(pre, u, edges[i].to))
upward[u][edges[i].to] = pre, dist[u][edges[i].to] = dist[pre][u] + 1, q.push(make_pair(u, edges[i].to));
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &m, &k);
for (int i = 1, u, v; i <= m; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
for (int i = 1, x, y, z; i <= k; i++)
scanf("%d%d%d", &x, &y, &z), vecs[x][y].push_back(z);
bfs();
puts("-1");
return 0;
}
CF1244D
刚开始觉得挺复杂，后面发现多数情况都可以被判作无解：除了一条链的情况，其他都可以被认为是无解的，这个很容易证明。所以，搞 6 次就可以拿到解。
// CF1244D.cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 1e5 + 200;
int head[MAX_N], current, n, color[4][MAX_N], dp[MAX_N], deg[MAX_N], answer[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void dfs(int u, int fa, int A, int B)
{
dp[u] = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
dfs(edges[i].to, u, B, A ^ B);
dp[u] += dp[edges[i].to];
}
dp[u] += color[A ^ B][u];
}
void getAns(int u, int fa, int A, int B)
{
answer[u] = A ^ B;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
getAns(edges[i].to, u, B, A ^ B);
}
signed main()
{
memset(head, -1, sizeof(head));
scanf("%lld", &n);
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n; j++)
scanf("%lld", &color[i][j]);
for (int i = 1, u, v; i < n; i++)
scanf("%lld%lld", &u, &v), deg[u]++, deg[v]++, addpath(u, v), addpath(v, u);
int pt = 0;
bool flag = false;
for (int i = 1; i <= n; i++)
flag |= deg[i] > 2, pt = (deg[i] == 1 ? i : pt);
if (flag)
puts("-1"), exit(0);
int ans = 1e18, oA, oB;
for (int A = 1; A <= 3; A++)
for (int B = 1; B <= 3; B++)
if (A != B)
{
dfs(pt, 0, A, B);
if (dp[pt] < ans)
oA = A, oB = B, ans = dp[pt];
}
getAns(pt, 0, oA, oB);
printf("%lld\n", ans);
for (int i = 1; i <= n; i++)
printf("%lld ", answer[i]);
return 0;
}