复 健 训 练

感觉高考考得一般般，估计要打 ACM 了，提前开始复健，大致在这里记录一些或许有意义的题。

估计接下来题解风格都会焕然一新。（大概）

[ARC122]

summary

实况：题不会想，代码也不会写了，真的爬了。

[ARC122 A]

solution

题面：一行有 个数，相邻两个数可以添加 或者 ，其中两个 不能相邻，求所有方案的和。

做法：考虑算 的贡献。 表示长度为 末尾为 的方案数，于是就可以对每个位置的 号算贡献了。

复杂度 。

//2021.6.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int n,a[N],f[N][2],g[N][2];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        res ans=0,sum=0;
        for(res i=1;i<=n;i++)add(sum,a[i]);
        //0 + 1 - f pre g suf
        f[1][0]=1,g[1][0]=1;
        for(res i=2;i<=n;i++)f[i][0]=Add(f[i-1][0],f[i-1][1]),f[i][1]=f[i-1][0];
        ans=mul(sum,Add(f[n][0],f[n][1]));
        for(res i=2;i<=n;i++)add(ans,mul(Add(kcz-a[i],kcz-a[i]),mul(f[n-i+1][0],f[i-1][0])));
        printf("%d\n",ans);
    }
}

[ARC122 B]

solution

题面：给定 个正整数 ，需确定一个正整数 使得 最小。

做法：对 排序后，考虑 且 ，直接预处理前缀和算出当前答案。于是枚举 即可。

复杂度 。

//2021.6.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int n,a[N];
    LL sum[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        sort(a+1,a+n+1);
        for(res i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
        RG LL ans=INF;
        for(res m=0;m<=n;m++){
            ans=min(ans,sum[n]*2+1LL*n*a[m]-2LL*a[m]*(n-m)-2LL*sum[m]);
        }
        printf("%.10Lf\n",(long double)ans/(2.0*n));
    }
}

[ARC122 C]

solution

题面：输入一个小于等于 的正整数数 ，初始 为零，现有四种操作：

求构造一种方案使得 ，操作次数不超过 次。

做法：考虑每次 在后序的贡献。如果后续总是 的循环，则显然这个 的贡献系数是与 Fib 的某一项。大胆猜想这样的操作次数小于等于 。于是将 拆成若干个 Fib 的和即可。

复杂度 。

//2021.6.14 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    LL N;
    LL f[100+10];
    int n;
    int cnt[150+10],cntx;
    inline void MAIN(){
        f[0]=f[1]=1;
        for(res i=2;i<=100;i++){f[i]=f[i-1]+f[i-2],n=i;if(f[i]>=1e18)break;}
        N=Read();
        for(res i=n-1;~i;i--){
            if(N>=f[i]){
                N-=f[i];
                if(i&1)cnt[++cntx]=2;
                else cnt[++cntx]=1;
            }
            cnt[++cntx]=3+(i&1);
        }
        if(cntx>=130)cntx=200;
        printf("%d\n",cntx);
        for(res i=1;i<=cntx;i++)printf("%d\n",cnt[i]);
    }
}

[ARC122 D]

solution

题面：A 和 B 在博弈，两个人分别从 个数各抽出一个数取异或，每次异或取大为最终答案。A 希望最终结果最大，B 希望最终结果最小，A 先手，求最终答案。

做法：对 个数建立 Trie 树后，考虑递归 Trie 树。

若当前节点的左儿子内有奇数个数，说明右儿子也有奇数个数，则无论 B 如何取，总有一对分别来自两个儿子，于是暴力递归如两个儿子计算答案，这样的话，B每次可以狙击 A，即尽量保证 A 最小。

若当前节点的左儿子内有偶数个数，说明右儿子也有偶数个数，那么继续递归入两个儿子。

总复杂度 。

//2021.6.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int n;
    LL a[N];
    int tr[N*31][2],sz[N*31];
    int tot,rt;
    inline void insert(const RG LL &x){
        if(!rt)rt=++tot;
        res now=rt;
        sz[now]++;
        for(res i=30;~i;i--){
            if(x&(1ll<<i)){
                if(!tr[now][1])tr[now][1]=++tot;
                now=tr[now][1],sz[now]++;
            }
            else {
                if(!tr[now][0])tr[now][0]=++tot;
                now=tr[now][0],sz[now]++;
            }
        }
    }
    LL ans;
    LL dfs(res n1,res n2,RG LL ret,res dep){
        RG LL qaq=INF;
        if(dep==-1)return ret;
        if(tr[n1][0]){
            if(tr[n2][0])qaq=dfs(tr[n1][0],tr[n2][0],ret,dep-1);
            else if(tr[n2][1])qaq=dfs(tr[n1][0],tr[n2][1],ret|(1ll<<dep),dep-1);
        }
        if(tr[n1][1]){
            if(tr[n2][1])qaq=min(qaq,dfs(tr[n1][1],tr[n2][1],ret,dep-1));
            else if(tr[n2][0])qaq=min(qaq,dfs(tr[n1][1],tr[n2][0],ret|(1ll<<dep),dep-1));
        }
        return qaq;
    }
    void solve(res now,res dep){
        if(sz[tr[now][0]]&1)ans=max(ans,dfs(tr[now][0],tr[now][1],1ll<<(dep-1),dep-2));
        else {
            if(tr[now][0])solve(tr[now][0],dep-1);
            if(tr[now][1])solve(tr[now][1],dep-1);
        }
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<=2*n;i++)a[i]=Read(),insert(a[i]);
        solve(rt,31),printf("%lld\n",ans);
    }
}

[ARC122 E]

solution

题面：有 个互不相同的正整数，现要求你找出一组这 个数的排列，使得前缀 递增。

做法：考虑从后往前构造，下证明后面的选取不会影响前面。

假设前面的 为 ，后两个数为 ，若后面的选取会影响前面，则要满足（假定顺序为 ）

$$\begin{cases} \operatorname{lcm} (A,a) < \operatorname{lcm} (A,a,b) \\\\ A = \operatorname{lcm} (A,a) \\\\ \operatorname{lcm} (A,b) < \operatorname{lcm} (A,a,b) \\\\ A < \operatorname{lcm} (A,b) \end{cases}$$

即

$$\begin{cases} \gcd(\operatorname{lcm} (A,a),b) < b \\\\ \gcd(A,a) = a \\\\ \gcd(\operatorname{lcm} (A,b),a) < a \\\\ \gcd(A,b) < b \end{cases}$$

根据第二条，可得 （ 为一正整数）。但根据第三条， 显然被 整除，但与 的 却小于 ，矛盾。

于是证出了后面的选取不会影响前面，因此暴力从后往前即可，时间复杂度 。

具体实现上，需小心爆long long，稍微注意一些细节即可。

//2021.6.24 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
    int n;
    LL a[N];
    bool vis[N];
    LL b[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=Read();
        for(res T=1;T<n;T++){
            bool Fl=0;
            for(res i=1;i<=n;i++){
                if(vis[i])continue;
                RG LL ret=1;
                bool fl=0;
                for(res j=1;j<=n;j++){
                    if(vis[j]||i==j)continue;
                    RG LL p=__gcd(a[j],a[i]);
                    if((long double)ret/__gcd(ret,p)>=(long double)a[i]/p){fl=1;break;}
                    ret=(long long)((__int128)ret*p/__gcd(ret,p));
                }
                if(fl)continue;
                b[n-T+1]=a[i],Fl=1,vis[i]=1;break;
            }
            if(!Fl){puts("No");return;}
        }
        for(res i=1;i<=n;i++)if(!vis[i])b[1]=a[i];
        puts("Yes");
        for(res i=1;i<=n;i++)printf("%lld ",b[i]);
    }
}

[ARC122 F]

solution

题面：有 个红石， 个蓝石。你可以任意移动石子，代价是曼哈顿距离。你的目标是，用最小的代价，使得每个红石右上方都至少有 个蓝石。

做法：先把绝对无意义的红石去掉，即 。

每个红石头右上角有 个蓝石头，等价于蓝石头可以分为 组，其中每一组都是一个时的答案。

然后我们考虑 。注意到一个蓝石头支配的红石头一定是一个连续的区间，于是考虑怎么计算答案。

