【考试总结】2022-03-25
异或矩阵
使用 库默尔定理 发现,如果 \(y-x\subseteq k-1\) 那么 \((1,y)\) 将向 \((k,x)\) 造成贡献
考虑当 \(k=2^x\) 时转移只有两个地方是子集，那么分 \(\log\) 步迭代完成转移即可
Code Display
const int N=3e6+10;
unsigned int a[N],f[N];
int n,k;
signed main(){
freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout);
n=read(); k=read(); a[1]=read();
for(int i=2;i<=n;++i) a[i]=1145141*a[i-1]+(ui)1919*i+810;
for(int i=0;i<23;++i) if((k-1)>>i&1){
for(int j=1;j+(1< 树
点集 \(\rm LCA\) 是子树的根等价于从不少于 \(2\) 个子树里面选点或者选择它本身
使用容斥原理即可
感觉 xzh 同学这种明显的恶意不取模行为是十分强大的
Code Display
const int N=1e5+10;
int siz[N],ans[N],n;
vector G[N];
inline void dfs(int x,int fat){
siz[x]=1; ans[x]=mod-1;
for(auto t:G[x]) if(t!=fat){
dfs(t,x); siz[x]+=siz[t];
ckdel(ans[x],del(ksm(2,siz[t]),1));
}
ckadd(ans[x],ksm(2,siz[x]));
}
signed main(){
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=read();
for(int i=1;i 黑白树
考虑线段树历史有条件最值的一种计算方式：在 push_down 时如果满足条件再转移到两个子区间里面，push_up 时如果子区间和母区间的条件一致再进行信息的维护
那么本题中的 “条件” 就是两个点处在同色联通块中，而判定条件就是 两个点颜色相同 并且 根链上的异色点数量 相同
将每个同色联通块的信息都挂到联通块中深度最小的点上面，求得这个点具体是谁可以使用 重链剖分 配合 std::set 来实现找到根链上第一个异色点再跳儿子即可
将线段树上某个区间管辖点视作其所有点的 \(\rm LCA\)，维护如下信息：
-
cnt[0/1]表示两个颜色点数 -
Mx[0/1]表示两种颜色联通块中的最值 -
cnt_tag[0/1],col_tag[0/1],tag分别表示三种懒标记：点数修改，同色权值加，子树/链 加
在进行区间修改的时候先查询联通块最浅点的 cnt 信息，再对其进行子树加即可，注意 \(\rm DFS\) 序区间上不满足 cnt 值相同的区间不能放懒标记
实现的时候注意维护当前信息需要的是哪种颜色以及 push_down 时信息下放的顺序：异色点数要在同色联通块加之前来保证正确性
Code Display
const int N=2e5+10,inf=0x3f3f3f3f3f3f3f3f;
int dfn[N],ord[N],top[N],son[N],siz[N],dep[N],fa[N],tim;
vector G[N];
int n,Q,col[N];
inline void dfs1(int x,int fat){
dep[x]=dep[fa[x]=fat]+(siz[x]=1);
for(auto t:G[x]) if(t!=fat){
dfs1(t,x); siz[x]+=siz[t];
if(siz[son[x]]>1; push_down(p);
if(pos<=mid) return query_cnt(pos,c,lson);
else return query_cnt(pos,c,rson);
} // 查询一个点根链上异色点个数
inline int query_max(int st,int ed,int c,int num,int p=1,int l=1,int r=n){
if(cnt[p][c^1]>num) return -inf;
if(st<=l&&r<=ed) return Mx[p][c];
int mid=(l+r)>>1,res=0; push_down(p);
if(st<=mid) ckmax(res,query_max(st,ed,c,num,lson));
if(ed>mid) ckmax(res,query_max(st,ed,c,num,rson));
return res;
} // 查询同一个联通块的最大值
inline void cnt_add(int st,int ed,int c,int v,int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return push_cnt(p,c,v);
int mid=(l+r)>>1; push_down(p);
if(st<=mid) cnt_add(st,ed,c,v,lson);
if(ed>mid) cnt_add(st,ed,c,v,rson);
return push_up(p);
} // 更改异色点个数
inline void give_add(int st,int ed,int v,int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return push_add(p,v);
int mid=(l+r)>>1; push_down(p);
if(st<=mid) give_add(st,ed,v,lson);
if(ed>mid) give_add(st,ed,v,rson);
return push_up(p);
} // 链加，子树加
inline void col_add(int st,int ed,int c,int num,int v,int p=1,int l=1,int r=n){
if(cnt[p][c^1]>num) return ;
if(st<=l&&r<=ed) return push_col(p,c,v);
int mid=(l+r)>>1; push_down(p);
if(st<=mid) col_add(st,ed,c,num,v,lson);
if(ed>mid) col_add(st,ed,c,num,v,rson);
return push_up(p);
} // 联通块加
inline void change_col(int pos,int p=1,int l=1,int r=n){
if(l==r) return swap(Mx[p][0],Mx[p][1]);
int mid=(l+r)>>1; push_down(p);
if(pos<=mid) change_col(pos,lson);
else change_col(pos,rson);
return push_up(p);
}
}T;
set > st[2][N];
inline int find(int x){
int c=col[x]^1,ans=x;
for(;x;x=fa[top[x]]){
auto t=st[c][top[x]].upper_bound(make_pair(dep[x],inf));
if(t!=st[c][top[x]].begin()){
--t;
if(t->sec==x) return ans;
else return son[t->sec];
}else ans=top[x];
} return ans;
}
signed main(){
freopen("astill.in","r",stdin); freopen("astill.out","w",stdout);
n=read(); Q=read();
for(int i=1;idep[y]) swap(x,y);
T.give_add(dfn[x],dfn[y],v);
}else if(opt==5){
int x=read(),v=read();
T.give_add(dfn[x],dfn[x]+siz[x]-1,v);
}
}
return 0;
}