【杂题选讲】2023下半年合集

trsins · 2023-07-03 21:52:32 · 个人记录

陽だまりの小部屋。

回忆。

很深沉的单词啊，，。

时间不多了。

• 给出一个 1\sim n 的排列 a，同时有 n 个点构成的无向图，点的编号从 1 到 n。如果排列 a 同时满足 a_i>a_j 且 i<j，那么图中有一条连接点 i 和点 j 的边。 如果按照以上规则生成的图是二分图，则称该排列为二分图排列。现在你可以选择任意数量（可以为 0）的 i，将 a_i 改为 -a_i。 请问能否通过这种操作将排列变为二分图排列？如果能，输出操作后的二分图排列中，字典序最小的一个。n \leq 10^6。

二分图没奇环，所以排列中没有长度为 3 的下降子序列。我们对于所有满足 a_i>a_j,i<j 的 j 拎出来，那么这些 j 构成的子序列显然是单调上升的（否则就存在 a_{i_1}>a_{j_1}>a_{j_2}），对于剩下的也是形成了一个单调上升子序列。这个和题目要求显然是充要的。

那么 dp_{i,0/1} 表示其中一个子序列（哪个不重要）当前以 i 结尾且 a_i 符号为负/正，另外一个子序列末项的最大值。然后转移便枚举 dp_{i-1} 在哪个子序列中，以及是否取反，共 4 中情况。

对于输出我们发现题目要求字典序最小，那我们 dp 白做了重新改为从后往前dp，当前到 i，另一个子序列首项的最大值。转移同理。那么对于方案直接从前往后看能不能放负数，能放就放，注意时刻保证子序列的单调上升。O(n)。

dp=-inf;
dp[n][0]=dp[n][1]=inf;
for(int i=n-1;i;i--){
    for(int j=0;j<2;j++){
        for(int k=0;k<2;k++){
            int x=a[i]*(j?1:-1),y=a[i+1]*(k?1:-1);
            if(x<y)dp[i][j]=max(dp[i][j],dp[i+1][k]);//同个子序列 
            if(x<dp[i+1][k])dp[i][j]=max(dp[i][j],y);//不同子序列 
        }
    }
    if(dp[i][0]==-inf&&dp[i][1]==-inf)NO;
}
YES;
A=B=-inf;//维护两个子序列当前的末项 
for(int i=1;i<=n;i++){
    if(-a[i]>A&&dp[i][0]>B)A=-a[i],out(-a[i]);
    else if(-a[i]>B&&dp[i][1]>A)B-=a[i],out(-a[i]);
    else{
        if(a[i]>A)A=a[i];else B=a[i];
        out(a[i]);
    }
    if(A<B)swap(A,B);
}

2023.7.4 白鸟。

• 有 n 个开区间并保证它们都包含某个整点 x。求最少的移动次数使所有区间不交。一次移动定义为将区间整体左移/右移。n\le 5\times 10^3。

必定存在一个区间其不动，情况必定不劣。我们定义该区间为不动点。剩余的区间相当于要么移到不动点左边要么右边。

考虑总代价：

其中 o 表示不动点，而 p,q 表示左边的区间从左到右、右边的区间从右到左。那么显然是区间长度越小的越靠近 o。

设 dp_{i,j} 表示前 i 个区间中有 j 个区间放在左边的最小代价。可以枚举不动点然后 O(n^3) dp。

考虑 |P| 与 |Q| 的关系。考虑操作完后 o 移动，其每向左移动一次产生的代价为 |Q|+1-|P|。那么若 |P|\neq |Q|，则 o 必定会移动，与假设存在一个区间不动矛盾。故左右两边区间个数应是相同的。此时 o 的贡献便是 \frac{n-1}2\times len_o。

所以在 dp 上增加一维 0/1 表示是否加入了不动点（即是否计算其贡献）。

对于 n 是偶数的情况加入区间 (0,0)，在计算 o 的贡献时记得减去 l_o，也就是 (0,0) 会走到 l_o 的贡献。

更好的理解请看：https://www.luogu.com.cn/blog/310801/cf1749f-distance-to-the-path-ti-xie