画一个坐标系，其中只有 轴和 轴上有点，规定在 轴向上代价为 ，向下代价为 ， 轴向左代价为 ，向右代价为 。

对于每个蓝石头，从 向 连一条代价为 的边。

容易证明此时从 到 的最短路就是使得 的右上角有蓝石头的最小代价。（因为越往右上一直越有意义）

然后我们再对于每个红石头，从 到 连一条代价为 的边。

这样就可以使从起点到终点的路程被切成若干个区间，然后从 到 跑个最短路就行了。

至于 的话，等价于起点往 连一条容量为 的边即可。

复杂度 。

//2021.6.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int n,m,k;
    Pair r[N],b[N];
    struct E{
        int next,to,val,cap;
        E() {}
        E(res next,res to,res val,res cap):next(next),to(to),val(val),cap(cap) {}
    }edge[N*6];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v,const res &w,const res &c){
        edge[++cnt]=E(head[u],v,w,c),head[u]=cnt;
        edge[++cnt]=E(head[v],u,-w,0),head[v]=cnt;
    }
    int id;
    LL dis[N],h[N];
    int lim[N],pre[N],las[N];
    int S,T;
    priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > Q;
    inline bool spfa(){
        for(res i=1;i<=id;i++)dis[i]=INF,lim[i]=inf;
        Q.push(mp(dis[S]=0,S)),pre[T]=-1;
        while(!Q.empty()){
            res x=Q.top().se;
            RG LL d=Q.top().fi;
            Q.pop();
            if(dis[x]!=d)continue;
            for(res i=head[x];~i;i=edge[i].next){
                res tox=edge[i].to;
                if(dis[tox]>dis[x]+edge[i].val+h[x]-h[tox]&&edge[i].cap){
                    dis[tox]=dis[x]+edge[i].val+h[x]-h[tox],lim[tox]=min(lim[x],edge[i].cap),pre[tox]=x,las[tox]=i;
                    Q.push(mp(dis[tox],tox));
                }
            }
        }
        return pre[T]!=-1;
    }
    inline LL mcmf(){
        RG LL mincost=0;
        while(spfa()){
            res now=T;
            mincost+=1ll*lim[T]*(dis[T]+h[T]-h[S]);
            while(now!=S)edge[las[now]].cap-=lim[T],edge[las[now]^1].cap+=lim[T],now=pre[now];
            for(res i=1;i<=id;i++)h[i]+=dis[i];
        }
        return mincost;
    }
    map<int,int> Mx,My;
    int x[N],y[N],xx,yx;
    inline void MAIN(){
        n=read(),m=read(),k=read(),cnt=-1;
        for(res i=1;i<=n;i++)r[i].fi=read(),r[i].se=read();
        for(res i=1;i<=m;i++)b[i].fi=read(),b[i].se=read();
        sort(r+1,r+n+1);
        res nx=1;
        for(res i=2;i<=n;i++){
            while(nx&&r[nx].se<=r[i].se)nx--;
            r[++nx]=r[i];
        }
        n=nx;
        for(res i=1;i<=n;i++){
            if(!Mx.count(r[i].fi))Mx[r[i].fi]=++id,x[++xx]=r[i].fi;
            if(!My.count(r[i].se))My[r[i].se]=++id,y[++yx]=r[i].se;
        }
        for(res i=1;i<=m;i++){
            if(!Mx.count(b[i].fi))Mx[b[i].fi]=++id,x[++xx]=b[i].fi;
            if(!My.count(b[i].se))My[b[i].se]=++id,y[++yx]=b[i].se;
        }
        T=Mx[r[n].fi],S=++id;
        for(res i=1;i<=id;i++)head[i]=-1;
        sort(x+1,x+xx+1),sort(y+1,y+yx+1);
        for(res i=1;i<xx;i++)addedge(Mx[x[i]],Mx[x[i+1]],x[i+1]-x[i],inf),addedge(Mx[x[i+1]],Mx[x[i]],0,inf);
        for(res i=1;i<yx;i++)addedge(My[y[i]],My[y[i+1]],0,inf),addedge(My[y[i+1]],My[y[i]],y[i+1]-y[i],inf);
        for(res i=1;i<=m;i++)addedge(My[b[i].se],Mx[b[i].fi],0,1);
        for(res i=1;i<n;i++)addedge(Mx[r[i].fi],My[r[i+1].se],0,inf);
        addedge(S,My[r[1].se],0,k),printf("%lld\n",mcmf());
    }
}

[CF1534]

summary

实况：时间太迟了，脑子差到了极点。

[CF1534 F]

solution

题面：给你一个 行 列的网格和一个长度为 的序列 。每个位置要么是空的，要么有一块沙子。我们保证 的值小于等于网格第 列的沙子块数。
你可以选择任意一块仍然在网格中的沙子并“干扰”这块沙子。当一块沙子被“干扰”后，它会从当前位置竖直下落，并最终掉出网格。另外，所有与一块下落的沙子经过的任意位置相邻的沙子也会开始竖直下落，任意下落的沙子都会使相邻的沙子下落（如果这一段看不懂，可以阅读样例，样例中用黑色方框标记的是被“干扰”的沙子，用叉标记的是自动下落的沙子）。
你的目标是使第 列至少有 块沙子掉出网格。
求你最少需要“干扰”多少块沙子。

做法：每一块沙对有影响的沙连边后（只连有直接影响的沙），缩点重新看这张图。 的限制可以转化成每列自下往上数的第 块沙，只要这块特殊沙掉落了就满足了 的条件。当 特殊沙可以影响 特殊沙时，则 特殊沙的存在显得毫无意义，可以将其删除。在删去无意义沙之后，我们才可以证明每一块沙影响的特殊沙是一段连续的区间（若不连续，则存在第 列的 特殊沙阻隔了两端区间，由于 列必须有一块普通沙连接两段区间，发现这块普通沙若在特殊沙上方时，会影响到特殊沙；在下方时， 特殊沙会影响相邻区间里的一块特殊沙，而这种特殊沙已经删除了，所以矛盾）。有了这样的性质，求出每一块入度为零的沙所影响的区间，做一个贪心就行了。时间复杂度 。

代码实现感觉挺麻烦的。下面代码已去掉调试，还是可以看看的。

//2021.7.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    char str[N];
    vector<char> v[N];
    vector<int> G[N];
    vector<int> E[N];
    int dfn[N],low[N],idx,vis[N],st[N],top,sig[N],nw;
    int Fl[N];
    int mn[N],mx[N];
    void tarjan(res x){
        dfn[x]=low[x]=++idx,vis[st[++top]=x]=1;
        for(auto tox:G[x]){
            if(!dfn[tox])tarjan(tox),low[x]=min(low[x],low[tox]);
            else if(vis[tox])low[x]=min(low[x],dfn[tox]);
        }
        if(low[x]==dfn[x]){
            res y=0;
            nw++;
            do{
                vis[y=st[top--]]=0,sig[y]=nw;
            }while(x!=y);
        }
    }
    int las[N];
    int a[N];
    int fl[N],du[N];
    vector<int> B;
    int Vis[N];
    void dfs(res x){
        Vis[x]=1;
        for(auto tox:E[x]){
            if(Vis[tox]){mn[x]=min(mn[x],mn[tox]),mx[x]=max(mx[x],mx[tox]);continue;}
            dfs(tox),mn[x]=min(mn[x],mn[tox]),mx[x]=max(mx[x],mx[tox]);
        }
    }
    int jud[N];
    void Dfs(res x){
        for(auto tox:E[x]){
            if(jud[tox])continue;
            jud[tox]=1,Dfs(tox);
        }
    }
    Pair seg[N];
    int tot;
    int A[N];
    int Mpx;
    inline void MAIN(){
        res n=read(),m=read();
        for(res i=1;i<=n*m;i++)mn[i]=n*m+1;
        for(res i=1;i<=n;i++){
            scanf("%s",str+1);
            v[i].pb(' ');
            for(res j=1;j<=m;j++)v[i].pb(str[j]);
            for(res j=1;j<=m;j++){
                if(str[j]=='#'){
                    res id=(i-1)*m+j;
                    if(!las[j])B.pb(id);
                    fl[id]=1;
                    if(j>1&&las[j-1]){
                        G[las[j-1]].pb(id);
                        if(str[j-1]=='#')G[id].pb(las[j-1]);
                    }
                    if(j<m&&las[j+1])G[las[j+1]].pb(id);
                    if(las[j]){
                        G[las[j]].pb(id);
                        if(v[i-1][j]=='#')G[id].pb(las[j]);
                    }
                    las[j]=id;
                }
            }
        }
        for(res i=1;i<=m;i++)a[i]=read();
        for(res j=1;j<=m;j++){
            res now=0;
            for(res i=n;i;i--){
                if(v[i][j]=='#')now++;
                if(now==a[j]){Fl[(i-1)*m+j]=j,A[j]=(i-1)*m+j;break;}
            }
        }
        for(res i=1;i<=n*m;i++)if(!dfn[i]&&fl[i])tarjan(i);
        for(res x=1;x<=n*m;x++){
            if(!fl[x])continue;
            for(auto tox:G[x]){
                if(sig[tox]==sig[x])continue;
                E[sig[x]].pb(sig[tox]),du[sig[tox]]++;
            }
        }
        for(res i=1;i<=m;i++)if(a[i])Dfs(sig[A[i]]);
        for(res i=1;i<=m;i++){
            if(jud[sig[A[i]]]||!a[i]||mx[sig[A[i]]])continue;
            mn[sig[A[i]]]=mx[sig[A[i]]]=++Mpx;
        }
        for(res i=1;i<=nw;i++)if(!du[i])dfs(i),seg[++tot]=mp(mn[i],mx[i]);
        sort(seg+1,seg+tot+1);
        res ans=0;
        for(res i=1,rm=0,rf=0,j=1;i<=Mpx;i++){
            while(j<=tot&&seg[j].fi<=i)rf=max(rf,seg[j].se),j++;
            if(i>rm)ans++,rm=rf;
        }
        printf("%d\n",ans);
    }
}

