2024 七月杂题 上

怎么今年都过了一半了还是这么菜。

P10220 [省选联考 2024] 迷宫守卫

传送门

题意

• 有一棵 $2^{n+1}-1$ 个结点的满二叉树。叶结点权值构成一个排列。
• 现在 Bob 要 dfs 这棵树，他在每个结点可以选择先进入左儿子或右儿子，最小化 dfs 序上叶结点权值的字典序。对于每个非叶结点 $u$，Alice 可以花费 $w_u$ 的代价将其涂色使得 Bob 必须先进入左儿子。Alice 一共可以花费 $K$ 的代价。她想最大化 Bob dfs 序上叶结点权值的字典序。
• Alice 操作完毕后 Bob 再操作，在双方都采取最优策略的情况下，求最终叶结点序列。
• $1\le n\le 16$，整个操作过程中所有数不会爆 long long。

题解

幽默 sfsl 没想清楚就写怒调一上午。

首先“最小化/最大化字典序”是经典贪心，每次可以不计后效的最小化/最大化第一个没确定的。

那么先考虑 Bob 如何在 Alice 的影响下最小化第一个叶子。容易想到一个 DP。设 $dp_{i,j}$ 表示在结点 $i$ 的子树中，要让 Bob 走到当前子树大于等于第 $j$ 小的叶子 Alice 需要花费的最小代价是多少。对于内存问题，可以将每一层存成长度为 $2^n$ 的数组，空间复杂度就是 $O(n2^n)$。考虑如何转移。

若 Bob 进入左儿子，只有两种可能，一是 Alice 给当前结点涂了色，二是进左儿子更优一点。

设左儿子中的第 $j$ 大是当前结点的第 $j^{\ast}$ 大，于是找到右儿子第一个大于 $j$ 的点 $j'$，有：

$$ dp_{i,j^{\ast}}=dp_{ls,j}+\min(dp_{rs,j'},w_i) $$

对于右儿子转移到当前结点，容易发现只可能是右儿子更优一点，因为 Alice 不能要求 Bob 先进右儿子。转移略。

那么就能找到 Bob 进入的第一个叶结点了，简单二分即可。一个显然的想法是从这个点一层一层往上跳，每次走进另一个分支做一遍相同的子问题（如果是从 $w_i$ 转移就完全相同，否则考虑能不能从更大的 $j''$ 转移过来）。但是这个有点问题啊，有可能最小值是从 $w_i$ 转移过来的，但是 $m$ 足够从一个 $j'$ 转移过来。这种时候从 $j'$ 转移反而会更优一点。这种情况特殊考虑一下即可。

每个结点只会访问 $O(1)$ 次，结点内操作是 $O(\log n)$ 的，所以瓶颈在预处理，复杂度 $O(n2^n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1<<16|5,inf=1e18;
i64 n,m,w[N],q[N];
i64 dp[17][N];
pii p[17][N],pre[17][N];
void work(i64 l,i64 r,i64 dpt,i64 id){
    if(l==r){
        dp[dpt][l]=0;
        return;
    }
    i64 mid=(l+r)>>1;
    work(l,mid,dpt+1,id<<1);work(mid+1,r,dpt+1,id<<1|1);
    i64 pl=l,pr=mid+1;
    forup(i,l,r){
        if(pr>r||(pl<=mid&&p[dpt+1][pl].fi<p[dpt+1][pr].fi)){
            if(pr<=r&&dp[dpt+1][pr]<=w[id]){
                dp[dpt][i]=dp[dpt+1][pl]+dp[dpt+1][pr];
                pre[dpt][i]=mkp(pl,pr);
            }else{
                dp[dpt][i]=dp[dpt+1][pl]+w[id];
                pre[dpt][i]=mkp(pl,-pr);
            }
            ++pl;
        }else{
            if(pl==mid+1){
                dp[dpt][i]=inf;
                pre[dpt][i]=mkp(0,0);
            }else{
                dp[dpt][i]=dp[dpt+1][pr]+dp[dpt+1][pl];
                pre[dpt][i]=mkp(pl,pr);
            }
            ++pr;
        }
    }
    fordown(i,r,l){
        if(dp[dpt][i]>inf) dp[dpt][i]=inf;
        if(i<r) dp[dpt][i]=min(dp[dpt][i],dp[dpt][i+1]);
    }
    merge(p[dpt+1]+l,p[dpt+1]+mid+1,p[dpt+1]+mid+1,p[dpt+1]+r+1,p[dpt]+l);
}
vector<i64> ans;
void gans(i64 l,i64 r,i64 dpt,i64 tp){
    if(l==r){
        ans.push_back(q[l]);
        return;
    }
    i64 L;
    if(tp==-1){
        L=upper_bound(dp[dpt]+l,dp[dpt]+r+1,m)-dp[dpt]-1;
        m-=dp[dpt][L];
    }else{
        m+=dp[dpt][tp];
        L=upper_bound(dp[dpt]+l,dp[dpt]+r+1,m)-dp[dpt]-1;
        m-=dp[dpt][L];
    }
    ans.push_back(q[p[dpt][L].se]);
    stack<pair<i64,pii> > stk;
    forup(d,dpt,n-1){
        i64 mid=(l+r)>>1;
        stk.push(mkp(L,mkp(l,r)));
        if(p[d][L].se>mid){
            l=mid+1;L=pre[d][L].se;
        }else{
            if(pre[d][L].se<0){
                r=mid;L=pre[d][L].fi;
            }else{
                r=mid;L=pre[d][L].fi;
            }
        }
    }
    i64 d=n-1;
    while(stk.size()){
        i64 L=stk.top().fi,l=stk.top().se.fi,r=stk.top().se.se,mid=(l+r)>>1;stk.pop();
        if(p[d][L].se>mid){
            gans(l,mid,d+1,pre[d][L].fi);
        }else{
            if(pre[d][L].se<0){
                if(-pre[d][L].se<=r&&dp[d+1][pre[d][L].fi]+dp[d+1][-pre[d][L].se]-dp[d][L]<=m){
                    m-=(dp[d+1][pre[d][L].fi]+dp[d+1][-pre[d][L].se]-dp[d][L]);
                    gans(mid+1,r,d+1,-pre[d][L].se);
                }else{
                    gans(mid+1,r,d+1,0);
                }
            }else{
                gans(mid+1,r,d+1,pre[d][L].se);
            }
        }
        --d;
    }
}
void solve(){
    n=read();m=read();
    forup(i,1,(1<<n)-1){
        w[i]=read();
    }
    forup(i,0,(1<<n)-1){
        p[n][i].fi=q[i]=read();
        p[n][i].se=i;
    }
    work(0,(1<<n)-1,0,1);
    ans.clear();
    gans(0,(1<<n)-1,0,0);
    for(auto i:ans){
        printf("%lld ",i);
    }puts("");
}
signed main(){
    i64 t=read();
    while(t--){
        solve();
    }
}

P10537 [APIO2024] 九月

传送门

题意

• 有一棵 $n$ 个结点，以 $0$ 为根的树，每天会重复若干次“删掉一个叶子”的操作，最终删的只剩下根节点。
• 有 $m$ 个序列，都是将每天删掉的叶子乱序排列后并排放在一起得到的。问最多有多少天。
• $1\le n\le 10^5,1\le m\le 5$，带多测，但是函数交互。

题解

纯水题，但有唐人 WA 一发。

首先每个序列中一天占的下标区间肯定是一样的。那么每个点出现在序列中的最前位置和最后位置之间肯定是同一天。

因为每个点只能在它的后代删完之后删，所以一个点与它子树内的最后位置肯定也是同一天。

然后随便维护一下就好了，我用的并查集，复杂度 $O(n\alpha(n))$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int l[N],r[N];
vector<int> e[N];
void dfs(int x){
    for(auto i:e[x]){
        dfs(i);
        r[x]=max(r[x],r[i]);
    }
}
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int solve(int n,int m,vector<int> f,vector<vector<int>> s){
    forup(i,0,n-1){
        l[i]=n;r[i]=-1;
        e[i].clear();
        fa[i]=i;
    }
    forup(i,1,n-1){
        e[f[i]].push_back(i);
    }
    forup(i,0,m-1){
        forup(j,0,n-2){
            l[s[i][j]]=min(l[s[i][j]],j);
            r[s[i][j]]=max(r[s[i][j]],j);
        }
    }
    dfs(0);
    forup(i,1,n-1){
        for(int j=getfa(l[i]);j<r[i];j=getfa(j)){
            fa[j]=getfa(j+1);
        }
    }
    int res=0;
    forup(i,0,n-2){
        if(fa[i]==i) ++res;
    }
    return res;
}
//signed main(){
//  int t=read();
//  while(t--){
//      int n=read(),m=read();
//      vector<int> f(n);
//      vector<vector<int>> s(m,vector<int>(n));
//      f[0]=-1;
//      forup(i,1,n-1) f[i]=read();
//      forup(i,0,m-1){
//          forup(j,0,n-2){
//              s[i][j]=read();
//          }
//      }
//      printf("%d\n",solve(n,m,f,s));
//  }
//}

P9481 [NOI2023] 贸易

传送门

题意

• 有一 $2^n-1$ 个点的满二叉树，每条边都是指向父亲的带权有向边。
• 另有 $m$ 条带权有向非树边，每条非树边都从 $u$ 指向它子树内的某个 $v$。
• 令 $dis(u,v)$ 表示 $u$ 到 $v$ 的最短路径长度，若 $u$ 不可达 $v$ 则取 $0$。求 $\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}dis(i,j)$。
• $2\le n\le 18,1\le m\le 2^n$，所有边权在 $10^9$ 以内。

题解

由于非树边都是前向边（即无横叉边），那么显然任意两点间的路径都要经过其 $\mathrm{lca}$，那么容易想到枚举 $\mathrm{lca}$ 统计跨子树的答案。下面考虑从点 $u$ 的左子树经过点 $u$ 到达点 $u$ 右子树的路径。（下文没提，但是注意统计以 $u$ 为起点/终点的路径）。

容易发现，任意一条路径必定形如 $x\rightsquigarrow u\rightsquigarrow a\to b\rightsquigarrow y$，即从 $x$ 出发到达一个深度小于等于 $u$ 的点（这一段必定只走树边，不然显然就有环），经过一条非树边 $a\to b$ 进入 $u$ 的右子树，再经过若干条树边或非树边到达 $y$。

容易发现对于所有 $x$ 和一个固定的 $y$，$u\rightsquigarrow a\to b\rightsquigarrow y$ 的长度都是相同的，否则全都可以换成最短的那个。于是求出 $u$ 到右子树所有点的最短路就能统计了。具体细节略。

但是注意到复杂度问题，如果每次都在全图上跑最短路肯定复杂度会爆（大概是 $O(4^nn)$ 的），一个显然的想法是每次只在 $u$ 的子树内跑最短路。对于 $u\rightsquigarrow a\to b$ 的部分，如果直接在跑的时候加入 $u$ 的祖先，那么每次就会访问一堆没用的边，复杂度会炸掉。一个想法每次枚举 $b$，然后直接找 $b$ 的入边。这样每条边最多被访问 $2n$ 次（在出边和入边时各 $n$ 次，因为每个点至多属于 $n$ 个子树）。

复杂度 $O(n^22^n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=3e5+5,mod=998244353;
const i64 inf=1e18;
int n,m,f[N],sum[N],ans;
i64 len[N];
struct edge{
    int v,w;
};
vector<edge> e1[N],e[N];
void dfs(int id,int dpt){
    sum[id]=len[id]%mod;
    if(dpt==n) return;
    len[id<<1]=len[id]+f[id<<1];
    len[id<<1|1]=len[id]+f[id<<1|1];
    dfs(id<<1,dpt+1);dfs(id<<1|1,dpt+1);
    (sum[id]+=sum[id<<1])%=mod;
    (sum[id]+=sum[id<<1|1])%=mod;
}
int vis[N];
i64 dis[N];
priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> q;
void Get(int dpt,int id,int rt){
    vis[id]=0;
    if(id!=rt){
        dis[id]=inf;
        for(auto i:e1[id]){
            int v=i.v,w=i.w;
            if(v<=rt) dis[id]=min(dis[id],len[rt]-len[v]+w);
        }
        if(dis[id]!=inf&&id!=rt) q.push(mkp(dis[id],id));
    }
    if(dpt==n) return;
    Get(dpt+1,id<<1,rt);
    Get(dpt+1,id<<1|1,rt);
}
void dijkstra(int s){
    while(q.size()) q.pop();
    dis[s]=0;vis[s]=1;
    Get((31^__builtin_clz(s))+1,s,s);
    while(q.size()){
        int u=q.top().se;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:e[u]){
            int v=i.v,w=i.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(mkp(dis[v],v));
            }
        }
        if(u!=s){
            int v=(u>>1),w=f[u];
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(mkp(dis[v],v));
            }
        }
    }
}
pii calc(int id,int dpt){
    pii rr=(dis[id]==inf?mkp(0,0):mkp(int(dis[id]%mod),1));
    if(dpt==n) return rr;
    pii r1=calc(id<<1,dpt+1);
    (rr.fi+=r1.fi)%=mod;
    (rr.se+=r1.se)%=mod;
    r1=calc(id<<1|1,dpt+1);
    (rr.fi+=r1.fi)%=mod;
    (rr.se+=r1.se)%=mod;
    return rr;
}
signed main(){
    n=read();m=read();
    forup(i,2,(1<<n)-1){
        f[i]=read();
    }
    forup(i,1,m){
        int u=read(),v=read(),w=read();
        e[u].push_back(edge{v,w});
        e1[v].push_back(edge{u,w});
    }
    dfs(1,1);
    forup(i,1,(1<<(n-1))-1){
        dijkstra(i);
        int d=(31^__builtin_clz(i))+1,cnt=(1<<(n-d))-1;
        pii rr=calc(i<<1|1,d+1);
        (ans+=1ll*rr.fi*(cnt+1)%mod)%=mod;
        (ans+=1ll*(rr.se+1)*(sum[i<<1]-1ll*len[i]*cnt%mod+mod)%mod)%=mod;
        rr=calc(i<<1,d+1);
        (ans+=1ll*rr.fi*(cnt+1)%mod)%=mod;
        (ans+=1ll*(rr.se+1)*(sum[i<<1|1]-1ll*len[i]*cnt%mod+mod)%mod)%=mod;
    }
    printf("%d\n",ans);
}

P3705 [SDOI2017] 新生舞会

传送门

题意

• 给定一完全二分图，左右部点均为 $n$ 个。每条边有 $a,b$ 两权值。
• 求出一个最大匹配，最大化匹配中的 $\frac{\sum a_{i,j}}{\sum b_{i,j}}$。
• $1\le n\le 100,1\le a_{i,j},b_{i,j}\le 10^4$。

题解

看到最大化某分数考虑一些类似 $01$ 分数规划的东西，二分答案。