考虑如果不是到一条路径的距离而是到一个点怎么做。

发现 k 很小。于是一个自然且朴素的想法就是做一个 f_{u,k} 维护 u 子树内距离点 u\le k 的所有点要加上多少，对于查询便暴力往上跳至多 20 次，加上他们对应到点 u 的 f。发现这样对于 u 的祖先的情况不好处理，考虑容斥的思想，改为距离正好是 k 的所有点。对于距离 u\le k 的且在子树外的点考虑用祖先去覆盖。

那么先处理 f_{u,k}，对于 f_{fa_u} 会发现如果是 f_{fa_u,k}，能够覆盖到 u 的 k-1 层儿子，这是好的；但是子树外会存在点 v 使 dis_{u,v}=k+1>k，但 v 却被打上标记。而对于 f_{fa_u,k-1} 能够避免外部点到 u 距离大于 k 的情况，却难以覆盖 u 的 k-1 层儿子。

自然会想到容斥。但是容斥好烦。不要容斥。考虑“算2次，跳1次”的方法：处理 f_{u,k},f_{u,k-1}，然后是 f_{fa_u,k-1},f_{fa_u,k-2}\dots，容易发现这样能够完美覆盖全部距离 u\le k 的节点。往上最多跳 k 次，跳到 rt 时记得将剩下的 f 全部处理。

回归本题在路径上的情况：某个点到达路径的最终点必然要么是从下往上，要么从上往下。前者可以在 u\to v 路径上任何一个节点 p 的子树中出现，后者必然是 lca(u,v) 的祖先的情况。

考虑一样的做法，先树链剖分，对于每个 k 建一棵线段树，修改操作时先修改 u\to v 上所有点的 f_{node,k}，然后找到 lca 后往上执行“算2次，跳1次”的操作，复杂度为 O(q\log^2n+dq\log n)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls p<<1
#define rs p<<1|1

const int N=2e5+6;

int n,Q,tot,head[N],dep[N],sz[N],son[N],top[N],idx,dfn[N],rev[N],tr[N<<2][22],tag[N<<2][22],fa[N];

struct edge{
    int to,nxt;
}e[N<<1];

inline void addedge(int u,int v){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
    return;
}

inline void dfs1(int u,int faa){
    fa[u]=faa,sz[u]=1,dep[u]=dep[faa]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==faa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
    return;
}

inline void dfs2(int u,int tp){
    top[u]=tp,dfn[u]=++idx,rev[idx]=u;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
    return;
}

inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

inline void pushup(int p,int k){
    tr[p][k]=tr[ls][k]+tr[rs][k];
    return;
}

inline void pushdown(int p,int l,int r,int k){
    if(!tag[p][k])return;
    int mid=(l+r)>>1;
    tr[ls][k]+=tag[p][k]*(mid-l+1),tr[rs][k]+=tag[p][k]*(r-mid);
    tag[ls][k]+=tag[p][k],tag[rs][k]+=tag[p][k],tag[p][k]=0;
    return;
}

inline void update(int p,int l,int r,int s,int t,int k,int val){
    if(s<=l&&r<=t){
        tr[p][k]+=val*(r-l+1),tag[p][k]+=val;
        return;
    }
    pushdown(p,l,r,k);
    int mid=(l+r)>>1;
    if(s<=mid)update(ls,l,mid,s,t,k,val);
    if(t>mid)update(rs,mid+1,r,s,t,k,val);
    pushup(p,k);
    return;
}

inline int query(int p,int l,int r,int ps,int k){
    if(l==r)return tr[p][k];
    int mid=(l+r)>>1;
    pushdown(p,l,r,k);
    if(ps<=mid)return query(ls,l,mid,ps,k);
    else return query(rs,mid+1,r,ps,k);
}