[CF1534 G]

solution

题面：你在一个二维平面直角坐标系的原点 上，你可以向上或向右移动 单位长度任意次。
现在给你 个点，第 个点为 。你需要对这 个点都打上标记。具体的，在任意时刻，如果你在点 并希望对点 打标记，你需要花费 单位能量。

求最少花费多少单位能量。

做法：一种叫 Slope trick 的做法。

先考虑一个简单的事实，一个点到一条路径的切比雪夫距离最小肯定是经过这个点的斜率为 的直线与路径的交点间的距离。这个性质过于显然，就不证了。

有这样的事实后，考虑将点以 为序排列好。这样的话，一条路径总会按序经过每个点所在的斜率为 的直线。于是做一个暴力的 dp，即设 为当前 dp到第 个点，当前横坐标为 的最小代价。转移式容易写出 。接下来我们考虑 以第二维作为横坐标时的图像。我们可以有一个结论：已知 为定义域为 且连续的函数，令 ，其中 为一定值，则 为连续函数。这个证明省略，感兴趣可以咨询笔者 QQ。又因为 是下凸函数，而下凸函数与下凸函数的和还是下凸函数（因为 ），所以可以归纳证明 也为下凸函数。接下来我们考虑维护这个下凸壳。取 操作等于将 的最低点向右拉长 的距离，右部分同时平移，其余不变。至于加入一个 我们可以做这样一件事，定义一个有序可重集中的一个元素表示当前凸壳在此处斜率减少了 。于是我们只需维护这个可重集，就可以维护好 了。

具体实现上，我们每次加入一个点分三类讨论，若当前 在最低点左边/最低点/最低点右边。在其左时， 的左边斜率都减一，而右边都加一，等于在 的位置减少了 ，所以我们朝左部分可重集加入两个 ，同时最左边的最低点此时已经不再是最低点，所以将其放入右部分可重集里。放入右部分可重集时要注意我们打了全局的右部分平移量标记，可以放入前要先减去此标记，不然拿出来时就不是真实值了。其余情况同理维护一下。此时 的贡献就是离它最近的最低点的贡献。

时间复杂度 。

//2021.7.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=8e5+10;
namespace MAIN{
    int n;
    Pair a[N];
    LL ans;
    priority_queue<int> L;
    priority_queue<int,vector<int>,greater<int> > R;
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++){
            res x=read(),y=read();
            a[i].fi=x+y,a[i].se=x;
        }
        sort(a+1,a+n+1),L.push(a[1].se),R.push(a[1].se);
        res tagr=0;
        for(res i=2;i<=n;i++){
            tagr+=a[i].fi-a[i-1].fi;
            res l=L.top(),r=R.top()+tagr,x=a[i].se;
            if(x<l)L.pop(),R.push(l-tagr),L.push(x),L.push(x),ans+=l-x;
            if(x>r)R.pop(),L.push(r),R.push(x-tagr),R.push(x-tagr),ans+=x-r;
            if(l<=x&&x<=r)L.push(x),R.push(x-tagr);
        }
        printf("%lld\n",ans);
    }
}

[CF1534 H]

solution

题面：交互。 个点的树，需要你猜出这棵树上的两个特殊节点 。首先，会告诉你一个整数 ，满足 在 的路径上。接下来你可以进行询问，具体的，每次给定整数 ，交互器会给你当树的根节点为 时，节点 的最近公共祖先是哪个节点。特别地，在给定树的形态之后，你需要先给出在所有 的可能的取值中，至少需要多少次询问才能保证得出特殊节点的编号。

做法：经典两个相似名称的函数调用了，在 split_sz 中调用了 split，调了我两个小时。

先思考它交互器返回的是什么，其实就是点 到 路径上的最近点。那以它为根就不重要了，我们考虑以 为根。

我们询问 的一个儿子 ，若返回的是 ，说明 在 的路径上，而 不在；若返回的是 ，那么 在 的路径上；若返回的是 的祖先，说明 都不在路径上，而返回的那个点在。于是我们可以设计出一个交互步骤，递归入树，先询问叶子，如果叶子在路径上那它一定是一个端点，否则一直到叶子返回的那个点前都不是路径上点，而在叶子返回的那个点再往另一边递归，如果都返回它那它就是端点，否则在另外一边递归时就会找到（类似第一次的情况），于是我们就能找到两个端点了。

但这存在一个问题，交互次数的问题，它要求我们按最小交互次数输出，这该怎么办呢？

我们再重新考虑最小次数是多少。设 为知道 的子树中有无端点（若有，需要知道位置）的最少询问次数。根据上述思考，我们每次询问只会是叶子，于是考虑当前询问了 的儿子 子树中的一个叶子 。若它返回是 ，除非它是 的分支中最后一次询问的了，不然这次操作不能确定端点位置，而这次询问就不会被 涵盖。若它返回的不是 ，那么意味着端点在 的子树内，说明通过对 子树的询问就可以让我们知道端点的位置，与 已经无关了，而且这次询问已经被 所涵盖。

我们利用这东西转移，最坏情况肯定是想要前面若干次询问都是无效的（无效就不会让我们递归入子树），直到当前有效是最大的才好。数字化表示，就是 。而我们想要 最小，那么贪心地想，肯定要 从大到小排好，这样转移肯定是最优的。维护这个转移我们使用平衡树，每次插入一个新的数就让比小的数的权值加一，那么维护的就是权值最大了。

它题目要求我们输出所有的 的情况，发现这个东西可以做换根 ，于是就可以做了。时间复杂度 。

最终要求出两个端点，那我们考虑枚举 的两个儿子，分别计算它们确定端点的最小次数，即 。

这个东西也是可以贪心地，想要最小，可以发现也是按 从大到小的顺序， 换根 可以维护，于是就求出了答案。

而如何交互的问题也迎刃而解了，是从最大的 开始交互即可。

坑：1. 因为有两个 split，我一手贱就混用了，调了好久。

1. 大小顺序容易写错，注意一下。

