A. xor on tree
在一棵 \(n\) 个点的树上，第 \(i\) 个点初始点权 \(w_i\)，有 \(q\) 次操作：
0 u v：\(v\to w_u\)1 x：查询 \(w_x\operatorname{xor}w_y\) 的最大值，其中 \(y\) 是 \(x\) 的祖先（包括 \(x\)）\(n,q\le 10^5\), TL=2s, ML=128MB.
在考场上先是绞尽脑汁想到一个时间复杂度 \(O(n\log n\log V)\) 的动态开点先段树 + 01 trie 的做法，在注释里写道 bravo! is it correct? I bet it is.。写完 debug 时突然意识到空间有点大，一看 ML，128MB，愤怒地在注释里写道 Oh no, Memory limit 128M! You must be kidding!。随后稳定产出不能实际优化空间复杂度的做法（包括把 01trie 上动态开点线段树改成线段树分治+动态开点 01trie 这种奇怪的算法）。无奈只能先去看后两题，发现 T2 送了 60 分，T3 暴力都不会。又回来想 T1，冥思苦想之后，我发现空间复杂度大的原因其实是线段树和动态开点线段树同时存在，这样至少一个要动态开点，而只要其中一个不需要用，另一个的复杂度就可以保证了。我又想到，xor 问题一般要么想 01trie，要么想按位考虑，咦，那按位考虑能不能行呢？发现确实可以逐位确定答案，做一个类似基数排序或者数位 DP 的事情，这样时间复杂度不变，01trie 却被完全解构了，只需要用普通线段树维护区间加、单点查即可，而用树状数组就更快了。赛后发现我这个做法居然是空间复杂度最小的！跟大家都不一样！我只用了 27MB，但是其他人都是 40MB+。
从最开始的方法说起吧。首先考虑能树剖吗？想想发现不太行。尝试离线，并考虑到形如“从根到 \(u\)”的查询的常见离线方法是按照 dfs 序 dfs，进入一个点时加入一些东西，回溯时撤销，到点时统计此时的答案给到询问。
那么我们所需要支持的，就是将一个在某一段时间之内存在的数，插入 01trie，以及在线查询 01trie 的一个子树目前是否为空。
稍加思考便可发现，我们可以对这棵 01trie 的每个点开一棵线段树，插入时对在 trie 上经过的 \(O(\log V)\) 的点的线段树执行区间 \([timl,timr]\) \(+1\)(插入)/\(-1\)(删除) 操作。而询问时，设询问的时间是 \(tim\)，就只需要单点查询想去的儿子的线段树的 \(tim\) 位置是否为 \(0\)，来判断是否能往那边走。
但是正如上文所说，这是一个空间复杂度过高的算法。考虑到 xor 问题的另一种解决思路——逐位确定——我们尝试先来确定各询问答案的最高位。
对于一个询问 \(W=w_x\)，\(W\) 的按位取反（~W）一定是最优的。我们现在称一个“事件”为以下两种：
- \((0,timl,timr,x,u)\)：在 \(u\) 处有一个 \([timl,timr]\) 内有效的数 \(x\)
- \((1,tim,x,u)\)：在 \(u\) 处有一个 \(tim\) 时的查询数 \(x\)
将所有 \(x\) 的最高位 \(=1\) 的事件一起考虑，其他事件暂时不考虑，用栈做一个类似虚树上 dfs 的过程，一个事件被降维为 \([timl,timr]\) 区间加或 \(tim\) 单点查。查得答案为 \(0\) 表示“理想与现实不匹配”。同理处理最高位 \(=0\) 及同理从高到低确定每一位（例如确定第 2 高位时就是把前两位为 00,01,10,11 的拉出来分别一起考虑），与基数排序非常相似。当然，如果在这一位发现“理想与现实不匹配”，就要修改理想的这一位为现实，以便后面的位能正确地排序。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO {
const int buflen=1<<21;
int x;
bool f;
char ch,buf[buflen],*p1=buf,*p2=buf;
inline char gc(){return p1==p2&&(p2=buf+fread(p1=buf,1,buflen,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
x=0,f=1,ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return f?x:-x;
}
}
using IO::read;
void print(int x){
if(x/10)print(x/10);
putchar(x%10+48);
}
const int N=1e5+5,U=(1<<30)-1;
int n,q,num,dfc,w[N],ww[N],op[N],ans[N],nod[N],stk[N*2],fa[N][18],dep[N];
vector<int>G[N];
vector<pair<int,int> >qu[N];
struct thing {
int type,x,l,r,u;
}a[N*2],d[N*2];
struct BIT {
int c[N];
inline void add(int x,int y){
for(;x<=q+1;x+=x&-x)c[x]+=y;
}
inline int ask(int x){
int s=0;for(;x;x-=x&-x)s+=c[x];
return s;
}
}T;
inline void chg(int l,int r,int v){
T.add(l+1,v),T.add(r+2,-v);
}
inline int ask(int p){
return T.ask(p+1);
}
void init(int x,int p){
fa[x][0]=p,dep[x]=dep[p]+1;
for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
nod[++dfc]=x;
reverse(qu[x].begin(),qu[x].end());
int las=q+1;
for(auto o:qu[x])if(o.second>=0){
a[++num]=thing{0,o.second,o.first,las-1,dfc};
las=o.first;
}
else a[++num]=thing{1,U^(-o.second),o.first,0,dfc};
for(int y:G[x])if(y^p)init(y,x);
}
inline int glca(int u,int v){
if(u==v)return u;
if(dep[u]>dep[v])swap(u,v);
for(int i=17;~i;i--)if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
if(u==v)return u;
for(int i=17;~i;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int main(){
freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
n=read(),q=read();
for(int i=1;i<=n;i++)w[i]=read(),ww[i]=w[i];
for(int i=2,p;i<=n;i++)p=read(),G[p].emplace_back(i);
for(int i=1;i<=n;i++)qu[i].emplace_back(0,w[i]);
for(int i=1,u,v;i<=q;i++){
op[i]=read(),u=read();
if(op[i]==0){
v=read();
ww[u]=v;
qu[u].emplace_back(i,v);
}
else qu[u].emplace_back(i,-ww[u]);
}
init(1,0);
for(int b=29,B=0;~b;b--){
B|=1<<b;
sort(a+1,a+num+1,[&](thing a,thing b){return (a.x&B)==(b.x&B)?a.u==b.u?a.type<b.type:a.u<b.u:(a.x&B)<(b.x&B);});
for(int i=1,j=0;i<=num;i++){
while(j<num&&(a[j+1].x&B)==(a[i].x&B))j++;
int tp=0;
for(int k=i;k<=j;k++){
while(tp&&glca(nod[a[stk[tp]].u],nod[a[k].u])!=nod[a[stk[tp]].u]){
chg(a[stk[tp]].l,a[stk[tp]].r,-1);
tp--;
}
if(!a[k].type)stk[++tp]=k,chg(a[k].l,a[k].r,1);
else ans[a[k].l]|=(!!ask(a[k].l))<<b;
}
while(tp)chg(a[stk[tp]].l,a[stk[tp]].r,-1),tp--;
i=j;
}
for(int i=1;i<=num;i++)if(a[i].type&&!(ans[a[i].l]>>b&1))a[i].x^=1<<b;
}
for(int i=1;i<=q;i++)if(op[i])print(ans[i]),putchar('\n');
return 0;
}
/*
g++ -o tree.exe tree.cpp -O2 -lm -std=c++14 -Wall -Wextra
time ./tree.exe<in>out
Queries turn into "How many dfn\in [l,r] are there in u's subtree on trie" and there is already O(loansg^2)
This is online query
using 2d BIT it is possible to do this in O(log^2),but too slow and memory too large
we can do this through dfs(first offline-ize)
add elements(queries and modifications)relevant to node x when passing node x and erase on departure
with timl, timr
so we can change the segment tree of all its ancestors on trie by range [timl,timr]
complexity: O(nlognlogV)
bravo! is this correct? I bet it is.
Oh no! Memory limit 128M! You must be kidding!
Specificity:we are only querying w[x], instead of an arbitrary number.
Therefore, w[y] can predict w[x]
*/
B. calc on lowbit
定义 \(F(x)\) 为通过每次等概率将 \(x\) 加上或减去 \(\operatorname{lowbit}(x)\) 来将 \(x\) 变为 \(0\) 的期望步数。
求 \(\sum_{i=L}^R F(i)\)。
\(1\le L\le R< 2^60\)
第一个观察是 \(x\) 形如 \(2^k\) 时 \(F(x)=2\)，但是它用处不大。
考虑如何按位 DP 计算 \(F(x)\)（因为用 map 记忆化算对正解没什么启发）。
观察到每次改变的位是最低的一些位，而改变之后会有一个更长的后缀变成全 0。变成了 0 的就不会再被操作了。于是这种侵略的顺序就提示我们进行按位 DP。
设 \(f(i,j)\) 表示 \(x[0..i-1]\) 都已变成 0，并且对 \(i\) 产生了 \(j\in \{0,1\}\) 的进位，期望步数；同理定义辅助 dp 数组 \(g(i,j)\) 为概率。
由于对于不同 \(x\)，计算过程是雷同的，因此我们就可以修改 \(f,g\) 的含义，统一地 dp。
首先把 \([L,R]\) 差分为 \([0,R]-[0,L)\)，接下来要用数位 dp 解决 \(\le R\) 的 \(\sum F(x)\)。
由于是从低位到高位，套路地设 \(f(i,j,b)\) 为当前到了第 \(i\) 位，把 \(x[0..i-1]\) 都变成 0，并且第 \(i-1\) 位进了 \(j\in \{0,1\}\) 到 \(i\) 来，对于所有 \(x[0..i-1]\le R[0..i-1](b==0)/>R[0..i-1](b==1)\) 的期望步数之和。同理定义辅助 dp 数组 \(g(i,j,b)\) 为概率。
转移枚举 \(k\) 为 \(x[i]\)：
- 若 \(j+k=0\)，\(f(i+1,0,b')\gets f(i,j,b),g(i+1,0,b')\gets g(i,j,b)\)
- 若 \(j+k=1\)，\(f(i+1,1,b')\gets {f(i,j,b)+g(i,j,b)\over 2},g(i+1,1,b')\gets {g(i,j,b)\over 2}\)，\(f(i+1,0,b')\gets {f(i,j,b)+g(i,j,b)\over 2},g(i+1,0,b')\gets {g(i,j,b)\over 2}\)
- 若 \(j+k=2\)，\(f(i+1,1,b')\gets f(i,j,b),g(i+1,1,b')\gets g(i,j,b)\)
点击查看代码
// ubsan: undefined
// accoders
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long ll;
// namespace IO {
// const int buflen=1<<21;
// int x;
// bool f;
// char ch,buf[buflen],*p1=buf,*p2=buf;
// inline char gc(){return p1==p2&&(p2=buf+fread(p1=buf,1,buflen,stdin),p1==p2)?EOF:*p1++;}
// inline int read(){
// x=0,f=1,ch=gc();
// while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
// while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
// return f?x:-x;
// }
// }
// using IO::read;
// const int mod=998244353,I2=(mod+1)/2;
// map<ll,int>mp;
// inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
// inline int calc(ll x){
// if(x==(x&-x))return 2;
// if(mp.count(x))return mp[x];//cerr<<x<<';';
// return mp[x]=(ll)I2*(calc(x^(x&-x))+calc(x+(x&-x))+2)%mod;
// }
// int main(){
// freopen("calc.in","r",stdin);freopen("calc.out","w",stdout);
// int T;
// cin>>T;
// while(T--){
// ll L,R;
// cin>>L>>R;
// int ans=0;
// for(ll i=L;i<=R;i++)add(ans,calc(i));
// cout<<ans<<'\n';
// }
// return 0;
// }
// /*
// g++ -o calc.exe calc.cpp -O2 -lm -std=c++14 -Wall -Wextra
// ./calc.exe<in
// */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353,I2=(mod+1)/2;
int f[66][2][2],g[66][2][2];
inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
int calc(ll lim){
memset(f,0,sizeof f),memset(g,0,sizeof g);
f[0][0][0]=0,g[0][0][0]=1;
for(int i=0;i<60;i++)for(int j=0;j<=1;j++)for(int b=0;b<=1;b++){
for(int k=0;k<=1;k++){
int _b=(k>(lim>>i&1)?1:k==(lim>>i&1)?b:0);
if(j+k==0)add(f[i+1][0][_b],f[i][j][b]),add(g[i+1][0][_b],g[i][j][b]);
if(j+k==1){
add(f[i+1][1][_b],((ll)I2*(f[i][j][b]+g[i][j][b]))%mod);
add(g[i+1][1][_b],(ll)g[i][j][b]*I2%mod);
add(f[i+1][0][_b],((ll)I2*(f[i][j][b]+g[i][j][b]))%mod);//if(i==0&&!_b)cerr<<((ll)I2*(f[i][j][b]+g[i][j][b]))%mod<<':';
add(g[i+1][0][_b],(ll)I2*g[i][j][b]%mod);
}
if(j+k==2)add(f[i+1][1][_b],f[i][j][b]),add(g[i+1][1][_b],g[i][j][b]);
}
}
//cerr<<f[1][0][0]<<';';
return (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;
cin>>T;
while(T--){
ll L,R;
cin>>L>>R;
cout<<(calc(R)-calc(L-1)+mod)%mod<<'\n';
}
}
/*
g++ -o calc.exe calc.cpp -O2 -lm -std=c++14 -Wall -Wextra
./calc.exe<in
let f[i][j][b] denote the sum of expected steps to make x[0...i-1] zero over all x from 0 to (1<<i)-1
and that's <=(b=0)/>(b=1) lim, and carries j(0/1) to the i-th bit
let g[i][j][b] denote the sum of possibilities
f[0][0][0]=0,g[0][0][0]=1
enumerate k:
j+k==0: f[i+1][0]+=f[i][j] g[i+1][0]+=g[i][j]
j+k==1: f[i+1][1]+=f[i][j]/2+g[i][j] g[i+1][1]+=g[i][j]/2 f[i+1][0]+=f[i][j]/2+g[i][j] g[i+1][0]+=g[i][j]/2
j+k==2: f[i+1][1]+=f[i][j] g[i+1][1]+=g[i][j]
b' is very easy to transit from b.
Overall complexity: O(TlogV)
*/
C. color on board
有一个 \(n\times m\) 的方格，一开始所有格子都是白色的，你的最终目的是把方格涂成你想要的颜色——二维 01 数组 \(s\)。
你有三种刷的方法：
- 横着刷连续的 \(k\) 格，代价是 \(ak+b\)；
- 竖着刷连续的 \(k\) 格，代价是 \(ak+b\)；
- 只刷某个格子，代价是 \(c\)。
每个格子的颜色是最后刷它的那个刷子的颜色，但是有以下几个限制：
- 每个格子最多只能被刷两次，无论这些刷子是否同色；
- 每个格子不能先刷白色刷子再刷黑色刷子，因为白色染料比较特殊，这会导致格子变成灰色，但是你可以先刷黑色刷子再刷白色刷子，也可以在一开始格子是初始颜色白色时刷黑色刷子。
现在你需要求出，刷出指定颜色的最小代价。
\(1\le n,m,\le 40,0\le a,b,c\le 40\)
经过一番尝试不难发现这题是道网络流题。
因此考虑拆贡献。
【套路】最小割可以用来计算一个由若干 01 变量 \(x1..n\) 构成的表达式的最小值。
A*(1-xi)*xj can be translated into an edge from i to j of capacity A
A*xi can be translated into an edge from S to i of capacity A
A*(1-xi) can be translated into an edge from i to T of capacity A
(explanation: take A*xi as example, if xi decides to be 0, then it means (S,xi) isn't cut, contribute 0; otherwise cut)
set 4 0/1 variant for each cell: bh[x][y] wv[x][y] _bv[x][y] and _wh[x][y] (bh=brushed black horizontally; _bv=1-[brushed black vertically])
for each (x,y), consider its contribution as each of the roles among the following:
1. one of the cells when black-brushing l->r on the x-th row: a*bh[x][y]
2. one of the cells when white-brushing l->r on the x-th row: a*(1-_wh[x][y])
3. one of the cells when black-brushing l->r on the y-th column: a*(1-_bv[x][y])
4. one of the cells when white-brushing l->r on the y-th column: a*wv[x][y]
5. cell y when black-brushing y->some r on the x-th row: b*(1-bh[x][y-1])*bh[x][y] (when y-1==0,bh[x][y-1] is a constant)
6. cell y when white-brushing y->some r on the x-th row: b*_wh[x][y-1]*(1-_wh[x][y]) (same as above)
7. cell x when black-brushing x->some r on the y-th row: b*_bv[x-1][y]*(1-_bv[x][y])
8. cell x when white-brushing x->some r on the y-th row: b*(1-wv[x-1][y])*wv[x][y])
9. individual brushing of a cell which should eventually be black: c*(1-bh[x][y])*_bv[x][y]+inf*wv[x][y]+inf*(1-_wh[x][y])
10. individual brushing of a cell which should eventually be white: c*bh[x][y]*(1-wv[x][y])+c*(1-_bv[x][y])*_wh[x][y]+inf*bh[x][y]*(1-_bv[x][y])
这就是本题拆贡献的方法。
总的来说，这种题就是要：
1. 说出题目中的个体所涉及到的一堆 01 变量，找到其中决定性的那些。
2. 然后写出它们对答案贡献的表达式。
3. 最后通过网络流决定它们最优的取值组合。
const int N=45,V=12805,E=40*40*11+5;
int n,m,S,T,a,b,c,idx,tot=1,we[E*2],bh[N][N],wv[N][N],_wh[N][N],_bv[N][N];
char s[N][N];
vector<pair<int,int> >G[V];
int dis[V];
queue<int>Q;
inline void adde(int u,int v,int w){
//v+=idx;
G[u].emplace_back(v,++tot),we[tot]=w;
G[v].emplace_back(u,++tot),we[tot]=0;
}
bool bfs(){
memset(dis,-1,sizeof dis);
dis[S]=0;
Q.push(S);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(auto e:G[x]){
int y=e.first,z=e.second;
if(we[z]&&dis[y]==-1){
dis[y]=dis[x]+1;
Q.push(y);
}
}
}
return dis[T]!=-1;
}
int dfs(int x,int in){
if(x==T)return in;
int out=0;
for(auto e:G[x]){
if(!in)break;
int y=e.first,z=e.second;
if(we[z]&&dis[y]==dis[x]+1){
int los=dfs(y,min(in,we[z]));
in-=los,out+=los,we[z]-=los,we[z^1]+=los;
}
}
if(!out)dis[x]=-1;
return out;
}
int main(){
freopen("color.in","r",stdin);freopen("color.out","w",stdout);
int tc;
scanf("%d",&tc);
while(tc--){
for(int i=1;i<=idx;i++)G[i].clear();
idx=0,tot=1;
scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
bh[i][j]=++idx;
wv[i][j]=++idx;
_bv[i][j]=++idx;
_wh[i][j]=++idx;
}
S=++idx,T=++idx;
for(int x=1;x<=n;x++)for(int y=1;y<=m;y++){
adde(S,bh[x][y],a);
adde(_wh[x][y],T,a);
adde(_bv[x][y],T,a);
adde(S,wv[x][y],a);
if(y>1)adde(bh[x][y-1],bh[x][y],b);else adde(S,bh[x][y],b);
if(y>1)adde(_wh[x][y],_wh[x][y-1],b);else adde(_wh[x][y],T,b);
if(x>1)adde(_bv[x][y],_bv[x-1][y],b);else adde(_bv[x][y],T,b);
if(x>1)adde(wv[x-1][y],wv[x][y],b);else adde(S,wv[x][y],b);
if(s[x][y]=='#')adde(bh[x][y],_bv[x][y],c),adde(S,wv[x][y],1e9),adde(_wh[x][y],T,1e9);
else adde(wv[x][y],bh[x][y],c),adde(_bv[x][y],_wh[x][y],c),adde(_bv[x][y],bh[x][y],1e9);
}
int flow=0;
while(bfs())flow+=dfs(S,1e9);
cout<<flow<<'\n';
}
return 0;
}