inline void upd(int u,int v,int k,int val){
    if(k<0)return;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,1,n,dfn[top[u]],dfn[u],k,val);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    update(1,1,n,dfn[v],dfn[u],k,val);
    return;
}

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    scanf("%lld",&Q);
    while(Q--){
        int op,u,v,k,val,ans=0,o;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld",&u);
            for(int i=0;i<=20;i++){
                ans+=query(1,1,n,dfn[u],i);
                u=fa[u];
                if(!u)break;
            }
            printf("%lld\n",ans);
        }
        else{
            scanf("%lld%lld%lld%lld",&u,&v,&val,&k),o=lca(u,v);
            upd(u,v,k,val),upd(o,o,k-1,val);
            for(int i=k-1;i>=0;i--){
                if(o==1){
                    for(int j=i-1;j>=0;j--)upd(o,o,j,val);
                    break;
                }
                else o=fa[o],upd(o,o,i,val),upd(o,o,i-1,val);
            }
        }
    }
    return 0;
}

• 2020 ICPC Asia Shenyang Regional,J - Descent of Dragons

• 有一个长度为 n 的初始全部为 0 的序列 a，Q 次操作，每次操作分为：1. l,r,x 表示 \forall l\le i\le r,a_i+=[a_i=x]；2. l,r 表示询问区间 a_i 的max。n,Q\le 5\times 10^5。

对于每个 a_i=x 建立一棵线段树，那么修改操作相当于将第 x 棵树上的 [l,r] 区间删除后粘贴到第 x+1 棵树上。查询时 [l,r] 会在很多棵树上出现，时间复杂度就寄了。不会做啊！怎么办！

改为对于 a_i\ge x 建立线段树。那么每次修改只需要将 [l,r] 复制到第 x+1 棵树。那么 [l,r] 会转为出现在一段前缀上。我会二分！O(n\log^2n)。

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+6;
const int M=1e7+8;

int n,m,Q,tr[M],ls[M],rs[M],rt[N],idx;

inline void pushup(int p){
    tr[p]=tr[ls[p]]+tr[rs[p]];
    return;
}

inline void build(int&p,int l,int r){
    if(!p)p=++idx;
    if(l==r){
        tr[p]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls[p],l,mid),build(rs[p],mid+1,r);
    pushup(p);
    return;
}

inline void copy(int&p,int q,int l,int r,int s,int t){
    if(!q)return;
    if(s<=l&&r<=t){
        p=q;
        return;
    }
    else idx++;
    int mid=(l+r)>>1;
    ls[idx]=ls[p],rs[idx]=rs[p],tr[idx]=tr[p],p=idx;
    if(s<=mid)copy(ls[p],ls[q],l,mid,s,t);
    if(t>mid)copy(rs[p],rs[q],mid+1,r,s,t);
    pushup(p);
    return;
}

inline int query(int p,int l,int r,int s,int t){
    if(s<=l&&r<=t)return tr[p];
    int mid=(l+r)>>1,res=0;
    if(s<=mid)res+=query(ls[p],l,mid,s,t);
    if(t>mid)res+=query(rs[p],mid+1,r,s,t);
    return res;
}

int main(){
    scanf("%d%d",&n,&Q);
    build(rt[0],1,n);
    for(int i=1;i<=Q;i++){
        int op,l,r,x=0;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            scanf("%d",&x);
            copy(rt[x+1],rt[x],1,n,l,r);
        }
        else{
            int L=0,R=i;
            while(L<=R){
                int mid=(L+R)>>1;
                if(query(rt[mid],1,n,l,r))L=mid+1,x=mid;
                else R=mid-1;
            }
            printf("%d\n",x);
        }
    }
    return 0;
}

• [ABC221H] Count Multiset

• 求多少个大小为 k，集合数之和为 n，且一个数出现次数 \le m 的所有集合。n,m\le 5\times 10^3。

没有脑子选手会转化为一个长度为 k 的不降序列，和为 k，不出现连续 m 个相同的数。

一种常规的做法是差分来去除“不降”这个限制，令 b_i=a_i-a_{i-1}，有 \sum b_i(k-i+1)=n，由于 b 之间没有位置顺序限制所以 reverse 一下，变为 \sum ib_i=n。设 f_{i,j} 表示当前在 b_i，和为 j。

其中 p 为枚举上一个不同的数的位置，B 即枚举 b_i。B 是调和级数，可以前缀和优化至 O(n^2\ln n)。