//2021.9.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n;
    vector<int> G[N];
    int f[N];
    struct Treap{
        int mx,son[2],val,laz,sz,va,pri;
    }tr[N*3];
    int rt[N],tot,st[N*3],top;
    inline int newnode(const res &va,const res &val){
        res cur=0;
        if(top)cur=st[top--];
        else cur=++tot;
        tr[cur].va=va,tr[cur].mx=tr[cur].val=val,tr[cur].sz=1,tr[cur].pri=rng(),tr[cur].son[0]=tr[cur].son[1]=tr[cur].laz=0;
        return cur;
    }
    inline void change(const res &x,const res &v){
        if(!x)return;
        tr[x].mx+=v,tr[x].val+=v,tr[x].laz+=v;
    }
    inline void pushdown(const res &x){
        if(!tr[x].laz||!x)return;
        change(tr[x].son[0],tr[x].laz),change(tr[x].son[1],tr[x].laz),tr[x].laz=0;
    }
    inline void pushup(const res &x){
        tr[x].mx=max({tr[tr[x].son[0]].mx,tr[tr[x].son[1]].mx,tr[x].val});
        tr[x].sz=tr[tr[x].son[0]].sz+tr[tr[x].son[1]].sz+1;
    }
    int merge(res x,res y){
        if(!x||!y)return x|y;
        pushdown(x),pushdown(y);
        if(tr[x].pri<tr[y].pri){
            tr[x].son[1]=merge(tr[x].son[1],y);
            pushup(x);
            return x;
        }
        else {
            tr[y].son[0]=merge(x,tr[y].son[0]);
            pushup(y);
            return y;
        }
    }
    void split(res now,res k,res &x,res &y){
        if(!now){x=y=0;return;}
        pushdown(now);
        if(tr[now].va<=k)x=now,split(tr[now].son[1],k,tr[now].son[1],y);
        else y=now,split(tr[now].son[0],k,x,tr[now].son[0]);
        pushup(now);
    }
    void split_sz(res now,res k,res &x,res &y){
        if(!now){x=y=0;return;}
        pushdown(now);
        if(tr[tr[now].son[0]].sz<k)x=now,split_sz(tr[now].son[1],k-tr[tr[now].son[0]].sz-1,tr[now].son[1],y);
        else y=now,split_sz(tr[now].son[0],k,x,tr[now].son[0]);
        pushup(now);
    }
    inline void insert(res &RT,const res &v){
        res a,b;
        split(RT,v,a,b),change(a,1),RT=merge(merge(a,newnode(v,v+tr[b].sz)),b);
    }
    void dfs(res x,res fax){
        rt[x]=0;
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs(tox,x),insert(rt[x],f[tox]);
        }
        f[x]=max(1,tr[rt[x]].mx);
    }
    inline void erase(res &RT,const res &v){
        res a,b,c,d;
        split(RT,v,a,b),split_sz(a,tr[a].sz-1,c,d);
        if(d)st[++top]=d;
        change(c,-1),RT=merge(c,b);
    }
    inline int get(res &RT){
        res a,b,ret=0;
        split_sz(RT,tr[RT].sz-1,a,b),ret=tr[b].va-1+max(1,tr[a].mx);
        RT=merge(a,b);
        return ret;
    }
    int ans;
    void Dfs(res x,res fax){
        ans=max(ans,get(rt[x]));
        for(auto tox:G[x]){
            if(tox==fax)continue;
            res F=f[x],G=f[tox];
            erase(rt[x],f[tox]),f[x]=max(1,tr[rt[x]].mx);
            insert(rt[tox],f[x]),f[tox]=max(1,tr[rt[tox]].mx);
            Dfs(tox,x),f[x]=F,f[tox]=G,insert(rt[x],f[tox]);
        }
    }
    inline bool cmp(const res &x,const res &y){
        return f[x]>f[y];
    }
    int Ans[2],Ansx;
    inline int ask(const res &x){
        printf("? %d\n",x),fflush(stdout);
        return read();
    }
    int get(res x,res fax){
        sort(G[x].begin(),G[x].end(),cmp);
        res r=0;
        for(auto tox:G[x]){
            if(tox==fax)continue;
            res ret=get(tox,x);
            if(x!=ret)return ret;
            r=1;
        }
        if(!r)return ask(x);
        return x;
    }
    inline void MAIN(){
        n=read();
        for(res i=1;i<n;i++){
            res u=read(),v=read();
            G[u].pb(v),G[v].pb(u);
        }
        dfs(1,0),Dfs(1,0),printf("%d\n",ans),fflush(stdout),tot=top=0;
        res f=read();
        dfs(f,0),sort(G[f].begin(),G[f].end(),cmp);
        for(auto tox:G[f]){
            res tmp=get(tox,f);
            if(tmp==f)continue;
            Ans[Ansx++]=tmp;
            if(Ansx==2)break;
        }
        if(!Ans[0])Ans[0]=f;
        if(!Ans[1])Ans[1]=f;
        printf("! %d %d\n",Ans[0],Ans[1]),fflush(stdout);
    }
}

[CF1537]

summary

实况：C 都想歪了，构造半天搞出怪的东西，导致 D 开始梦游。幸亏最后看眼 E2 发现后缀数组可以艹过去，不然就无了。

[CF1537 D]

solution

题面：有一个正整数 ，现 A 和 B 每次可以让 减去它当前的一个因数，不能减去 和 ，谁先不能减谁输。问最后谁赢。

做法：先利用 sg​ 函数打个表，容易发现当 是奇数以及 且 为奇数时，先手必输。下面证明这个结论正确。

1. 当 不是 时，

当 是偶数但不是 时，此时 必然存在一个奇数因数，因此可让 变成一个奇数。

当 是奇数时，此时 只有奇数因数，于是只能让 变成一个偶数。

又因为最终停止只能是质数，而除了 以外的质数都是奇数，同时 不可能减到 （因为 ），于是只能减到一个奇质数。而减到奇质数时， 显然是个偶数，因此 是奇数时先手必输。

1. 当 是 时，

若减去的数不是 ，则会转换为 中情况，则先手必输。

若减去的数是 ，则对手也只能减去 ，以此类推，则 为奇数时先手必输。

综上，得证。

复杂度 。

代码有带打表的。

//2021.6.21 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    int pw[30+10];
    int sg[100+10];
    bool vis[100+10];
    inline void MAIN(){
        res T=read();
        pw[0]=1;
        for(res i=1;i<=30;i++)pw[i]=pw[i-1]<<1;
        sg[1]=sg[2]=sg[3]=0;
        for(res i=4;i<=100;i++){
            for(res j=0;j<=100;j++)vis[j]=0;
            for(res j=2,sz=int(sqrt(i));j<=sz;j++){
                if(i%j==0)vis[sg[i-j]]=vis[sg[i-(i/j)]]=1;
            }
            for(res j=0;j<=100;j++)if(!vis[j]){sg[i]=j;break;}
        }
//        for(res i=1;i<=20;i++)printf("%d %d\n",sg[i],i);
        while(T--){
            res n=read();
            RG bool fl=0;
            for(res i=1;i<=30;i++)if(n==pw[i]){puts(i&1?"Bob":"Alice"),fl=1;break;}
            if(fl)continue;
            if(n&1)puts("Bob");
            else puts("Alice");
        }
    }
}

[CF1537 E]

solution

题面：给出一个字符串 ，现有两种操作：

1. 删去字符串的最后一位
2. 循环倍长字符串

现想将 变成字典序最小的长度为 的字符串，输出最终串。

做法：先倍长 以去掉不当情况，那么最终串一定是从前往后找一个位置使得当前位置的后缀大于开头位置的后缀即可，从这个位置开始删除容易证明是最优的。这里可以用 kmp 或者后缀数组等实现。

复杂度 或 。

代码是后缀数组的。