设二分出来的答案为 $mid$，简单推式子可得：

$$ \begin{aligned} \frac{\sum a_{i,j}}{\sum b_{i,j}}&\ge mid\\ \sum a_{i,j}&\ge \sum (b_{i,j}\times mid)\\ 0&\ge \sum (b_{i,j}\times mid-a_{i,j}) \end{aligned} $$

然后就转化成了带权二分图最大匹配使得匹配边权值最小。直接费用流即可。

复杂度 $O(n^3 k\log V)$，其中 $k$ 是 SPFA 复杂度里面的那个“通常不大于二 $2$”的常数。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using ld=long double;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f;
const ld eps=1e-7;
int n,a[N][N],b[N][N];
namespace flow{
    struct edge{
        int v,rst;
        ld w;
        int nxt;
    }e[N*N*8];
    int head[N*2],incf[N*2],pre[N*2],vis[N*2],cnte,s,t;
    ld dis[N*N];
    void init(){
        forup(i,1,t){
            head[i]=0;
        }
        cnte=1;
    }
    void adde(int u,int v,int rst,ld w){
        e[++cnte]=edge{v,rst,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,-w,head[v]};head[v]=cnte;
    }
    bool spfa(){
        forup(i,1,t){
            dis[i]=1e18;
        }
        incf[s]=inf;incf[t]=0;
        queue<int> q;dis[s]=0;
        q.push(s);vis[s]=1;
        while(q.size()){
            int u=q.front();q.pop();
            vis[u]=0;
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v,rst=e[i].rst;
                ld w=e[i].w;
                if(!rst||dis[v]<=dis[u]+w) continue;
                dis[v]=dis[u]+w;
                incf[v]=min(incf[u],rst);
                pre[v]=i;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
        return incf[t]!=0;
    }
    pair<int,ld> SSP(){
        ld mnc=0;
        int mxf=0;
        while(spfa()){
            mxf+=incf[t];
            for(int i=t;i!=s;i=e[pre[i]^1].v){
                mnc+=e[pre[i]].w*incf[t];
                e[pre[i]].rst-=incf[t];
                e[pre[i]^1].rst+=incf[t];
            }
        }
        return mkp(mxf,mnc);
    }
}
signed main(){
    n=read();
    flow::s=n*2+1;flow::t=n*2+2;
    forup(i,1,n){
        forup(j,1,n){
            a[i][j]=read();
        }
    }
    forup(i,1,n){
        forup(j,1,n){
            b[i][j]=read();
        }
    }
    ld ll=1,rr=10000,mm;
    forup(i,1,50){
        mm=(ll+rr)/2;
        flow::init();
        forup(i,1,n){
            forup(j,1,n){
                flow::adde(i,j+n,1,mm*b[i][j]-a[i][j]);
            }
        }
        forup(i,1,n){
            flow::adde(flow::s,i,1,0);
            flow::adde(i+n,flow::t,1,0);
        }
        pair<int,ld> res=flow::SSP();
        if(res.se<=0) ll=mm;
        else rr=mm;
    }
    printf("%.6Lf",ll);
}

P1712 [NOI2016] 区间

基础知识掌握不完全，进阶知识完全没掌握。

题意

• 给定 $n$ 个区间 $[l_i,r_i]$，选择一个大小为 $m$ 的区间集合使其全都覆盖某个点（端点也算覆盖）。
• 最小化其中最长区间减去最短区间。
• $1\le n\le 5\times 10^5,1\le m\le 2\times 10^5$，其余数据在 $10^9$ 以内。

题解

妈的好傻逼啊正确思路想到一半给自己否决了去想神秘诡异思路。

首先题意完全能转化成选择至少 $m$ 个区间使得其中至少 $m$ 个覆盖同一个点，然后用大的减小的。这两种问题的最优情况是完全等价的。

显然选择按长度排序后连续的若干个区间是不劣的（对于固定的最短和最长，跳过中间若干个对答案没有影响，还会使得覆盖同一个点的区间数变少）。容易发现对于一个最长区间，选择最长的合法最短区间显然是最优的，并且容易发现对于两最长区间长度 $len_j>len_i$，最长的合法左端点也必有 $len_{j'}\ge len_{i'}$（因为 $i'\sim j$ 的区间集合完全包含 $i'\sim i$ 的区间集合，必然合法）。

那么直接双指针就完了，可以用线段树维护是否有 $m$ 个区间覆盖同一个点。

复杂度 $O(n\log n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,m,sz,len[N];
pii rg[N];
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int mx[N<<3],mark[N<<3];
    void PushUp(int id){
        mx[id]=max(mx[id<<1],mx[id<<1|1]);
    }
    void PushDown(int id){
        mx[id<<1]+=mark[id];
        mx[id<<1|1]+=mark[id];
        mark[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Update(int L,int R,int X,int l=1,int r=sz,int id=1){
        if(L<=l&&r<=R){
            mark[id]+=X;
            mx[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id);
    }
    int Query(){
        return mx[1];
    }
}mt;
signed main(){
    n=read();m=read();
    vector<int> lsh;
    forup(i,1,n){
        rg[i].fi=read();rg[i].se=read();
        lsh.push_back(rg[i].fi);lsh.push_back(rg[i].se);
    }
    sort(rg+1,rg+n+1,[&](pii a,pii b){
        return a.se-a.fi<b.se-b.fi;
    });
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    sz=lsh.size();
    forup(i,1,n){
        len[i]=rg[i].se-rg[i].fi;
        rg[i].fi=lower_bound(lsh.begin(),lsh.end(),rg[i].fi)-lsh.begin()+1;
        rg[i].se=lower_bound(lsh.begin(),lsh.end(),rg[i].se)-lsh.begin()+1;
    }
    int pl=1,ans=inf;
    forup(i,1,n){
        mt.Update(rg[i].fi,rg[i].se,1);
        while(mt.Query()>=m){
            ans=min(ans,len[i]-len[pl]);
            mt.Update(rg[pl].fi,rg[pl].se,-1);
            ++pl;
        }
    }
    if(ans!=inf){
        printf("%d\n",ans);
    }else{
        puts("-1");
    }
}

P4121 [WC2005] 双面棋盘

传送门

题意

• 有一个 $n\times n$ 由黑白格子构成的棋盘，有 $m$ 个操作，每个操作为翻转某个格子（黑变白，白变黑）。
• 每次操作后询问黑色四连通块和白色四连通块的数量。
• $1\le n\le 200,1\le m\le 10^4$

题解

挺版的。

首先显然黑白是独立的，那么不妨只看黑色的。那么每个操作就是“加入”或者“删除”某个黑点。

那么就是一个很版的线段树分治了。可撤销并查集维护即可。另外容易发现黑白显然可以一起维护。

复杂度 $O((n^2+m)\log m\log n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=205,inf=0x3f3f3f3f;
int n,m,a[N][N],b[N][N];
vector<int> cg[N][N];
#define po(x,y) (((x)-1)*n+(y))
int fa[N*N],sz[N*N],cnt[2];
stack<pair<pii,int>> stk;
int getfa(int x){return x==fa[x]?x:getfa(fa[x]);}
void merge(int u,int v,int co){
    u=getfa(u);v=getfa(v);
    if(u==v) return;
    if(sz[u]>sz[v]) swap(u,v);
    fa[u]=v;sz[v]+=sz[u];
    --cnt[co];
    stk.push(mkp(mkp(u,v),co));
}
void rback(int Tm){
    while((int)stk.size()>Tm){
        int u=stk.top().fi.fi,v=stk.top().fi.se,co=stk.top().se;stk.pop();
        fa[u]=u;sz[v]-=sz[u];++cnt[co];
    }
}
int nxt[4][2]={
    {0,1},{1,0},{0,-1},{-1,0}
};
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    vector<pair<pii,int> > node[50000];
    void Update(int L,int R,pair<pii,int> nd,int l=1,int r=m,int id=1){
        if(L>R) return;
        if(L<=l&&r<=R){
            node[id].push_back(nd);
            return;
        }
        if(L<=mid) Update(L,R,nd,lson);
        if(mid< R) Update(L,R,nd,rson);
    }
    void Solve(int l=1,int r=m,int id=1){
        int nt=stk.size();
        for(auto i:node[id]){
            int x=i.fi.fi,y=i.fi.se,co=i.se;
            b[x][y]=co;++cnt[co];
            forup(j,0,3){
                int nx=x+nxt[j][0],ny=y+nxt[j][1];
                if(nx<1||ny<1||nx>n||ny>n||b[nx][ny]!=co) continue;
                merge(po(x,y),po(nx,ny),co);
            }
        }
        if(l==r){
            printf("%d %d\n",cnt[1],cnt[0]);
        }else{
            Solve(lson);Solve(rson);
        }
        rback(nt);
        for(auto i:node[id]){
            int x=i.fi.fi,y=i.fi.se,co=i.se;
            b[x][y]=-1;--cnt[co];
        }
    }
};
SegTree mt;
signed main(){
    n=read();
    forup(i,1,n){
        forup(j,1,n){
            a[i][j]=read();
            b[i][j]=-1;
            fa[po(i,j)]=po(i,j);sz[po(i,j)]=1;
            cg[i][j].push_back(1);
        }
    }
    m=read();
    forup(i,1,m){
        int x=read(),y=read();
        cg[x][y].push_back(i);
    }
    forup(i,1,n){
        forup(j,1,n){
            cg[i][j].push_back(m+1);
            int sz=cg[i][j].size(),c=a[i][j];
            forup(k,0,sz-2){
                mt.Update(cg[i][j][k],cg[i][j][k+1]-1,mkp(mkp(i,j),c));
                c^=1;
            }
        }
    }
    mt.Solve();
}

CF1221F Choose a Square

传送门

题意

• 有一平面，其上有 $n$ 个点，每个点有权值。
• 现在你需要选择一个矩形 $(x_1,y_1,x_2,y_2)$，要求 $x_1=y_1,x_2=y_2$。令一个矩形的权值为其覆盖（包含边缘）的点权值和减去其边长。最大化权值，输出方案。
• $1\le n\le 5\times 10^5$，坐标在 $[0,10^9]$ 中，点权在 $[-10^6,10^6]$ 中。

题解

容易发现这个选矩形就是个幌子，实际上可以看做是在 $y=x$ 这条直线上选一个区间。那么用 $[l,r]$ 表示直线 $y=x$ 上横坐标在 $[l,r]$ 区间内的一段。

容易发现一个点 $(x,y)$（设 $x\le y$）会对 $l\le x,r\ge y$ 的区间 $[l,r]$ 产生贡献。于是就转化成了“$[l,r]$ 的权值是其覆盖的区间权值和减去 $r-l$”的问题。

这个很显然可以把所有区间挂到右端点，每个区间就是一个前缀加（这个需要离散化）。对于“减去 $r-l$”的问题，每次再做一个前缀减即可。复杂度 $O(n\log n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=5e5+5,inf=1e18;
i64 n,x[N],y[N],v[N],sz,ans,ax,ay;
vector<i64> lsh;
vector<pii> nd[N<<1];
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 mx[N<<3],po[N<<3],mark[N<<3];
    void PushUp(i64 id){
        if(mx[id<<1]>mx[id<<1|1]){
            mx[id]=mx[id<<1];
            po[id]=po[id<<1];
        }else{
            mx[id]=mx[id<<1|1];
            po[id]=po[id<<1|1];
        }
    }
    void Build(i64 l=0,i64 r=sz,i64 id=1){
        if(l==r){
            po[id]=l;
            mx[id]=0;
            return;
        }
        Build(lson);Build(rson);
        PushUp(id);
    }
    void PushDown(i64 id){
        mx[id<<1]+=mark[id];
        mx[id<<1|1]+=mark[id];
        mark[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Update(i64 L,i64 R,i64 X,i64 l=0,i64 r=sz,i64 id=1){
        if(L<=l&&r<=R){
            mx[id]+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id);
    }
    pii Query(int L,int R,int l=0,int r=sz,int id=1){
        if(L<=l&&r<=R){
            return mkp(mx[id],po[id]);
        }
        if(mark[id]) PushDown(id);
        pii res=mkp(0,-1);
        if(L<=mid) res=max(res,Query(L,R,lson));
        if(mid< R) res=max(res,Query(L,R,rson));
        return res;
    }
}mt;
signed main(){
    n=read();
    forup(i,1,n){
        x[i]=read(),y[i]=read(),v[i]=read();
        lsh.push_back(x[i]);lsh.push_back(y[i]);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    sz=lsh.size()-1;
    forup(i,1,n){
        x[i]=lower_bound(lsh.begin(),lsh.end(),x[i])-lsh.begin();
        y[i]=lower_bound(lsh.begin(),lsh.end(),y[i])-lsh.begin();
        if(x[i]<=y[i]){
            nd[y[i]].push_back(mkp(x[i],v[i]));
        }else{
            nd[x[i]].push_back(mkp(y[i],v[i]));
        }
    }
    mt.Build();
    ans=0;
    ax=ay=lsh[sz]+1;
    forup(i,0,sz){
        for(auto j:nd[i]){
            mt.Update(0,j.fi,j.se);
        }
        if(i) mt.Update(0,i-1,lsh[i-1]-lsh[i]);
        pii res=mt.Query(0,i);
        if(res.se!=-1&&res.fi>ans){
            ans=res.fi;
            ax=lsh[res.se];ay=lsh[i];
        }
    }
    printf("%lld\n",ans);
    printf("%lld %lld %lld %lld\n",ax,ax,ay,ay);
}

P5468 [NOI2019] 回家路线

传送门

题意

• 有 $n$ 个站台 $m$ 个航班，第 $i$ 个航班从 $x_i$ 站台到 $y_i$ 站台，$p_i$ 时刻出发并且 $q_i$ 时刻到达。
• 称一个航班序列 $s_1,s_2\dots s_k$ 为一个合法的回家路线当且仅当：
  • $x_{s_1}=1,y_{s_k}=n$
  • 对于所有 $j\in [1,k),y_j=x_{j+1}$，并且 $q_j\le p_{j+1}$
• 对于一个合法的回家路线，它的代价为（$A,B,C$ 均在数据开头给定）：

$$ q_{s_k}+\sum_{j=1}^{k}\left(A\times(p_{s_j}-q_{s_{j-1}})^2+B\times (p_{s_j}-q_{s_{j-1}})+C\right) $$

• 此处钦定 $q_{s_0}=0$。
• 找到代价最小的回家路线，保证有解。
• $1\le n\le 10^5,1\le m\le 2\times 10^5$，其它数据大致在答案不爆 long long 的范围内。

题解

决策单调性做法。

首先以点为状态是不好做的，因为一个点可能有多条入边，很难概括全部信息。不妨以边为状态。

容易想到代价中的 $q_{s_k}$ 可以不管它，最后枚举以 $y_i=n$ 的边 $i$ 统计答案即可。

设 $f_i$ 表示走到边 $i$ 的最小代价。那么转移就形如 $f_i=f_j+w(j,i)$，其中 $w(j,i)=A\times(p_i-q_j)^2+B\times (p_i-q_{s_j})+C$。注意到这个满足四边形不等式，具体证明直接拆式子即可，此处略。于是可以用决策单调性优化。

具体来说，对每个点维护入边序列 $ed_i$ 和出边序列 $pos_i$（别问为什么这样叫，问就是马蜂问题），分别按结束时间 $q_j$ 和开始时间 $p_j$ 排序。决策单调性体现在若两出边 $i_1,i_2$ 满足 $p_{i_1}\le p_{i_2}$，那么它们对应的转移边 $j_1,j_2$ 必定满足 $q_{j_1}\le q_{j_2}$。于是套路地，对每个点用 deque 维护每个入边转移到的出边区间（对出边离散化）即可。

复杂度 $O(m\log m)$，但是写丑了常数巨大。

另外代码里面开的是加强版的数据范围。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1e5+5,inf=1e18;
int n,m;
i64 ans=inf,A,B,C;
i64 calc(int len){
    return A*len*len+B*len+C;
}
struct edge{
    int x,y,s,e,pos;
}seq[1000005];
struct Node{
    int l,r,j;
};
deque<Node> q[N];
vector<int> pos[N];
queue<int> ed[N];
int mp[1000005],vis[1000005];
i64 dp[1000005];
i64 tr(int j,int i){
    if(j==-1) return inf;
    if(seq[j].e>seq[i].s) return inf;
    return dp[j]+calc(seq[i].s-seq[j].e);
}
signed main(){
    n=read();m=read();A=read();B=read();C=read();
    forup(i,1,m){
        seq[i].x=read();seq[i].y=read();seq[i].s=read();seq[i].e=read();
        dp[i]=inf;
    }
    sort(seq+1,seq+m+1,[&](edge a,edge b){
        if(a.s!=b.s) return a.s<b.s;
        return a.e<b.e;
    });
    forup(i,1,m){
        pos[seq[i].x].push_back(i);
        mp[i]=pos[seq[i].x].size()-1;
        seq[i].pos=i;
    }
    sort(seq+1,seq+m+1,[&](edge a,edge b){
        return a.e<b.e;
    });
    forup(i,1,m){
        ed[seq[i].y].push(seq[i].pos);
    }
    sort(seq+1,seq+m+1,[&](edge a,edge b){
        return a.pos<b.pos;
    });
    dp[0]=0;
    seq[0]=edge{1,1,0,0,0};
    q[1].push_back(Node{0,(int)pos[1].size()-1,0});
    forup(i,2,n){
        if(pos[i].size()) q[i].push_back(Node{0,(int)pos[i].size()-1,-1});
    }
    forup(i,1,m){
        int x=seq[i].x,y=seq[i].y,e=seq[i].e;
        while(q[x].front().r<mp[i]) q[x].pop_front();
        int j=q[x].front().j;
        if(j!=-1){
            dp[i]=tr(j,i);
        }
        vis[i]=1;
        if(y!=n){
            while(ed[y].size()&&vis[ed[y].front()]){
                int p=ed[y].front();ed[y].pop();
                int L=pos[y].size(),R=pos[y].size()-1;
                while(q[y].size()&&tr(p,pos[y][q[y].back().l])<tr(q[y].back().j,pos[y][q[y].back().l])){
                    L=q[y].back().l;
                    q[y].pop_back();
                }
                if(q[y].size()&&tr(p,pos[y][q[y].back().r])<tr(q[y].back().j,pos[y][q[y].back().r])){
                    i64 ll=q[y].back().l,rr=q[y].back().r,mm;
                    while(ll<rr){
                        mm=(ll+rr)>>1;
                        if(tr(p,pos[y][mm])<tr(q[y].back().j,pos[y][mm])) rr=mm;
                        else ll=mm+1;
                    }
                    L=ll;
                    q[y].back().r=L-1;
                }
                if(L<=R) q[y].push_back(Node{L,R,p});
            }
        }else{
            ans=min(ans,dp[i]+e);
        }
    }
    printf("%lld\n",ans);
}

P4761 [CERC2014] Vocabulary

传送门

题意

• 给定三个由小写字母和 ? 组成的字符串 $s_1,s_2,s_3$。
• 将问号替换成任意小写字母，问有多少种替换方式使得对于字典序，有 $s_1<s_2<s_3$。
• 有多测，字符串总长小于等于 $10^6$

题解

容易想到 DP，设 $dp_{i,0/1,0/1}$ 表示考虑前 $i$ 位，$s_1$ 是否小于 $s_2$，$s_2$ 是否小于 $s_3$ 的方案数。显然二三维可以状压。

对于转移，别暴力搞，会出人命的。容易想到用矩阵概括，预处理枚举三个数是多少，简单分讨即可得到矩阵中的每一格，然后分别换成 ? 加到（此处指矩阵的线性加）对应的转移里即可。

对于空字符，视为一个比所有字符均小的字符即可，注意 ? 不能替换为空字符。

复杂度 $O(27^3+n\times 4^3)$，但是其实可以压掉一个 $4$，懒得写了。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f,mod=1e9+9;
char str[N];
int n[3],a[3][N];
struct Matrix{
    int c[4][4];
    Matrix(){
        mem(c,0);
    }
    Matrix operator *(const Matrix &r){
        Matrix res;
        forup(i,0,3){
            forup(j,0,3){
                forup(k,0,3){
                    (res.c[i][j]+=1ll*c[i][k]*r.c[k][j]%mod)%=mod;
                }
            }
        }
        return res;
    }
    void operator +=(const Matrix &r){
        forup(i,0,3){
            forup(j,0,3){
                (c[i][j]+=r.c[i][j])%=mod;
            }
        }
    }
};
map<pair<pii,int>,Matrix> trans;
void solve(){
    forup(i,0,2){
        scanf(" %s",str+1);
        n[i]=strlen(str+1);
        forup(j,1,n[i]){
            if(str[j]!='?'){
                a[i][j]=str[j]-'a'+1;
            }else{
                a[i][j]=-1;
            }
        }
    }
    int nn=max({n[0],n[1],n[2]});
    forup(i,0,2){
        forup(j,n[i]+1,nn){
            a[i][j]=0;
        }
    }
    Matrix res;
    res.c[0][0]=1;
    forup(i,1,nn){
        res=res*trans[mkp(mkp(a[0][i],a[1][i]),a[2][i])];
    }
    printf("%d\n",res.c[0][3]);
}
signed main(){
    forup(i,0,26){
        forup(j,0,26){
            forup(k,0,26){
                Matrix nw;
                if(i==j){
                    if(j==k){
                        nw.c[0][0]=nw.c[1][1]=nw.c[2][2]=nw.c[3][3]=1;
                    }else if(j<k){
                        nw.c[0][2]=nw.c[1][3]=nw.c[2][2]=nw.c[3][3]=1;
                    }else{
                        nw.c[2][2]=nw.c[3][3]=1;
                    }
                }else if(i<j){
                    if(j==k){
                        nw.c[0][1]=nw.c[1][1]=nw.c[2][3]=nw.c[3][3]=1;
                    }else if(j<k){
                        nw.c[0][3]=nw.c[1][3]=nw.c[2][3]=nw.c[3][3]=1;
                    }else{
                        nw.c[2][3]=nw.c[3][3]=1;
                    }
                }else{
                    if(j==k){
                        nw.c[1][1]=nw.c[3][3]=1;
                    }else if(j<k){
                        nw.c[1][3]=nw.c[3][3]=1;
                    }else{
                        nw.c[3][3]=1;
                    }
                }
                trans[mkp(mkp(i,j),k)]+=nw;
                if(k) trans[mkp(mkp(i,j),-1)]+=nw;//-1 即 ?
                if(j) trans[mkp(mkp(i,-1),k)]+=nw;
                if(k&&j) trans[mkp(mkp(i,-1),-1)]+=nw;
                if(i) trans[mkp(mkp(-1,j),k)]+=nw;
                if(i&&k) trans[mkp(mkp(-1,j),-1)]+=nw;
                if(i&&j) trans[mkp(mkp(-1,-1),k)]+=nw;
                if(i&&j&&k) trans[mkp(mkp(-1,-1),-1)]+=nw;
            }
        }
    }
    int t=read();
    while(t--){
        solve();
    }
}

P1973 [NOI2011] NOI 嘉年华

传送门

题意

• 有 $n$ 个给定区间 $[l,r)$，你要给序列涂成黑白二色。若一个给定区间颜色相同则给对应颜色 $+1$ 贡献。
• 解决两个问题：
  • 不加任何限制，计算两颜色中贡献较小值的最大值。
  • 对于每个给定区间，限制它必须产生贡献，计算两颜色贡献较小值的最大值。
• $1\le n\le 200$，区间考虑离散化。

题解

首先对于第一问，有简单 DP。设 $f_{i,j}$ 表示考虑序列上 $[1,i]$ 的部分，其中一种颜色的贡献为 $j$ 时另一种颜色的最大贡献，转移考虑枚举上一个断点，然后考虑这一段时加入当前颜色还是另一颜色：

$$ f_{i,j}=\max_{k=1}^{j-1}\begin{Bmatrix}\max(f_{k,j}+w(k,i),f_{k,j-w(k,i)})\end{Bmatrix} $$

其中 $w(l,r)$ 表示被 $[l,r]$ 完全包含的区间数量，是容易 $O(n^3)$ 预处理的。有一点边界情况。

然后考虑第二问，其实就相当于限制区间 $[l_i,r_i)$ 全涂黑，考虑把前后缀的贡献拼起来，设 $g_{i,j}$ 表示考虑序列上 $[i,m]$ 的部分的 $f$（就是后缀版本的 $f$，这里的 $m$ 指离散化后的值域上界），容易发现限制 $[l_i,r_i)$ 涂黑的答案即为：

$$ \max_{L=1}^{l_i}\max_{R=r_i}^m\max_{x=0}^n\max_{y=0}^n\min(x+w(L,R)+y,f_{L,x}+g_{R,y}) $$

就是枚举中间这段涂黑的区间有多长后再枚举左右各有多少个黑区间。

容易发现可以先对于所有 $L,R$ 求出答案，这样就能 $O(n^2)$ 单组询问了。但是对所有 $L,R$ 暴力求是 $O(n^4)$ 的，如何优化？

容易发现对于 $x_2>x_1$，其所对应最优的 $y_2\le y_1$（否则 $pre_{L,x}$ 和 $suf_{R,y}$ 会同时减小，对于较小值而言显然是不优的）。于是就能双指针压掉枚举 $y$ 的一个 $n$ 了。

复杂度 $O(n^3)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=405,inf=0x3f3f3f3f;
int n,val[N][N],pre[N][N],suf[N][N],sz;
int l[N],r[N],f[N][N];
vector<int> pp[N];
int calc(int l,int r,int x,int y){
    return min(x+y+val[l][r],pre[l][x]+suf[r][y]);
}
signed main(){
    vector<int> lsh;
    n=read();
    forup(i,1,n){
        l[i]=read();r[i]=read();
        r[i]=r[i]+l[i];
        lsh.push_back(l[i]);
        lsh.push_back(r[i]);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    sz=lsh.size();
    forup(i,1,n){
        l[i]=lower_bound(lsh.begin(),lsh.end(),l[i])-lsh.begin()+1;
        r[i]=lower_bound(lsh.begin(),lsh.end(),r[i])-lsh.begin()+1;
        pp[r[i]].push_back(l[i]);
    }
    forup(i,1,sz){
        sort(pp[i].begin(),pp[i].end(),greater<int>());
        int cnt=0,pl=i;
        for(auto j:pp[i]){
            while(pl>j){
                val[pl][i]=val[pl][i-1]+cnt;
                --pl;
            }
            ++cnt;
        }
        while(pl>=0){
            val[pl][i]=val[pl][i-1]+cnt;
            --pl;
        }
    }
    mem(pre,-inf);mem(suf,-inf);
    forup(i,1,sz){
        pre[i][0]=suf[i][0]=0;
    }
    forup(i,1,sz){
        forup(j,0,n){
            fordown(k,i-1,1){
                pre[i][j]=max(pre[i][j],pre[k][j]+val[k][i]);
                if(val[k][i]<=j) pre[i][j]=max(pre[k][j-val[k][i]],pre[i][j]);
            }
        }
    }
    fordown(i,sz,1){
        forup(j,0,n){
            forup(k,i+1,sz){
                suf[i][j]=max(suf[i][j],suf[k][j]+val[i][k]);
                if(val[i][k]<=j) suf[i][j]=max(suf[k][j-val[i][k]],suf[i][j]);
            }
        }
    }
    int ans=0;
    forup(i,0,n){
        ans=max(ans,min(pre[sz][i],i));
    }
    printf("%d\n",ans);
    forup(l,1,sz-1){
        forup(r,l+1,sz){
            int x=0;
            fordown(y,n,0){
                while(x<n&&calc(l,r,x+1,y)>calc(l,r,x,y)) ++x;
                f[l][r]=max(f[l][r],calc(l,r,x,y));
            }
        }
    }
    forup(i,1,n){
        int ans=0;
        fordown(L,l[i],1){
            forup(R,r[i],sz){
                ans=max(ans,f[L][R]);
            }
        }
        printf("%d\n",ans);
    }
}

以下为集训内容，先口胡，代码想写了再说

这是分割线，无内容。

QOJ#1279 Goldfish and pikes

传送门

懒得上 QOJ 了，谷上没有的一律挂 vjudge。

题意

• 给定一大小为 $n$ 的可重集。有 $m$ 个修改或询问，每个修改形如加入或删除一个数。
• 每次询问给定两个数 $s,k$ 问从 $s$ 开始，每次选一个没选过且严格小于 $s$ 的数 $w$，使得 $s\gets s+w$，求最少选多少次才能使 $s\ge k$，询问间独立。
• $1\le n\le 3\times 10^5,1\le m\le 10^5,1\le s,k,\le 10^{18}$

题解

首先显然的贪心是每次选最大的严格小于 $s$ 的 $w$。而最好情况就是每次 $s$ 都大约扩展两倍，这样计算次数就是 $O(\log V)$ 的。

但是很显然大部分情况都不能拓展两倍，一个想法是找到第一个 $w'\ge s$（或者直接找到 $k$），然后维护要用多少个 $w$ 拼出 $w'-s$，再加上 $w'$，这样就能直接拓展到一个大于 $s+w'$ 的 $s'$，显然是大于 $2s$ 的。

那么每次就查找值域前缀上最短的后缀，使得总和大于等于 $w'-s$（对于“一个数只能选一次”的限制，考虑计算用过的数的总和），这个可以线段树上二分做到 $O(\log v)$，这里的 $v$ 是离散化后值域，就是 $O(n)$ 级别的。

于是复杂度 $O(m\log n\log V)$，12000ms 应该能随便过。

QOJ#1281 Longest Common Subsequence

传送门

题意

• 给定两个长度分别为 $n,m$ 的序列 $a_i,b_i$，求其最长公共子序列 $c_i$ 的长度，满足 $c_i$ 单调不减。
• $1\le n,m,\le 10^6,1\le a_i,b_i\le 3$

题解

注意到值域只有 $3$，也就是说 $c_i$ 形如一堆 $1$ 加一堆 $2$ 加一堆 $3$。

考虑维护 $a,b$ 含有 $i$ 个 $1$ 的最短前缀长度 $La_i,Lb_i$。和含有 $i$ 个 $3$ 的最短后缀长度 $Ra_i,Rb_i$。设 $Sa_i=\sum_{j=1}^i[a_j=2],Sb_i=\sum_{j=1}^i[b_j=2]$，那么答案即为（钦定 $n<m$）： $$ \max_{i=1}^n\max_{j=1}^n i+j+\min(Sa_{Ra_j-1}-Sa_{La_i},Sb_{Rb_j-1}-Sb_{Lb_i}) $$ 可能需要注意一下边界吧。这样就能简单 $O(n^2)$ 做了，考虑优化。

如果想优化的话显然必须把 $i,j$ 拆开。如果想拆开 $\min$ 的话需要分类讨论，于是先考虑什么时候 $Sa_{Ra_j-1}-Sa_{La_i}\le Sb_{Rb_j-1}-Sb_{Lb_i}$。

简单化式子可得 $Sa_{Ra_j-1}-Sb_{Rb_j-1}\le Sa_{La_i}-Sb_{Lb_i}$，这就达到了把 $i,j$ 拆开的目的。再考虑一下边界，发现还需要满足 $La_i< Ra_j,Lb_i< Rb_j$，容易发现随着 $i$ 的递增，$La_i,Lb_i$ 是不降的，$Ra_i,Rb_i$ 是不增的。那么可以把这两个限制合成一个限制用双指针维护，就变成了一个类似于二维偏序的东西，用树状数组维护 $j+Sa_{Ra_j-1}$ 的最大值，将其与 $i-Sa_{La_i}$ 合并起来即可。

另一种情况把第一个限制反过来即可，具体维护方式是相似的。

复杂度 $O(n\log n)$。

CF1656H Equal LCM Subsets

传送门

题意

• 有两个集合 $A,B$，大小分别为 $n,m$，你需要找两个非空子集 $S_A\subseteq A,S_B\subseteq B$，使得 $\mathrm{lcm}(S_A)=\mathrm{lcm}(S_B)$，其中 $\mathrm{lcm}(S)$ 表示集合 $S$ 中所有数的最小公倍数。
• 判断是否有解并输出方案，带多测，$1\le \sum n,\sum m\le 1000,1\le a_i,b_i\le 4\times 10^{36}$。

题解

首先，$\mathrm{lcm}(S_A)=\mathrm{lcm}(S_B)$ 等价于： $$ \forall a\in S_A,a\mid \mathrm{lcm}(S_B)\land \forall b\in S_B,b\mid \mathrm{lcm}(S_A) $$ 证明比较简单，若满足前者说明 $\mathrm{lcm}(S_B)\ge \mathrm{lcm}(S_A)$，而满足后者说明 $\mathrm{lcm}(S_A)\ge \mathrm{lcm}(S_B)$，于是有 $\mathrm{lcm}(S_B)= \mathrm{lcm}(S_A)$。

而 $a\mid \mathrm{lcm}(S_B)$ 的意思就是对于 $a$ 的质因数分解 $a=\prod p_i^{e_i}$ 中的所有 $i$，均存在至少一个 $b\in S_B$ 满足 $p_i^{e_i}\mid b$（考虑 $\mathrm{lcm}$ 就是每个质因子取到集合中所有元素的最高次项）。于是可以得到 $a\mid \mathrm{lcm}(S_B)\Leftrightarrow a=\mathrm{lcm}(\gcd(a,b))$，其中 $b$ 是 $S_B$ 中的元素。

接下来的想法是若一个 $a\ne \mathrm{lcm}(\gcd(a,b))$（这里的 $b$ 是 $B$ 中的元素），那么显然无论如何 $a$ 都不合法，完全可以将其删去。对于“删去”这个操作，由于 $\mathrm{lcm}$ 不存在逆运算但有结合律，可以考虑用线段树维护。那么对于每个 $b$ 维护一棵线段树，每个结点维护其在 $A$ 上对应区间的 $\mathrm{lcm}(\gcd(a,b))$。同理对每个 $a$ 维护一棵类似的线段树。

由于有 $O(n)$ 次删除，每次影响 $O(n)$ 个线段每次求 $\mathrm{lcm}$ 是 $O(\log W)$ 的，所以复杂度看起来是 $O(n^2\log W\log n)$ 的，看起来不太能过。但其实并不是，由于求 $\mathrm{lcm}$ 的复杂度是 $O(\log \frac{\min(a,b)}{\gcd(a,b)})$ 的（显然嘛，考虑辗转相除法每两次取模至少会使 $\min(a,b)$ 除以二，一共只需要除这么多）。那么其实每个质因子都只会对时间复杂度产生至多一次影响，其实复杂度是 $O(n^2(\log W+\log n))$ 的，还是能轻松通过。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=__uint128_t;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
void print(i64 x,bool p=true){
    if(x==0){
        if(p) putchar('0');
        return;
    }
    print(x/10,false);
    putchar(x%10+'0');
}
const i64 N=1<<10;
i64 n,m,a[N],b[N],va[N],vb[N];
i64 gcd(i64 a,i64 b){
    return b!=0?gcd(b,a%b):a;
}
i64 lcm(i64 a,i64 b){
    if(a==0||b==0) return a+b;
    i64 gg=gcd(a,b);
    return (a/gg)*(b/gg)*gg;
}
struct SegTree{
    i64 val[N<<1];
    void clear(){
        mem(val,0);
    }
    void Update(i64 P,i64 X){
        val[P+N]=X;
        for(i64 i=(P+N)/2;i;i>>=1){
            val[i]=lcm(val[i*2],val[i*2+1]);
        }
//      if(P==m) print(val[1]),putchar('|');
    }
    i64 Query(){
        return val[1];
    }
};
SegTree ta[N],tb[N];
void solve(){
    n=read();m=read();
    forup(i,1,n) a[i]=read();
    forup(i,1,m) b[i]=read();
    forup(i,1,n){
        ta[i].clear();va[i]=0;
        forup(j,1,m){
            ta[i].Update(j,gcd(a[i],b[j]));
        }
//      print(ta[i].val[1]);puts("|");
    }
    forup(i,1,m){
        tb[i].clear();vb[i]=0;
        forup(j,1,n){
            tb[i].Update(j,gcd(a[j],b[i]));
        }
    }
    i64 ca=n,cb=m;
    while(ca>0&&cb>0){
        bool flag=true;
        forup(i,1,n){
            if(!va[i]&&ta[i].Query()!=a[i]){
//              printf("%d %d|\n",(int)ta[i].Query(),(int)a[i]);
                forup(j,1,m){
                    if(!vb[j]) tb[j].Update(i,0);
                }
                va[i]=1;--ca;
                flag=false;
            }
        }
        forup(i,1,m){
            if(!vb[i]&&tb[i].Query()!=b[i]){
//              printf("%d %d|\n",(int)tb[i].Query(),(int)b[i]);
                forup(j,1,n){
                    if(!va[j]) ta[j].Update(i,0);
                }
                vb[i]=1;--cb;
                flag=false;
            }
        }
        if(flag) break;
    }
    if(!ca||!cb){
        puts("NO");
    }else{
        puts("YES");
        i64 cnt=0;
        forup(i,1,n){
            if(!va[i]){
                ++cnt;
            }
        }
        print(cnt);putchar(' ');
        cnt=0;
        forup(i,1,m){
            if(!vb[i]){
                ++cnt;
            }
        }
        print(cnt);puts("");
        forup(i,1,n){
            if(!va[i]){
                print(a[i]);putchar(' ');
            }
        }
        puts("");
        forup(i,1,m){
            if(!vb[i]){
                print(b[i]);putchar(' ');
            }
        }
        puts("");
    }
}
signed main(){
    i64 t=read();
    while(t--){
        solve();
    }
}

QOJ#1178 Clique

传送门

题意

• 给定长度为 $10^6$ 的环状序列上 $n$ 个区间，求最大子集使得子集内任两区间有交。
• $1\le n\le 3000$

题解

感觉很神秘啊。

考虑先枚举一个区间 $p$，设它的左右端点分别为 $lp,rp$，长度为 $len_p$，并且钦定它是所选子集里面最短的区间。一个结论是若某区间 $q$ 同时包含 $p$ 的左右端点（可能是覆盖 $p$，也可能是从另一半圆绕过来），那么任意区间与 $q$ 有交当且仅当与 $p$ 有交（注意 $p$ 是最短的区间），证明分讨即可，此处略。

于是可以先把所有同时包含 $p$ 左右端点的区间选上了。剩下的区间中可能合法的显然全都是包含 $p$ 的其中一个端点的。那么就可以把这样的区间分成两类：包含 $lp$ 的和包含 $rp$ 的。并且每个区间可以被分成“在 $p$ 以内”和“在 $p$ 以外”的两部分。设这两部分的长度分别为 $in_i,out_i$。

首先包含 $lp$ 的肯定两两相交，包含 $rp$ 的也肯定两两相交。所以只需要考虑左右是否相交即可。那么考虑左边的一个区间 $a$ 和右边的一个区间 $b$。若 $a,b$ 相交，显然有 $in_a+in_b\ge len_p\lor out_a+out_b\ge 10^6-len_p$。这玩意就很像个偏序问题。把 $a$ 当成黑点 $(in_a,out_a)$，$b$ 当成白点 $(len_p-in_b,10^6-len_p-out_b)$，显然 $a,b$ 不相交当且仅当 $a$ 在 $b$ 的左下方。那么显然合法方案就是一条单调不升的折线，选完它左下方的白点和右上方的黑点。

这貌似是一个经典 DP，设 $f_{i,j}$ 表示考虑横坐标 $[1,i]$，折线折到 $j$ 的最大贡献。考虑每次维护 $f_i\to f_{i+1}$ 的变化，那么一个白点就是后缀加，黑点就是前缀加，然后折线“向下折”就是取后缀 $\max$，可以线段树维护。

复杂度 $O(n^2\log n)$。

CF1270H Number of Components

传送门

题意

• 给定一个长度为 $n$ 的数组 $a$，$a$ 中的元素两两不同。对于 $i<j$，若 $a_i<a_j$，则在 $i,j$ 间连一条边。
• 有 $q$ 次单点修改，每次修改后输出图中连通块数。
• $1\le n,q,\le 5\times 10^5,1\le a_i\le 10^6$

题解

首先容易发现每个连通块是一段连续的区间，并且下一段区间的最大值小于上一段区间的最小值。

考虑用线段树维护，那么每次合并时考虑两儿子中间的区间是否合并即可。若不发生合并，那么右儿子的最大值 $rmx$ 大于左儿子的最小值 $lmn$，否则左儿子第一个最小值小于 $rmx$ 的区间一直到右儿子最后一个最大值大于 $lmn$ 的区间全合为一个。

然后你会发现这玩意就是 P4198 楼房重建，维护每个结点跨越中点的那个区间（或者没有区间跨越中点时中点左右区间分别的）的最大值和最小值，每次线段树上二分找到合并出来新区间的左右端点，这里为了统计贡献还需要记一下左右儿子对当前区间的贡献（或者合并出来的新区间覆盖了多少个原有区间），注意合并时每次上传应减去在当前节点被合并过的区间，复杂度 $O(n\log n+q\log^2 n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f;
int n,q,a[N];
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int mx[N<<2],mn[N<<2],num[N<<2],bmx[N<<2],bmn[N<<2],lnum[N<<2],rnum[N<<2];
    pii Getnum(int val,int FLAG,int l,int r,int id){
        if(l==r) return mkp(0,mx[id]);
        pii rr;
        if(FLAG){
            if(bmx[id]>val){
                rr=Getnum(min(bmn[id],val),FLAG,rson);
                rr.se=min(rr.se,mn[id<<1]);
            }else{
                rr=Getnum(val,FLAG,lson);
                rr.fi-=(num[id<<1]-lnum[id]);
                rr.fi+=rnum[id];
                if(bmx[id]>bmn[id]) ++rr.fi;//说明区间被合并过
            }
        }else{
            if(bmn[id]<val){
                rr=Getnum(max(bmx[id],val),FLAG,lson);
                rr.se=max(rr.se,mx[id<<1|1]);
            }else{
                rr=Getnum(val,FLAG,rson);
                rr.fi-=(num[id<<1|1]-rnum[id]);
                rr.fi+=lnum[id];
                if(bmx[id]>bmn[id]) ++rr.fi;
            }
        }
        return rr;
    }
    void PushUp(int id,int l,int r){
        mx[id]=max(mx[id<<1],mx[id<<1|1]);mn[id]=min(mn[id<<1],mn[id<<1|1]);
        if(mn[id<<1]>mx[id<<1|1]){
            num[id]=num[id<<1]+num[id<<1|1];
            lnum[id]=num[id<<1];
            rnum[id]=num[id<<1|1];
            bmn[id]=mn[id<<1];bmx[id]=mx[id<<1|1];
        }else{
            pii rr=Getnum(mx[id<<1|1],0,lson);
            bmx[id]=max(rr.se,mx[id<<1|1]);
            lnum[id]=rr.fi;
            rr=Getnum(mn[id<<1],1,rson);
            bmn[id]=min(rr.se,mn[id<<1]);
            rnum[id]=rr.fi;
            num[id]=lnum[id]+rnum[id]+1;
        }
    }
    void Build(int l=1,int r=n,int id=1){
        if(l==r){
            mx[id]=mn[id]=a[l];
            num[id]=1;
            return;
        }
        Build(lson);
        Build(rson);
        PushUp(id,l,r);
    }
    void Update(int P,int X,int l=1,int r=n,int id=1){
        if(l==r){
            mx[id]=mn[id]=X;
            num[id]=1;
            return;
        }
        if(P<=mid) Update(P,X,lson);
        else       Update(P,X,rson);
        PushUp(id,l,r);
    }
    #undef mid
    #undef lson
    #undef rson
}mt;
signed main(){
    n=read();q=read();
    forup(i,1,n){
        a[i]=read();
    }
    mt.Build();
    forup(i,1,q){
        int p=read(),x=read();
        mt.Update(p,x);
        printf("%d\n",mt.num[1]);
    }
}

QOJ#1163 Another Tree Queries Problem

传送门

题意

• 有一棵 $n$ 个点的无根树，每个点带权值 $A_i$，最初为 $0$，有 $q$ 次操作每次操作形如以下三种之一：
• 以 $u$ 为根时 $v$ 的子树 $+1$。
• 链 $+1$。
• 给定 $u$，查询 $\sum_{v=1}^ndis(u,v)\times A_v$。
• $1\le n,q\le 2\times 10^5$。

题解

首先钦定点 $1$ 为根，那么操作 $1$ 就是子树加或者全局加子树减。

看到 $dis(u,v)$ 就拆，于是 $\sum_{v=1}^ndis(u,v)\times A_v=\sum_{v=1}^n(dpt_u+dpt_v-2dpt_{\mathrm{lca}(u,v)})A_v$，其中 $dpt_u$ 是 $u$ 的深度。

把括号拆开，我们就是要维护以下三个东西：

• $dpt_u\sum_{v=1}^nA_v$。
• $\sum_{v=1}^ndpt_v\times A_v$。
• $\sum_{v=1}^n-2dpt_{\mathrm{lca(u,v)}}\times A_v$。

前两个是简单的，第一个只需要维护链长度和子树大小，第二个需要维护链上深度总和和子树内深度总和。考虑第三个。

容易发现这个可以看作 $v$ 给所有祖先加上一个 $A_v$ 的权值（不妨设这个值为 $B_i$，其实就是 $i$ 的子树和），它就等于 $u$ 所有祖先（包含 $u$ 自己）的 $B_i$ 之和乘以 $-2$（这里注意需要钦定根 $1$ 的深度为 $1$）。

首先无论是链加还是子树加，对其最顶端点（子树加的点 $u$，或者链加的 $\mathrm{lca}$）到根的这条链上的贡献是相同的，直接树剖就能简单维护了。

对于子树加，容易发现对子树内某个 $B_i$ 的增加量是 $i$ 的子树大小，相当于区间加另一个固定的数组，可以直接维护。

对于链加，容易发现是一个等差数列，也可以直接维护。

复杂度 $O(n\log^2 n)$，貌似很难写的样子。

Gym#101754A Letters Swap

传送门

题意

• 对于一个只包含 a,b,c 的字符串，定义“好的”字符串如下：
• $\varnothing$ 是好的。
• 若 $s$ 是好的，那么 $a+s+a,b+s+b,c+s+c$ 是好的。
• 若 $s,t$ 均是好的，那么 $s+t$ 是好的。
• 这里加号表示字符串的连接。
• 给定一长度为 $n$ 的字符串 $s$，求有多少组 $(i,j)$，满足交换 $s_i,s_j$ 后，$s$ 是好的。
• $1\le n\le 10^5$

题解

讲题人讲的太神秘了，但是他补充了另一个做法。

这玩意就很像括号序列啊。容易发现对于一对匹配的字符，它们必定一个下标为偶数另一个下标为奇数。

那么构造三个能求逆的不同矩阵 $A,B,C$，对于一个字符 $a$，若它的下标为奇数则替换为 $A$，否则替换为 $A^{-1}$，$b,c$ 同理。显然若序列合法则按顺序把矩阵乘起来能得到单位矩阵 $I$。（另外讲题人的神秘做法是构造矩阵 $A$ 满足 $A\times A=I$，并且把重点放在了如何构造这个上面导致后面我没咋搞懂）。

然后考虑分治，交换分治中点左侧的一个 $s_i$ 和右侧的一个 $s_j$。那么先枚举 $s_i,s_j$ 具体是哪个字符，一共有 $6$ 种情况（对于 $s_i=s_j$ 的情况，显然可以单独处理）。然后能 $O(n')$（这里的 $n'$ 是分治区间的长度）的算出替换某个 $s_i$ 后完整序列开头到分治中心的矩阵积和分治中心到完整序列结尾的矩阵积，预处理分治区间内矩阵前缀积和后缀积即可。对于左右分别存储乘出来的每种矩阵有多少个，左右结合一下乘起来就行（就是右边的需要是左边的逆矩阵，求逆可以 $O(w^3)$，其中 $w$ 是矩阵大小，感觉取 $w=2$ 或 $w=3$ 应该都行）。常数很大，用哈希可以压到 $O(w^3n\log n)$，但是感觉用 map $O(w^3n\log^2n)$ 也能过 6000ms 吧。

CF1548E Gregor and the Two Painters

传送门

题意

• 给定两长度分别为 $n,m$ 的序列 $a_i,b_i$ 和一个参数 $x$，
• 生成一个 $n\times m$ 的黑白矩阵，$(i,j)$ 为黑当且仅当 $a_i+b_j\le x$。
• 求黑色四连通块数量。
• $1\le n,m,a_i,b_i,x\le 2\times 10^5$

题解

考虑一个黑连通块显然存在一个 $a_i+b_j$ 的最小值点（若有多个可以钦定最左上角的一个之类的，这个属于细节问题）。那么考虑在最小值点统计到某个连通块。换句话说，若某黑点 $(i,j)$ 无法到达任何 $(i',j')$ 满足 $a_{i'}+b_{j'}<a_i+b_j$，则产生一次贡献。

考虑一个点 $(i,j)$，一个比它小的点 $(i',j')$ 要么 $a_{i'}<a_i$，要么 $b_{j'}<b_j$。那么考虑维护最近的 $i'$ 满足 $a_{i'}<a_i$，记为 $prea_i,sufa_i$，同理有 $preb_i,sufb_i$。显然若 $(i,j)$ 能到达更远的比它小的行/列则一定能到达这些行/列的其中之一。

一个结论是若 $(i,j)$ 能到达 $prea_i$ 这一行（不考虑经过其它三者），则必然能到达 $(prea_i,j)$ 这个点，并且是走直线到达的。因为 $[preb_j+1,sufb_j-1]$ 区间内的所有 $b_{j'}$ 均大于等于 $b_j$，假如这个区间内某个 $(i',j')$ 是黑的那么 $(i',j)$ 也是黑的，所以若连通则那条直的路径必定连通。

于是考虑这条直路何时不连通，容易发现 $(i,j)$ 不能到达 $(prea_i,j)$ 当且仅当 $\max_{k=prea_i+1}^{i-1}a_k+b_j>x$，原因显然。不能到达 $(sufa_i,j)$ 也是类似的。记这两个“最大值”中的较小值为 $na_i$。那么 $(i,j)$ 上下都不能到更小的行当且仅当 $na_i+b_j>x$。同理有 $a_i+nb_j>x$。

那么容易发现一个点 $(i,j)$ 产生贡献当且仅当： $$ \begin{cases} na_i>x-b_j\\ a_i>x-nb_j\\ a_i\le x-b_j \end{cases} $$ 于是就是一个三维偏序，cdq 直接 $O(n\log^2 n)$ 做即可。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,m,x,a[N],b[N],prea[N],sufa[N],na[N],preb[N],sufb[N],nb[N];
struct SpareTable{
    i64 st[19][N];
    void init(i64 *a,i64 n){
        forup(i,1,n) st[0][i]=a[i];
        forup(i,0,17){
            forup(j,1,n-(1<<(i+1))+1){
                st[i+1][j]=max(st[i][j],st[i][j+(1<<i)]);
            }
        }
    }
    i64 query(i64 l,i64 r){
        i64 len=31^__builtin_clz(r-l+1);
        return max(st[len][l],st[len][r-(1<<len)+1]);
    }
}st;
struct Node{
    i64 x,y,z,tp;
}p[N<<1];
void initpo(){
    stack<i64> stk;
    stk.push(0);
    forup(i,1,n){
        while(a[stk.top()]>a[i]) stk.pop();
        prea[i]=stk.top();stk.push(i);
    }
    while(stk.size()) stk.pop();
    stk.push(n+1);
    fordown(i,n,1){
        while(a[stk.top()]>=a[i]) stk.pop();
        sufa[i]=stk.top();stk.push(i);
    }
    while(stk.size()) stk.pop();
    st.init(a,n);
    forup(i,1,n){
        if(prea[i]>=1&&sufa[i]<=n){
            na[i]=min(st.query(prea[i],i),st.query(i,sufa[i]));
        }else if(prea[i]>=1){
            na[i]=st.query(prea[i],i);
        }else if(sufa[i]<=n){
            na[i]=st.query(i,sufa[i]);
        }else{
            na[i]=inf;
        }
    }
    forup(i,1,n){
        p[i]=Node{na[i],a[i],a[i],0};
    }
    stk.push(0);
    forup(i,1,m){
        while(b[stk.top()]>b[i]) stk.pop();
        preb[i]=stk.top();stk.push(i);
    }
    while(stk.size()) stk.pop();
    stk.push(m+1);
    fordown(i,m,1){
        while(b[stk.top()]>=b[i]) stk.pop();
        sufb[i]=stk.top();stk.push(i);
    }
    while(stk.size()) stk.pop();
    st.init(b,m);
    forup(i,1,m){
        if(preb[i]>=1&&sufb[i]<=m){
            nb[i]=min(st.query(preb[i],i),st.query(i,sufb[i]));
        }else if(preb[i]>=1){
            nb[i]=st.query(preb[i],i);
        }else if(sufb[i]<=m){
            nb[i]=st.query(i,sufb[i]);
        }else{
            nb[i]=inf;
        }
    }
    forup(i,n+1,n+m){
        p[i]=Node{x-b[i-n],x-nb[i-n],x-b[i-n],1};
    }
}
struct BIT{
    i64 c[N];
    void upd(i64 x,i64 k){for(;x<=2e5;x+=x&-x)c[x]+=k;}
    i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
i64 ans=0;
void cdq(i64 l,i64 r){
    if(l==r) return;
    i64 mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    i64 pl=l;
    forup(i,mid+1,r){
        while(pl<=mid&&p[pl].y>p[i].y){
            if(!p[pl].tp) mt.upd(p[pl].z,1);
            ++pl;
        }
        if(p[i].z>0&&p[i].tp){
            ans+=mt.sum(p[i].z);
        }
    }
    forup(i,l,pl-1){
        if(!p[i].tp) mt.upd(p[i].z,-1);
    }
    inplace_merge(p+l,p+mid+1,p+r+1,[&](Node a,Node b){
        return a.y>b.y;
    });
}
signed main(){
    n=read();m=read();x=read();
    forup(i,1,n){
        a[i]=read();
    }
    forup(i,1,m){
        b[i]=read();
    }
    initpo();
    sort(p+1,p+n+m+1,[&](Node a,Node b){
        if(a.x!=b.x) return a.x>b.x;
        return a.tp>b.tp;
    });
    cdq(1,n+m);
    printf("%lld\n",ans);
}

CF1209G2 Into Blocks (hard version)

传送门

题意

• 有一长度为 $n$ 的序列 $a_i$，有 $q$ 次单点修改。
• 每次修改后，你可以进行任意次操作，每次操作形如将序列中所有等于 $a_x$ 的元素全部变成 $a_y$。你需要保证操作后不存在 $i<j<k$，使得 $a_i=a_k\land a_j\ne a_k$。每次操作的代价是序列中与 $a_x$ 相等的数个数。输出最小代价。（注意，你的操作不会对序列产生实际影响）
• $1\le n,q\le 2\times 10^5$

题解

首先这个条件的意思就是相同的数在序列上连续。

设某个数 $i$ 第一次出现和最后一次出现分别是 $L_i,R_i$，由于一个颜色只能捆绑起来改，必然有 $L_i=R_i$，于是在最终序列中有 $\forall j\in[L_i,R_i),a_j=a_{j+1}$。显然若两个 $L_i,R_i$ 有交就需要合并。而一段合并起来的区间所需代价显然就是其长度减去出现次数最多的区间（把某个 $x$ 修改两遍必定不优，而最小化修改的 $x$ 总数就是最多的哪个不懂）。

这玩意第一反应肯定是用并查集维护，那就寄了。因为带修所以肯定要考虑线段树分治之类的东西，那么并查集合并的次数显然就炸了。

这时候就有个神奇想法了。维护一个数组 $c_i$，对于一个 $[L_i,R_i)$，将 $c_i\in[L_i,R_i)$ 全部 $+1$。这样就只需要维护每个极长非 $0$ 连续段的贡献了。每个 $L_i,R_i$ 可以用 set 简单维护。

对于 $L_i=R_i$ 的情况，容易发现无论何时它都不会产生影响，若单独成段则无需操作，若在某一段内则不可能是最大值（它在某一段内意味着那一段有至少一个 $\ge 2$ 的）。

但是“最大值”这个东西仍然不好维护。一个想法是将 $i$ 的出现次数挂在 $L_i$ 上用另一棵线段树维护区间最大值，然后合并的时候进行一次区间查询，这个是双 $\log $ 的。貌似已经能过了。

其实还可以再优化。显然每个连续段只需要查一次。那么若合并的时候其中一个儿子最小值不是 $0$，显然这个非 $0$ 连续段就不是极长的，不需要查询。只有当两个儿子的最小值均为 $0$ 时交界处的那个连续段才是极长的（除了左端点为 $1$ 的情况，钦定 $c_0=0$ 即可），这样就能实现对“每一段仅进行一次查询”。

那么维护每个区间的最小值，左侧第一个 $0$ 的下标，右侧第一个 $0$ 的下标，既不靠左也不靠右的连续段贡献之和。

这时候又有个问题，因为有区间修改，“第一个 $0$ 的下标”是不好维护的。这种时候（不知道算不算套路，但我是第二次看到这个东西了）就可以转而维护“第一个区间最小值的下标”，因为 $c_n$ 始终等于 $0$ 所以在全局查询时是正确的，这个就能维护了。同理，其它所有地方也要将维护 $0$ 换成维护区间最小值。

复杂度 $O(n\log n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1<<18,inf=0x3f3f3f3f;
int n,q,a[N];
set<int> ind[N];
struct SegTree1{
    int mx[N<<1];
    void Update(int P,int X){
        mx[P+N]=X;
        for(int i=(P+N)>>1;i;i>>=1){
            mx[i]=max(mx[i<<1],mx[i<<1|1]);
        }
    }
    int Query(int l,int r){
        int res=0;
        for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1){
            if(!(l&1)) res=max(res,mx[l^1]);
            if(  r&1 ) res=max(res,mx[r^1]);
        }
        return res;
    }
}t1;
struct SegTree2{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int llen[N<<2],rlen[N<<2],mn[N<<2],res[N<<2],mark[N<<2];
    void PushUp(int id,int l,int r){
        mn[id]=min(mn[id<<1],mn[id<<1|1]);
        res[id]=0;
        if(mn[id]==mn[id<<1]){
            llen[id]=llen[id<<1];
            res[id]+=res[id<<1];
        }else{
            llen[id]=llen[id<<1|1];
        }
        if(mn[id]==mn[id<<1|1]){
            rlen[id]=rlen[id<<1|1];
            res[id]+=res[id<<1|1];
        }else{
            rlen[id]=rlen[id<<1];
        }
        if((mn[id<<1]==mn[id<<1|1])&&(rlen[id<<1]!=mid||llen[id<<1|1]!=mid+1)){
            res[id]+=(llen[id<<1|1]-rlen[id<<1]-t1.Query(rlen[id<<1]+1,llen[id<<1|1]-1));
        }
    }
    void PushDown(int id){
        mn[id<<1]+=mark[id];
        mn[id<<1|1]+=mark[id];
        mark[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Build(int l=0,int r=n,int id=1){
        mark[id]=0;
        if(l==r){
            mn[id]=0;
            llen[id]=rlen[id]=l;
            res[id]=0;
            return;
        }
        Build(lson);Build(rson);
        PushUp(id,l,r);
    }
    void Update(int L,int R,int X,int l=0,int r=n,int id=1){
        if(L<=l&&r<=R){
            mn[id]+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id,l,r);
    }
    int Query(){
        return res[1];
    }
}t2;
void add(int i){
    if(ind[i].size()<=1) return;
    int l=*ind[i].begin(),r=*prev(ind[i].end());
    t1.Update(l,ind[i].size());
    t2.Update(l,r-1,1);
}
void del(int i){
    if(ind[i].size()<=1) return;
    int l=*ind[i].begin(),r=*prev(ind[i].end());
    t1.Update(l,0);
    t2.Update(l,r-1,-1);
}
signed main(){
    n=read();q=read();
    forup(i,1,n){
        a[i]=read();
        ind[a[i]].insert(i);
    }
    t2.Build();
    forup(i,1,2e5){
        add(i);
    }
    printf("%d\n",t2.Query());
    forup(i,1,q){
        int p=read(),x=read();
        del(a[p]);del(x);
        ind[a[p]].erase(p);
        ind[x].insert(p);
        add(a[p]);add(x);
        a[p]=x;
        printf("%d\n",t2.Query());
    }
}

QOJ#1838 Intellectual Implementation

传送门

题意

• 给定二维平面上 $n$ 个矩形，顶点均为整点，边平行于坐标轴。求三元组 $(i,j,k)$ 的数量，满足 $1\le i<j<k\le n$，且矩形 $i,j,k$ 两两无交
• $1\le n\le 2\times 10^5$

题解

正难则反，考虑用 $\binom{n}{3}$ 减去有交的三元组个数。

容易发现有交的三元组只有三种：两两有交的，其中一个和另外两个均有交，但另外两个无交，两个有交，第三个和这两个均无交。分别记为 $c_1,c_2,c_3$。

有一个神秘方法可以把 $c_1,c_2$ 一起干掉，不知道怎么想到的。考虑记 $d_i$ 表示与矩形 $i$ 有交的矩形个数，这个可以做四次二维数点 $+$ 容斥解决。容易发现 $\sum_{i} d_i\times(n-2)=2c_1+4c_2+6c_3,\sum_{i}\binom{d_i}{2}=c_2+3c_3$，这两个进行一些简单的线性变换就能得到 $c_1+c_2$ 的值，于是只需要求 $c_3$ 了。

考虑扫描线。从上往下扫，遇到矩形上边界就将其横向的区间加入某个结构，遇到下边界就去掉。这样每次在加入某个区间 $[l,r]$ 时统计有多少对和它相交的区间两两相交即可。这玩意还是不好维护，又是正难则反。记一个总区间数，用当前结构里的总区间数减去不与它相交的区间数即可得到与它相交的区间数 $p$，这个可以维护 $l$ 左侧的右端点数和 $r$ 右侧的左端点数。然后就有 $\binom{p}{2}$ 对和它相交的区间。某一对区间不相交当且仅当其中一个的右端点 $r_{j}$ 在另一个的左端点 $l_k$ 左侧。这个可以直接线段树维护，具体实现略。并且容易发现可能满足这种情况且与 $[l,r]$ 相交的区间对必然有 $r_j\in[l,r]$ 且 $l_k\in[l,r]$，线段树区间查即可。复杂度 $O(n\log n)$。

QOJ#3029 The Great Drone Show

传送门

题意

• 一个三维空间中有 $n$ 个点，第 $i$ 个点的初始坐标为 $(x,y,0)$，某些点之间由细绳相连，共有 $m$ 条细绳，每条细绳有一个最长长度 $l_i$，连接 $(u_i,v_i)$，一条细绳所连接的两个点距离若超过 $l_i$ 就会断掉并且不会再次相连，此处“距离”为三维空间中的欧几里得距离。保证细绳不在点之外的地方相交，保证初始图连通，且初始不会断裂。
• 有 $m$ 次移动，每次移动都是将某个点的 $z$ 轴坐标 $+h$。
• 有 $q$ 次询问，每次询问两个点在哪次移动后开始不连通，若始终连通输出 $-1$。
• $2\le n,k,q\le 5\times 10^5,n-1\le m\le 3n,|x_i|,|y_i|\le 10^8,|h|\le 10^9$。

题解

首先假如我们知道了每条边什么时候断，应该如何求答案。容易发现这是一个瓶颈路问题，将断裂时间作为边权，求出最大生成树后每次查询两点间路径上边的最小权值即可。

那么考虑维护每条边的断裂时间。首先考虑对于树的情况应该怎么做。

容易发现对于一条细线 $(u,v,l)$，它不会断当且仅当 $|z_u-z_v|$ 小于某个数（这个可以 $O(1)$ 计算），或者说若 $z_u$ 固定，那么 $z_v$ 在某一段区间内。但我们显然不能对所有连边维护这个区间，不然每次 $z_u$ 改变会影响一车 $v$。一个很典的想法是只在 $u$ 的父亲处维护这个东西，每次 $z_u$ 改变就先查询它的儿子是否断掉，再修改挂在父亲处的区间看它是否断掉。具体维护可以用 set 维护左右端点，复杂度是均摊 $O((k+m)\log n)$ 的。

然后考虑对于一般图怎么做。一个很典的想法是对于将每条边视为从两端点中度数较小者连向度数较大者的有向边，每个点向所有出边指向的点挂这个区间。进行一些根号分治可以发现出度总和大约是 $n\sqrt{m}$ 级别的。于是复杂度就是 $O((k+n\sqrt{m})\log n)$ 的。

……吗？

这里要用到平面图的性质，根据平面图的性质，一个平面图中度数最小的点度数小于等于 $5$。那么显然刚才这样定向所得到的出度总和其实是 $5n$ 级别的（考虑相当于每次把度数最小的点拎出来然后删掉），复杂度就是 $O((k+5n)\log m)$ 的，于是就能比较轻松地通过了。

P10540 [THUPC 2024 决赛] 古明地枣的袜子

传送门

题意

• 有一个初始全 $0$，长度为 $n$ 的序列 $a$。另有一个长度为 $n$ 的操作序列 $(x_i,y_i)$ 表示将 $[1,x_i]$ 全部增加 $y_i$。
• 有 $m$ 次查询，每次询问进行了操作序列上 $i\in [l,r]$ 的所有操作后 $a_i$ 的最大值。
• $1\le n,m\le 5\times 10^5,1\le x_i\le n,|y_i|\le n$

题解

神秘分块。

考虑记 $c_j$ 表示 $x_i=j$ 的操作数。设一个阈值 $B$，将序列 $a_i$ 分为 $t$ 块使得每一块中 $c_j$ 的总和都小于 $B$（或者这一块只包含一个点 $j$，且 $c_j\ge b$），显然 $k$ 是 $O(\frac{n}{B})$ 级别的。

考虑离线下来对每一块求出最大值，再合并起来。只考虑某一块 $[l,r]$，显然若 $x_ir$，则操作 $i$ 的贡献可以直接对操作序列做前缀和解决。那么对于这一块本质不同的查询其实只有 $O(B^2)$ 种。

一个做法是直接 $O(B^2\log n)$ 线段树维护，此时取 $B=\sqrt{\frac{n}{\log n}}$ 复杂度是 $O(n\sqrt{n\log n})$，貌似常数小是能过的。

但是存在 $O(B^2)$ 做法，是一个神秘分治。将 $O(B)$ 个操作按 $x$ 排序，每次找到将区间内的操作尽可能均分的下标。对于每一层维护 $(r-l)^2$ 个状态，在上一层是解压再合并，然后考虑所有 $x>mid$ 的操作对左区间的影响，复杂度是 $T(B)=2T(\frac{B}{2})+O(B^2)=O(B^2)$，这样复杂度就是 $O(\frac{n}{B}(n+m)+\frac{n}{B}B^2+mB)=O((n+m)\sqrt{n})$。

QOJ#8008 Fortune Wheel

传送门

题意

• 有一个长度为 $n$ 的环，给定一个长度为 $m$ 的序列（集合？）$k_i$，你最初在点 $x$。
• 你有两种走路方式，一种是从序列中选一个 $k_i$，向前走 $k_i$ 距离（$x\gets (x+k_i)\bmod n$），另一种是在环上均匀随机地跳到一个点（包括当前所在点），问从 $x$ 走到 $0$ 在最优策略下，所需最小步数的期望。以分数输出。
• $1\le n\le 10^5,1\le m \le 500,1\le k_i\le n,0\le x\le n-1$

题解

首先显然的，方案肯定是先随机跳若干次再用 $k$ 走到 $0$，因为一次随机跳会让之前的所有 $k$ 打水漂。

那么“用 $k$ 走到 $0$”的最小步数是好求的，$O(nm)$ 的 bfs 即可。考虑枚举一个阈值 $B$，方案是随机跳到任意一个所需步数小于等于 $B$ 的点后就开始用 $k$ 走。正确性显然。

假如步数小于等于 $B$ 的点有 $i$ 个，所需步数总和为 $s$（显然这两个都能均摊 $O(1)$ 求出来），称这样的点为“好点”。首先若 $x$ 就是好点直接走即可，否则跳到一个好点的期望步数应是 $\frac{n}{i}$，然后会均匀随机地跳到其中一个点，走到 $0$ 的期望步数应是 $\frac{s}{i}$，枚举 $B$，每次把这两个加起来取最小值即可。这部分复杂度 $O(n)$。

CF741C Arpa’s overnight party and Mehrdad’s silent entering

传送门

题意

• 有一个长度为 $2n$ 的环，你要给其中的点涂成黑白二色。要求相邻的三个点不能同色。
• 给定 $n$ 个点对，一个点在且仅在一个点对中，同一个点对中的点不能同色。
• 构造任意一组方案。
• $1\le n\le 10^5$

题解

很厉害的构造题。

构造方案是把第一个条件加强成编号为 $2i,2i+1$ 的点不能同色。然后二分图染色，就过了。

分析一下正确性，首先任意连续三个点肯定包含一对这样的点，满足限制。

我们把原先的第二种限制连白边，新增的这种限制连黑边。容易发现每个点都恰好连了一条白边一条黑边。因为每个点度数都为 $2$ 所以必定是若干个环，因为不存在连续的白边或连续的黑边，所以不存在奇环。于是正确。复杂度 $O(n)$

启发是对同一个点集的任意两个匹配并起来都是二分图。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,co[N],a[N],b[N];
vector<int> e[N];
void dfs(int x){
    for(auto i:e[x]){
        if(co[i]) continue;
        co[i]=3-co[x];
        dfs(i);
    }
}
signed main(){
    n=read();
    forup(i,1,n){
        e[i*2].push_back(i*2+1);
        e[i*2+1].push_back(i*2);
        a[i]=read();b[i]=read();
        e[a[i]].push_back(b[i]);
        e[b[i]].push_back(a[i]);
    }
    forup(i,1,n*2){
        if(!co[i]){
            co[i]=1;
            dfs(i);
        }
    }
    forup(i,1,n){
        printf("%d %d\n",co[a[i]],co[b[i]]);
    }
}

CF1656G Cycle Palindrome

传送门

题意

• 给定一个长度为 $n$ 的数列 $a$，你需要找到一个长度为 $n$ 的置换 $p$，使其作用于 $a$ 得到的 $a'$ 是一个回文数列。并且 $p$ 中仅包含一个置换环。
• 多测，$1\le \sum n\le2\times 10^5$。

题解

另一道很厉害的构造题。

首先把原题扔掉，考虑置换的性质。

容易发现若交换两不同环上的 $p_i$，这两个环会连在一起。反之，若交换同一个环上的 $p_i$，这个环会断开。

容易发现回文数列有很棒的性质，首先有 $\left\lfloor\frac{n}{2}\right\rfloor$ 对可以任意交换的数（$p_i$ 和 $p_{n+1-i}$），并且任意两对之间也能任意交换（但是注意这样交换是断两条边连两条边，即将两个环改成另一形状的两个环，还需要一次交换把这两个环连起来）。

那么思路就明了了。先随便搞一个回文数列出来，然后不破坏其回文性质地把其中所有的环连成大环。

复杂度大概是 $O(n\alpha(n))$ 的，感觉需要并查集维护。

然后还有一点边界情况。对于奇数的情况，容易发现只需要让中间这个点连入任意的另一个环，对其余成对点的做上述操作就行了。连不了则无解。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,a[N],p[N];
vector<int> vec[N];
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void merge(int u,int v){
    u=getfa(u);v=getfa(v);
    if(u==v) return;
    fa[u]=v;
}
void solve(){
    n=read();
    forup(i,1,n) vec[i].clear();
    forup(i,1,n){
        a[i]=read();
        fa[i]=i;
        vec[a[i]].push_back(i);
    }
    int pl=0;
    if(n&1){
        bool flag=true;
        forup(i,1,n){
            if(vec[i].size()&1){
                if(flag){
                    flag=false;
                }else{
                    puts("NO");
                    return;
                }
                p[(n+1)/2]=vec[i].back();
                merge(p[(n+1)/2],(n+1)/2);
            }
            forup(j,0,vec[i].size()/2-1){
                ++pl;
                p[pl]=vec[i][j];
                merge(pl,p[pl]);
                p[n+1-pl]=vec[i][j+(vec[i].size()/2)];
                merge(n+1-pl,p[n+1-pl]);
            }
        }
        if(p[(n+1)/2]==(n+1)/2){
            int c=a[p[(n+1)/2]];
            if(vec[c].size()==1){
                puts("NO");
                return;
            }
            forup(i,1,n/2){
                if(a[p[i]]==c){
                    merge(i,(n+1)/2);
                    swap(p[i],p[(n+1)/2]);
                    break;
                }
            }
        }
    }else{
        forup(i,1,n){
            if(vec[i].size()&1){
                puts("NO");
                return;
            }
            forup(j,0,vec[i].size()/2-1){
                ++pl;
                p[pl]=vec[i][j];
                merge(pl,p[pl]);
                p[n+1-pl]=vec[i][j+(vec[i].size()/2)];
                merge(n+1-pl,p[n+1-pl]);
            }
        }
    }
    forup(i,1,n/2){
        if(getfa(i)!=getfa(n+1-i)){
            swap(p[i],p[n+1-i]);
            merge(i,n+1-i);
        }
        if(i>1&&getfa(i)!=getfa(i-1)){
            merge(i,i-1);
            swap(p[i],p[i-1]);
            swap(p[n+1-i],p[n+2-i]);
            swap(p[i],p[n+1-i]);
        }
    }
    puts("YES");
    forup(i,1,n){
        printf("%d ",p[i]);
    }puts("");
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

CF1844E Great Grids

传送门

题意

• 定义一个 $n\times m$ 的矩形是好的，当且仅当：
• 它仅由字符 A,B,C 构成。
• 任意 $2\times 2$ 子矩形都包含三种不同字符。
• 任意两相同字符不共用边
• 现在给定 $k$ 个限制，每个限制形如两共用顶角的字符相同，问存不存在好的矩形。
• $2\le n,m \le 2000,1\le k\le 4000$

题解

画出所有 $2\times 2$ 的矩形观察一下（不妨钦定左上角为 A，右上角为 $B$）： $$ \begin{bmatrix}A&B\\C&A\end{bmatrix}\begin{bmatrix}A&B\\B&C\end{bmatrix} $$ 显然只有这两种。容易发现若视这三个数分别为 $0,1,2$，$B-A$ 和 $A-C,C-B$ 在 $\bmod{3}$ 意义下均为 $1$，并且在纵向上也有类似的性质。感觉上原因是确定了一个后和它相邻的两个都不能是它，那么对角的那个就必须是它，而 $\bmod{3}$ 意义下任意一个数和另外两个数的差都相同。

因为所有 $2\times 2$ 矩形都要满足这种性质，那么任意相邻两列所有数的差应都相同，任意相邻两行也是。所以我们不妨用每一行和上一行的差概括这个矩形，记为 $a_i$，同理在列上有 $b_i$，显然这两个数的取值范围应该是 $[1,2]$。

这时候我们瞄一眼限制。若限制为「左上-右下」，那么说明这个共用顶点对应的行列差分应有 $a_i\ne b_j$，同理，「右上-左下」的应有 $a_i=b_j$。

那么就形成了若干对这样的关系，可以类似二分图染色的做，复杂度 $O(n)$。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=4005,inf=0x3f3f3f3f;
int n,m,k;
struct edge{
    int v,tp;
};
vector<edge> e[N*2];
int co[N],ans;
void dfs(int x){
    for(auto i:e[x]){
        int v=i.v,tp=i.tp;
        if(co[v]){
            if((co[v]!=co[x])^tp){
                ans=false;
            }
            continue;
        }
        co[v]=(tp?3-co[x]:co[x]);
        dfs(v);
    }
}
void solve(){
    n=read();m=read();k=read();
    forup(i,1,n+m) e[i].clear(),co[i]=0;
    forup(i,1,k){
        int x1=read(),y1=read(),x2=read(),y2=read();
        if(y2>y1){
            e[x2].push_back(edge{y2+n,1});
            e[y2+n].push_back(edge{x2,1});
        }else{
            e[x2].push_back(edge{y1+n,0});
            e[y1+n].push_back(edge{x2,0});
        }
    }
    ans=1;
    forup(i,1,n+m){
        if(!co[i]){
            co[i]=1;
            dfs(i);
            if(ans==0){
                puts("NO");
                return;
            }
        }
    }
    puts("YES");
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

QOJ#6376 LaLa and Lamp

传送门

题意

• 有 $\frac{n(n+1)}{2}$ 个点排成一个正三角形，每个点是黑色或白色，每次可以选平行于任意一边的一行反转这一行上所有点的颜色。
• 问能否把所有点都变成白色。
• $1\le n\le 2000$

题解

感觉很考验对高消的理解，这真是的贪心/构造吗？

首先一个显然的暴力是高消。假如把每一行看成一个变量，就有 $3n$ 个变量，但是把每个点看成一个方程有 $O(n^2)$ 个方程，所以目标是找到一部分点使其能解出所有变量。

但其实并不需要，容易发现若确定两边的 $2n$ 个变量后，方案合法当且仅当所有黑点都在平行于第三条边的行上是整行整行的。

于是目标变成了确定（或者枚举） $2n$ 个变量后模拟，找出是否是整行的。

那么有哪些和两边相关的 $2n$ 个方程呢？容易发现，最下面两行的 $2n-1$ 个方程，在枚举这两行是否操作后就是只和两边的 $2n$ 个变量相关的方程，再随便枚举其中一个就能求出剩下的。而且甚至不需要高消，因为每个方程只连接两个变量，枚举第一个就能求出下一个。

于是做完了，复杂度 $O(2^3n^2)$。

QOJ#5416 Fabulous Fungus Frenzy

cool，是原神题

题意

• 有一个 $n\times m$ 的矩阵，每个位置上有一种颜色。同时有 $k$ 种模型，第 $i$ 种模型是一个 $n_i\times m_i$ 的矩阵，同样每个位置上有一种颜色。
• 你可以进行两种操作：
• 交换两个相邻格子的颜色。
• 将左上角 $n_i\times m_i$ 的子矩形颜色涂成某个模型的颜色。
• 构造方案，操作序列长度不超过 $4\times 10^5$
• $n,m,k\le 20$

题解

很有 ICPC 风格的题目。

发现正着做比较困难，考虑倒着做。首先当前矩形能经过若干操作拼出哪些模型是可知的。只需统计每种颜色的个数。那么每次贪心地在左上角拼出一个模型，然后换成通配符就好了，显然每次选能消掉非通配符颜色最多的就不会原地踏步了。每次至多 $(nm)\times(n+m)$ 次操作拼出一个结构，至少增加一个通配符（否则无解），操作次数约为 $O(n^2m^2(n+m))$，貌似需要卡一点常。

PKU-CPC 2023 C Empty up a Bottle

怎么办，vjudge 上都找不到这道题。

题意

• 有三个容量充分大的瓶子 $A,B,C$，初始分别装了一些水，初始水量记为 $A,B,C$。
• 你可以进行若干次操作，每次操作形如选择两个瓶子，将其中较多的一个倒入较少的一个，使较小者水量翻倍。构造方案清空其中一个瓶子。
• 因为确定两个瓶子后显然就确定了是从哪个瓶子倒入哪个瓶子（除非相等，但下一步无论如何都做完了），所以你可以合并 $k$ 个操作，即 $x\;y\;k$ 表示对 $(x,y)$ 这对瓶子进行 $k$ 次操作，你最多能使用 $200$ 组操作。
• $A,B,C\le 3\times 10^{13}$

题解

瞪眼法可得一次对 $A,B$ 的操作等价于 $A\gets 2A\bmod(A+B),B\gets 2B\bmod(A+B)$，即模 $A+B$ 意义下乘以 $2$ 的幂次。

若 $A+B$ 是偶数它并没有什么特别好的性质。但若 $A+B$ 是奇数，由于 $2$ 与奇数互质，那么对于任意 $2^k$ 必然存在 $2^{k'}$ 使得 $2^{k}\times 2^{k'}\equiv 1\pmod{A+B}$（数论中的欧拉定理）。即存在逆元，可以进行“除以 $2^k$”的操作。

那么若 $A,B$ 是偶数，$C$ 是奇数，且 $A<B$，显然可以进行 $(A,B,C)\to (2^kA,B-(2^k-1)A,C)$，此时 $2^kA+C$ 是个奇数，那么可以对 $A$ 进行“除以 $2^k$” 的操作，就能得到 $(A,B-(2^k-1)A,C+(2^k-1)A)$，这时候我们取最大的 $k$ 使得 $B\ge (2^k-1)A$，大体上每次解决二进制的最高位就能使得 $B\le 2A$，然后每次 $k$ 取 $1$ 进行辗转相减，大概只需 $O(\log)$ 次就能让 $A=B$，下一次就过了。

若不是两偶一奇，对于三奇可以合出两个偶数，对于三偶显然可以三个都除以 $2$，对于一偶两奇可以变成三奇，都能转化为两偶一奇。

对于求逆元，因为 $2^{\varphi(A+B)}\equiv 1\pmod{A+B}$，所以需要求大数的 $\varphi$ 函数。可以对 $\sqrt{A+B}$ 以内线性筛，更大的就略微分解一点质因数，用积性函数的性质算出来，大概能做到 $O(n^{\frac{1}{4}})$，只算 $200$ 次应该没有时间问题。

好像需要卡点操作数量的常数。

CF1693F I Might Be Wrong

传送门

题意

• 给定一长度为 $n$ 的 $01$ 串 $s$，你可以进行若干次操作，每次操作形如选择一个区间 $[l,r]$，花费 $|cnt_0-cnt_1|+1$ 的代价将其排序（其中 $cnt_0,cnt_1$ 表示区间内 $0,1$ 的数量），求将整个串排序的最小代价。
• $1\le n\le2\times 10^5$

题解

一个结论是存在最优解使得每次操作的区间均有 $cnt_0=cnt_1$。考虑证明，证明思路是任意 $cnt_0\ne cnt_1$ 的操作都能转化成若干个代价和不劣的 $cnt_0=cnt_1$ 的操作。

考虑一个 $cnt_0\ne cnt_1$ 的操作 $[l,r]$，首先其中不可能全 $0$，那么找到第一个 $1$ 的位置 $l'$，显然操作 $[l',r]$ 和操作 $l,r$ 是等价的。不妨设 $[l',r]$ 中 $cnt_0>cnt_1$（$cnt_1>cnt_0$ 的情况可以翻转后反转）。那么找到 $[l',r]$ 的第一个满足 $cnt_0=cnt_1$ 的前缀 $[l',r']$，如果对它进行操作就会将至少一个 $0$ 提到 $l'$ 处，那么再找到下一个 $1$ 进行递归操作。显然至多进行 $cnt_0-cnt_1$ 次操作就会使 $[l',r]$ 中 $cnt_0\le cnt_1$，这时候找到 $[l,r]$ 的 $cnt_1=cnt_0$ 的后缀进行操作就能 Cosplay 一次对 $[l,r]$ 的操作，并且代价不大于 $|cnt_0-cnt_1|+1$。

假设整个 $s$ 中的 $0$ 比 $1$ 多（同样的，否则反转后翻转即可），那么每次从第一个 $1$ 找一个尽量长的区间使得 $0,1$ 相等，直到第一个 $1$ 之前的 $0$ 数量等于 $1$ 的数量，再对后缀操作。这样每耗费一个代价去掉的逆序对是最多的，非常优秀。维护是比较简单的，可以把它看成一个类似括号序列的东西，把每个值的最后一个下标存下来即可。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,a[N],c[2],val[N],ind[N];
char str[N];
void solve(){
    n=read();
    c[0]=c[1]=0;
    scanf(" %s",str+1);
    forup(i,0,n*2) ind[i]=-1;
    bool flag=true;
    forup(i,1,n){
        a[i]=str[i]-'0';
        ++c[a[i]];
        if(a[i]<a[i-1]) flag=false;
    }
    if(flag){
        puts("0");
        return;
    }
    if(c[1]>c[0]){
        reverse(a+1,a+n+1);
        forup(i,1,n){
            a[i]=1-a[i];
        }
        swap(c[0],c[1]);
    }
    val[0]=0;
    forup(i,1,n){
        val[i]=val[i-1]+(a[i]?-1:1);
        ind[val[i]]=i;
    }
    int l=0,ans=0;
    while(l<n&&!a[l+1]) ++l;
    while(l<c[0]-c[1]){
        ++ans;
        l+=(ind[l]+1-l)/2;
    }
    printf("%d\n",ans+1);
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

QOJ#1436 Split in Sets

传送门

题意

• 有 $n$ 个互相区分的球，每个球有一个权值。
• 有 $k$ 个互相区分的盒子，将球放入盒子里，使得不存在空盒。一个放置方案的代价是每个盒子里球权值的按位与之和。最大化代价，并求出代价最大时的方案数。
• $1\le k\le n\le 10^5$

题解

感觉算是比较常规的贪心。首先“最大化位运算之和”肯定从高往低最大化每一位的贡献。

假设最高位为 $2^b$，且包含这一位的数有 $cnt$ 个，那么分情况讨论：

1. 若 $cnt<k$，那么把每一个 $\ge 2^b$ 的数单独放一个盒子是不劣的。考虑 $x,y$ 分别放在两盒子里的贡献是 $x+y=x\And y+x\mid y$，而放一起的贡献是 $x\And y$，会损失 $x\mid y$ 的贡献。那么剩下的就是一个子问题了。
2. 若 $cnt\ge k$ 并且 $cnt<n$，那么 $2^b$ 这一位最多产生 $k-1$ 次贡献，这需要把其余数全部合在一起，这是最优的，证明与上面类似。那么不妨就把它们合成一个数。计算 $2^b$ 的贡献后去掉 $2^b$ 这一位，就又是子问题了。
3. 若 $cnt=n$，那么每个盒子必然对最高位有贡献，计算贡献后去掉最高位即可。

对于边界条件，首先 $k=n$ 显然是一个边界，此时一个盒子只能放一个，$k=1$ 也是一个边界，只能把所有东西放一个盒子里。$b=-1$ 也是一个边界条件，虽然这玩意在整数范围内不是良定义，但是它能说明当前的数和盒子不能产生任何贡献，直接退出算法即可。

对于方案数，容易发现在边界条件 $1$ 会产生一个阶乘的贡献，在操作 $1$ 会产生组合数乘阶乘的贡献。在边界条件 $3$ 贡献是版子。于是做完了。

每次递归要么将 $b$ 减小 $1$，要么将 $k$ 减小至少 $1$，复杂度是 $O(n)$ 的，大概要维护一些东西。

CF1646F Playing Around the Table

传送门

题意

• 有 $n$ 个人围成一圈，从 $1$ 到 $n$ 编号，有 $n^2$ 张牌，每张牌也有一个编号，且每种编号的牌恰好有 $n$ 张。初始每个人手上有 $n$ 张牌。
• 会进行若干回合游戏，每回合每个人都必须将自己手上的一张牌送给下一人，并且这些操作是同时执行的。
• 请构造一种方案，使得在 $n^2-n$ 次操作内，每个玩家集齐所有编号和自己相同的牌。
• $2\le n\le 100$，可以证明必定有解。

题解

比较另类的构造。

首先每个人手上拿到编号和自己相同的牌是非常不好做的，因为每张牌的目的地固定了，假如一个人拿齐了自己的牌就不得不送一个给下一人。

一个想法是让 $i-1$ 手上留一张 $i$ 牌，这样 $i$ 就有一个空位了。但是假如有两个连续的这样的人，那么下一步又不得不出现刚刚的情况。

那么不妨做的绝对一点，每个人手上留 $1\sim n$ 的所有牌。那么就发生了非常神奇的事情：

1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

这里每一行代表一个人，我们把每个人手上的牌排列顺序换一下：

2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4

那么第一列转一次，第二列转两次，第三列转三次，就能在 $\frac{n^2-n}{2}$ 次操作得到目标了。

现在的问题是如何构造“每个人手上有所有牌”的情况。一个显然的贪心是每个人随便选一张重复的牌送给下一人，因为还有上一个人送来的牌，那么其实有 $n+1$ 张牌参与决策，重复的牌显然是存在的（除非当前状况已经是答案了）。

考虑所需操作数。容易发现一张牌至多传递 $n-1$ 次（到某个手上没有这张牌的人时就停下）最坏情况就是所有编号相同牌都在一个人手上，所需操作数是 $\frac{n(n-1)}{2}$，但是有 $n$ 种编号，但是每次能传递 $n$ 张牌，那么操作数就是 $\frac{n(n-1)}{2}$，刚好合法。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123=(e);i<=E123;++i)
#define fordown(i,s,e) for(int i=(s),E123=(e);i>=E123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f;
int n;
vector<set<int>> cc[N];
set<int> pp[N];
int cnt[N][N];
void Erase(int i,int c){
    cc[i][cnt[i][c]].erase(c);
    if(cc[i][cnt[i][c]].empty()) pp[i].erase(cnt[i][c]);
    --cnt[i][c];
    if(cc[i][cnt[i][c]].empty()) pp[i].insert(cnt[i][c]);
    cc[i][cnt[i][c]].insert(c);
}
void Insert(int i,int c){
    cc[i][cnt[i][c]].erase(c);
    if(cc[i][cnt[i][c]].empty()) pp[i].erase(cnt[i][c]);
    ++cnt[i][c];
    if(cc[i][cnt[i][c]].empty()) pp[i].insert(cnt[i][c]);
    cc[i][cnt[i][c]].insert(c);
}
vector<vector<int>> ans;
signed main(){
    n=read();
    forup(i,1,n){
        cc[i].resize(n+1);
        mem(cnt[i],0);
        forup(j,1,n){
            int a=read();
            ++cnt[i][a];
        }
        forup(j,1,n){
            cc[i][cnt[i][j]].insert(j);
            pp[i].insert(cnt[i][j]);
        }
    }
    while(1){
        int pos=0;
        forup(i,1,n){
            if(*prev(pp[i].end())!=1){
                pos=i;
                break;
            }
        }
        if(pos==0) break;
        vector<int> vv(n);
        forup(i,0,n-1){
            int u=(pos+i-1)%n+1,v=(pos+i)%n+1;
            int nw=*cc[u][*pp[u].upper_bound(1)].begin();
            vv[u-1]=nw;
            Erase(u,nw);Insert(v,nw);
        }
        ans.push_back(vv);
    }
    forup(i,1,n-1){
        fordown(j,i,1){
            vector<int> vv(n);
            forup(k,1,n){
                vv[k-1]=(k+j-1)%n+1;
            }
            ans.push_back(vv);
        }
    }
    printf("%d\n",(int)ans.size());
    for(auto i:ans){
        for(auto j:i){
            printf("%d ",j);
        }
        puts("");
    }
}

QOJ#895 Color

传送门

题意

• 给定一个 $n$ 个点的完全图，每条边都被染了 $m$ 种颜色的其中一种。
• 你需要再加入 $m-n+1$ 个点连成 $m+1$ 个点的完全图，并且给新边涂色，使得每个点相邻的边均取遍 $m$ 种颜色。
• $1\le n,m\le 200,n\le m+1$

题解

首先若原图就不合法显然不合法。然后由于每条边会给两个点贡献颜色，那么若 $m+1$ 是奇数显然也不可能合法。

容易发现在目标图上把某种颜色 $i$ 的边集单独拎出来，必定会形成恰好 $\frac{m+1}{2}$ 个匹配。而这样的匹配在原图上有三种情况，一种是两点和边均在原图上，第二种是其中一个点在原图上，那条边和另一个点为新增，第三种是两个点和一条边均为新增的，记这三个值分别为 $c_{i,2},c_{i,1},c_{i,0}$，这三个的和记为 $c_i$。

显然在确定原图后这三个值都是能求出来的，那么若一个颜色的 $c_{i,1}+c_{i,2}>\frac{m+1}{2}$，则不合法。反之必然合法，证明参考后文的构造方式。

考虑每次加入一个点，维护每个颜色的 $c_{i}$ 不超过 $\frac{m+1}{2}$。

不难想到用二分图匹配来构造，左部点 $m$ 个表示 $m$ 种颜色，右边 $n+1$ 个点，前 $n$ 个点表示图中的点，最后一个点表示不连边（显然这个点需要往左侧连 $m-n$ 条边）。在这张二分图上 $(u,v)$ 这条边的含义是“新点向点 $v$ 连一条颜色为 $u$ 的边”。

那么这张图右侧前 $n$ 个点要连哪些边是明了的，若 $v$ 周围没有颜色 $i$ 就连边 $(v,i)$。但是我们考虑一下第 $n+1$ 个点，容易发现颜色 $i$ 能向这个点连边当且仅当 $c_{i,0}\ne 0$，再跑二分图匹配（因为最后一个点的存在，感觉已经不算严格的二分图匹配了，貌似只能用最大流做），只要满流，就成功地从 $n$ 拓展到了 $n+1$。

那么为什么满流呢？这个证明就非常神奇了。左部点 $i$ 向 $n+1$ 连的边换成 $2c_{i,0}$ 条重边显然对二分图匹配不产生任何影响，容易发现这样连后，所有左部点的度数都是 $m+1-n$，右部点的度数都是 $m-(n-1)$（除去第 $n+1$ 个点）。而第 $n+1$ 个点的度数是 $2\sum c_{i,0}=(m+1-n)^2$，那么必定存在一个将其拆成 $m+1-n$ 个点的方式使得拆出来的每个点度数也为 $m+1-n$，显然也不影响答案，这是一个二分正则图，根据 Hall 定理必定存在完美匹配。

复杂度 $O(n^2m)$，这里代入的是 dinic 算法复杂度上界，实际应该有更紧的上界但是不重要，反正这个复杂度已经是对的了。

PKU-CPC2024D. Number Solidity

vj 上没有这道

题意

• 我们可以对一个数 $x$ 进行如下分解操作：
• 选择两个数 $a,b>1$，且 $b\mid x,a^b\mid x$，使得 $x\gets \frac{x}{a^b}$。
• 定义一个数的“牢固度”为它最多能进行分解的次数。
• 给定 $n$，求 $[1,n]$ 所有数的牢固度之和。
• $1\le n\le 10^{14}$

题解

显然的，$a,b$ 只选 $x$ 的质因子是不劣的。并且显然每次 $b$ 都选 $x$ 的最小质因子是不劣的。

那么一个数的分解操作就是取 $b$ 为 $x$ 的最小质因子，然后从大到小枚举每个数能不能成为 $a$，若 $x$ 的质因数分解是 $\prod p_i^{c_i}$，牢固度即为 $\sum\left\lfloor\frac{c_i}{b}\right\rfloor$。

显然不能枚举 $x$ 来算，考虑枚举最小质因子 $b$，再枚举大于等于 $b$ 的质数 $a$，那么 $\mathrm{lcm}(b,a^2)$ 的倍数中不含小于 $b$ 的质因子的就能被 $(a,b)$ 分解一次，$\mathrm{lcm}(b,a^4)$ 就能被分解两次，依此类推。

这个“是 $\mathrm{lcm}(b,a^p)$ 的倍数但不是小于 $b$ 的质数的倍数”可以容斥算，容易发现 $13^{13}>10^{14}$，所以 $b$ 的取值是非常小的，感觉怎么写都能过吧。

LOJ#3632 Lovely Dogs

传送门

题意

• 有一棵大小问 $n$ 的树，根为 $1$，点有点权 $a_i$，且 $a_i$ 构成一个排列。
• 给定常数 $d$，若某数 $z$ 的质因数分解为 $\prod p_i^{c_i}$，那么定义 $f(z)=\prod (-1)^{c_i}[c_i\le d]$（容易发现若存在 $c_i>d$ 则 $f(z)=0$）。
• 对于每个结点 $x$，求出 $\sum_{i\le j}f(a_i\times a_j)$，其中 $i,j$ 在 $x$ 的子树中。
• $1\le n\le 2\times 10^5,1\le d\le 20$

题解

讲题人说这是处理 $\mu$ 或者类似函数的套路。

因为要求一些 $f(a_i\times a_j)$，假如 $f$ 是完全积性函数显然会好搞一点，这样可以直接 DSU on tree。但它不是。

首先因为 $a$ 是一个排列，我们可以将所有点重新标号（后文默认 $i=a_i$，代码中没有干这件事）。

容易发现 $f$ 长得非常像 $\mu$，讲题人说处理 $\mu$ 的一个套路是容易发现 $\mu(ij)=\mu(i)\mu(j)\mu(ij)^2$（这个暂且按下不表，使用方法和后文类似）。这道题一样，容易发现 $f(ij)=f(i)f(j)f(ij)^2$，若 $f(ij)=0$ 显然这个就是 $0$，否则 $f(ij)^2=1$，又因为此时显然有 $f(ij)=f(i)f(j)$，所以它是对的。

那么这有什么用呢？容易发现我们把一个值域为 $-1,0,1$ 的函数转化为了一个值域为 $0,1$ 的函数，考虑用艾佛森括号来概括。设 $h(n)$ 等于最大的质数 $p$，满足 $p^{d+1}\mid n$，显然 $f(n)^2=[h(n)=1]$。

考虑 DSU on tree 需要什么，即我们每次将一个数 $i$ 插入一个集合 $S$，希望求出 $\sum_{j\in S}f(ij)$。考虑化一下式子： $$ \begin{aligned} \sum_{j\in S}f(ij)&=\sum_{j\in S}f(i)f(j)f(ij)^2\\ &=f(i)\sum_{j\in S}f(j)[h(ij)=1]\\ &=f(i)\sum_{j\in S}f(j)\sum_{t\mid h(ij)}\mu(t)\\ &=f(i)\sum_{j\in S}f(j)\sum_{t^{d+1}\mid ij}\mu(t) \end{aligned} $$ 然后这里有一个观察，由于 $t^{d+1}\mid ij$，那么若 $t\not\mid i$，则必然存在一个 $t$ 的因子 $t_{\ast}$ 满足 $t_{\ast}^{d+1}\mid j$，则 $f(j)=0$，不会产生贡献，于是我们只需要枚举 $t$ 是 $i$ 的因子： $$ \begin{aligned} \sum_{j\in S}f(ij)&=f(i)\sum_{j\in S}f(j)\sum_{t^{d+1}\mid ij}\mu(t)\\ &=f(i)\sum_{t\mid i}\mu(t)\sum_{j\in S}f(j)[t^{d+1}\mid ij]\\ &=f(i)\sum_{t\mid i}\mu(t)\sum_{j\in S}f(j)[\frac{t^{d+1}}{\gcd(i,t^{d+1})}\mid j] \end{aligned} $$ 然后就能做了。

具体来说，每次枚举 $i$ 的因子 $t$ 来计算贡献。对于某个 $i$，显然 $\frac{t^{d+1}}{\gcd(i,t^{d+1})}$ 可以预处理。一个聪明的做法是对 $i$ 的每个质因子 $p^c$ 存下 $p^{d+1-c}$，然后用枚举集合的方式枚举 $t$，就能直接得到 $\frac{t^{d+1}}{\gcd(i,t^{d+1})}$ 的值了。

代码略微难写，注意各种操作不要带 $\log$，复杂度 $O(n\log^2n)$（每次操作复杂度是因子个数级别的，每个数至多操作 $\log n$ 次）

参考代码

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,d,a[N],f[N],ans[N];
vector<int> e[N];
vector<int> ff[N];
map<int,int> fct[N];
vector<int> pri,vec[N],val[N];
int vv[N],mu[N];
void initpri(){
    mu[1]=1;
    forup(i,2,n){
        if(!vv[i]){
            fct[i][i]=1;
            mu[i]=-1;
            pri.push_back(i);
        }
        for(auto j:pri){
            if(i*j>n) break;
            vv[i*j]=1;
            fct[i*j]=fct[i];
            fct[i*j][j]++;
            if(i%j){
                mu[i*j]=-mu[i];
            }else{
                mu[i*j]=0;
            }
        }
    }
}
int ss[N];
int son[N],cnts,sz[N];
void dfs1(int x,int fa){
    sz[x]=1;son[x]=-1;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs1(i,x);
        sz[x]+=sz[i];
        if(son[x]==-1||sz[i]>sz[son[x]]) son[x]=i;
    }
}
int dfn[N],Tm,mp[N];
void dfs2(int x,int fa,int kep){
    auto work=[&](int a){
        if(!f[a]) return;
        int sz=vec[a].size(),res=0;
        forup(i,0,(1<<sz)-1){
            i64 mul=1;
            forup(j,0,sz-1){
                if(i&(1<<j)) mul*=vec[a][j];
                if(mul>n) break;
            }
            if(mul<=n) res+=mu[val[a][i]]*ss[mul]*f[a];
        }
        ans[x]+=res;
    };
    auto add=[&](int a){
        if(f[a]){
            for(auto i:ff[a]){
                ss[i]+=f[a];
            }
        }
    };
    dfn[x]=++Tm;mp[dfn[x]]=x;
    ans[x]=0;
    for(auto i:e[x]){
        if(i==fa||i==son[x]) continue;
        dfs2(i,x,0);
    }
    if(son[x]!=-1){
        dfs2(son[x],x,1);
        ans[x]+=ans[son[x]];
    }
    for(auto i:e[x]){
        if(i==fa||i==son[x]) continue;
        ans[x]+=ans[i];
        forup(j,dfn[i],dfn[i]+sz[i]-1) work(a[mp[j]]);
        forup(j,dfn[i],dfn[i]+sz[i]-1) add(a[mp[j]]);
    }
    add(a[x]);
    work(a[x]);
    if(!kep){
        forup(i,dfn[x],dfn[x]+sz[x]-1){
            if(f[a[mp[i]]]){
                for(auto j:ff[a[mp[i]]]){
                    ss[j]=0;
                }
            }
        }
    }
}
signed main(){
    n=read();d=read();
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    forup(i,1,n) a[i]=read();
    initpri();
    forup(a,1,n){
        for(int j=a;j<=n;j+=a){
            ff[j].push_back(a);
        }
        vector<int> v1;
        for(auto i:fct[a]){
            i64 rr=1;
            forup(j,1,d+1-i.se){
                rr*=i.fi;
                if(rr>n) break;
            }
            if(rr<=n) vec[a].push_back(rr);
            v1.push_back(i.fi);
        }
        int al=1<<fct[a].size();
        val[a].resize(al);
        val[a][0]=1;
        forup(msk,1,al-1){
            int lb=31^__builtin_clz(msk&-msk);
            val[a][msk]=val[a][msk^(1<<lb)]*v1[lb];
        }
    }
    forup(i,1,n){
        f[i]=1;
        for(auto j:fct[i]){
            if(j.se>d){
                f[i]=0;
                break;
            }
            f[i]*=((j.se&1)?-1:1);
        }
    }
    dfs1(1,0);dfs2(1,0,0);
    forup(i,1,n){
        printf("%d\n",ans[i]);
    }
}

Comments