没脑子选手不会 dp 怎么办？发现题目去掉 m 的限制就是分拆数。而对于 m 的限制相当于数列前 m+1 项都是 1，方案数也就是 p_{i-j,j-(m+1)}。所以和分拆数一样 dp 就完事了。O(n^2)。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e3+4;
const int mod=998244353;

int n,m,dp[N][N],sdp[N][N];

signed main(){
    scanf("%d%d",&n,&m);
    dp[0][0]=sdp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=i;k<=j;k+=i){
                dp[i][j]=(dp[i][j]+sdp[i-1][j-k])%mod;
                if(i>m)dp[i][j]=(dp[i][j]-sdp[i-m-1][j-k]+mod)%mod;
            }
            sdp[i][j]=(sdp[i-1][j]+dp[i][j])%mod;
        }
        sdp[i][0]=1;
    }
    for(int i=1;i<=n;i++)printf("%d\n",dp[i][n]);
    return 0;
}

• CF1842G Tenzing and Random Operations

• 有一个长度为 n 的序列 a，定义其权值为所有元素的乘积。有 m 次操作，每次等概率选择一个 i 然后将序列 a 的 [i,n] 这个后缀全部加 v。求最后序列 a 权值的期望。n\le 5000,m,v\le 10^9。

boring。将 m 次操作与长度为 n 的序列合起来变为 (m+1)\times n 的矩阵 M，其中 M_{i,j} 表示第 i 次操作选择了第 j 个位置加上 v。每一行都是形如一段前缀 0 以后接着一段后缀 v。总期望就是 \prod \sum M_{i,j}，也就是每一列的和的乘积。那这玩意相当于一个 (t_1+t_2+...)(t'_1+t'_2+...)(t''_1+t''_2+...)... 的一个东西，直接拆贡献就是第 i 个位置在每次操作时选择 0/v/a_i。选择 0 贡献就没了就不管，也就是每次要么选 v 要么就是 a_i。

设 f_{i,j} 表示 [1,i] 选择好了且被这些元素选择的行共 j 行。转移枚举 i+1 的决策：

1. 选择 a_{i+1}：f_{i,j}\times a_{i+1}\to f_{i+1,j}
2. 选择之前选过的 j 行中的 v：f_{i,j}\times jv\to f_{i+1,j}
3. 选择不在 j 行中的 v：f_{i,j}\times (m-j)v\to f_{i+1,j+1}

总期望即为 \dfrac{\sum f_{n,j}n^{m-j}}{n^m}。O(n^2)。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=1e9+7;
const int N=5e3+4;

int n,m,v,ans,dp[N][N],a[N];

inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

signed main(){
    scanf("%lld%lld%lld",&n,&m,&v),dp[0][0]=1;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        for(int j=0;j<=min(n,m);j++){
            dp[i][j]=(dp[i][j]+dp[i-1][j]*(a[i]+j*v%mod)%mod)%mod;
            dp[i][j+1]=(dp[i][j+1]+dp[i-1][j]*(m-j)%mod*i%mod*v%mod)%mod;
        }
    }
    for(int i=0;i<=min(n,m);i++)ans=(ans+dp[n][i]*qpow(n,m-i)%mod)%mod;
    printf("%lld",ans*qpow(qpow(n,m),mod-2)%mod);
    return 0;
}

• [AGC058D] Yet Another ABC String

• 求有多少长度为 a + b + c 的只包含 ABC 三个字母的字符，满足恰好有 a 个 A，b 个 B，c 个 C，且不包含形如 ABC，BCA，CAB 的连续子串。a,b,c\le 10^6。

挺nb的。若 [i,i+2],[i+2,i+4] 不合法，那么 [i+1,i+3] 也不合法。看起来很蠢对吧，但是就是这么蠢，容斥有 s 个段 [i,i+2] 不合法，那么 [i+1,i+3] 必须合法。做完了！O(n)。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=998244353;
const int N=3e6+7;

int n,k,A,B,C,fac[N],ifac[N],pw[N],ans;

inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline void init(int n){
    fac[0]=ifac[0]=pw[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,pw[i]=pw[i-1]*2%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    return;
} 

inline int c(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

signed main(){
    scanf("%lld%lld%lld",&A,&B,&C),n=A+B+C,k=min(A,min(B,C));
    init(n),ans=c(n,A)*c(n-A,B)%mod;
    for(int i=1;i<=k;i++){
        int m=n-3*i,t=c(m,A-i)*c(m-(A-i),B-i)%mod;
        if(i&1)ans=(ans-(t*c(m+i,i)%mod*pw[i]%mod+t*c(m+i-1,i-1)%mod*pw[i-1]%mod)%mod+mod)%mod;
        else ans=(ans+(t*c(m+i,i)%mod*pw[i]%mod+t*c(m+i-1,i-1)%mod*pw[i-1]%mod)%mod)%mod;
    }
    printf("%lld",ans);
    return 0;
}

• loj6077 「2017 山东一轮集训 Day7」逆序对

• 求有多少长度为 n 的排列使其逆序对对数为 k。n,k\le 10^5。

pbyyds。

相信大家都会 O(n^2)。我们发现从小到大插入 i 时产生新的逆序对个数 x_i\in[0,i-1] 且每种情况唯一。那么题目就是求 \sum x_i=k 的方案数了，其中 x_i\in[0,i-1]。

相信大家都会容斥。将其转化为

其中 S 为钦定的不满足条件的 i 的集合，那么对于 i\in S 有 x_i\ge i,x_i-i\ge0。而不属于 S 的限制为 x_i\ge 0。定义 \forall i\in S ,y_i=x_i-i，那么属于 S 的 y_i 和不属于 S 的 x_i 共同限制都是 \ge 0。

所以 R(j) 含义即为 (\sum_{i=1}^nz_i)=j 的方案数，其中 z_i\ge0。那么这个大家都会插板法，所以问题转化为如何快速求出 \sum_{i\in S}i。

考虑设计dp：f_{i.j} 表示从 1\sim n 中选择 i 和不同的数且和为 j 的方案数。

不妨令此时我们选择了 a_1<a_2<\dots <a_i，那么令 x 轴为下标、y 轴为 a_I 的值，那么 j 即为一个形如从左下至右上增长的一个阶梯形的面积。

考虑转移。为了使转移不重不漏，我们钦定只能向下/左转移。我们可以给 a 集体加一，那么相当于在阶梯下方垫高一层，转移为 f_{i,j}\to f_{i,j+i}。此时显然 a 仍满足两两不同。

考虑对于 i 这维的转移。在垫高一层后考虑在最左侧增加一个高度为 1 的列，此时便形如 1,a_1,a_2,\dots, a_i，仍满足两两不同。转移为 f_{i,j}\to f_{i+1,j+i+1}。

注意到最右侧的一列高度可能会大于 n，那么减去这一列即为不合法的方案，是 f_{i-1,j-n-1}。

注意 j 范围 \le k，而 j 为阶梯面积，故 i 范围是 O(\sqrt k) 的。总时间复杂度 O(k\sqrt k)。

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+6;
const int M=470;
const int mod=1e9+7;

int n,k,dp[M][N],fac[N<<1],ifac[N<<1],ans;

inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline void init(int n){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
    return;
}

inline int C(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

signed main(){
    scanf("%lld%lld",&n,&k),init(N*2-1);
    dp[0][0]=1;
    for(int i=1;i<=453;i++)for(int j=1;j<=k;j++){
        if(j>=i)dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%mod;
        if(j>n)dp[i][j]=(dp[i][j]-dp[i-1][j-n-1]+mod)%mod;
    }
    for(int i=0;i<=453;i++)for(int j=0;j<=k;j++)ans=(ans+(i&1?mod-1:1)*dp[i][j]%mod*C(k-j+n-1,n-1)%mod)%mod;
    printf("%lld",ans);
    return 0;
}

• gaze

• 给定序列 a，支持单点修改，查询给定 x 求所有值 \ge x 的位置形成的连通块个数。n\le 2\times 10^5。

连通块个数=分界点/2。定义分界点为 a,b 之间表示 a\ge x,b<x 或反之。

使用树状数组维护分界点个数，对于 a\ge x 时加一，b>x 时减一。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+6;

int n,m,lsh[N<<1],a[N],tot,tr[N<<2];
struct node{int op,x,y;}q[N];

inline int lowbit(int x){return x&-x;}
inline void add(int x,int val){while(x<=tot)tr[x]+=val,x+=lowbit(x);}
inline int qry(int x){int res=0;while(x)res+=tr[x],x-=lowbit(x);return res;}

inline void upd(int x,int op){
    int l=a[x-1],r=a[x];
    if(l>r)swap(l,r);l++;
    add(l,op),add(r+1,-op);
    return;
}

int main(){
    scanf("%d%d",&n,&m),lsh[++tot]=0;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),lsh[++tot]=a[i];
    for(int i=1;i<=m;i++){
        scanf("%d",&q[i].op);
        if(q[i].op==1)scanf("%d",&q[i].x),lsh[++tot]=q[i].x;
        else scanf("%d%d",&q[i].x,&q[i].y),lsh[++tot]=q[i].y;
    }
    sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
    for(int i=0;i<=n+1;i++)a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
    for(int i=1;i<=n+1;i++)upd(i,1);
    for(int i=1;i<=m;i++){
        if(q[i].op==1){
            q[i].x=lower_bound(lsh+1,lsh+tot+1,q[i].x)-lsh;
            printf("%d\n",qry(q[i].x)/2);
        }
        else{
            q[i].y=lower_bound(lsh+1,lsh+tot+1,q[i].y)-lsh;
            upd(q[i].x,-1),upd(q[i].x+1,-1),a[q[i].x]=q[i].y;
            upd(q[i].x,1),upd(q[i].x+1,1);
        }
    }
    return 0;
}

• CF799F Beautiful fountains rows

• 长度为 m 的数轴上有每个区间，每个区间都有各有一种颜色且颜色不同（即该区间内每个点染上区间编号对应的颜色，一个点可以存在多个颜色，区间颜色不给定）。定义一个区间 [l,r] 是好的当且仅当其至少包含一种颜色，且对于其包含在内的每种颜色，颜色出现次数为奇数。n,m\le 10^6。

出现奇数次和可以出现 0 次看似有点冲突，将将题目改成出现次数为偶数次。

一个经典的trick：使用异或和来判断奇偶，给每一个区间随机一个权值即颜色，则当选择的区间中所有点的异或和为零时，每种颜色都出现偶数次，再使用前缀异或和即可维护。

对于把奇数个转为偶数个，将每个区间（包括自己选择的好区间）左侧或右侧 +/-1 即可。

#include<bits/stdc++.h>
using namespace std;

#define int long long

mt19937_64 rnd(time(0));

const int N=1e5+6;

int n,m,a[N],t[N],ans,c;
map<int,int>cnt,mps;

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        int x=rnd(),l,r;
        scanf("%lld%lld",&l,&r),l++;
        a[l]^=x,a[r+1]^=x;
        t[l-1]++,t[r+1]--;
    }
    for(int i=1;i<=m;i++){
        a[i+2]^=a[i],t[i]+=t[i-1],c++;
        if(t[i])c=0;
        cnt[a[i]]++,mps[a[i]]+=i-1;
        ans+=cnt[a[i]]*i-mps[a[i]]-c*(c+1)/2;
    }
    printf("%lld\n",ans);
}