//2021.6.18 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    char str[N],s[N];
    int n;
    int rnk[N],buc[N],sa[N],hei[N],fi[N],se[N],m;
    inline void get_SA(){
        m=10000;
        for(res i=1;i<=n;i++)buc[fi[i]=str[i]]++;
        for(res i=2;i<=m;i++)buc[i]+=buc[i-1];
        for(res i=n;i;i--)sa[buc[fi[i]]--]=i;
        for(res k=1;k<=n;k<<=1){
            res num=0;
            for(res i=n-k+1;i<=n;i++)se[++num]=i;
            for(res i=1;i<=n;i++)if(sa[i]>k)se[++num]=sa[i]-k;
            memset(buc,0,sizeof(buc));
            for(res i=1;i<=n;i++)buc[fi[i]]++;
            for(res i=2;i<=m;i++)buc[i]+=buc[i-1];
            for(res i=n;i;i--)sa[buc[fi[se[i]]]--]=se[i],se[i]=0;
            swap(fi,se);
            fi[sa[1]]=1;
            num=1;
            for(res i=2;i<=n;i++)fi[sa[i]]=(se[sa[i]]==se[sa[i-1]]&&se[sa[i]+k]==se[sa[i-1]+k])?num:++num;
            if(num==n)break;
            m=num;
        }
    }
    inline void get_hei(){
        res k=0;
        rnk[sa[1]]=1;
        for(res i=2;i<=n;i++)rnk[sa[i]]=rnk[sa[i-1]]+(fi[sa[i]]!=fi[sa[i-1]]||se[sa[i]]!=se[sa[i-1]]);
        for(res i=1;i<=n;i++){
            if(rnk[i]==1)continue;
            if(k)k--;
            res j=sa[rnk[i]-1];
            while(j+k<=n&&i+k<=n&&str[i+k]==str[j+k])k++;
            hei[rnk[i]]=k;
        }
    }
    int st[N][21];
    inline void PRE(){
        for(res i=1;i<=n;i++)st[i][0]=hei[i];
        for(res j=1;j<=20;j++)
            for(res i=1;i+(1<<j)-1<=n;i++)
                st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
    int Lg[N];
    inline int query_min(res l,res r){
        res k=Lg[r-l];
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
    inline int LCP(const res &l,const res &r){
        if(l==r)return n-l+1;
        res x=rnk[l],y=rnk[r];
        if(x>y)swap(x,y);
        return query_min(x+1,y);
    }
    inline void pre(){
        get_SA(),get_hei(),PRE();
    }
    int k;
    inline void MAIN(){
        n=read(),k=read();
        scanf("%s",str+1);
        for(res i=n+1;i<=2*n;i++)str[i]=str[i-n];
        n=2*n;
        str[n+1]=26;
        for(res i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;
        pre();
        for(res i=2;i<=n;i++){
            if(str[i]>str[1]){
                n=i-1;
            }
        }
        for(res i=2;i<=n;i++){
            RG int fl=0;
            if(str[i]==str[1]){
                res t=LCP(1,i);
                if(t>=i-1);
                else if(str[t+1]<str[t+i]){n=i-1;fl=1;}
            }
            if(fl)break;
        }
        res j=1;
        for(res i=1;i<=k;i++){
            putchar(str[j]);
            j=j+1;
            if(j==n+1)j=1;
        }
    }
}

[CF1537 F]

solution

题面：有一张无向连通图，每个点具有一个点权。现可将一条边连接的两个点的点权同时加或减 ，问能否让所有点的点权都变为 ？

做法：

性质：若两点距离为偶数，则可一加一减同样的数；若两点距离为奇数，则可同时加减一个数。

1. 有奇环。

当一张连通图有奇环，可以证明每个点要么在一个奇环上，要么不在环上（因为若一个点在偶环上，必然可以连接至一个奇环使得这个点在这个大奇环上）。

因此考虑将非环上的点按照拓扑序改变点权至 ，这样的改变是唯一的。于是只剩下一堆环上以及连接环和环的点了。

容易发现对一个奇环绕一圈加减相同的数时，最终的结果是可以使一个点加减 。经过这样多次操作，可以使每个点的点权为 或 或 。现考虑将点权不为 的点两两匹配，根据性质，则当不为 的点个数为偶数时，必然可使所有点点权为 。若不为偶数，由于每次改变点权不会改变总和的奇偶，于是显然无解。

1. 无奇环。

当一张连通图无奇环上，这张图则为二分图。

我们先考虑一个基础的四元环，容易发现此时有解是对角线之和相同的充要条件。放在二分图上，则是两部分分别的和相同。

现考虑一张二分图，同上般的去除一些点，剩下的只是一堆环上以及连接环和环的点了。通过改变连接环和环的点的点权，容易证明这可以让每个环两边的点权和都相同（因为在二分图上的改变并不影响两边点权和之差）。再根据四元环时的构造，则可以轻松证明二分图两部分分别的和相同是有解的充要条件了。

时间复杂度 。

//2021.6.22 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,m;
    int a[N];
    int col[N];
    vector<int> G[N];
    bool vis[N];
    bool ok;
    void dfs(res x){
        for(auto tox:G[x]){
            if(ok)return;
            if(vis[tox]){
                if(col[tox]==col[x]){ok=1;return;}
                continue;
            }
            vis[tox]=1,col[tox]=col[x]^1,dfs(tox);
        }
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read(),m=read(),ok=0;
            for(res i=1;i<=n;i++)a[i]=read(),vis[i]=col[i]=0,G[i].clear();
            for(res i=1;i<=n;i++)a[i]-=read();
            for(res i=1;i<=m;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            vis[1]=1,dfs(1);
            if(ok){
                RG LL sum=0;
                for(res i=1;i<=n;i++)sum+=a[i];
                if(sum&1)puts("NO");
                else puts("YES");
            }
            else {
                RG LL s0=0,s1=0;
                for(res i=1;i<=n;i++)if(!col[i])s0+=a[i];else s1+=a[i];
                if(s0==s1)puts("YES");
                else puts("NO");
            }
        }
    }
}

[牛客挑战赛51]

summary

实况：我是 口 胡 王！（并查集写错，LCT 写不动，瘫痪了）（随机开题也挺怪的）

[牛客挑战赛51 C]

solution

题面：给你一个正整数 ，求第 小的正整数 满足 且 是一个回文数。

做法：考虑求 到 之间的回文数的个数，直接数位 dp。 表示总长为 ，当前到了第 位，有无上界限制的回文数个数。每次二分 ，暴力转移一下即可。总时间复杂度 。

//2021.7.13 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    LL x;
    int k;
    int a[20];
    int f[20][20][2],now[20];
    int dp(res len,res cur,res lim){
#define g f[len][cur][lim]
        if(!cur)return 1;
        if(~g)return g;
        res ret=0,lm=lim?9:a[cur];
        for(res i=0;i<=lm;i++){
            now[cur]=i;
            if(len==cur&&!i)ret+=dp(len-1,cur-1,lim|(i!=lm));
            else if(cur<=(len+1)/2){
                if(now[len-cur+1]==i)ret+=dp(len,cur-1,lim|(i!=lm));
            }
            else ret+=dp(len,cur-1,lim|(i!=lm));
        }
        return g=ret;
    }
    inline int solve(RG LL n){
        memset(f,-1,sizeof(f));
        res ax=0;
        while(n)a[++ax]=int(n%10),n/=10;
        return dp(ax,ax,0);
    }
    inline void MAIN(){
        x=Read(),k=read();
        RG LL o=solve(x-1);
        RG LL l=0,r=(LL)1e18,ret=0;
        while(l<=r){
            RG LL mid=(l+r)>>1;
            if(solve(mid)-o>=k)r=mid-1,ret=mid;
            else l=mid+1;
        }
        printf("%lld\n",ret);
    }
}

[牛客挑战赛51 D]

solution

题面：中文题面建议自己看。

做法：注意到贡献是独立的，所以没必要纠结长度为 中有多少个模式串，而只用算模式串总共出现了多少次。考虑枚举模式串头的位置，那么接下来 个位置被固定，其他位置看限制任意填。发现这些都可以直接维护。没啥细节，比标算的矩阵快速幂正常了一万倍。时间复杂度 。

