A. xor on tree
操作分块，每 \(Q/B\) 次遍历整棵树，每个询问需要特殊查询 \(B\) 个
复杂度 \(\frac{Q}{B}nlog + QB\)
大力卡常能过
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e5 + 5;
vector<int>son[maxn], point;
int n, w[maxn], q, qnt, ans[maxn], las[maxn];
int tim, dfn[maxn], dfnr[maxn], sum[maxn];
struct node{int tim, x, val;};
struct rem{int qid, tim;};
vector<node>o; vector<rem>qy[maxn];
bool in[maxn];
struct Trie{
int ch[maxn * 31][2], si[maxn * 31], cnt = 1, rt = 1;
void insert(int x, int op){
int now = rt;
for(int i = 30; i >= 0; --i){
if(!ch[now][(x >> i) & 1])ch[now][(x >> i) & 1] = ++cnt;
now = ch[now][(x >> i) & 1]; si[now] += op;
}
}
int query(int x){
int res = 0, now = 1;
for(int i = 30; i >= 0 && now; --i){
if(si[ch[now][((x >> i) & 1) ^ 1]])res += (1 << i), now = ch[now][((x >> i) & 1) ^ 1];
else now = ch[now][(x >> i) & 1];
}
return res;
}
}T;
void pre(int x){
dfn[x] = ++tim;
for(int v : son[x])pre(v);
dfnr[x] = tim;
}
void dfs(int x){
if(sum[dfn[x] - 1] == sum[dfnr[x]])return;
if(!in[x])T.insert(w[x], 1);
for(rem v : qy[x])ans[v.qid] = T.query(v.tim);
for(int v : son[x])dfs(v);
if(!in[x])T.insert(w[x], -1);
}
void sol(){
for(int i = 1; i <= n; ++i)sum[i] += sum[i - 1];
dfs(1);
for(node v : o)
if(v.tim){
for(int p : point)
if(dfn[v.x] >= dfn[p] && dfnr[v.x] <= dfnr[p])
ans[v.val] = max(ans[v.val], w[v.x] ^ w[p]);
}else w[v.x] = v.val;
o.clear(); point.clear(); for(int i = 1; i <= n; ++i)sum[i] = in[i] = false, qy[i].clear();
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = read(), q = read();
for(int i = 1; i <= n; ++i)las[i] = w[i] = read();
for(int i = 2; i <= n; ++i)son[read()].push_back(i);
pre(1);
int B = sqrt(n * 30) * 3.4;
for(int i = 1; i <= q; ++i){
int op = read(), u = read();
if(!op){o.push_back({0, u, read()}); in[u] = true; las[u] = o.back().val; point.push_back(u); }
else {qy[u].push_back({++qnt, las[u]}); o.push_back({1, u, qnt}); ++sum[dfn[u]];}
if(i % B == 0)sol();
}
sol();
for(int i = 1; i <= qnt; ++i)printf("%d\n",ans[i]);
return 0;
}
B. calc on lowbit
转成差分的形式，现在计算\(\sum_{i = 1}^r f(i)\)
设 \(f, g _{i, 1 / 0, 1 / 0}\) 表示考虑后 \(i\) 位，是否有进位，是否比 \(r\) 大的概率和期望
枚举该位填啥进行转移
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int mod = 998244353, inv2 = (mod + 1) >> 1;
int f[62][2][2], g[62][2][2];
void add(int &x, int y){x += y; if(x >= mod)x -= mod;}
int calc(ll r){
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
g[0][0][0] = 1;
for(int i = 0; i < 60; ++i){
for(int j = 0; j <= 1; ++j)
for(int k = 0; k <= 1; ++k)
for(int p = 0; p <= 1; ++p){
bool big = ((r >> i) & 1) < p || (((r >> i) & 1) == p && k);
if(j + p == 0){
add(f[i + 1][0][big], f[i][j][k]);
add(g[i + 1][0][big], g[i][j][k]);
}else if(j + p == 1){
int val = 1ll * (f[i][j][k] + g[i][j][k]) * inv2 % mod;
int v2 = 1ll * g[i][j][k] * inv2 % mod;
add(f[i + 1][0][big], val);
add(g[i + 1][0][big], v2);
add(f[i + 1][1][big], val);
add(g[i + 1][1][big], v2);
}else{
add(f[i + 1][1][big], f[i][j][k]);
add(g[i + 1][1][big], g[i][j][k]);
}
}
}
return (0ll + f[60][0][0] + f[60][1][0] + 2ll * g[60][1][0]) % mod;
}
int main(){
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
int T = read();
for(int i = 1; i <= T; ++i){
ll l = read(), r = read();
printf("%d\n",(calc(r) - calc(l - 1) + mod) % mod);
}
return 0;
}
C. color on board
数据范围就很网络流
每个点建出四个点，表示横着涂黑，竖着涂白，没有竖着涂黑，没有横着涂白
对于 \(ak + b\) 的 \(b\)， 钦定在最后的位置贡献
以横黑为例，如果 \((i,j)\) 涂了， \((i + 1, j)\) 没涂，那么需要有 \(b\) 的代价
或者其是最后一列，涂白的代价本身就是 \(a + b\)
其他情况同理
现在考虑单个点的限制
如果最终要涂黑，那么之前不能涂白，改白色的代价为 \(inf\)， 如果没有横竖涂黑，那么需要单点涂黑，有 \(c\) 的代价
建出来长这样
对于白色，可以证明一定不会被同方向不同颜色涂，所以涂横黑必然涂竖白或者单点涂白
并且限制了不能两次涂黑
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 41 * 41 * 5;
const int maxm = maxn * 200;
int n, m, a, b, c;
char mp[45][45];
int hh[45][45], sb[45][45], fsh[45][45], fhb[45][45], cnt;
struct Dinic{
int s, t, head[maxn], tot = 1;
struct edge{int to, net, val;}e[maxm];
void add(int u, int v, int w){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
e[tot].val = w;
}
void link(int u, int v, int w){add(u, v, w); add(v, u, 0);}
int dep[maxn], now[maxn];
bool bfs(){
for(int i = 1; i <= t; ++i)dep[i] = 0;
queue<int>q; dep[s] = 1; q.push(s);
now[s] = head[s];
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(e[i].val > 0 && dep[v] == 0){
dep[v] = dep[x] + 1;
now[v] = head[v];
if(v == t)return true;
q.push(v);
}
}
}
return false;
}
int dfs(int x, int from){
if(x == t || from <= 0)return from;
int res = from, i;
for(i = now[x]; i; i = e[i].net){
int v = e[i].to;
if(e[i].val > 0 && dep[v] == dep[x] + 1){
int k = dfs(v, min(res, e[i].val));
if(k <= 0)dep[v] = 0;
e[i].val -= k;
e[i ^ 1].val += k;
res -= k;
if(res <= 0)break;
}
}
now[x] = i;
return from - res;
}
int dinic(){
int ans = 0;
while(bfs())ans += dfs(s, inf);
return ans;
}
void clear(){
for(int i = 1; i <= t; ++i)head[i] = 0;
cnt = 0; tot = 1;
}
void init(){
n = read(), m = read(), a = read(), b = read(), c = read();
for(int i = 1; i <= n; ++i)scanf("%s",mp[i] + 1);
for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)hh[i][j] = ++cnt, sb[i][j] = ++cnt, fsh[i][j] = ++cnt, fhb[i][j] = ++cnt;
s = ++cnt, t = ++cnt;
for(int i = 1; i <= n; ++i)
for(int j = 1; j < m; ++j){
link(hh[i][j + 1], hh[i][j], b);
link(fhb[i][j], fhb[i][j + 1], b);
}
for(int i = 1; i < n; ++i)
for(int j = 1; j <= m; ++j){
link(sb[i + 1][j], sb[i][j], b);
link(fsh[i][j], fsh[i + 1][j], b);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(mp[i][j] == '#'){
link(hh[i][j], fsh[i][j], c);
link(s, sb[i][j], inf);
link(s, hh[i][j], a + (j == m ? b : 0));
link(fhb[i][j], t, inf);
link(fsh[i][j], t, a + (i == n ? b : 0));
}else{
link(s, hh[i][j], a + (j == m ? b : 0));
link(s, sb[i][j], a + (i == n ? b : 0));
link(fsh[i][j], t, a + (i == n ? b : 0));
link(fhb[i][j], t, a + (j == m ? b : 0));
link(sb[i][j], hh[i][j], c);
link(fsh[i][j], fhb[i][j], c);
link(fsh[i][j], hh[i][j], inf);
}
printf("%d\n", dinic());
clear();
}
}w;
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
int T = read();
for(int i = 1; i <= T; ++i)w.init();
return 0;
}