• [AGC003D] Anticube

• 给定 n 个数 a_i，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。n\le 10^5，a_i\le 10^{10}。

先考虑朴素地分解质因数，所有次数对 3 取模，得到 a_i=\prod p_i^{k_i}，有 b_i=\prod p_i^{3-k_i}，则 a_ib_i 为完全立方数。所以将每个数先转为次数 <3 的模式后对于每一对 a_ib_i 看哪个出现的多即可。

但是不能直接分解，但是可以分解 \sqrt[3] V 内的质因数。考虑剩下的那个数 d_i，此时仅有三种可能：p,pq,p^2，分类一下即可。

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N=1e5+6;
const int M=330;

int n,p[N],pid,cnt[N][M],ans;
bool vis[N],cubic[N];
ll a[N],b[N],d[N],mx;
map<ll,int>mps;
queue<ll>q;

void init(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i])p[++pid]=i;
        for(int j=1;j<=pid&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    return;
}

inline bool isq(ll x){
    ll y=sqrt(x);
    return y*y==x;
}

signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),mx=max(mx,a[i]);
    int A=pow(mx,1./3),B=sqrt(mx);
    init(B);
    for(int i=1;i<=n;i++){
        int tmp=1;
        for(int j=1;j<=pid&&p[j]<=A;j++){
            while(a[i]%p[j]==0)a[i]/=p[j],cnt[i][j]++;
            cnt[i][j]%=3;
            if(cnt[i][j])tmp*=p[j];
            if(cnt[i][j]==2)tmp*=p[j];
        }d[i]=a[i],a[i]*=tmp;
        if(a[i]==1)ans=1,cubic[i]=1;
    }
    for(int i=1;i<=n;i++)if(!cubic[i]){
        if(d[i]==1||(d[i]<=B&&!vis[d[i]])||isq(d[i]))
            q.push(i),mps[a[i]]++;
        else ans++;
    }
    while(!q.empty()){
        int i=q.front();q.pop();
        if(isq(d[i]))b[i]=sqrt(d[i]);
        else b[i]=d[i]*d[i];
        for(int j=1;j<=pid&&p[j]<=A;j++){
            if(cnt[i][j])b[i]*=p[j];
            if(cnt[i][j]==1)b[i]*=p[j];
        }
        ans+=max(mps[a[i]],mps[b[i]]),mps[a[i]]=mps[b[i]]=0;
    }
    printf("%d\n",ans);
    return 0;
}