//2021.12.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=500+10;
namespace MAIN{
    int n,m,k;
    char str[N];
    map<int,int> fl;
    map<int,int> F;
    map<Pair,int> ban;
    map<int,int> G;
    int q[N];
    int inv[N];
    inline void MAIN(){
        n=read(),m=read(),k=read(),scanf("%s",str+1),inv[0]=inv[1]=1;
        for(res i=2;i<=26;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=1;i<=k;i++){
            res op=read(),x=read(),ch=gc();
            while(ch<'a'||ch>'z')ch=gc();
            for(res j=1;j<=n&&x-j+1>=1;j++)if(x+n-j<=m)F[x-j+1]=1;
            if(!op){
                for(res j=1;j<=n&&x-j+1>=1;j++)if(str[j]==ch&&x+n-j<=m)fl[x-j+1]=1;
                if(ban[mp(x,ch-'a')]==2){puts("0");return;}
                ban[mp(x,ch-'a')]=1;
            }
            else {
                for(res j=1;j<=n&&x-j+1>=1;j++)if(str[j]!=ch&&x+n-j<=m)fl[x-j+1]=1;
                if(ban[mp(x,ch-'a')]==1){puts("0");return;}
                for(res j=0;j<26;j++){
                    if(j==ch-'a')continue;
                    if(ban[mp(x,j)]==2){puts("0");return;}
                }
                ban[mp(x,ch-'a')]=2;
            }
            q[i]=x;
        }
        sort(q+1,q+k+1),k=int(unique(q+1,q+k+1)-q-1);
        res ans=0,sum=1;
        for(res i=1;i<=k;i++){
            res o=0;
            for(res j=0;j<26;j++){
                if(!ban[mp(q[i],j)])o++;
                else if(ban[mp(q[i],j)]==2){o=1;break;}
            }
            if(!o){puts("0");return;}
            G[q[i]]=o;
            sum=mul(sum,o);
        }
        sum=mul(sum,qpow(26,m-k));
        for(auto x:F){
            if(fl[x.fi])continue;
            res ret=sum;
            for(res i=1;i<=n;i++){
                res p=x.fi+i-1;
                if(!G[p])ret=mul(ret,inv[26]);
                else ret=mul(ret,inv[G[p]]);
            }
            add(ans,ret);
        }
        add(ans,mul(m-n+1-int(F.size()),mul(sum,qpow(inv[26],n))));
        printf("%d\n",mul(ans,qpow(sum)));
    }
}

[牛客挑战赛51 E] [loj 2476]

solution

题面：给出 数组，求

$$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}E_{\gcd(i,k)}F_{\gcd(k,j)}.$$

做法：

$$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}E_{\gcd(i,k)}F_{\gcd(k,j)}\\\\ =\sum_{k=1}^n C_k\sum_{i=1}^n\sum_{j=1}^n A_iB_jD_{(i,j)} \sum_{p|(i,k)} (E\ast \mu)(p)\sum_{q|(k,j)} (F\ast \mu) (q)\\\\ =\sum_{\operatorname{lcm}(p,q)\leq n} (E\ast \mu)(p)(F\ast \mu)(q)(\sum_{k=1}^{\lfloor\frac{n}{\operatorname{lcm}(p,q)}\rfloor}C_k)\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{q}\rfloor}A_{ip}B_{jq}D_{(ip,jq)}\\\\ =\sum_d \sum_{xyd\leq n,(x,y)=1} (E\ast \mu)(xd)(F\ast \mu)(yd) (\sum_{k=1}^{\lfloor\frac{n}{xyd}\rfloor}C_k)\sum_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{yd}\rfloor} A_{ixd}B_{jyd}D_{d\cdot (ix,jy)}\\\\ 而 \sum_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{yd}\rfloor} A'_{ix}B'_{jy}D'_{(ix,jy)}\\\\ =\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}A'_{ix}\sum_{d'|ix} (D'\ast \mu) (d')\sum_{d'|jy,jy\leq n}B'_{jy}\\\\ =\sum_{x|z}A'_z\sum_{d'|z}(D'\ast \mu)(d')\sum_{d'|r}B'_r[y|r]$$

冷静一下，最后一条式子取 较小值去做，而最后一条式子是 前缀和，并且前面枚举 实际并不高，于是总复杂度经过积分分析就是 。

//2021.9.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    bool vis[N];
    int prim[N],tot;
    inline void F(RG ull *a,const res &n){
        for(res i=1;i<=n;i++)for(res j=i+i;j<=n;j+=i)a[j]-=a[i];
    }
    inline void G(RG ull *a,const res &n){
        for(res i=1;prim[i]<=n&&i<=tot;i++)for(res j=n/prim[i];j;j--)a[j]+=a[j*prim[i]];
    }
    inline void H(RG ull *a,const res &n){
        for(res i=1;prim[i]<=n&&i<=tot;i++)for(res j=1;j*prim[i]<=n;j++)a[j*prim[i]]+=a[j];
    }
    int n;
    ull a[N],b[N],c[N],d[N],e[N],f[N],p[N],q[N],r[N],s[N],t[N],w[N],u[N],v[N];
    inline void MAIN(){
        n=read();
        for(res i=2;i<=n;i++){
            if(!vis[i])prim[++tot]=i;
            for(res j=1;j<=tot&&prim[j]*i<=n;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0)break;
            }
        }
        for(res i=1;i<=n;i++)Read(a[i]);
        for(res i=1;i<=n;i++)Read(b[i]);
        for(res i=1;i<=n;i++)Read(c[i]);
        for(res i=1;i<=n;i++)Read(d[i]);
        for(res i=1;i<=n;i++)Read(e[i]);
        for(res i=1;i<=n;i++)Read(f[i]);
        RG ull ans=0;
        G(c,n),F(e,n),F(f,n);
        for(res i=1;i<=n;i++){
            res m=n/i;
            for(res j=1,k=i;j<=m;j++,k+=i)p[j]=e[k],q[j]=f[k],r[j]=c[k],s[j]=a[k],t[j]=b[k],w[j]=d[k];
            F(w,m);
            for(res x=1;x*x<=m;x++){
                for(res j=1;j<=m;j++)u[j]=v[j]=0;
                for(res j=x;j<=m;j+=x)u[j]=s[j],v[j]=t[j];
                G(u,m),G(v,m);
                for(res j=1;j<=m;j++)u[j]*=w[j],v[j]*=w[j];
                H(u,m),H(v,m);
                for(res j=1;j<=m;j++)u[j]*=t[j],v[j]*=s[j];
                for(res y=x;x*y<=m;y++)
                    if(__gcd(x,y)==1){
                        RG ull g=0,h=0;
                        for(res j=y;j<=m;j+=y)g+=u[j],h+=v[j];
                        ans+=p[x]*q[y]*r[x*y]*g;
                        if(x!=y)ans+=p[y]*q[x]*r[x*y]*h;
                    }
            }
        }
        printf("%llu\n",ans);
    }
}

[牛客挑战赛51 F]

solution

题面：所有 个点的有标号有根树的每个点深度的 次方的和，令根的深度为 。

做法：注意到贡献是独立的，所以没必要考虑一棵树的贡献量，可以选择按深度来分开来考虑。

考虑深度为 的点的贡献，那我们就要算有这个点的树的数量。首先它深度为 ，所以存在一条从根到这个点的链，然后其它点随意插入到这条链上。似乎不太好算，我们强制根到这个点的点是 ，最后乘上 。那么利用 序列，就等价于后 个是固定的，前 个数是任意的 内的数，第 个数是 的数。那么方案数直接就写出来了，总答案也写出来了，就是 。直接算是 ，但可以线性筛下变成 。

//2021.12.27 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+10;
namespace MAIN{
    int n,m;
    int inv[N],pw[N],Pw[N];
    int prim[N/10],tot;
    bool vis[N];
    inline void MAIN(){
        n=read(),m=int(Read()%(kcz-1)),inv[0]=inv[1]=Pw[0]=1,Pw[1]=n;
        res fac=1;
        for(res i=2;i<=n;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i),fac=mul(fac,i),Pw[i]=mul(Pw[i-1],n);
        for(res i=2;i<=n;i++)inv[i]=mul(inv[i],inv[i-1]);
        pw[1]=1;
        for(res i=2;i<=n;i++){
            if(!vis[i])prim[++tot]=i,pw[i]=qpow(i,m+1);
            for(res j=1;j<=tot&&prim[j]*i<=n;j++){
                vis[prim[j]*i]=1,pw[prim[j]*i]=mul(pw[prim[j]],pw[i]);
                if(i%prim[j]==0)break;
            }
        }
        res ans=0;
        for(res x=1;x<n;x++)add(ans,mul(mul(Pw[n-x-1],pw[x]),inv[n-x]));
        printf("%d\n",mul(Add(ans,qpow(n,m)),fac));
    }
}

[牛客挑战赛51 G]

solution

口胡：区间加区间求和用权值线段树，加区间则用个 set 以区间左端点排序然后二分进去找到它应在的位置在 LCT 上加边删边，删区间同理。时间复杂度 ？

题面：中文题面不会自己看？

做法：首先简化一下题意，它这个题面跟个鬼一样，还要倒腾半天。

操作一实际上就是对 区间内没被比它更小的区间覆盖到的位置加一个值，操作二则是被覆盖到的加值。其他操作倒是简单了。

题解做法我暂时还没看，不过 wxw 的做法应该暴打了标算。

注意操作一中修改位置的特征，以及区间互不交的特征。可以发现操作一修改的位置实际上就是在 中区间覆盖次数最少的地方。 一旦注意到这个性质，就直接做完了。等价于我们只要维护个区间覆盖次数的最小值以及总和还有一堆标记就好了，这些东西都是平凡的，用权值线段树维护下就好了，时间复杂度 。

//2021.12.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,Q;
    int ls[N*100],rs[N*100],sum[N*100],mn[N*100],cnt[N*100],len[N*100];
    int tag_sum[N*100],tag_mn[N*100],tot,tag_all_sum[N*100];
    int lastans;
    Pair a[N];
    inline void change_sum(const res &rt,const res &v){
        add(sum[rt],mul(v,cnt[rt])),add(tag_sum[rt],v);
    }
    inline void change_mn(const res &rt,const res &v){
        mn[rt]+=v,tag_mn[rt]+=v;
    }
    inline void change_all_sum(const res &rt,const res &v){
        add(sum[rt],mul(v,len[rt])),add(tag_all_sum[rt],v);
    }
    inline void pushdown(const res &rt){
        change_mn(ls[rt],tag_mn[rt]),change_all_sum(ls[rt],tag_all_sum[rt]);
        change_mn(rs[rt],tag_mn[rt]),change_all_sum(rs[rt],tag_all_sum[rt]);
        if(mn[ls[rt]]==mn[rt])change_sum(ls[rt],tag_sum[rt]);
        if(mn[rs[rt]]==mn[rt])change_sum(rs[rt],tag_sum[rt]);
        tag_mn[rt]=tag_sum[rt]=tag_all_sum[rt]=0;
    }
    inline void pushup(const res &rt){
        sum[rt]=Add(sum[ls[rt]],sum[rs[rt]]);
        mn[rt]=min(mn[ls[rt]],mn[rs[rt]]);
        cnt[rt]=0;
        if(mn[rt]==mn[ls[rt]])cnt[rt]=cnt[ls[rt]];
        if(mn[rt]==mn[rs[rt]])cnt[rt]+=cnt[rs[rt]];
    }
    int query_mn(res &rt,res l,res r,const res &L,const res &R){
        if(!rt)rt=++tot,len[rt]=cnt[rt]=r-l+1;
        if(L<=l&&r<=R)return mn[rt];
        res mid=(l+r)>>1,ret=n;
        if(!ls[rt])ls[rt]=++tot,len[ls[rt]]=cnt[ls[rt]]=mid-l+1;
        if(!rs[rt])rs[rt]=++tot,len[rs[rt]]=cnt[rs[rt]]=r-mid;
        pushdown(rt);
        if(L<=mid)ret=query_mn(ls[rt],l,mid,L,R);
        if(R>mid)ret=min(ret,query_mn(rs[rt],mid+1,r,L,R));
        pushup(rt);
        return ret;
    }
    void modify_sum(res &rt,res l,res r,const res &L,const res &R,const res &v,const res &lim){
        if(!rt)rt=++tot,len[rt]=cnt[rt]=r-l+1;
        if(L<=l&&r<=R){
            if(mn[rt]==lim)change_sum(rt,v);
            return;
        }
        res mid=(l+r)>>1;
        if(!ls[rt])ls[rt]=++tot,len[ls[rt]]=cnt[ls[rt]]=mid-l+1;
        if(!rs[rt])rs[rt]=++tot,len[rs[rt]]=cnt[rs[rt]]=r-mid;
        pushdown(rt);
        if(L<=mid)modify_sum(ls[rt],l,mid,L,R,v,lim);
        if(R>mid)modify_sum(rs[rt],mid+1,r,L,R,v,lim);
        pushup(rt);
    }
    void modify_mn(res &rt,res l,res r,const res &L,const res &R,const res &v){
        if(!rt)rt=++tot,len[rt]=cnt[rt]=r-l+1;
        if(L<=l&&r<=R){
            change_mn(rt,v);
            return;
        }
        res mid=(l+r)>>1;
        if(!ls[rt])ls[rt]=++tot,len[ls[rt]]=cnt[ls[rt]]=mid-l+1;
        if(!rs[rt])rs[rt]=++tot,len[rs[rt]]=cnt[rs[rt]]=r-mid;
        pushdown(rt);
        if(L<=mid)modify_mn(ls[rt],l,mid,L,R,v);
        if(R>mid)modify_mn(rs[rt],mid+1,r,L,R,v);
        pushup(rt);
    }
    void modify_all_sum(res &rt,res l,res r,const res &L,const res &R,const res &v){
        if(!rt)rt=++tot,len[rt]=cnt[rt]=r-l+1;
        if(L<=l&&r<=R){
            change_all_sum(rt,v);
            return;
        }
        res mid=(l+r)>>1;
        if(!ls[rt])ls[rt]=++tot,len[ls[rt]]=cnt[ls[rt]]=mid-l+1;
        if(!rs[rt])rs[rt]=++tot,len[rs[rt]]=cnt[rs[rt]]=r-mid;
        pushdown(rt);
        if(L<=mid)modify_all_sum(ls[rt],l,mid,L,R,v);
        if(R>mid)modify_all_sum(rs[rt],mid+1,r,L,R,v);
        pushup(rt);
    }
    int query_sum(res &rt,res l,res r,const res &L,const res &R){
        if(!rt)rt=++tot,len[rt]=cnt[rt]=r-l+1;
        if(L<=l&&r<=R)return sum[rt];
        res mid=(l+r)>>1,ret=0;
        if(!ls[rt])ls[rt]=++tot,len[ls[rt]]=cnt[ls[rt]]=mid-l+1;
        if(!rs[rt])rs[rt]=++tot,len[rs[rt]]=cnt[rs[rt]]=r-mid;
        pushdown(rt);
        if(L<=mid)ret=query_sum(ls[rt],l,mid,L,R);
        if(R>mid)add(ret,query_sum(rs[rt],mid+1,r,L,R));
        pushup(rt);
        return ret;
    }
    int RT;
    inline void MAIN(){
        n=read(),Q=read();
        a[1]=mp(1,n),modify_mn(RT,1,n,1,n,1);
        while(Q--){
            res opt=read();
            if(opt==1){
                res k=read(),val=read();
                res lim=query_mn(RT,1,n,a[k].fi,a[k].se);
                modify_sum(RT,1,n,a[k].fi,a[k].se,val,lim);
            }
            else if(opt==2){
                res k=read(),val=read();
                res lim=query_mn(RT,1,n,a[k].fi,a[k].se);
                modify_sum(RT,1,n,a[k].fi,a[k].se,kcz-val,lim);
                modify_all_sum(RT,1,n,a[k].fi,a[k].se,val);
            }
            else if(opt==3){
                res l=read(),r=read();
                print(lastans=query_sum(RT,1,n,l,r)),sr[++C]='\n';
            }
            else if(opt==4){
                res l=read()^lastans,r=read()^lastans,k=read();
                a[k]=mp(l,r),modify_mn(RT,1,n,l,r,1);
            }
            else {
                res k=read();
                modify_mn(RT,1,n,a[k].fi,a[k].se,-1),a[k]=mp(0,0);
            }
        }
    }
}

[ABC206 F]

solution

题面：有 段区间 。A 和 B 两人每次可以选择一个区间，A 先手。要求选择的区间不能相交，谁先不能选谁输。问最后谁赢。

做法：复习下博弈论。

令 为 游戏局面下的 sg​ 函数，那么转移就是从 和 两个局面过来，即 ，记忆化搜索下即可。时间复杂度 。