• P8352 [SDOI/SXOI2022] 小 N 的独立集

• 给定 n 个点的树的形态以及点的权值范围 k，对于任意 i \in [1,kn]， 求有多少种权值分配方案，使得树的最大权独立集大小为 i。n\le 1000,k\le 5。

最朴素的暴力即 f_{u,0/1} 表示选或不选，暴力枚举权值可能，O(nk^n)。注意到 f 值域为 O(nk) 的，所以可以 dp 套 dp，dp_{u,x,y} 表示 f_{u,0}=x,f_{u,1}=y 时的情况。O(n^4k^4)。

注意到瓶颈在于 dp 状态数就寄了，改变 f 的定义为是否钦定 u 不选，那么有 f_{u,0}-f_{u,1}\le a_u\le k，所以有 dp_{u,x,d}，其中 f_{u,0} 被表示为 x+d。O(n^2k^4)。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e3+4;
const int M=5*N;
const int mod=1e9+7;

int n,k,sz[N],f[N][M][6],g[M][6],tot,head[N];

struct edge{
    int to,nxt;
}e[N<<1];

inline void addedge(int u,int v){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
    return;
}

void dfs(int u,int fa){
    sz[u]=1;
    for(int i=1;i<=k;i++)f[u][0][i]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        memset(g,0,sizeof(g));
        for(int i=0;i<=k*sz[u];i++)
        for(int j=0;j<=k;j++)if(f[u][i][j])
        for(int p=0;p<=k*sz[v];p++)
        for(int q=0;q<=k;q++)if(f[v][p][q])
        (g[i+p+q][max(i+j+p,i+p+q)-(i+p+q)]+=f[u][i][j]*f[v][p][q]%mod)%=mod;
        memcpy(f[u],g,sizeof(g)),sz[u]+=sz[v];
    }
    return;
}

signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n*k;i++){
        int ans=0;
        for(int d=0;d<=min(i,k);d++)ans=(ans+f[1][i-d][d])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

• CF1842H Tenzing and Random Real Numbers

• 有 n 个 [0,1] 范围内的均匀随机变量 x_{1\cdots n} 和 m 条限制，每条限制形如 x_i+x_j\le 1 或 x_i+x_j\ge 1。请你求出所有限制均满足的概率。1\le n\le 20,\ 0\le m\le n^2+n。

先将 x[i]-=0.5，变为 x_i+x_j\le 0,x_i\in[-0.5,0.5]。将 x_i 按照绝对值大小排序后发现 x_i+x_j\le 0 等价于 x_j\le 0（钦定 |x_i|\le |x_j|），大于等于同理，所以按照绝对值排序后给每个数安排正负号，那么转为状压 dp，做完了。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=21;
const int mod=998244353;
const int inv2=(mod+1)/2;

int n,m,g[2][N],dp[1<<N],ans;

inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int op,x,y;
        scanf("%lld%lld%lld",&op,&x,&y),x--,y--;
        g[op][x]|=(1<<y),g[op][y]|=(1<<x);
    }dp[0]=1;
    for(int s=1;s<(1<<n);s++)for(int i=0;i<n;i++)if(s&(1<<i)){
        if(!(g[0][i]&s))dp[s]=(dp[s]+dp[s^(1<<i)])%mod;
        if(!(g[1][i]&s))dp[s]=(dp[s]+dp[s^(1<<i)])%mod;
    }
    int ans=dp[(1<<n)-1];
    for(int i=1;i<=n;i++)ans=ans*qpow(i,mod-2)%mod;
    printf("%lld",ans*qpow(inv2,n)%mod);
    return 0;
}

• Toxic Violet Cubes

• 给图的每⼀个点染上⼀种颜⾊，使得对于所有节点，⾄少有⼀半的邻点的颜⾊都与它不同。求最少⽤多少种颜⾊，并给出任意⼀种⽅案。n\le 5000,m\le 3\times 10^4。

大胆猜想答案 \le 2。对于 m=0 时答案为 1 否则为 2。怎么证明？

设 C=\sum_{(u,v)\in E}|col_u-col_v|，每次从图中随便拿一个不满足条件的点，即超过⼀半的邻点的颜⾊与它不同，将其反色，发现 C 至少 +1。那么 S 单增且有显然上界 m，故必定会终止即得证，且最多 m 轮，每轮容易通过记录每个点周围颜色与其是否相同的值之和做到 O(n)，总时间复杂度 O(nm)。

#include<bits/stdc++.h>
using namespace std;

const int N=5e3+4;

int n,m,a[N],col[N];
queue<int>q;
vector<int>g[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
        a[u]--,a[v]--;
    }
    if(!m){
        puts("1");
        for(int i=1;i<=n;i++)printf("1 ");
        return 0;
    }
    else puts("2");
    for(int i=1;i<=n;i++)q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        if(a[u]>=0)continue;
        col[u]^=1,a[u]*=-1;
        for(int v:g[u]){
            a[v]+=(col[u]!=col[v]?1:-1)*2;
            if(a[v]<0)q.push(v);
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",col[i]+1);
    return 0;
}

• CF1553H XOR and Distance

• 一个长度为 n 的序列 \{a_i\}，保证 \forall i\in[1,n],a_i\in[0,2^k)，要你对所有 x\in[0,2^k)，求出 \min_{i,j\in[1,n]\land i\not=j}\left|(a_i\oplus x)-(a_j\oplus x)\right|。k\le 19,n\le 2^k。

• P9595 「Daily OI Round 1」Xor

• 给定一个长度为 n 的序列，一共有 q 次询问，每次询问给定正整数 x，然后将全局异或 x 后求最长连续值域区间。n,q\le 5\times 10^5。

这两题对于我的做法而言没有区别，所以放在一起讲。

先把 trie 树建出来（实际上不需要真正建出），异或上 x 相当于将 x 拆成二的幂次的和后每次异或一个二次幂。在 trie 上异或 2^k 是好做的，相当于将从下往上（从 0 标号）的第 k 层两两相邻区间交换。

在每个节点上维护题目需要的信息，以 CF1553H 为例，我们维护该节点表示的区间的答案、最大值与最小值，那么节点的答案可以被左子树的最大值与右子树最小值的差值来转移。

注意对于某一层有影响的只有它下面的层，所以考虑这样的一个dp：