//2021.6.20 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=128;
namespace MAIN{
    int n;
    Pair a[N];
    int S[N][N];
    int sg(res l,res r){
        if(l==r)return 0;
        if(S[l][r]!=-1)return S[l][r];
        bool vis[N];
        for(res i=0;i<=127;i++)vis[i]=0;
        for(res i=1;i<=n;i++)if(l<=a[i].fi&&a[i].se<=r)vis[sg(l,a[i].fi)^sg(a[i].se,r)]=1;
        for(res i=0;;i++)if(!vis[i])return S[l][r]=i;
    }
    inline void MAIN(){
        res T=read();
        while(T--){
            n=read();
            for(res i=1;i<=n;i++)a[i].fi=read(),a[i].se=read();
            for(res i=1;i<=100;i++)for(res j=1;j<=100;j++)S[i][j]=-1;
            puts(sg(1,100)?"Alice":"Bob");
        }
    }
}

[CF1539 E]

solution

题面：有两个数 ，初始为 。每次给你一个限制：必须将其中一个数变为 ，而且要满足 ，问是否存在一组解。

做法：容易写出一个 的暴力，即 为第 次选择变了 ，第 次选择变了 ，转移显然。

考虑优化这个暴力。发现每次能转移到 （或 ）就尽量转移，这样的贪心是正确的（这是因为从后往前转移时，若可以换到 的话，则后续转移不用再考虑后面对 的限制，所以这样转移肯定不劣）。于是就将复杂度优化到 了。

构造答案的话，按照上面贪心的思路逆着来即可。

复杂度 。

//2021.6.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m;
    int k[N],al[N],ar[N],bl[N],br[N];
    int L[N][2],R[N][2];
    inline bool ck(const res &i,const res &x,const res &y){
        return al[i]<=x&&x<=bl[i]&&ar[i]<=y&&y<=br[i];
    }
    inline bool Ck(const res &i,const res &x,const res &y){
        return (L[i][0]<=x&&x<=L[i][1])||(R[i][0]<=y&&y<=R[i][1]);
    }
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)k[i]=read(),al[i]=read(),bl[i]=read(),ar[i]=read(),br[i]=read();
        L[n+1][0]=0,L[n+1][1]=m,R[n+1][0]=0,R[n+1][1]=m;
        for(res i=n;i>=1;i--){
            L[i][0]=m+1,L[i][1]=-1,R[i][0]=m+1,R[i][1]=-1;
            if(al[i]<=k[i]&&k[i]<=bl[i]){
                if(L[i+1][0]<=k[i]&&k[i]<=L[i+1][1])R[i][0]=ar[i],R[i][1]=br[i];
                else R[i][0]=max(R[i+1][0],ar[i]),R[i][1]=min(R[i+1][1],br[i]);
            }
            if(ar[i]<=k[i]&&k[i]<=br[i]){
                if(R[i+1][0]<=k[i]&&k[i]<=R[i+1][1])L[i][0]=al[i],L[i][1]=bl[i];
                else L[i][0]=max(L[i+1][0],al[i]),L[i][1]=min(L[i+1][1],bl[i]);
            }
        }
        if(Ck(1,0,0)){
            puts("Yes");
            res y=0;
            for(res i=1;i<=n;i++){
                if(ck(i,k[i],y)&&Ck(i+1,k[i],y))printf("%d ",0);
                else y=k[i],printf("%d ",1);
            }
        }
        else puts("No");
    }
}

[CF1539 F]

solution

题面：有 个正整数数 。当 时，定义 在 中的距离为 ，其中 为 在 排第几大（若有相同统一当最大），求 在所有区间中的最大距离。

做法：设 中小于 的数有 ，等于的有 个，大于有 个，那么此时 的距离为 。于是可将 从小到大（以及从大到小）枚举，使所有小于 的数（以及大于）变为 ，其余为 。因此，原命题等价于维护最大子段和。由于必须包含 这个位置，因此用线段树维护最大最小前缀和即可。

时间复杂度 。

//2021.6.24 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    int a[N];
    vector<int> vec[N];
    struct P{
        int mx,mn;
        P() {}
        P(res a,res b) {mx=a,mn=b;}
        inline void init(const res &p){
            mx=mn=-p;
        }
        inline P operator + (const RG P &x){
            RG P y;
            y.mx=max(mx,x.mx),y.mn=min(mn,x.mn);
            return y;
        }
        inline void change(const res &val){
            mx+=val,mn+=val;
        }
    }tr[N<<2];
    int laz[N<<2];
    inline void pushup(const res &rt){
        tr[rt]=tr[rt<<1]+tr[rt<<1|1];
    }
    void build(res rt,res l,res r){
        laz[rt]=0;
        if(l==r){tr[rt].init(l);return;}
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
    }
    inline void pushdown(const res &rt){
        if(laz[rt])tr[rt<<1].change(laz[rt]),laz[rt<<1]+=laz[rt],tr[rt<<1|1].change(laz[rt]),laz[rt<<1|1]+=laz[rt],laz[rt]=0;
    }
    void modify(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){tr[rt].change(2),laz[rt]+=2;return;}
        res mid=(l+r)>>1;
        pushdown(rt);
        if(L<=mid)modify(rt<<1,l,mid,L,R);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
    }
    P query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return tr[rt];
        res mid=(l+r)>>1;
        RG P ret=P(-inf,inf);
        pushdown(rt);
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)ret=ret+query(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
        return ret;
    }
    int ans[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read(),vec[a[i]].pb(i);
        build(1,0,n);
        for(res i=1;i<=n;i++){
            for(auto x:vec[i])modify(1,0,n,x,n);
            for(auto x:vec[i])ans[x]=(query(1,0,n,x,n).mx-query(1,0,n,0,x-1).mn-1)/2;
        }
        build(1,0,n);
        for(res i=n;i;i--){
            for(auto x:vec[i])modify(1,0,n,x,n);
            for(auto x:vec[i])ans[x]=max(ans[x],(query(1,0,n,x,n).mx-query(1,0,n,0,x-1).mn)/2);
        }
        for(res i=1;i<=n;i++)printf("%d ",ans[i]);
    }
}

[ULR #2]

summary

实况：一题都不会，精彩。

[ULR #2 A]

solution

题面：中文题面不会还要写吧，不会吧不会吧。

做法：考虑一种其他做法：设 表示当前总长为 第 位的贡献次数，转移是枚举 ，，打表可发现需用的状态数在合理的范围内，于是差分后就可以做了。

不过这个做法有点不好实现，建议使用官方题解。

标准做法是考虑将每次操作合并成一个大操作，使得最后只剩下一个数，然后考虑这种操作序列的个数。推出式子后，注意到 可以利用差分快速求出，于是就可以做到 或 了。

代码是 的。

//2021.6.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    namespace GenHelper{
        unsigned z1,z2,z3,z4,b;
        unsigned read(){
            b=((z1<<6)^z1)>>13;
            z1=((z1&4294967294U)<<18)^b;
            b=((z2<<2)^z2)>>27;
            z2=((z2&4294967288U)<<2)^b;
            b=((z3<<13)^z3)>>21;
            z3=((z3&4294967280U)<<7)^b;
            b=((z4<<3)^z4)>>12;
            z4=((z4&4294967168U)<<13)^b;
            return (z1^z2^z3^z4);
        }
        void srand(int x){
            z1=x;
            z2=(~x)^0x233333333U;
            z3=x^0x1234598766U;
            z4=(~x)+51;
        }
    }
    int n,seed;
    unsigned H[N],sumH[N],D[N],S[N],ans;
    inline void MAIN(){
        n=read(),seed=read(),GenHelper::srand(seed),H[1]=1;
        for(res i=1;i<=n;i++)for(res j=i+i;j<=n;j+=i)H[j]+=H[i];
        for(res i=1;i<=n;i++)sumH[i]=sumH[i-1]+H[i];
//        for(res i=0;i<=n;i++)printf("%d\n",sumH[i]);
        for(res i=0;i<=n;i++)D[i]=sumH[i]*2-1;
        for(res i=0;i<n;i++)S[i]=D[min(i,n-i-1)]+sumH[max(i,n-i-1)]+(i==0)+(i==n-1);
        for(res i=0;i<n;i++)ans+=GenHelper::read()*S[i];
        cout<<ans<<endl;
    }
}

[ULR #2 B]

solution

题面：中文题面不会还要写吧，不会吧不会吧。

做法：由于 ，其中 ,, 当且仅当 ， 为 删去第 行第 列的代数余子式。以及