2024 年 12 月杂题

唉 NOIP 可能寄了。

如果运气不好这可能就是这个网站的最后一篇内容了。

P10875 [COTS 2022] 游戏 M

传送门

题意

• 有一个 $n$ 个点的无向图，初始没有边，按顺序加入 $m$ 条边。
• 有 $q$ 次查询，每次查询两个点之间从什么时刻开始没有割边，若一直不连通或一直有割边输出 $-1$。
• $1\le n,m,q\le 3\times 10^5$

题解

挺套路的。

考虑找出原图的最小生成树（按时间戳最小），那么每一条非树边都会将一个环合并成双连通分量，那么就是查询两点何时开始处于同一集合。

考虑瓶颈路，每次合并时将合并的连通块用边权为当前时间戳的边连在一起，容易发现这样会连成一个森林，并且恰好是瓶颈树，那么链查最大值即可。无解当且仅当两点不在同一连通块。

复杂度 $O(n+(m+q)\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=3e5+5,inf=0x3f3f3f3f;
int n,m,q;
vector<int> e1[N];
vector<pii> e[N];
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool merge(int u,int v){
    u=getfa(u);v=getfa(v);
    if(u==v) return false;
    fa[u]=v;
    return true;
}
int ff[N],dpt[N];
void dfs(int x,int fa){
    ff[x]=fa;
    dpt[x]=dpt[fa]+1;
    for(auto i:e1[x]){
        if(i==fa) continue;
        dfs(i,x);
    }
}
struct Node{
    int u,v,w;
};
vector<Node> ed;
int f[N][20],g[N][20],vis[N];
int dd[N];
void dfs2(int x,int fa){
    dd[x]=dd[fa]+1;
    f[x][0]=fa;
    vis[x]=1;
    forup(i,1,19){
        f[x][i]=f[f[x][i-1]][i-1];
        g[x][i]=max(g[x][i-1],g[f[x][i-1]][i-1]);
    }
    for(auto i:e[x]){
        int v=i.fi,w=i.se;
        if(v==fa) continue;
        g[v][0]=w;
        dfs2(v,x);
    }
}
int Query(int u,int v){
    if(u==v) return 0;
    if(dd[u]>dd[v]) swap(u,v);
    int res=0;
    fordown(i,19,0){
        if(dd[f[v][i]]>=dd[u]){
            res=max(res,g[v][i]);
            v=f[v][i];
        }
    }
    if(u==v) return res;
    fordown(i,19,0){
        if(f[u][i]!=f[v][i]){
            res=max(res,g[u][i]);
            res=max(res,g[v][i]);
            u=f[u][i];v=f[v][i];
        }
    }
    res=max(res,g[u][0]);
    res=max(res,g[v][0]);
    return res;
}
signed main(){
    n=read();m=read();
    forup(i,1,n){
        fa[i]=i;
    }
    forup(i,1,m){
        int u=read(),v=read();
        if(merge(u,v)){
            e1[u].push_back(v);
            e1[v].push_back(u);
        }else{
            ed.push_back(Node{u,v,i});
        }
    }
    dfs(1,0);
    forup(i,1,n){
        fa[i]=i;
    }
    for(auto i:ed){
        int u=i.u,v=i.v;
        u=getfa(u);v=getfa(v);
        while(u!=v){
            if(dpt[u]<dpt[v]) swap(u,v);
            int fp=getfa(ff[u]);
            e[u].push_back(mkp(fp,i.w));
            e[fp].push_back(mkp(u,i.w));
            msg("%d %d %d|\n",u,fp,i.w);
            merge(u,ff[u]);
            u=getfa(u);
        }
    }
    forup(i,1,n){
        if(!vis[i]){
            dfs2(i,0);
        }
    }
    q=read();
    forup(i,1,q){
        int u=read(),v=read();
        if(getfa(u)!=getfa(v)){
            puts("-1");
        }else{
            printf("%d\n",Query(u,v));
        }
    }
}

Yosupo-point_set_range_sort_range_composite

传送门

题号即题面即题意，所见即所得。

题意

• 给定一个长度为 $n$ 的三元组序列 $(p_i,a_i,b_i)$，维护以下四个操作共 $m$ 次（下标从 $0$ 开始到 $n-1$）：
  • $0\;i\;p\;a\;b$，将下标为 $i$ 的三元组修改为 $(p,a,b)$。
  • $1\;l\;r\;x$，设 $f_i(x)=a_ix+b_i$，查询 $f_l(f_{l+1}(\dots f_{r-1}(x)))\bmod 998244353$（就是左闭右开区间从左到右复合）。
  • $2\;l\;r$，将区间 $[l,r)$ 中的三元组按 $p$ 递增排序重新编号。
  • $3\;l\;r$，将区间 $[l,r)$ 中的三元组按 $p$ 递减排序重新编号。
• $0\le a,b,x < 998244353,0\le p\le 10^9,1\le n,m\le 10^5$，保证 $p$ 两两不同。

题解

其实是比较复杂的裸题。

不难想到区间排序可以用区间推平维护，考虑 ODT，然后将每一段的贡献维护到另一棵线段树上，那么考虑如何实现段内计算贡献以及段的分割和合并。

可以对每一段开值域线段树，递增就是直接维护，递减就是反过来维护，对每一个结点开两种 tag 就行了。

然后段的分割和合并可以线段树分裂/合并维护，具体实现时需要注意这一段是递增的还是递减的。

复杂度 $O(n\log n)$。这个复杂度的分析非常有意思。

首先 ODT 显然是单 $\log$ 的。

线段树只有最开始和后续分裂区间时会新增结点，不难发现至多产生 $O(n\log n)$ 个结点，而线段树合并的复杂度上界就是结点总数，于是单 $\log$ 了。

参考代码

#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=1<<17,inf=0x3f3f3f3f,mod=998244353;
const int M=1e9;
int n,m;
struct mint{
    int v;
    mint(){}
    mint(int _v):v(_v){}
    mint operator +(const mint &r){
        int val=v+r.v;
        if(val>=mod) val-=mod;
        return mint(val);
    }
    mint operator *(const mint &r){
        return mint(1ll*v*r.v%mod);
    }
};
struct Node{
    mint kval,bval;
    Node(int _k=1,int _b=0):kval(_k),bval(_b){}
    Node operator +(const Node &r){
        Node res;
        res.kval=kval*r.kval;
        res.bval=bval*r.kval+r.bval;
        return res;
    }
};
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,ls[id]
    #define rson mid+1,r,rs[id]
    int ls[N*120],rs[N*120],cnt[N*120],cntn;
    Node val[N*120],rval[N*120];
    vector<int> stk;
    int New(){
        int nw;
        if(stk.empty()){
            nw=++cntn;
        }else{
            nw=stk.back();
            stk.pop_back();
        }
        ls[nw]=rs[nw]=0;
        val[nw]=rval[nw]=Node();
        return nw;
    }
    void PushUp(int id){
        if(ls[id]&&rs[id]){
            val[id]=val[ls[id]]+val[rs[id]];
            rval[id]=rval[rs[id]]+rval[ls[id]];
            cnt[id]=cnt[ls[id]]+cnt[rs[id]];
        }else{
            if(ls[id]){
                val[id]=val[ls[id]];
                rval[id]=rval[ls[id]];
                cnt[id]=cnt[ls[id]];
            }else{
                val[id]=val[rs[id]];
                rval[id]=rval[rs[id]];
                cnt[id]=cnt[rs[id]];
            }
        }
    }
    void Update(int P,int A,int B,int l,int r,int &id){
        if(!id) id=New();
        if(l==r){
            val[id]=rval[id]=Node(A,B);
            cnt[id]=1;
            return;
        }
        if(P<=mid) Update(P,A,B,lson);
        else       Update(P,A,B,rson);
        PushUp(id);
    }
    int Merge(int l,int r,int id,int pre){
        if(!id||!pre) return id|pre;
        if(l==r) msg("WARNING"),assert(0);
        ls[id]=Merge(lson,ls[pre]);
        rs[id]=Merge(rson,rs[pre]);
        PushUp(id);
        stk.push_back(pre);
        return id;
    }
    void Split(int key,int l,int r,int &id,int &nx){
        if(l==r||!id) return;
        nx=++cntn;
        if(ls[id]&&key<=cnt[ls[id]]){
            rs[nx]=rs[id];rs[id]=0;
            Split(key,lson,ls[nx]);
        }else{
            if(ls[id]) key-=cnt[ls[id]];
            Split(key,rson,rs[nx]);
        }
        PushUp(id);PushUp(nx);
    }
    void Erase(int l,int r,int id){
        stk.push_back(id);
        if(l==r) return;
        if(ls[id]) Erase(lson);
        if(rs[id]) Erase(rson);
    }
}t1;
struct SegTree2{
    Node val[N<<1];
    void Build(){
        forup(i,1,n){
            val[i+N]=Node();
        }
        fordown(i,N-1,0){
            val[i]=val[i<<1]+val[i<<1|1];
        }
    }
    void Update(int P,int A,int B){
        val[P+N]=Node(A,B);
        for(int i=(P+N)>>1;i;i>>=1){
            val[i]=val[i<<1]+val[i<<1|1];
        }
    }
    Node Query(int l,int r){
        Node resl,resr;
        for(l+=N,r+=N+1;l<r;l>>=1,r>>=1){
            if(l&1) resl=resl+val[l++];
            if(r&1) resr=val[--r]+resr;
        }
        return resl+resr;
    }
}t2;
map<pii,pii> odt;
using mit=map<pii,pii>::iterator;
mit split(int x){
    mit it=odt.lower_bound(mkp(x,0));
    if(it!=odt.end()&&it->fi.fi==x) return it;
    --it;
    int l=it->fi.fi,r=it->fi.se;
    int rt=it->se.fi,rev=it->se.se;
    t2.Update(l,1,0);
    odt.erase(it);
    int rtl=0,rtr=0;
    if(rev){
        t1.Split(r-x+1,0,M,rtr=rt,rtl);
        t2.Update(l,t1.rval[rtl].kval.v,t1.rval[rtl].bval.v);
        t2.Update(x,t1.rval[rtr].kval.v,t1.rval[rtr].bval.v);
        odt.insert(mkp(mkp(l,x-1),mkp(rtl,1)));
        return odt.insert(mkp(mkp(x,r),mkp(rtr,1))).fi;
    }else{
        t1.Split(x-l,0,M,rtl=rt,rtr);
        t2.Update(l,t1.val[rtl].kval.v,t1.val[rtl].bval.v);
        t2.Update(x,t1.val[rtr].kval.v,t1.val[rtr].bval.v);
        odt.insert(mkp(mkp(l,x-1),mkp(rtl,0)));
        return odt.insert(mkp(mkp(x,r),mkp(rtr,0))).fi;
    }
}
int Query(int l,int r,int x){
    if(r<n-1) split(r+1);
    split(l);
    Node res=t2.Query(l,r);
    return (res.kval*x+res.bval).v;
}
void work(int l,int r,int rev){
    mit ed=split(r+1),st=split(l);
    int rt=0;
    for(mit it=st;it!=ed;odt.erase(prev(++it))){
        t2.Update(it->fi.fi,1,0);
        rt=t1.Merge(0,M,rt,it->se.fi);
    }
    if(rev){
        t2.Update(l,t1.rval[rt].kval.v,t1.rval[rt].bval.v);
    }else{
        t2.Update(l,t1.val[rt].kval.v,t1.val[rt].bval.v);
    }
    odt.insert(mkp(mkp(l,r),mkp(rt,rev)));
}
void Point(int i,int p,int a,int b){
    if(i<n-1) split(i+1);
    mit it=split(i);
    t1.Erase(0,M,it->se.fi);
    int rt=0;
    t1.Update(p,a,b,0,M,rt);
    t2.Update(i,a,b);
    odt.erase(it);
    odt.insert(mkp(mkp(i,i),mkp(rt,0)));
}
signed main(){
    n=read();m=read();
    forup(i,0,n-1){
        int p=read(),a=read(),b=read();
        int rt=0;
        t1.Update(p,a,b,0,M,rt);
        t2.Update(i,a,b);
        odt.insert(mkp(mkp(i,i),mkp(rt,0)));
    }
    forup(i,1,m){
        int op=read();
        if(op==0){
            int i=read(),p=read(),a=read(),b=read();
            Point(i,p,a,b);
        }else if(op==1){
            int l=read(),r=read()-1,x=read();
            printf("%d\n",Query(l,r,x));
        }else if(op==2){
            int l=read(),r=read()-1;
            work(l,r,0);
        }else{
            int l=read(),r=read()-1;
            work(l,r,1);
        }
    }
}

模拟赛神秘题目 【1206 A组】B 生成树统计

《》

题意

• 给定一张 $n$ 个点，无自环，有重边的无向图。
• 再给定 $m$ 个点集 $S_i$。
• 求出这张图有多少生成树，满足对于任意 $i$，$S_i$ 的导出子图都是一个连通块（下文称这样的生成树为“合法”）。
• $1\le n\le 500,1\le m\le 2000$，答案对 $998244353$ 取模。

题解

很厉害吧。

设 $w(i,j)$ 表示有多少个 $S$ 同时包含点 $i,j$，容易发现生成树合法的一个必要条件是将 $w(i,j)$ 设为边 $(i,j)$ 的边权后，生成树边权和为 $\sum|S_i|-1$，不难发现这个条件也是充分的，因为每条边产生贡献的次数都足够多。

更进一步，我们容易发现任意一棵生成树边权和都不可能大于这个，于是转化成最大生成树计数问题（矩阵树定理典题），无解当且仅当最大生成树不等于这个。

于是做完了，最大生成树计数复杂度 $O(n^3)$，预处理 $w(i,j)$ 复杂度 $O(\frac{n^2m}{\omega})$。

参考代码

#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=505,M=2005,mod=998244353;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int n,m,grp[N][N],ans=1;
int val[N][N];
char str[N];
bitset<N> ed[N];
vector<pii> sve[M];
int a[N][N];
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool merge(int u,int v){
    u=getfa(u);v=getfa(v);
    if(u==v) return false;
    fa[u]=v;
    return true;
}
int tag[N],cntn;
vector<pii> e[N];
void dfs(int x){
    tag[x]=++cntn;
    for(auto i:e[x]){
        if(tag[i.fi]==-1){
            dfs(i.fi);
        }
        (a[tag[x]][tag[i.fi]]+=mod-i.se)%=mod;
        (a[tag[x]][tag[x]]+=i.se)%=mod;
    }
}
int calcdet(int n){
    msg("===\n");
    forup(i,1,n+1){
        forup(j,1,n+1){
            msg("%d ",a[i][j]);
        }
        msg("|\n");
    }
    int res=1;
    forup(i,1,n){
        int j=i;
        while(j<=n&&!a[j][i]) ++j;
        if(j>n) return 0;
        forup(k,1,n){
            swap(a[i][k],a[j][k]);
        }
        int inv=ksm(a[i][i],mod-2);
        res=1ll*res*a[i][j]%mod;
        forup(j,i,n){
            a[i][j]=1ll*a[i][j]*inv%mod;
        }
        forup(j,i+1,n){
            fordown(k,n,i){
                a[j][k]=(a[j][k]+mod-1ll*a[j][i]*a[i][k]%mod)%mod;
            }
        }
    }
    msg("====\n");
    forup(i,1,n){
        forup(j,1,n){
            msg("%d ",a[i][j]);
        }
        msg("|\n");
    }
    forup(i,1,n){
        res=1ll*res*a[i][i]%mod;
    }
    msg("===%d\n",res);
    return res;
}
int solve(int x){
    cntn=0;
    dfs(x);
    int res=calcdet(cntn-1);
    forup(i,1,cntn){
        forup(j,1,cntn){
            a[i][j]=0;
        }
    }
    return res;
}
void work(int v){
    msg("[%d]\n",v);
    forup(i,0,n-1) e[i].clear();
    for(auto i:sve[v]){
        int u=getfa(i.fi),v=getfa(i.se);
        if(u==v) continue;
        tag[u]=tag[v]=-1;
        e[u].push_back(mkp(v,grp[i.fi][i.se]));
        e[v].push_back(mkp(u,grp[i.fi][i.se]));
        msg("{%d %d|%d}\n",u,v,grp[i.fi][i.se]);
    }
    forup(i,0,n-1){
        if(tag[i]==-1){
            ans=1ll*ans*solve(i)%mod;
        }
    }
    for(auto i:sve[v]){
        merge(i.fi,i.se);
    }
}
struct Node{
    int u,v,w;
};
int calcmx(){
    forup(i,0,n-1){
        fa[i]=i;
    }
    vector<Node> vec;
    forup(i,0,n-1){
        forup(j,i+1,n-1){
            if(grp[i][j]){
                vec.push_back(Node{i,j,val[i][j]});
            }
        }
    }
    sort(vec.begin(),vec.end(),[&](Node a,Node b){return a.w>b.w;});
    int sum=0;
    for(auto i:vec){
        if(merge(i.u,i.v)){
            sum+=i.w;
        }
    }
    return sum;
}
signed main(){
    n=read();m=read();
    forup(i,0,n-1){
        fa[i]=i;
    }
    int cnt=n;
    forup(i,0,n-1){
        forup(j,i+1,n-1){
            grp[i][j]=read();
            ed[i][j]=(grp[i][j]!=0);
            if(grp[i][j]){
                if(merge(i,j)){
                    --cnt;
                }
            }
        }
    }
    if(cnt>1){
        puts("0");
        return 0;
    }
    int sum=0;
    forup(i,1,m){
        bitset<N> bs;
        scanf(" %s",str);
        int t=0;
        forup(i,0,n-1){
            bs[i]=(str[i]=='1');
            sum+=(str[i]=='1');
            if(str[i]=='1') t=1;
        }
        sum-=t;
        for(int p=bs._Find_first();p<=n;p=bs._Find_next(p)){
            bitset<N> b2=ed[p]&bs;
            for(int q=b2._Find_first();q<=n;q=b2._Find_next(q)){
                ++val[p][q];
            }
        }
    }
    forup(i,0,n-1){
        forup(j,i+1,n-1){
            if(grp[i][j]){
                msg("%d %d|%d\n",i,j,val[i][j]);
                sve[val[i][j]].push_back(mkp(i,j));
            }
        }
    }
    msg("%d %d|\n",calcmx(),sum);
    if(calcmx()!=sum){
        puts("0");
        return 0;
    }
    forup(i,0,n-1){
        fa[i]=i;
    }
    fordown(i,m,0){
        if(sve[i].size()){
            work(i);
        }
    }
    printf("%d\n",ans);
}

P2387 [NOI2014] 魔法森林

传送门

题意

• 有一张 $n$ 个点 $m$ 条边的图，每条边有两个权值 $a_i,b_i$。
• 现在有一个人想要从点 $1$ 到点 $n$，这个人有两个权值 $A,B$，想通过边 $i$ 必须要有 $A\ge a_i\land B\ge b_i$。
• 求他想从点 $1$ 到点 $n$ 所需 $A+B$ 的最小值是多少，无解输出 $-1$。
• $2\le n\le 50000,0\le m\le 100000,1\le a_i,b_i\le 50000$。

题解

LCT 板题。

不难想到枚举 $A$，查询所需最小的 $B$，那么需要动态维护最小生成树。

于是在每条边上开一个点，直接 LCT 维护点权最大值即可。

复杂度 $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=1e5+5,inf=1e18;
i64 n,m;
struct edge{
    i64 u,v,a,b;
}sv[N];
struct LCT{
    i64 ch[N][2],fa[N];
    i64 mx[N],mxp[N],val[N];
    i64 tag[N];
    void PushUp(i64 p){
        mx[p]=val[p];
        mxp[p]=p;
        if(ch[p][0]&&mx[ch[p][0]]>mx[p]){
            mx[p]=mx[ch[p][0]];
            mxp[p]=mxp[ch[p][0]];
        }
        if(ch[p][1]&&mx[ch[p][1]]>mx[p]){
            mx[p]=mx[ch[p][1]];
            mxp[p]=mxp[ch[p][1]];
        }
    }
    void modi(i64 p){
        swap(ch[p][0],ch[p][1]);
        tag[p]^=1;
    }
    void PushDown(i64 p){
        if(!tag[p]) return;
        if(ch[p][0]) modi(ch[p][0]);
        if(ch[p][1]) modi(ch[p][1]);
        tag[p]=0;
    }
    #define get(x) (x==ch[fa[x]][1])
    #define isRoot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)
    void Rotate(i64 x){
        i64 y=fa[x],z=fa[y],ss=get(x);
        if(!isRoot(y)) ch[z][y==ch[z][1]]=x;
        ch[y][ss]=ch[x][!ss];fa[ch[x][!ss]]=y;
        ch[x][!ss]=y;fa[y]=x;fa[x]=z;
        PushUp(y);PushUp(x);
    }
    void Update(i64 x){
        if(!isRoot(x)) Update(fa[x]);
        PushDown(x);
    }
    void Splay(i64 x){
        Update(x);
        for(i64 f=fa[x];f=fa[x],!isRoot(x);Rotate(x)){
            if(!isRoot(f)) Rotate(get(x)==get(f)?f:x);
        }
    }
    i64 Access(i64 x){
        i64 p=0;
        for(;x;p=x,x=fa[x]){
            Splay(x);ch[x][1]=p;PushUp(x);
        }
        return p;
    }
    void MakeRoot(i64 x){
        modi(Access(x));
    }
    i64 FindRoot(i64 p){
        Access(p);
        Splay(p);
        PushDown(p);
        while(ch[p][0]){
            p=ch[p][0];
            PushDown(p);
        }
        Splay(p);
        return p;
    }
    bool Connected(i64 x,i64 y){
        return FindRoot(x)==FindRoot(y);
    }
    void Link(i64 x,i64 y){
        if(Connected(x,y)) return;
        MakeRoot(x);Splay(x);
        fa[x]=y;
    }
    void Cut(i64 x,i64 y){
        MakeRoot(x);
        if(FindRoot(y)!=x||fa[y]!=x||ch[y][0]) return;
        ch[x][1]=fa[y]=0;
        PushUp(x);
    }
    pii Query(i64 x,i64 y){
        MakeRoot(x);
        i64 p=Access(y);
        return mkp(mx[p],mxp[p]);
    }
}mt;
i64 u[N],v[N];
signed main(){
    n=read();m=read();
    forup(i,1,m){
        sv[i].u=read();sv[i].v=read();
        sv[i].a=read();sv[i].b=read();
    }
    sort(sv+1,sv+m+1,[&](edge a,edge b){return a.a<b.a;});
    i64 ans=inf;
    int cntn=n;
    forup(i,1,m){
        if(mt.Connected(sv[i].u,sv[i].v)){
            pii rr=mt.Query(sv[i].u,sv[i].v);
            if(rr.fi>sv[i].b){
                i64 nw=rr.se;
                mt.Cut(nw,v[nw]);
                mt.Cut(nw,u[nw]);
                mt.mx[nw]=mt.val[nw]=sv[i].b;
                mt.mxp[nw]=nw;
                u[nw]=sv[i].u;v[nw]=sv[i].v;
                mt.Link(sv[i].u,nw);mt.Link(nw,sv[i].v);
            }
        }else{
            i64 nw=++cntn;
            mt.mx[nw]=mt.val[nw]=sv[i].b;
            mt.mxp[nw]=nw;
            u[nw]=sv[i].u;v[nw]=sv[i].v;
            mt.Link(sv[i].u,nw);mt.Link(nw,sv[i].v);
        }
        if(mt.Connected(1,n)){
            msg("%lld|%lld %lld|\n",i,sv[i].a,mt.Query(1,n).fi);
            msg("%lld|%lld %lld|\n",i,sv[i].a,mt.Query(1,n).fi);
            ans=min(ans,sv[i].a+mt.Query(1,n).fi);
        }
    }
    printf("%lld\n",ans==inf?-1:ans);
}

P2173 [ZJOI2012] 网络

传送门

题意

• 有一张 $n$ 个点 $m$ 条边的图，点有点权，边有颜色，值域为 $[0,C)$。
• 保证任意颜色的边不形成环，任意点相同颜色的出边至多两条。
• 有三种操作：
  • $0\;x\;v$：将点 $x$ 的权值变为 $v$。
  • $1\;x\;y\;w$：将边 $(x,y)$ 的颜色变为 $w$。
  • $2\;c\;x\;y$：询问由颜色为 $c$ 的边构成的图中，$x,y$ 之间简单路径上点权的最大值。
• 注意到操作 $1$ 可能让图变得不合法，不合法则报告为什么不合法（边不存在/出边过多/形成环），并且不修改，否则报告修改成功，并且修改。
• 操作 $2$ 不连通输出 $-1$。
• $1\le n\le 10^4，1\le m\le 10^5,0\le c< C\le 10$。

题解

LCT 版题，对每个颜色维护 LCT 即可。

比较有意思的是 LCT 的单点修改，类似于 Splay，MakeRoot 之后直接修改即可。

复杂度 $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=1e4+5,inf=0x3f3f3f3f;
int n,m,C,q,v[N];
int cntc[N][10];
struct LCT{
    int ch[N][2],fa[N];
    int mx[N];
    int tag[N];
    void PushUp(int p){
        mx[p]=v[p];
        if(ch[p][0]) mx[p]=max(mx[p],mx[ch[p][0]]);
        if(ch[p][1]) mx[p]=max(mx[p],mx[ch[p][1]]);
    }
    void modi(int id){
        swap(ch[id][0],ch[id][1]);
        tag[id]^=1;
    }
    void PushDown(int p){
        if(!tag[p]) return;
        if(ch[p][0]) modi(ch[p][0]);
        if(ch[p][1]) modi(ch[p][1]);
        tag[p]=0;
    }
    #define get(x) (x==ch[fa[x]][1])
    #define isRoot(x) (x!=ch[fa[x]][0]&&x!=ch[fa[x]][1])
    void Rotate(int x){
        int y=fa[x],z=fa[y],ss=get(x);
        if(!isRoot(y)) ch[z][y==ch[z][1]]=x;
        ch[y][ss]=ch[x][!ss];fa[ch[x][!ss]]=y;
        ch[x][!ss]=y;fa[y]=x;fa[x]=z;
        PushUp(y);PushUp(x);
    }
    void Update(int x){
        if(!isRoot(x)) Update(fa[x]);
        PushDown(x);
    }
    void Splay(int x){
        Update(x);
        for(int f=fa[x];f=fa[x],!isRoot(x);Rotate(x)){
            if(!isRoot(f)) Rotate(get(x)==get(f)?f:x);
        }
    }
    int Access(int x){
        int p=0;
        for(;x;p=x,x=fa[x]){
            Splay(x);ch[x][1]=p;PushUp(x);
        }
        return p;
    }
    void MakeRoot(int x){
        modi(Access(x));
    }
    int FindRoot(int p){
        Access(p);
        Splay(p);
        PushDown(p);
        while(ch[p][0]){
            p=ch[p][0];
            PushDown(p);
        }
        Splay(p);
        return p;
    }
    bool Connected(int x,int y){
        return FindRoot(x)==FindRoot(y);
    }
    void Link(int x,int y){
        if(Connected(x,y)) return;
        MakeRoot(x);Splay(x);
        fa[x]=y;
    }
    void Cut(int x,int y){
        MakeRoot(x);
        if(FindRoot(y)!=x||fa[y]!=x||ch[y][0]) return;
        ch[x][1]=fa[y]=0;
        PushUp(x);
    }
    int Query(int x,int y){
        if(!Connected(x,y)) return -1;
        MakeRoot(x);
        return mx[Access(y)];
    }
}t[10];
map<int,int> sve[N];
signed main(){
    n=read();m=read();C=read();q=read();
    forup(i,1,n){
        v[i]=read();
    }
    forup(i,1,m){
        int u=read(),v=read(),c=read();
        t[c].Link(u,v);
        sve[u][v]=sve[v][u]=c;
        ++cntc[u][c];++cntc[v][c];
    }
    forup(i,1,q){
        int op=read();
        if(op==0){
            int x=read(),y=read();
            forup(i,0,C-1){
                t[i].MakeRoot(x);
            }
            v[x]=y;
            forup(i,0,C-1){
                t[i].PushUp(x);
            }
        }else if(op==1){
            int u=read(),v=read(),w=read();
            if(!sve[u].count(v)){
                puts("No such edge.");
                continue;
            }
            if(w==sve[u][v]){
                puts("Success.");
                continue;
            }
            if(cntc[u][w]==2||cntc[v][w]==2){
                puts("Error 1.");
                continue;
            }
            if(t[w].Connected(u,v)){
                puts("Error 2.");
                continue;
            }
            puts("Success.");
            int c=sve[u][v];
            --cntc[u][c];--cntc[v][c];
            t[c].Cut(u,v);
            sve[u][v]=sve[v][u]=w;
            ++cntc[u][w];++cntc[v][w];
            t[w].Link(u,v);
        }else{
            int c=read(),u=read(),v=read();
            printf("%d\n",t[c].Query(u,v));
        }
    }
}

QOJ#6354 4

传送门

题意

• 给定 $n$ 个点 $m$ 条边的无向图，对 $K_4$（四元完全子图）进行计数。
• $4\le n\le 10^5,0\le m\le 10^5$

题解

妙妙题。

回忆一下经典题三元环计数，那道题是怎么做的。经典做法是给每条边定向，从度数更小的点指向度数更大的点。这样每个点出度就是 $O(\sqrt{n})$ 级别的，那么直接暴力，对每个点 $u$ 枚举一条出边 $v$ 再枚举 $v$ 的出边就行了，这样每个点会总共作为 $v$ 恰好 $m$ 次，然后再枚举出边是 $O(\sqrt{m})$ 的，于是 $O(m\sqrt{m})$。

那么这道题怎么做呢？考虑四元完全子图就是其中一个点出边的点集中的三元环，那么类似地，对边定向然后直接对这玩意进行三元环计数就能 $O(m\sqrt{m}+n\cdot m^{\frac{3}{4}})$ 了，但是好像不太能过。

考虑一个更暴力的做法：直接对点集进行 $O(\frac{|S|^2}{\omega})$ 暴力（枚举一条边，求两端点邻居的交），然后惊讶地发现这样做总复杂度是 $O(m\sqrt{m}+\frac{m^2}{\omega})$ 的，考虑 $\sum |S|=m$，那么就是将 $m$ 分为若干个 $s_i$ 相加，求 $\sum s_i^3$ 的上界，并且每个 $s_i$ 均有 $s_i\le 2\sqrt{m}$，不难想到在 $s_i$ 全取到 $2\sqrt{m}$ 时是最大的，此时总和是 $O(m^2)$ 级别的。

参考代码

#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=0x3f3f3f3f;
i64 n,m;
vector<i64> e[N],e2[N];
i64 vis[N];
bitset<640> ed[640];
i64 work(i64 u){
    i64 nw=0;
    for(auto v:e2[u]){
        vis[v]=++nw;
    }
    vector<pii> seq;
    for(auto p:e2[u]){
        for(auto q:e2[p]){
            if(vis[q]){
                seq.push_back(mkp(vis[p],vis[q]));
                ed[vis[p]][vis[q]]=ed[vis[q]][vis[p]]=1;
            }
        }
    }
    i64 cnt=0;
    for(auto i:seq){
        cnt+=(ed[i.fi]&ed[i.se]).count();
    }
    forup(i,1,nw){
        ed[i].reset();
    }
    for(auto v:e2[u]){
        vis[v]=0;
    }
    return cnt/3;
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        i64 u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    forup(i,1,n){
        for(auto j:e[i]){
            if(e[j].size()>e[i].size()||(e[j].size()==e[i].size()&&j>i)){
                e2[i].push_back(j);
            }
        }
    }
    i64 ans=0;
    forup(u,1,n){
        ans+=work(u);
    }
    printf("%lld\n",ans);
}

QOJ#7514 Clique Challenge

传送门

题意

• 给定一张 $n$ 个点 $m$ 条边的图，求该图中团（完全子图）的数量。
• $1\le n,m\le 1000$

题解

神秘的团搜索算法。感觉 $1000$ 已经是极限了。

首先如果 $n\le 50$，不难想到折半搜索，直接暴力是 $O(2^{\frac{n}{2}}\times n)$ 的，不太能过，但是可以递推，设 $f(S)$ 为点集 $S$ 中团的信息（可能是最大值/个数/权值等等），那么可以随便找 $S$ 中一个点，从 $f(S\setminus x)$ 和 $f((S\setminus x)\cap G_x)$ 递推过来（其中 $G_x$ 是 $x$ 的邻居点集），这个递推就是枚举是否计算 $x$ 的贡献。

那么这道题怎么做呢？做了上一题不难想到和上一题一样对边定向，那么转化为若干个规模不超过 $\sqrt{2m}$ 的问题，仍然还是每一个点集大小都取到上界时最劣，复杂度为 $O(\sqrt{\frac{m}{2}}2^{\frac{\sqrt{2m}}{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 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=1005,mod=1e9+7;
int n,m,ans;
int deg[N];
vector<int> e[N];
vector<pii> sve;
int vis[N];
i64 grp[50];
int cnt[1<<23];
bool f[1<<23];
i64 nei[1<<23];
int work(int p){
    int nw=0,res=0;
    for(auto u:e[p]){
        vis[u]=++nw;
        grp[nw]=(1ll<<(nw-1));
    }
    for(auto u:e[p]){
        for(auto v:e[u]){
            if(vis[v]){
                int pu=vis[u],pv=vis[v];
                grp[pu]|=(1ll<<(pv-1));
                grp[pv]|=(1ll<<(pu-1));
            }
        }
    }
    int w=nw/2;
    cnt[0]=1;
    forup(i,1,(1ll<<w)-1){
        cnt[i]=0;
        int u=__builtin_ctz(i)+1,pp=i^(1ll<<(u-1));
        cnt[i]=cnt[pp]+cnt[pp&grp[u]];
    }
    f[0]=1;nei[0]=(1ll<<w)-1;
    forup(i,0,(1ll<<(nw-w))-1){
        if(i){
            f[i]=0;
            int u=__builtin_ctz(i)+w+1;
            i64 pp=i^(1ll<<(u-w-1)),msk=pp<<w;
            f[i]=f[pp]&&((msk&grp[u])==msk);
            nei[i]=nei[pp]&grp[u];
        }
        if(f[i]){
            (res+=cnt[nei[i]])%=mod;
        }
    }
    for(auto u:e[p]){
        vis[u]=0;
    }
    return res;
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        int u=read(),v=read();
        ++deg[u];++deg[v];
        sve.push_back(mkp(u,v));
    }
    for(auto i:sve){
        int u=i.fi,v=i.se;
        if(deg[i.fi]>deg[i.se]||(deg[i.fi]==deg[i.se]&&i.fi>i.se)) swap(u,v);
        e[u].push_back(v);
    }
    forup(u,1,n){
        (ans+=work(u))%=mod;
    }
    printf("%d\n",ans);
}

QOJ#9783 Duloc Network

传送门

题意

• 交互题。
• 有一张 $n$ 个点的图，你需要通过若干次询问判断这张图是否连通。
• 每次询问你可以给交互库一个点集，交互库返回与这个点集中的点相邻，但不在这个点集中的点数。
• $1\le n\le 200$，询问次数不能超过 $3500$。

题解

妙妙题。

不难发现不连通当且仅当点 $1$ 所在的连通块大小不为 $n$，于是考虑找到点 $1$ 所在的连通块。

设 $f(S)$ 为交互库的返回值，不难发现 $f(S)+f(T)\ne f(S+T)$（其中 $S,T$ 无交）当且仅当 $\exists u\in S,v\in T$ 满足 $u,v$ 相邻。

那么我们可以维护点 $1$ 所在的连通块，然后二分找到现在和这个连通块相邻的最小点，询问次数大约是 $2n\log n$，时间复杂度 $O(n^2\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
const int N=205,inf=0x3f3f3f3f;
int n,bs[N],vis[N];
int query(int p,int r){
    cout<<"? ";
    forup(i,1,n){
        if(vis[i]){
            cout<<p;
        }else{
            cout<<(i<=r);
        }
    }
    cout<<endl;
    int v;cin>>v;
    return v;
}
int val0;
signed main(){
    cin>>n;
    vis[1]=1;
    int cnt=1;
    val0=query(1,0);
    while(val0){
        int ll=0,rr=n,mm;
        while(ll<rr){
            mm=(ll+rr)>>1;
            if(val0+query(0,mm)!=query(1,mm)) rr=mm;
            else ll=mm+1;
        }
        if(ll==0) break;
        vis[ll]=1;
        val0=query(1,0);
        ++cnt;
    }
    if(cnt==n){
        cout<<"! 1"<<endl;
    }else{
        cout<<"! 0"<<endl;
    }
}

QOJ#9490 Sub Brackets

传送门

题意

• 有一个长度为 $n$ 的括号序列，给定有 $m$ 个区间。
• 你现在需要确定每个点是左括号还是右括号，最大化这 $m$ 个区间中是合法括号子区间的数量。
• 你只需要输出最大数量。
• $1\le n,m\le 500$。

题解

还是挺妙的。

不妨先来想想何时能使所有 $m$ 个区间全部合法。

容易发现当存在某区间长度为奇数，或两区间交的长度为奇数时必定不合法，考虑这个条件是否是无解的必要条件。

考虑证否命题：不存在上述情况时必定合法。

不存在上述条件时，区间两两的交长度都是偶数，那么可以将其划分为三个不交的区间，只要三部分合法那两部分必定合法，容易构造出合法括号子区间。于是只考虑包含的情况，在包含时，我们发现将中间的所有小区间全部去掉，剩下的部分是个合法的括号序列就行了。以上，我们用构造法证明了必要性。

那么就转化成了一个最大独立集问题，发现两区间交为偶数仅当其左端点奇偶性不同，那么其实是二分图最大独立集，即为点数减去最大匹配，复杂度 $O(n^3)$（因为是稠密图），貌似匈牙利算法会快一点。

参考代码

#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=505,inf=0x3f3f3f3f;
int n,m;
struct Range{
    int l,r,pos;
}s[N];
int cntn;
namespace flow{
    struct edge{
        int v,rst,nxt;
    }e[N*N*4];
    int head[N],cur[N],cnte=1,dpt[N],s,t;
    void adde(int u,int v,int w){
        e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
    }
    bool bfs(){
        forup(i,1,t){
            cur[i]=head[i];
            dpt[i]=-1;
        }
        queue<int> q;
        dpt[s]=0;
        q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v,rst=e[i].rst;
                if(dpt[v]!=-1||!rst) continue;
                dpt[v]=dpt[u]+1;
                q.push(v);
            }
        }
        return ~dpt[t];
    }
    int dfs(int x,int flow){
        if(x==t||!flow) return flow;
        int res=0;
        for(int &i=cur[x];i;i=e[i].nxt){
            int v=e[i].v,rst=e[i].rst;
            if(dpt[v]!=dpt[x]+1||!rst) continue;
            int gt=dfs(v,min(rst,flow-res));
            if(gt){
                e[i].rst-=gt;
                e[i^1].rst+=gt;
                res+=gt;
                if(flow==res) break;
            }
        }
        return res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,inf);
        }
        return ans;
    }
}
vector<int> pos[N];
signed main(){
    n=read();m=read();
    cntn=0;
    forup(i,1,m){
        Range nw;
        nw.l=read();nw.r=read();
        if((nw.r^nw.l)&1){
            nw.pos=++cntn;
            s[cntn]=nw;
        }
    }
    sort(s+1,s+cntn+1,[&](Range a,Range b){return a.l<b.l;});
    flow::s=cntn+1;flow::t=cntn+2;
    forup(i,1,m){
        if(s[i].l&1){
            flow::adde(flow::s,s[i].pos,1);
        }else{
            flow::adde(s[i].pos,flow::t,1);
        }
        for(int j=s[i].l;j<=s[i].r;j+=2){
            for(auto v:pos[j]){
                if(s[i].l&1){
                    flow::adde(s[i].pos,v,1);
                }else{
                    flow::adde(v,s[i].pos,1);
                }
            }
        }
        pos[s[i].r].push_back(s[i].pos);
    }
    printf("%d\n",cntn-flow::dinic());
}

模拟赛神秘题目 【1211 A组】A 01串

题意

• 给定一个长度为 $n$ 的由 0,1,? 构成的字符串 $T$，求满足以下条件的由 $01$ 序列构成的序列 $S_i$ 的个数：
  • $|S_i|=i$
  • $S_{i+1}$ 可以由 $S_i$ 加上一个字符得到。
  • $S_n$ 可以将 $T$ 中的问号替换为 0,1 得到。
• $1\le n\le 250000$，答案对 $998244353$ 取模。

题解

太神秘了。

先不考虑问号，考虑这么一个策略：

对于连续的 $0$，如果要删一个 $0$ 我们视为删掉最左边的。对于连续的 $1$，如果要删一个视为删最右边的。

那么每次操作相当于将一个 10 子串合并为一个 ?。我们可以将其视作删掉一个“空格”，那么对于初始的 1，必有它右侧的空格比它左边的先删掉，对于 0 则是左边比右边先删掉，? 则无要求。

那么对于连续的长度为 $len$ 的非 ? 序列，相当于构造一个长度为 $len+1$ 的排列满足 $n-1$ 个相邻数的不等关系，那么显然 ? 将其分为了若干个独立的问题，乘一个多重集组合数即可。对于单个问题，有简单 $O(n^2)$ DP，但是与正解关系不大就不过多讨论，考虑这么一个容斥做法：

设 $dp_i$ 表示考虑前 $i$ 个空格（第 $1$ 个数左边的空格为第 $0$ 个）的合法排列数，考虑以 $i$ 结尾的极长上升段，假设是从前一个 $1$ 的位置 $j$ 开始，注意到我们需要求一个多重集组合数，于是不妨将所有 $dp_i$ 先除以一个 $i!$，后面再乘回来。那么 $dp_i\gets dp_j\times \frac{1}{(i-j)!}$，但是显然这会算到 $j < j+1$ 的情况，这是不合法的，于是再枚举下一个 $1$，乘一个 $-1$ 转移过来，那么转移方程如下（其中 $s$ 为题目给定序列 $cnt_i=\sum_{j=1}^i[s_j=1]$）：

$$ dp_i=(-1)^{cnt_{i-1}}\times \frac{1}{(i+1)!}+\sum_{j=0}^{i-1}s_j=1^{cnt_{i-1}-cnt_j}dp_j\times \frac{1}{(i-j)!} $$

前面的 $(-1)^{cnt_{i-1}}\times \frac{1}{(i+1)!}$ 表示钦定全部为 $0$ 的情况，注意编号从 $0$ 开始所以要乘以 $i+1$ 的阶乘分之一。

不难发现这个式子可以将 $i$ 和 $i-j$ 相关项拆开，那么是易于半在线卷积（或称分治 NTT）维护的。

于是做完了，复杂度 $O(n\log^2 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(s,b) memset(s,b,sizeof(s))
#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<<19|5,mod=998244353,inv3=332748118;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int n;
char str[N];
int fact[N],finv[N];
int binom(int n,int m){
    if(n<m) return 0;
    return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
int s[N],cnt[N];
int dp[N],f[N],rev[N];
void NTT(int *f,int n,int type){
    int w=31^__builtin_clz(n);
    forup(i,0,n-1){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(w-1));
        if(i<rev[i]) swap(f[i],f[rev[i]]);
    }
    for(int len=1;len<n;len<<=1){
        int wn=ksm(type==1?3:inv3,(mod-1)/(len<<1));
        for(int i=0;i<n;i+=(len<<1)){
            int nw=1;
            forup(j,0,len-1){
                int x=f[i+j],y=1ll*nw*f[i+len+j]%mod;
                f[i+j]=(x+y)%mod;
                f[i+len+j]=(x+mod-y)%mod;
                nw=1ll*nw*wn%mod;
            }
        }
    }
    if(type==-1){
        int inv=ksm(n,mod-2);
        forup(i,0,n-1) f[i]=1ll*f[i]*inv%mod;
    }
}
int a[N],b[N],c[N];
void solve(int l,int r){
    if(l==r){
        if(l==0){
            dp[l]=1;
        }else{
            dp[l]=1ll*dp[l]*(cnt[l-1]&1?mod-1:1)%mod;
            (dp[l]+=1ll*(cnt[l-1]&1?mod-1:1)*finv[l+1]%mod)%=mod;
        }
        f[l]=1ll*s[l]*dp[l]%mod*(cnt[l]&1?mod-1:1)%mod;
        return;
    }
    int mid=(l+r)>>1;
    solve(l,mid);
    int len=(r-l+1)<<1;
    forup(i,0,len){
        a[i]=b[i]=c[i]=0;
    }
    forup(i,l,r){
        if(i<=mid) a[i-l]=f[i];
        if(i>l) b[i-l]=finv[i-l];
    }
    NTT(a,len,1);NTT(b,len,1);
    forup(i,0,len){
        c[i]=1ll*a[i]*b[i]%mod;
    }
    NTT(c,len,-1);
    forup(i,mid+1,r){
        (dp[i]+=c[i-l])%=mod;
    }
    solve(mid+1,r);
}
int work(int l,int r){
    int len=r-l+2;
    int p=1;
    while(p<len) p<<=1;
    forup(i,0,p){
        s[i]=cnt[i]=dp[i]=0;
    }
    forup(i,l,r){
        s[i-l]=(str[i]=='1');
    }
    cnt[0]=s[0];
    forup(i,1,p-1){
        cnt[i]=cnt[i-1]+s[i];
    }
    dp[0]=1;
    solve(0,p-1);
    return 1ll*fact[len]*dp[len-1]%mod;
}
signed main(){
    n=read();
    scanf(" %s",str+1);
    fact[0]=1;
    forup(i,1,n+1) fact[i]=1ll*fact[i-1]*i%mod;
    finv[n+1]=ksm(fact[n+1],mod-2);
    fordown(i,n,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
    int lst=0;
    int ans=fact[n+1];
    str[n+1]='?';
    forup(i,1,n+1){
        if(str[i]=='?'){
            if(lst!=i-1){
                ans=1ll*ans*work(lst+1,i-1)%mod*finv[i-lst]%mod;
            }
            lst=i;
        }
    }
    printf("%d\n",ans);
}

QOJ#9224 Express Eviction

传送门

题意

• 有一张 $n\times m$ 的网格图，每个格子可能是黑色或者白色，你可以在格子边缘上行走。
• 你不能走到黑色格子周围的边上或角上，但是你可以将黑色格子涂白。
• 现在你需要从左上角走到右下角，问至少需要将多少个黑色格子涂白。
• $1\le n,m\le 50$。

题解

最小割题。

直接做不太好做，但是考虑平面图的路径能和对偶图的割一一对应，那么能不能从对偶图上考虑呢？

考虑由格子构成的图，容易发现一个合法的割必定周围相邻两格全是白色的。不难想到不存在合法的割当且仅当在每一步可以将横纵坐标均变化不超过 $2$ 的情况下，从左或下边界走到右或上边界且只走黑色格子的路径。

那么我们需要删一些点使得不存在这样的路径，这就是最小割版题了，将每个格子裂成两个点连边即可，点边数为 $O(nm)$，常数挺大的，但是数据范围小。

参考代码

#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=55,inf=0x3f3f3f3f;
int n,m,a[N][N];
char str[N];
namespace flow{
    struct edge{
        int v,rst,nxt;
    }e[N*N*50];
    int head[N*N*2],cur[N*N*2],dpt[N*N*2],cnte=1,s,t;
    void adde(int u,int v,int w){
        e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
    }
    bool bfs(){
        forup(i,1,t){
            cur[i]=head[i];
            dpt[i]=-1;
        }
        queue<int> q;
        dpt[s]=0;
        q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v;
                if(!e[i].rst||dpt[v]!=-1) continue;
                dpt[v]=dpt[u]+1;
                q.push(v);
            }
        }
        return ~dpt[t];
    }
    int dfs(int x,int flow){
        if(x==t||!flow) return flow;
        int res=0;
        for(int &i=cur[x];i;i=e[i].nxt){
            int v=e[i].v,rst=e[i].rst;
            if(dpt[v]!=dpt[x]+1||!rst) continue;
            int gt=dfs(v,min(flow-res,rst));
            if(gt){
                e[i].rst-=gt;
                e[i^1].rst+=gt;
                res+=gt;
                if(res==flow) break;
            }
        }
        return res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,inf);
        }
        return ans;
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,n){
        scanf(" %s",str+1);
        forup(j,1,m){
            a[i][j]=(str[j]=='#');
        }
    }
    flow::s=n*m*2+1;flow::t=flow::s+1;
    forup(i,1,n){
        forup(j,1,m){
            if(!a[i][j]) continue;
            int p=(i-1)*m+j,q=p+n*m;
            if(i==n||j==1) flow::adde(flow::s,p,inf);
            if(i==1||j==m) flow::adde(q,flow::t,inf);
            flow::adde(p,q,1);
            forup(h,-2,2){
                forup(w,-2,2){
                    if(h==0&&w==0) continue;
                    int nx=i+h,ny=j+w;
                    if(nx<1||nx>n||ny<1||ny>m||!a[nx][ny]) continue;
                    int pn=(nx-1)*m+ny;
                    flow::adde(q,pn,inf);
                }
            }
        }
    }
    printf("%d\n",flow::dinic());
}

QOJ#8517 Interesting Paths

传送门

题意

• 给定一张 $n$ 个点 $m$ 条边的 DAG，定义满足下列条件的路径序列是好的：
  • 每条路径的起点都是 $1$，终点都是 $n$。
  • 每条路径都包含至少一条此前从未出现过的边。
• 求最长的好的路径序列有多长（就是说你最多能往这个序列里面塞多少条路径）。
• $2\le n\le 10^6,1\le m\le 10^6$

题解

妙妙题。

首先显然“不存在一条从 $1$ 到 $n$ 的路径通过”的点和边是不需要的，所以我们只保留这些能被 $1\to n$ 的路径穿过的点和边。

然后找一下答案的上界，考虑建一棵以 $1$ 为根的外向树，不难发现每一条从 $1$ 开始的垂直树链至少会同时使用一次，那么除去 $1\to n$ 的树链，剩下的所有路径都需要经过至少一条非树边，一条边至多产生一次贡献，答案显然不会超过非树边条数 $+1$。

而这个上界是可以构造得到的，将非树边从深到浅作为“从未出现过的边”使用即可。于是就能 $O(n+m)$ 简单计算了。

参考代码

#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;
int n,m;
vector<int> e[2][N];
int vis[2][N];
void dfs(int x,int p){
    vis[p][x]=1;
    for(auto i:e[p][x]){
        if(vis[p][i]) continue;
        dfs(i,p);
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        int u=read(),v=read();
        e[0][u].push_back(v);
        e[1][v].push_back(u);
    }
    dfs(1,0);dfs(n,1);
    int cntn=0,cnte=0;
    forup(i,1,n){
        if(vis[0][i]&&vis[1][i]){
            ++cntn;
            for(auto v:e[0][i]){
                if(vis[0][v]&&vis[1][v]) ++cnte;
            }
        }
    }
    if(!vis[0][n]){
        puts("0");
    }else{
        printf("%d\n",cnte-cntn+2);
    }
}

CF843D Dynamic Shortest Path

传送门

题意

• 给定一张 $n$ 个点 $m$ 条边边带权的有向图，有 $q$ 次操作，每次操作在下面两个里面选一个：
  • $1\; v$：求点 $1$ 到 $v$ 的最短路长度。
  • $2\; c\;l_1\;l_2\;\cdots\; l_c$：将编号为 $l_1,l_2,\dots$ 的边边权加一。
• $1\le n,m\le 10^5,1\le q\le 2000,\sum c\le 10^6$，每次操作中，同一个 $l$ 不会出现两次。

题解

考验对最短路的理解。

首先可以 $O(n\log n)$ 先求出最短路。

不难想到每次操作每个点最短路的增量不会超过 $\min(c,n-1)$，因为一条最短路最多经过 $n-1$ 条边，那么考虑能不能对最短路的增量做最短路，这样可以不用堆维护，而是对每个权值开桶做到 $O(n+m)$。

设 $f_u$ 表示这次操作使得 $1\rightsquigarrow i$ 的最短路增加了多少，不难推出 $f$ 的递推式：

$$ f_v=\min_{(u,v,w)\in E}f_u+dis_u+w-dis_v $$

发现根据三角形不等式，$dis_u+w-dis_v$ 必定非负，可以使用 dijkstra。

复杂度大约是 $O(nq)$，因为 $n,m$ 大致相同我就不管了，需要卡常。

参考代码

#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<i64,int>;
#define fi first
#define se second
#define mkp make_pair
char *p1,*p2,buf[1<<21];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
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;
int n,m,q,vis[N];
i64 dis[N];
int num[N];
struct edge{
    int v,w,nxt;
}e[N];
int cnte,head[N];
int adde(int u,int v,int w){
    e[++cnte]=edge{v,w,head[u]};
    return head[u]=cnte;
}
void dij(){
    priority_queue<pii,vector<pii>,greater<pii>> q;
    forup(i,1,n){
        dis[i]=1e18;
    }
    dis[1]=0;
    q.push(mkp(0,1));
    while(q.size()){
        int u=q.top().se;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(dis[v]<=dis[u]+w) continue;
            dis[v]=dis[u]+w;
            q.push(mkp(dis[v],v));
        }
    }
}
int f[N];
vector<int> vec[N];
void dij2(int mx){
    forup(i,1,n){
        f[i]=n;vis[i]=0;
        vec[i].clear();
    }
    f[1]=0;
    vec[0].emplace_back(1);
    int pl=0;
    while(pl<=mx){
        if(vec[pl].empty()){
            ++pl;continue;
        }
        int u=vec[pl].back();vec[pl].pop_back();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=dis[u]+f[u]+e[i].w-dis[v];
            if(f[v]<=w) continue;
            f[v]=w;
            vec[w].emplace_back(v);
        }
    }
    forup(i,1,n){
        dis[i]+=f[i];
    }
}
signed main(){
    n=read();m=read();q=read();
    forup(i,1,m){
        int u=read(),v=read(),w=read();
        num[i]=adde(u,v,w);
    }
    dij();
    forup(i,1,q){
        int op=read();
        if(op==1){
            int v=read();
            printf("%lld\n",(vis[v]?dis[v]:-1));
        }else{
            int c=read();
            forup(i,1,c){
                int p=read();
                ++e[num[p]].w;
            }
            dij2(min(c,n-1));
        }
    }
}

模拟赛神秘题目 【1213 A组】C 逆转函数

《》

题意

• 给定一个由数字构成的长度为 $n$ 的字符串 $a_i$，字符集是不超过 $m$ 的正整数集（令 $A$ 为字符集）。
• 定义一个区间的权值如下：
  • 设一个函数 $f:A\to A$，问有多少种函数，能使这个区间 $[l,r]$ 的 $a_l,a_{l+1},\dots a_r$ 和 $f(a_r),f(a_{r-1}),\dots,f(a_l)$ 完全相同。
• 求所有区间的权值和。
• $1\le n,m\le 3\times 10^5$

题解

Manacher 技巧题。

不难想到使用类似回文串的技巧，使用类似 Manacher 的做法难点就在于拓展区间，但是我们显然不可能将一个区间的所有映射全部存下来，不然数据量就是 $O(n^2)$ 的了。一个很妙的想法是我们其实只需要维护每个字符的前驱后继（前后第一个相同字符的位置）$pre_i$ 和 $nxt_i$，那么拓展时只需要满足以下条件：

• $pre_r\le l$ 或 $a_{l+r-pre_r}=a_r$
• $nxt_l\ge r$ 或 $a_{l+r-nxt_l}=a_l$

就能从 $[l+1,r-1]$ 拓展到 $[l,r]$ 了。

然后若区间有解，那么区间的权值应为 $m^{m-c(l,r)}$，其中 $c(l,r)$ 是区间内的不同字符数。不难发现 $c(l,r)$ 也能在拓展的时候 $O(1)$ 递推（仍然使用前驱后继）。

但是有一个问题，Manacher 过程中，当复制了前面某个点的信息时可能会有一个收缩操作（即代码中 k=min(r-i+1,d[l+r-i])），直接暴力收缩的复杂度是否正确呢？

注意到当收缩发生时，Manacher 维护的“$r$ 最大的区间”必定发生变化，不妨设收缩前最右区间的中心点为 $p$，当前要求的区间是 $p+t$，显然它的信息是从 $p-t$ 复制过来的，因为 $p$ 是最右的区间，所以必然有 $r_{p-t}+p-t\le r_p+p$，即 $r_{p-t}-r_p\le t$，那么收缩次数就是 $(p-(r_p-p))-((p-t)-(r_{p-t}-(p-t)))=2t+r_{p-t}-r_{p}\le 3t$，是 $O(t)$ 级别的，而这次操作会让最右区间的中心点移动 $t$ 的距离，那么复杂度就是 $O(n)$ 了。

注意收缩时应关注点 $p-t$ 而非 $p+t$ 的信息，然后注意根据这个复杂度分析，显然在右端点恰好等于最右区间右端点时也应改变最右区间。

参考代码

#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;
int n,m,a[N],ans,pw[N];
int pre[N],nxt[N];
int lst[N];
int d[N],cc[N],val[N];
void manacher(){
    int r=0,l=1;
    forup(i,1,n){
        int k=1;
        if(i<=r){
            int p=l+r-i;
            cc[i]=cc[p];
            val[i]=val[p];
            k=d[p];
            while(i+k-1>r){
                val[i]=(val[i]+mod-pw[m-cc[i]])%mod;
                cc[i]-=(pre[p+k-1]<=p-k+1);
                cc[i]-=(nxt[p-k+1]>p+k-1);
                --k;
            }
        }else{
            cc[i]=1;
            val[i]=pw[m-cc[i]];
        }
        while(i+k<=n&&i-k>=1&&(pre[i+k]<=i-k||a[i*2-pre[i+k]]==a[i-k])&&(nxt[i-k]>=i+k||a[i*2-nxt[i-k]]==a[i+k])){
            cc[i]+=(pre[i+k]<=i-k);
            cc[i]+=(nxt[i-k]>i+k);
            (val[i]+=pw[m-cc[i]])%=mod;
            ++k;
        }
        d[i]=k--;
        (ans+=val[i])%=mod;
        if(i+k>=r){
            r=i+k;l=i-k;
        }
    }
    forup(i,1,n){
        d[i]=cc[i]=val[i]=0;
    }
    r=0;l=1;
    forup(i,2,n){
        int k=1;
        if(i<=r){
            int p=l+r-i+1;
            cc[i]=cc[p];
            val[i]=val[p];
            k=d[p];
            while(i+k-1>r){
                val[i]=(val[i]+mod-pw[m-cc[i]])%mod;
                cc[i]-=(pre[p+k-1]<=p-k);
                cc[i]-=(nxt[p-k]>p+k-1);
                --k;
            }
        }else{
            cc[i]=1+(a[i]!=a[i-1]);
            val[i]=pw[m-cc[i]];
        }
        while(i+k<=n&&i-k-1>=1&&(pre[i+k]<=i-k-1||a[i*2-1-pre[i+k]]==a[i-k-1])&&(nxt[i-k-1]>=i+k||a[i*2-1-nxt[i-k-1]]==a[i+k])){
            cc[i]+=(pre[i+k]<=i-k-1);
            cc[i]+=(nxt[i-k-1]>i+k);
            (val[i]+=pw[m-cc[i]])%=mod;
            ++k;
        }
        d[i]=k--;
        (ans+=val[i])%=mod;
        if(i+k>=r){
            r=i+k;l=i-k-1;
        }
    }
}
signed main(){
    n=read();m=read();
    pw[0]=1;
    forup(i,1,m){
        pw[i]=1ll*pw[i-1]*m%mod;
    }
    forup(i,1,n){
        a[i]=read();
    }
    forup(i,1,n){
        pre[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    forup(i,1,m) lst[i]=n+1;
    fordown(i,n,1){
        nxt[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    manacher();
    printf("%d\n",ans);
}

CF1477D Nezzar and Hidden Permutations

传送门

题意

• 给定 $m$ 个限制 $(l,r)$，你要构造两个长度为 $n$ 排列 $p,q$，满足对于任意一对限制，$(p_l-p_r)\times (q_l-q_r) > 0$。
• 最大化 $p_i\ne q_i$ 的位置数。
• $1\le n,m\le 5\times 10^5$，带多测 $\sum n,\sum m\le 5\times 10^5$

题解

太牛了。

首先不难把问题抽象成给无向图定向，然后给点标两个不同的点位最多的拓扑序。

不难想到度数为 $n-1$ 的点必有 $p_i=q_i$，因为不管怎么定向它前驱后继的个数都是确定的，同理删掉它之后找度数为 $n-2$ 的点，依此类推。

然后不难猜到可能不存在这样的点时能让所有位置都有 $p_i\ne q_i$，如何构造呢？

这就非常人类智慧了，考虑这张图的补图，因为每个点度数都不为 $n-1$ 则必然能分成若干个大小不小于 $2$ 的连通块。不难想到将值域分成一块一块的分给每个连通块就能让连通块之间合法了，于是考虑连通块内怎么做。

连通块内怎么做呢？一个非常牛的想法是求出生成树后将其分为若干个大小不小于 $2$ 的不共用点的菊花图，仍然把值域一块一块的分给菊花图，设值域为 $[l,r]$，将菊花图根的 $p,q$ 分别赋为 $l,r$，然后叶子的 $p$ 赋为 $l+1,l+2\dots r$，$q$ 赋为 $l,l+1,l+2\dots r-1$。因为是补图，所以叶子和根均没有连边，而叶子之间的限制显然是满足的。

那么我们只需要求出补图的生成森林即可。一个想法是用一个 set 维护所有点，每次选一个点将没有被删掉且没有和它连边的点全部在另一张图上连边，练了边就删掉。

于是做完了，复杂度 $O((n+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=5e5+5,inf=0x3f3f3f3f;
int n,m,p[N],q[N];
vector<int> e[N],e2[N];
set<pii> ss;
int deg[N];
int vis[N];
set<int> sp;
using sit=set<int>::iterator;
int blg[N],num[N],rt[N],cntb;
vector<int> seq[N];
void work(){
    sp.clear();
    forup(i,1,n){
        if(!p[i]){
            sp.insert(i);
        }
    }
    forup(u,1,n){
        if(p[u]) continue;
        vis[u]=1;
        for(auto v:e[u]){
            vis[v]=1;
        }
        for(sit it=sp.begin();it!=sp.end();){
            if(vis[*it]){
                ++it;
            }else{
                // msg("[%d %d]\n",u,*it);
                e2[u].push_back(*it);
                e2[*it].push_back(u);
                sp.erase(prev(++it));
            }
        }
        vis[u]=0;
        for(auto v:e[u]){
            vis[v]=0;
        }
    }
    cntb=0;
    forup(u,1,n){
        if(p[u]||blg[u]) continue;
        int cnt=0,p=0;
        for(auto v:e2[u]){
            if(!blg[v]){
                ++cnt;
            }else{
                p=v;
            }
        }
        msg("%d|%d %d|\n",u,cnt,p);
        if(cnt){
            ++cntb;
            num[cntb]=1;
            for(auto v:e2[u]){
                if(!blg[v]){
                    blg[v]=cntb;
                    ++num[cntb];
                }
            }
            blg[u]=cntb;rt[cntb]=u;
        }else{
            if(rt[blg[p]]==p||num[blg[p]]==2){
                blg[u]=blg[p];++num[blg[p]];
                rt[blg[p]]=p;
            }else{
                --num[blg[p]];
                blg[p]=blg[u]=++cntb;
                num[cntb]=2;rt[cntb]=u;
            }
        }
    }
    forup(i,1,n){
        if(p[i]) continue;
        if(i!=rt[blg[i]]) seq[blg[i]].push_back(i);
    }
    forup(i,1,cntb){
        msg("%d %d|",num[i],rt[i]);
        for(auto j:seq[i]){
            msg("%d ",j);
        }
        msg("|\n");
    }
    int v=1;
    forup(i,1,cntb){
        int l=v,r=v+num[i]-1;
        v+=num[i];
        p[rt[i]]=l;q[rt[i]]=r;
        for(auto u:seq[i]){
            p[u]=++l;q[u]=l-1;
        }
    }
}
void solve(){
    n=read();m=read();
    forup(i,1,n){
        e[i].clear();
        e2[i].clear();
        p[i]=q[i]=0;
        blg[i]=num[i]=rt[i]=0;
        seq[i].clear();
    }
    forup(i,1,m){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    ss.clear();
    forup(i,1,n){
        deg[i]=e[i].size();
        ss.insert(mkp(deg[i],i));
    }
    int cntn=n;
    while(ss.size()&&prev(ss.end())->fi==cntn-1){
        int u=prev(ss.end())->se;
        p[u]=q[u]=cntn--;
        ss.erase(prev(ss.end()));
        for(auto i:e[u]){
            if(p[i]) continue;
            ss.erase(mkp(deg[i],i));
            --deg[i];
            ss.insert(mkp(deg[i],i));
        }
    }
    work();
    forup(i,1,n){
        printf("%d ",p[i]);
    }puts("");
    forup(i,1,n){
        printf("%d ",q[i]);
    }puts("");
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

CF1508D Swap Pass

传送门

题意

• 有一张二维坐标系，上面有 $n$ 个点，这 $n$ 个点的点权 $a_i$ 构成一个排列。
• 你可以进行以下操作任意次：
  • 选择两个点 $i,j$（可以相等）满足它们的连线不和之前画的连线相交（端点处相交不算相交，完全重合算相交）。
  • 将其用线段连接，并且交换 $a_i,a_j$。
• 你的目标是使得最终点权满足 $a_i=i$，构造一个方案，不要求最优。
• $1\le n\le 2000,|x_i|,|y_i|\le 10^6$，保证不存在三点共线，无解输出 $-1$。

题解

构造题。

不妨先考虑只有一个置换环的情况。

一个想法是按置换环的顺序依次操作，但是容易发现这样在一个置换环内就可能会出现边相交的情况。一个想法是定一个根，将其它点按顺序和它操作，因为不存在三点共线这样就显然正确了。

那么多个置换环怎么做呢？一个想法是将其成一个置换环，但是如何保证这样连出来的边不会相交呢？不难想到定根后将其作为原点将其它点按极角排序，然后枚举每个点，如果和它前后的点不属于同一个环就交换一下合并到同一个环。只要相邻的角不出现优角这样就是显然正确的。那么如何保证不出现优角呢？取横坐标最小的点即可。

复杂度 $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=2005;
int n,mp[N];
struct Node{
    int x,y,pos,val;
};
vector<Node> vec;
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;
}
vector<pii> ans;
signed main(){
    n=read();
    forup(i,1,n){
        fa[i]=i;
    }
    forup(i,1,n){
        Node nw;
        nw.x=read();nw.y=read();nw.val=read();
        nw.pos=i;
        if(nw.val!=i){
            merge(i,nw.val);
            vec.push_back(nw);
        }
    }
    if(vec.empty()){
        puts("0");
        return 0;
    }
    sort(vec.begin(),vec.end(),[&](Node a,Node b){return a.x>b.x;});
    Node rt=vec.back();vec.pop_back();
    int x=rt.x,y=rt.y;
    sort(vec.begin(),vec.end(),[&](Node a,Node b){return atan2(a.y-y,a.x-x)<atan2(b.y-y,b.x-x);});
    forup(i,0,vec.size()-1){
        mp[vec[i].pos]=i;
    }
    forup(i,1,vec.size()-1){
        if(getfa(vec[i].pos)!=getfa(vec[i-1].pos)){
            swap(vec[i].val,vec[i-1].val);
            merge(vec[i].pos,vec[i-1].pos);
            ans.push_back(mkp(vec[i].pos,vec[i-1].pos));
        }
    }
    for(int p=rt.pos,i=rt.val;i!=rt.pos;i=vec[mp[i]].val){
        ans.push_back(mkp(p,i));
    }
    printf("%d\n",(int)ans.size());
    for(auto i:ans){
        printf("%d %d\n",i.fi,i.se);
    }
}

CF1662J Training Camp

传送门

题意

• 有一个 $n\times n$ 的方阵，每一格有 $a_{i,j},c_{i,j}$ 两个权值，并且 $c_{i,j}$ 不是 $0$ 就是 $1$，每一行每一列的 $a_{i,j}$ 均构成排列。
• 在每一行每一列格选择一个格子涂黑，要求对于任意没有涂黑的格子，它所在行/列的黑色格子的 $a_{i,j}$ 要么全大于它，要么全小于它。
• 最大化涂黑的 $c_{i,j}$ 之和，求出 $c_{i,j}$ 之和最大是多少。
• $1\le n\le 128$

题解

考虑这个匹配不是很好刻画，怎么办呢？

考虑这么一个东西：对于每一个黑点，将其所在行比它小的点全部涂红，所在列比它大的全部涂蓝，显然每个黑点都会涂恰好 $n-1$ 个点，并且每个点被涂恰好一次。

那么我们能不能刻画每个点被涂色的情况呢？这启发我们进行最小割建模。

具体来说，首先由于我们割的是一个“点”，所以先把每个点割成两个，然后每一行/列按值从小到大连容量为正无穷的边。因为我们要最小化选出的 $0$ 的个数，所以将 $c_{i,j}=0$ 的点之间边的容量设为 $1$，为 $1$ 的设为 $0$。

但是有一个问题，我们必须割 $n$ 个点，直接这样建可能会让割点数量不对。怎么办呢？注意到割边数量不可能小于 $n$，那么我们将所有点间边的容量加上 $n$ 即可，这样多割点必定不优，后面计算答案时减去 $n^2$ 即可。

复杂度不会超过 $O(n^2m)$，随便过的。

参考代码

#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=150,inf=0x3f3f3f3f;
int n,a[N][N],c[N][N];
namespace flow{
    struct edge{
        int v,rst,nxt;
    }e[N*N*10];
    int head[N*N*2],cur[N*N*2],dpt[N*N*2],cnte=1,s,t;
    void adde(int u,int v,int w){
        e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
    }
    bool bfs(){
        forup(i,1,t){
            cur[i]=head[i];
            dpt[i]=-1;
        }
        queue<int> q;
        q.push(s);
        dpt[s]=0;
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v,rst=e[i].rst;
                if(dpt[v]!=-1||!rst) continue;
                dpt[v]=dpt[u]+1;
                q.push(v);
            }
        }
        return dpt[t]!=-1;
    }
    int dfs(int x,int flow){
        if(x==t||!flow) return flow;
        int res=0;
        for(int &i=cur[x];i;i=e[i].nxt){
            int v=e[i].v,rst=e[i].rst;
            if(dpt[v]!=dpt[x]+1||!rst) continue;
            int gt=dfs(v,min(flow-res,rst));
            if(gt){
                e[i].rst-=gt;
                e[i^1].rst+=gt;
                res+=gt;
                if(res==flow) break;
            }
        }
        return res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,inf);
        }
        return ans;
    }
}
int mp[N];
signed main(){
    n=read();
    forup(i,1,n){
        forup(j,1,n){
            a[i][j]=read();
        }
    }
    forup(i,1,n){
        forup(j,1,n){
            c[i][j]=read();
        }
    }
    flow::s=n*n*2+1;flow::t=flow::s+1;
    forup(i,1,n){
        forup(j,1,n){
            int p=(i-1)*n+j;
            flow::adde(p,p+n*n,!c[i][j]+1);
        }
    }
    forup(i,1,n){
        forup(j,1,n) mp[a[i][j]]=j;
        forup(j,1,n-1) flow::adde((i-1)*n+mp[j]+n*n,(i-1)*n+mp[j+1],inf);
        flow::adde(flow::s,(i-1)*n+mp[1],inf);
        flow::adde((i-1)*n+mp[n]+n*n,flow::t,inf);
    }
    forup(j,1,n){
        forup(i,1,n) mp[a[i][j]]=i;
        forup(i,1,n-1) flow::adde((mp[i]-1)*n+j+n*n,(mp[i+1]-1)*n+j,inf);
        flow::adde(flow::s,(mp[1]-1)*n+j,inf);
        flow::adde((mp[n]-1)*n+j+n*n,flow::t,inf);
    }
    printf("%d\n",n-flow::dinic()+n);
}

Gym101667J Strongly Matchable

传送门

题意

• 有一张 $n$ 个点 $m$ 条边的图，保证 $n$ 是偶数。
• 问这张图是否满足以下条件：
  • 对于任意一个选出 $\frac{n}{2}$ 个点作为左部点涂黑，其余点作为右部点涂白，删除两端点颜色相同的边得到的二分图均有完美匹配。
• $1\le n\le 100,0\le m\le \binom{n}{2}$

题解

超级妙妙题。

首先最好想到的是考虑判断是否存在涂色方式不存在完美匹配。

考虑 Hall 定理：有完美匹配的充要条件是对于任意一个左部点集合 $S$，其邻接集合 $P(S)$ 满足 $|N(S)|\ge |S|$。那么不妨先枚举一个 $S$，然后考虑 $P(S)$ 的最小值是多少。

设原图上 $S$ 的邻接集合为 $N(S)$，左部点 $T\supseteq S$，那么 $|P(S)|=|N(S)|-|N(S)\cap T|$，既然 |N(S)| 是固定的，那么考虑 $|N(S)\cap T|$ 的最大值是多少，不难发现就是 $\min(|N(S)|,\frac{n}{2}-|S|)$，于是不存在完美匹配当且仅当 $|S|-|N(S)|+\min(|N(S)|,\frac{n}{2}-|S|) > 0$，即 $\frac{n}{2}-|N(S)| > 0$，于是我们只需要找是否存在大小不超过 $\frac{n}{2}$ 的集合 $S$ 满足 $|N(S)| < \frac{n}{2}$ 即可。

然后又有一个转化，我们枚举一个集合 $Q$，查询是否存在大小不超过 $\frac{n}{2}$ 的集合 $S$ 满足 $N(S)\subseteq Q$。那么什么样的集合满足 $N(S)\subseteq Q$ 呢？不难发现就是将 $Q$ 中的点全部删掉后的一整个连通块。继续思考，在删掉一个大小小于 $n$ 的点集后，何时存在一个连通块大小不超过 $n$ 呢？显然当且仅当剩下的点不全连通。

于是继续转化，可以枚举两个点，找至少删几个点能让它们不连通，这个是最小割经典模型。

复杂度可以套 $O(nm\sqrt{S})$ 的结论，那么总复杂度就是 $O(n^3m\sqrt{n})$，因为跑不满还是比较能过的。

/// details | 参考代码 open: False tupe: success

#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=105,inf=0x3f3f3f3f;
int n,m;
namespace flow{
    struct edge{
        int v,rst,nxt;
    }e[N*N*6];
    int head[N*2],cur[N*2],dpt[N*2],cnte=1,s,t;
    void init(int p,int q){
        s=p;t=q;
        for(int i=2;i<=cnte;i+=2){
            e[i].rst+=e[i+1].rst;e[i+1].rst=0;
        }
    }
    void adde(int u,int v,int w){
        e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
        e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
    }
    bool bfs(){
        forup(i,1,n*2){
            cur[i]=head[i];
            dpt[i]=-1;
        }
        queue<int> q;
        q.push(s);
        dpt[s]=0;
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                int v=e[i].v,rst=e[i].rst;
                if(dpt[v]!=-1||!rst) continue;
                dpt[v]=dpt[u]+1;
                q.push(v);
            }
        }
        return dpt[t]!=-1;
    }
    int dfs(int x,int flow){
        if(x==t||!flow) return flow;
        int res=0;
        for(int &i=cur[x];i;i=e[i].nxt){
            int v=e[i].v,rst=e[i].rst;
            if(dpt[v]!=dpt[x]+1||!rst) continue;
            int gt=dfs(v,min(flow-res,rst));
            if(gt){
                e[i].rst-=gt;
                e[i^1].rst+=gt;
                res+=gt;
                if(res==flow) break;
            }
        }
        return res;
    }
    int dinic(){
        int ans=0;
        while(bfs()){
            ans+=dfs(s,inf);
        }
        return ans;
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,n){
        flow::adde(i,i+n,1);
    }
    forup(i,1,m){
        int u=read(),v=read();
        flow::adde(u+n,v,inf);
        flow::adde(v+n,u,inf);
    }
    forup(p,1,n){
        forup(q,p+1,n){
            flow::init(p+n,q);
            if(flow::dinic()<n/2){
                puts("-1");
                return 0;
            }
        }
    }
    puts("1");
}

///

CF1965F Conference

传送门

题意

• 有 $n$ 个教授，第 $i$ 个教授在第 $l_i$ 天到第 $r_i$ 天会在大学，这段时间学校可以邀请教授前来参加讲座。
• 一段时间 $[L,R]$ 能开设讲座当且仅当每一天都能邀请到不同的教授前来参加。
• 对于 $1\le k\le n$，求有多少长度为 $k$ 的时间段能开设讲座。
• $1\le n,l_i,r_i\le 2\times 10^5$

题解

妙妙题，考虑 Hall 定理。

一个结论是：若 $l_i$ 互不相同，且 $r_i$ 互不相同，那么 Hall 定理就只需要管 $[L,R]$ 这个全集是否有 $|P(S)|\ge |S|$，其中 $P(S)$ 表示 $S$ 的邻域。

因为我们考虑假设存在一个不合法的子集 $S$，我们将这个区间一点一点拓展，由于不存在 $l_i$ 或 $r_i$ 相同，那么当 $P(S)$ 加一时，$S$ 至少也会加一，于是我们只需要管全集 $[L,R]$ 了。

那么若 $l,r$ 不互相同，这玩意显然有单调性，于是我们只需要双指针即可维护，考虑能否将所有情况都转化为 $l,r$ 不同。

不难想到若两个 $l_i$ 相同，将其中更长的一个左端点向右平移即可，因为可以用调整法将原情况调整到这样的情况。$r_i$ 同理。

于是做完了，复杂度 $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=2e5+5,inf=0x3f3f3f3f;
int n,ans[N],vis[N];
struct Node{
    int l,r;
}s[N];
vector<int> vec[N];
int vl[N],vr[N];
signed main(){
    n=read();
    forup(i,1,n){
        s[i].l=read();s[i].r=read();
    }
    int mx=0;
    forup(i,1,n){
        vec[s[i].l].push_back(i);
        mx=max(mx,s[i].l);
    }
    priority_queue<pii,vector<pii>,greater<pii>> q;
    forup(i,1,mx){
        for(auto j:vec[i]){
            q.push(mkp(s[j].r,j));
        }
        while(q.size()&&q.top().fi<i){
            vis[q.top().se]=1;
            q.pop();
        }
        if(q.size()){
            int u=q.top().se;q.pop();
            s[u].l=i;
        }
        vec[i].clear();
    }
    mx=0;
    forup(i,1,n){
        if(vis[i]) continue;
        vec[s[i].r].push_back(i);
        mx=max(mx,s[i].r);
    }
    priority_queue<pii> q2;
    fordown(i,mx,1){
        for(auto j:vec[i]){
            q2.push(mkp(s[j].l,j));
        }
        while(q2.size()&&q2.top().fi>i){
            vis[q2.top().se]=1;
            q2.pop();
        }
        if(q2.size()){
            int u=q2.top().se;q2.pop();
            s[u].r=i;
        }
        vec[i].clear();
    }
    forup(i,1,n){
        if(!vis[i]){
            ++vl[s[i].l];++vr[s[i].r];
        }
    }
    int pl=1,cnt=0;
    forup(i,1,mx){
        cnt+=vl[i];
        while(cnt<(i-pl+1)){
            cnt-=vr[pl];
            ++pl;
        }
        ++ans[1];--ans[i-pl+2];
    }
    forup(i,1,n){
        ans[i]+=ans[i-1];
        printf("%d\n",ans[i]);
    }
}

QOJ#1812 Interesting Coloring

传送门

题意

• 给定一张 $n$ 个点 $m$ 条边的无向边双连通图，没有重边自环，你需要给每条边染色，然后对于每条边 $(u,v)$，找到一条路径 $u\rightsquigarrow v$，使得上面有至多 $8$ 种不同的颜色。
• 构造一个方案。
• $1\le n\le 5555,3\le m\le 9999$。

题解

尽显精妙的数值设计。

考虑这样一个做法：随便找一棵 dfs 生成树，给每条边树涂色使得每一条从根开始的路径上颜色数都不超过 $7$。因为非树边都是前向边，那么这样可以给非树边随意涂色，然后每个点随便找一个只有一条非树边的环就行了。

那么具体如何涂色呢？考虑这么一个贪心：将点 $u$ 的儿子按子树大小从大到小排序，然后从前往后先用 $u$ 的祖先中出现过的颜色，再用全新的颜色。这样就能保证每条从 $1$ 开始的链都有至多 $7$ 种颜色了。

为什么呢？设 $g(i)$ 表示若一个点的祖先中有 $i$ 种颜色，它的子树在最坏情况最大能是多少。不妨考虑想让子树不合法最小大小是多少，不难发现如果有至少 $i$ 个儿子大小超过 $g(i+1)$ 就不合法了，那么 $g(i)=1+i(g(i+1)+1)-1=i\cdot g(i+1)+i$。

然后我们惊讶地发现，若取 $g(8)=1$，我们能算出 $g(1)=5914 > 5555$，所以不可能达到“必须要 $8$ 种颜色”的情况。

于是做完了，复杂度 $O(n^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 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=1e4+5,inf=0x3f3f3f3f;
int n,m;
int u[N],v[N];
vector<pii> e[N],son[N];
int vis[N],ntr[N],co[N],sz[N],fp[N],dpt[N],ff[N];
vector<int> ans[N];
void dfs(int x,int fa){
    vis[x]=1;sz[x]=1;
    dpt[x]=dpt[fa]+1;
    ff[x]=fa;
    for(auto i:e[x]){
        int v=i.fi,p=i.se;
        if(v==fa) continue;
        if(vis[v]){
            ntr[p]=1;
            continue;
        }
        son[x].push_back(i);
        fp[v]=p;
        dfs(v,x);
        sz[x]+=sz[v];
    }
}
vector<int> vc;
int tt=0;
void dfs2(int x,int pc){
    vector<pii> vec;
    if(fp[x]){
        co[fp[x]]=pc;
    }
    for(auto i:son[x]){
        int v=i.fi;
        vec.push_back(mkp(sz[v],v));
    }
    sort(vec.begin(),vec.end(),greater<pii>());
    int nc=0;
    forup(i,0,vec.size()-1){
        if(nc<(int)vc.size()&&vc[nc]==pc) ++nc;
        if(nc>=(int)vc.size()){
            vc.push_back(++tt);
            dfs2(vec[i].se,tt);
            vc.pop_back();
        }else{
            dfs2(vec[i].se,vc[nc]);
            ++nc;
        }
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        u[i]=read();v[i]=read();
        e[u[i]].push_back(mkp(v[i],i));
        e[v[i]].push_back(mkp(u[i],i));
    }
    dfs(1,0);
    dfs2(1,0);
    forup(i,1,n){
        msg("%d %d|%d|\n",ff[i],fp[i],co[fp[i]]);
    }
    forup(i,1,m){
        if(ntr[i]){
            printf("%d ",++tt);
            if(dpt[u[i]]<dpt[v[i]]) swap(u[i],v[i]);
            vector<int> vec;
            vec.push_back(tt);
            for(int p=u[i];p!=v[i];p=ff[p]){
                vec.push_back(co[fp[p]]);
            }
            sort(vec.begin(),vec.end());
            vec.erase(unique(vec.begin(),vec.end()),vec.end());
            for(int p=u[i];p!=v[i];p=ff[p]){
                if(ans[fp[p]].empty()){
                    ans[fp[p]]=vec;
                }
            }
            ans[i]=vec;
        }else{
            printf("%d ",co[i]);
        }
    }
    puts("");
    forup(i,1,m){
        printf("%d ",(int)ans[i].size());
        for(auto j:ans[i]){
            printf("%d ",j);
        }
        puts("");
    }
}

CF600F Edge coloring of bipartite graph

传送门

题意

• 给定一张 $a+b$ 个点 $m$ 条边的二分图，其中 $a$ 个左部点，$b$ 个右部点。
• 现在你要给每条边染色，使得任意一个结点所有连边颜色不同。
• 最小化不同颜色数，输出方案。
• $1\le a,b\le 1000,0\le m\le 10^5$

题解

二分图边染色算法，比较类似匈牙利找增广路。

我们先枚举边 $(u,v)$，然后设 $\mathrm{mex_{\mathit{u}}}=C_1,\mathrm{mex_{\mathit{u}}}_v=C_2$（此处 $\mathrm{mex}$ 指一个点出边颜色中最小的没出现过的边），然后直接把这条边赋值为 $C_1$，若 $C_1=C_2$ 则显然正确，否则可能会和 $v$ 的一个出边（不妨设为 $(v,w)$）冲突，那么我们把 $(v,w)$ 染色为 $C_2$ 就不会冲突了，但是又可能和 $w$ 的出边 $(w,x)$ 冲突，由于 $(v,w)$ 原本颜色是 $C_1$，我们把它改成了 $C_2$，那么我们继续将 $(w,x)$ 改为 $C_1$ 是不会在 $w$ 处冲突的。

依次类推，类似于匈牙利算法找增广路，从左到右的边赋值为 $C_1$，从右到左的赋值为 $C_2$，由于是二分图没有奇环，所以这条增光路必定是一条点不重复的链（若重复则形成偶环，那么在那个环末尾就已经合法了），于是每次增广复杂度 $O(a+b)$，于是总复杂度 $O(m(a+b))$。

参考代码

#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=2005,M=1e5+5,inf=0x3f3f3f3f;
int a,b,m,c[M],ans;
int u[M],v[M],deg[N];
int co[N][N];
signed main(){
    a=read();b=read();m=read();
    forup(i,1,m){
        u[i]=read();v[i]=read()+a;
        ++deg[u[i]];++deg[v[i]];
    }
    forup(i,1,a+b) ans=max(ans,deg[i]);
    forup(i,1,m){
        int c1=1,c2=1;
        while(co[u[i]][c1]) ++c1;
        while(co[v[i]][c2]) ++c2;
        co[u[i]][c1]=v[i];
        co[v[i]][c2]=u[i];
        if(c1==c2) continue;
        for(int tmp=c2,w=v[i];w;w=co[w][tmp],tmp^=c1^c2){
            swap(co[w][c1],co[w][c2]);
        }
    }
    printf("%d\n",ans);
    forup(i,1,m){
        forup(j,1,ans){
            if(co[u[i]][j]==v[i]){
                printf("%d ",j);
                break;
            }
        }
    }
}

P10062 [SNOI2024] 拉丁方

传送门

题意

• 有一个 $n$ 行 $n$ 列的数字矩阵，值域为 $[1,n]$，给定这个矩阵左上角 $R\times C$ 的子矩阵，保证不存在某一行/列存在两个相同的数。
• 构造矩阵剩下的部分，使得这个矩阵每一行每一列都是排列。
• $1\le n\le 500$

题解

还是比较复杂的，第一眼感觉是 flow 结果死活想不出来，然后发现需要不会的板子。

首先考虑简化的问题：若 $R=n$ 怎么做。首先不难发现这样必定有解，那么如何构造呢？

对于每一个空列，我们需要分配每种颜色各一个，对于每一行，我们需要补齐这一行没有的颜色。不难想到这类似于二分图匹配，但是并不好概括“颜色”的信息。怎么办呢？一个想法是将每一行最为二分图左部点，每一种颜色作为二分图右部点，构造二分图边染色模型（即上面这道题），将每一列作为边的颜色。每条边 $(u,v,c)$ 的意义是：第 $u$ 行的颜色 $v$ 被填在了第 $c$ 列。

那么 $R\ne n$ 的情况呢？不难想到先将左侧 $n\times C$ 的矩形解决，就转化成了上面的问题。首先无解是易于判断的，若某种颜色需求量超过了 $n-R$ 那么就必不可能给每一列都贡献，那么剩下的也能和上面一样的做了。

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

参考代码

#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=505;
int n,r,c,a[N][N];
pii ed[N*N];
int cnte;
int v[N*N],co[N*2][N*2];
void work(int n){
    mem(co,0);mem(v,0);
    forup(i,1,cnte){
        int u=ed[i].fi,v=ed[i].se;
        int c1=1,c2=1;
        while(co[u][c1]) ++c1;
        while(co[v][c2]) ++c2;
        co[u][c1]=v;co[v][c2]=u;
        if(c1==c2) continue;
        for(int tmp=c2,w=v;w;w=co[w][tmp],tmp^=c1^c2){
            swap(co[w][c1],co[w][c2]);
        }
    }
    forup(i,1,cnte){
        forup(j,1,n){
            if(co[ed[i].fi][j]==ed[i].se){
                v[i]=j;
            }
        }
    }
}
int vis[N],cnt[N];
void solve(){
    n=read();r=read();c=read();
    mem(cnt,0);
    forup(i,1,r){
        forup(j,1,c){
            a[i][j]=read();
        }
    }
    cnte=0;
    forup(j,1,c){
        forup(i,1,r){
            vis[a[i][j]]=1;
        }
        forup(i,1,n){
            if(!vis[i]){
                ed[++cnte]=mkp(j,i+c);
                ++cnt[i];
            }
            vis[i]=0;
        }
    }
    forup(i,1,n){
        if(cnt[i]>n-r){
            puts("No");
            return;
        }
    }
    work(c+n);
    forup(i,1,cnte){
        a[v[i]+r][ed[i].fi]=ed[i].se-c;
    }
    cnte=0;
    forup(i,1,n){
        forup(j,1,c){
            vis[a[i][j]]=1;
        }
        forup(j,1,n){
            if(!vis[j]){
                ed[++cnte]=mkp(i,j+n);
            }
            vis[j]=0;
        }
    }
    work(n+n);
    forup(i,1,cnte){
        a[ed[i].fi][v[i]+c]=ed[i].se-n;
    }
    puts("Yes");
    forup(i,1,n){
        forup(j,1,n){
            printf("%d ",a[i][j]);
            a[i][j]=0;
        }
        puts("");
    }
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

QOJ#8047 DFS Order 4

传送门

题意

• 求 $n$ 个点的以 $1$ 为根的树有多少种不同的 dfs 序。
• 要求 dfs 遍历每个点儿子的时候从小到大遍历，并且每个点父亲的编号 $f_i < i$。
• $1\le n\le 800$，答案对输入的一个质数取模。

题解

很妙的一道题，感觉完全想不出来啊。

注意到一个序列可能和多棵不同的有标号树对应，那么能不能想办法只统计其中的一棵呢？

注意到最大的限制是每个点必须比父亲更大，那么考虑这样的一个贪心构造：将树初始化为点 $1$，然后遍历 dfs 序列 $p$，维护 $1\sim p_{i-1}$ 的树链，在加入点 $p$ 时，若 $p_{i-1} < p_i$ 则直接接在 $p_{i-1}$ 上，否则暴力往上跳，将大于 $p_i$ 的全部弹出，然后接在第二个小于 $p_i$ 的祖先上（不难发现接在第一个上面时 dfs 序是不对的）。这样构造能使每一步的树链都尽可能长，如果一个点在这种情况下都接不上那必定不可能接上了。

考虑这样的树有什么特征，除去 $f_i < i$ 之外，我们发现对于点 $u$ 的两个儿子 $a,b(a < b)$，必定满足 $a$ 不是叶子且 $a$ 最大的儿子 $v > b$，否则 $b$ 就会接在 $a$ 或者 $v$ 上面（具体哪些情况接在 $a$ 上还需分类讨论，总之不可能接在 $u$ 上）。

换句话说，我们就能得到一系列 $u < a,a < b,a < v,b < v$ 的大小关系，不难发现这样的大小关系会在不同子树中来回连有向边（表示大小关系），这是不方便进行树形 DP 的。

那么能不能想办法让所有边都从一个子树指向另一子树呢？一个很厉害的想法是考虑容斥，将 $b < v$ 的关系转化成所有情况减去 $b > v$ 的情况，这样所有边都是从 $a$ 子树连向 $b$ 子树的了。并且不难发现我们甚至可以把 $a\to b$ 的边删掉，那么大小关系就变成一棵外向树了。

那么在确定一棵 $n$ 个点的外向树的形态后，其拓扑序的数量应为 $\frac{n!}{\prod sz_i}$，因为拓扑序合法当且仅当每个点编号是其子树内最小的。

接下来怎么做呢？考虑进行 DP。设 $dp_{i,j}$ 表示考虑原图上一个大小为 $i$ 的子树，这个子树在大小关系的连边中又额外连了总大小为 $j$ 的子树，这个子树内部的点对答案的总贡献。。由于答案是 $\frac{n!}{\prod sz_i}$ 的形式，根据套路我们把 $n!$ 提出来，于是只计算若干个 $\frac{1}{sz_i}$ 的贡献了。同时为了方便容斥，$dp_{i,j}$ 不计点 $i$ 的 $\frac{1}{i+j}$ 贡献。

那么对于 $dp_{i,j}$ 的转移，考虑枚举 $i$ 的编号最小的子树的大小 $k$，于是将 $i$ 的子树分为了 $k$ 和 $i-k$ 两部分，那么从 $dp_{i-k,j}$ 和 $dp_{k,i-1-k+j}$ 两部分转移过来，由于 $i-k$ 这一部分本来就包含了点 $i$，在之前已经计算过容斥系数了，所以只需要考虑 $k$ 这一部分的系数，那么有转移方程：

$$ dp_{i,j}=\frac{1}{i+j-1}\left(dp_{i-1,0}+\sum_{k=2}^{i-2}(dp_{k,0}-dp_{k,i-1-k+j})dp_{i-k,j}\right) $$

前面的 $dp_{i-1,0}$ 是 $i$ 除去 $j$ 只有一个子树的情况。后面 $k$ 枚举的上下界是因为除去最后一个子树外每个子树都不能是叶子，那么这些子树的大小都必须大于等于 $2$。

然后显然初始状态是 $dp_{1,i}=1$。

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

参考代码

#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=805,inf=0x3f3f3f3f;
int n,mod,dp[N][N];
int inv[N<<1];
signed main(){
    n=read();mod=read();
    inv[1]=1;
    forup(i,2,n*2){
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
    forup(j,0,n-1){
        dp[1][j]=1;
    }
    forup(i,2,n){
        forup(j,0,n-i){
            int val=dp[i-1][0];
            forup(k,2,i-2){
                (val+=1ll*(dp[k][0]-dp[k][i-1-k+j]+mod)*dp[i-k][j]%mod)%=mod;
            }
            dp[i][j]=1ll*inv[i+j-1]*val%mod;
        }
    }
    int ans=dp[n][0];
    forup(i,1,n-1){
        ans=1ll*ans*i%mod;
    }
    printf("%d\n",ans);
}

P9140 [THUPC 2023 初赛] 背包

传送门

题意

• 有 $n$ 个物品，每个物品有一个体积 $v_i$ 和一个价值 $c_i$。
• $q$ 次询问，每次询问给定一个容积 $v$,求恰好填满容积 $V$ 能得到的物品最大价值是多少。
• $1\le n\le 50,1\le q\le 10^5,1\le v_i\le 10^5,1\le c_i\le 10^6,10^{11}\le V< 10^{12}$

题解

同余最短路技巧题。

注意到容积非常大，但是 $v_i$ 的上界非常小，这启发我们拿出一个 $v_i$ 当作模数做同余最短路。

具体来说，我们找到 $\frac{c_p}{v_p}$ 最大的 $p$，显然尽可能选这个是不劣的。令 $m=v_p,w=c_p$，那么对于两个 $V' < V,V'\equiv V\pmod{m}$，有 $f(V)=f(V')+w\times \frac{V-V'}{m}$。

于是我们只需要对模 $m$ 的每个值分别求出一组解即可。即对于每个 $r$ 求出 $f(km+r)-kw$ 的最大值，可以跑 SPFA 求出最长路，但是复杂度不太好。

我们可以使用同余最短路的转圈技巧，对于每个 $i$，会将环分为 $\gcd(m,v_i)$ 个子环，在每个子环中至多只会加入 $\frac{m}{\gcd(v_i,m)}-1$ 个物品（否则会回到原点），那么我们绕着这个环转两圈即可考虑到所有转移，复杂度 $O(nm)$。

由于 $\frac{w}{m}$ 是最大的，所以这张图上没有正环，又因为最长路的性质不会经过重复点，那么 $V'$ 至多不会超过 $m^2\approx 10^{10}$，又因为 $V\ge 10^{11}$，所以不需要额外特判。

于是总复杂度 $O(nm+q)$。

参考代码

#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 M=1e5+5,N=55,inf=1e18;
i64 gcd(i64 a,i64 b){return b?gcd(b,a%b):a;}
i64 n,q;
struct Node{
    i64 v,c;
    bool operator >(const Node &r)const{
        return c*r.v>v*r.c;
    }
}s[N];
i64 dis[M];
signed main(){
    n=read();q=read();
    i64 mx=0;
    forup(i,1,n){
        s[i].v=read();s[i].c=read();
        if(mx==0||s[i]>s[mx]) mx=i;
    }
    i64 m=s[mx].v;
    forup(i,0,m-1) dis[i]=-inf;
    dis[0]=0;
    forup(i,1,n){
        if(i==mx) continue;
        i64 v=s[i].v%m,u=s[i].v/m,c=s[i].c,p=gcd(v,m);
        forup(i,0,p-1){
            i64 t=i,cnt=0;
            while(cnt<2){
                i64 nx=t+v,d=u;
                if(nx>=m) nx-=m,++d;
                if(dis[t]!=-inf) dis[nx]=max(dis[nx],dis[t]+c-d*s[mx].c);
                t=nx;
                if(t==i) ++cnt;
            }
        }
    }
    forup(i,1,q){
        i64 v=read();
        i64 p=v%m;
        if(dis[p]==-inf){
            puts("-1");
        }else{
            printf("%lld\n",dis[p]+s[mx].c*(v/m));
        }
    }
}

P10004 [集训队互测 2023] Permutation Counting 2

传送门

题意

• 设 $f(x,y)$ 表示满足恰有 $x$ 个 $i$ 满足 $p_i < p_{i+1}$，且逆排列中恰有 $y$ 个 $i$ 满足 $p_i' < p_{i+1}'$ 的排列 $p$ 的数量。
• 给定 $n$，对于 $0\le x < n,0\le y < n$，输出 $f(x,y)$。
• $1\le n\le 500$，答案对一个输入的大质数取模。

题解

二项式反演复杂题。

首先假如只有 $x$ 一维，一个想法是计算 $p_i$ 的递增连续段，钦定一些东西然后二项式反演。那么这道题能不能这样做呢？

那么一个想法是钦定 $p_i$ 中有 $a$ 个递增段，$p_i'$ 中有 $b$ 个递增段，这样后面看起来就能二维二项式反演做了，于是先考虑前面怎么做。

不妨钦定 $p_i$ 有 $a$ 个递增连续段，$p_i'$ 有 $b$ 个，不难发现若排列中存在值域和位置都连续的递增段这两个就会相交，我们还需要考虑相交的情况。那么我们可以用一个 $a\times b$ 的矩阵概括相交的信息，$G_{i,j}$ 表示 $p_i$ 的第 $i$ 个递增连续段和 $p_i'$ 的第 $i$ 个递增连续段相交的长度。不难发现一个这样 $a\times b$ 的矩阵和“钦定 $p_i$ 中有 $a$ 个递增段，$p_i'$ 中有 $b$ 个递增段”的排列一一对应。于是转而对这样的矩阵进行计数。这样的一个矩阵合法当且仅当每行每列都不是全 $0$，并且整个矩阵总和为 $n$。去掉非空的限制是好做的，设 $q_{c,d}$ 为不考虑非空的 $c\times d$ 的矩阵数，有 $q_{c,d}=\binom{cd+n-1}{cd-1}$（经典的盒子里放小球问题），那么再考虑一下空行就是经典二项式反演了。设 $g_{c,d}$ 表示没有空行/列的矩阵数。显然 $q_{x,y}=\sum_{a\le x}\sum_{b\le y}\binom{x}{a}\binom{y}{b}g_{a,b}$，根据二项式反演，则 $g_{x,y}=\sum_{a\le x}\sum_{b\le y}\binom{x}{a}\binom{y}{b}(-1)^{x-a+y-b}q_{a,b}$，看起来需要 $O(n^4)$，其实画一下式子发现 $g_{x,y}=\sum_{a\le x}(-1)^{x-a}\binom{x}{a}\sum_{b\le y}\binom{y}{b}(-1)^{y-b}q_{a,b}$，可以先枚举 $y$，求出后面的部分 $h_a=\sum_{b\le y}\binom{y}{b}(-1)^{y-b}q_{a,b}$ 再做前面的部分就能 $O(n^3)$ 了。

注意到我们连续段的信息是“钦定”得到的，那么我们还需要容斥掉钦定的有问题的情况，即我们钦定出的递增段不是极长的的情况，不难发现 $g_{n-x,n-y}=\sum_{a\ge x}\sum_{b\ge y}\binom{a}{x}\binom{b}{y}f(a,b)$（这里的 $f$ 就是题面上的 $f$），即我们钦定答案中有多少个递增点没被算到，没被算到的点就是递增段的交界处。然后类似地二项式反演拆式子就不展开了。

于是复杂度 $O(n^3)$，

参考代码

#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=505,inf=0x3f3f3f3f;
#define ull unsigned long long 
#define ui128 __uint128_t
struct Barrett{
    ull d;ui128 m;
    void init(ull _d){
        d=_d,m=(((ui128)(1)<<64)/d);
    }
}mod;
ull operator %(ull a,Barrett mod){
    ull w=(mod.m*a)>>64;w=a-w*mod.d;
    if(w>=mod.d)w-=mod.d;return w;
}
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int n,p;
int binom[N][N];
int fact[N*N+N],finv[N*N+N];
int binom_big(int n,int m){
    if(n<m) return 0;
    return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
int q[N][N],g[N][N],f[N][N];
int h[N];
void workg(){
    forup(y,1,n){
        forup(a,1,n){
            h[a]=0;
            forup(b,1,y){
                h[a]=(h[a]+1ll*binom[y][b]*((y-b)&1?p-1:1)%mod*q[a][b]%mod)%mod;
            }
        }
        forup(x,1,n){
            forup(a,1,x){
                g[x][y]=(g[x][y]+1ll*binom[x][a]*((x-a)&1?p-1:1)%mod*h[a]%mod)%mod;
            }
        }
    }
    forup(i,1,n){
        forup(j,1,n){
            msg("%d ",g[i][j]);
        }
        msg("|\n");
    }
}
void workf(){
    forup(y,0,n-1){
        forup(a,0,n-1){
            h[a]=0;
            forup(b,y,n-1){
                h[a]=(h[a]+1ll*binom[b][y]*((b-y)&1?p-1:1)%mod*g[n-a][n-b]%mod)%mod;
            }
        }
        forup(x,0,n-1){
            forup(a,x,n-1){
                f[x][y]=(f[x][y]+1ll*binom[a][x]*((a-x)&1?p-1:1)%mod*h[a]%mod)%mod;
            }
        }
    }
}
signed main(){
    n=read();p=read();
    mod.init(p);
    forup(i,0,n){
        binom[i][0]=1;
        forup(j,1,i){
            binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%mod;
        }
    }
    fact[0]=1;
    int nn=n*n+n;
    forup(i,1,nn) fact[i]=1ll*fact[i-1]*i%mod;
    finv[nn]=ksm(fact[nn],p-2);
    fordown(i,nn-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
    forup(a,1,n){
        forup(b,1,n){
            q[a][b]=binom_big(a*b+n-1,a*b-1);
        }
    }
    workg();
    workf();
    forup(i,0,n-1){
        forup(j,0,n-1){
            printf("%d ",f[i][j]);
        }
        puts("");
    }
}

P7735 [NOI2021] 轻重边

传送门

题意

• 有一棵 $n$ 个点的树，每条边有黑白两色，初始全为白色，维护下面两个操作共 $m$ 次：
  • 给定 $u,v$，对于 $u,v$ 之间的简单路径，将上面每个点周围的边全部染成白色，再把路径上的边全部染成黑色。
  • 给定 $u,v$，询问 $u,v$ 之间简单路径上有多少条边是黑色的。
• $1\le n,m\le 10^5$，带多测，$T\le 3$

题解

妙妙题。

考虑给每个点染色，初始每个点颜色两两不同。

然后每次修改将路径上的点全部染成同一种新的颜色。

这样一条边是黑色的当且仅当两端点颜色相同，于是可以直接树剖线段树维护了。

复杂度 $O(n\log^2 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=1<<17;
int n,m,cntn;
vector<int> e[N];
int sz[N],son[N],dfn[N],Tm,hig[N],ff[N],dpt[N];
void dfs(int x,int fa){
    sz[x]=1;ff[x]=fa;dpt[x]=dpt[fa]+1;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
        sz[x]+=sz[i];
        if(!son[x]||sz[i]>sz[son[x]]) son[x]=i;
    }
}
void dfs2(int x,int fa,int hh){
    dfn[x]=++Tm;hig[x]=hh;
    if(son[x]){
        dfs2(son[x],x,hh);
    }
    for(auto i:e[x]){
        if(i==fa||i==son[x]) continue;
        dfs2(i,x,i);
    }
}
struct Node{
    int lc,rc,num;
    Node operator +(const Node &r){
        Node res;
        if(lc==0) return r;
        if(r.lc==0) return *this;
        res.lc=lc;res.rc=r.rc;
        res.num=num+r.num+(rc==r.lc);
        return res;
    }
};
struct SegTree{
    Node tr[N<<1];
    int mark[N<<1];
    int getlen(int id){
        return 1<<(17-(31^__builtin_clz(id)));
    }
    void pushup(int id){
        tr[id]=tr[id<<1]+tr[id<<1|1];
    }
    void modi(int id,int v){
        tr[id].num=getlen(id)-1;
        tr[id].lc=tr[id].rc=v;
        mark[id]=v;
    }
    void pushdown(int id){
        if(!mark[id]) return;
        modi(id<<1,mark[id]);modi(id<<1|1,mark[id]);
        mark[id]=0;
    }
    void PushUp(int l,int r){
        l+=N;r+=N+1;
        forup(i,1,17){
            if(l!=((l>>i)<<i)) pushup(l>>i);
            if(r!=((r>>i)<<i)) pushup((r-1)>>i);
        }
    }
    void PushDown(int l,int r){
        l+=N;r+=N+1;
        fordown(i,17,1){
            if(l!=((l>>i)<<i)) pushdown(l>>i);
            if(r!=((r>>i)<<i)) pushdown((r-1)>>i);
        }
    }
    void Build(){
        mem(mark,0);
        forup(i,1,n) tr[i+N]=Node{i,i,0};
        fordown(i,N-1,0) pushup(i);
    }
    void Update(int L,int R,int v){
        PushDown(L,R);
        for(int l=L+N,r=R+N+1;l<r;l>>=1,r>>=1){
            if(l&1) modi(l++,v);
            if(r&1) modi(--r,v);
        }
        PushUp(L,R);
    }
    Node Query(int L,int R){
        PushDown(L,R);
        Node r1=Node{0,0,0},r2=Node{0,0,0};
        for(int l=L+N,r=R+N+1;l<r;l>>=1,r>>=1){
            if(l&1) r1=r1+tr[l++];
            if(r&1) r2=tr[--r]+r2;
        }
        return r1+r2;
    }
}mt;
void Update(int u,int v,int cc){
    while(hig[u]!=hig[v]){
        if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
        mt.Update(dfn[hig[u]],dfn[u],cc);
        u=ff[hig[u]];
    }
    if(dfn[u]>dfn[v]) swap(u,v);
    mt.Update(dfn[u],dfn[v],cc);
}
int Query(int u,int v){
    Node r1=Node{0,0,0},r2=Node{0,0,0};
    while(hig[u]!=hig[v]){
        if(dpt[hig[u]]<dpt[hig[v]]){
            r2=mt.Query(dfn[hig[v]],dfn[v])+r2;
            v=ff[hig[v]];
        }else{
            r1=mt.Query(dfn[hig[u]],dfn[u])+r1;
            u=ff[hig[u]];
        }
    }
    if(dfn[u]<dfn[v]){
        r2=mt.Query(dfn[u],dfn[v])+r2;
    }else{
        r1=mt.Query(dfn[v],dfn[u])+r1;
    }
    swap(r1.lc,r1.rc);
    return (r1+r2).num;
}
void solve(){
    n=read();m=read();
    forup(i,1,n){
        e[i].clear();
        sz[i]=son[i]=dfn[i]=0;
    }
    cntn=n;Tm=0;
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    dfs2(1,0,1);
    mt.Build();
    forup(i,1,m){
        int op=read(),a=read(),b=read();
        if(op==1){
            Update(a,b,++cntn);
        }else{
            printf("%d\n",Query(a,b));
        }
    }
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

CF1930H Interactive Mex Tree

传送门

题意

• 交互题。
• 给定一棵 $n$ 个点的树，你需要构造两个排列 $p_1,p_2$，有 $q$ 次询问，每次给树上每个点随机赋权值为 $0\sim n-1$ 的排列，你需要回答一条路径上的权值 $\mathrm{mex}$。
• 每次询问中，你可以询问交互库以下问题至多五次：
  • ? t l r：在排列 $p_t$ 中，第 $l$ 到第 $r$ 项之间点权最小值是多少。
• 然后以 ! x 的格式输出答案，输出答案后请额外读入一个整数。
• $1\le n\le 10^5,1\le q\le 10^4$，带多测，$\sum n\cdot q\le 3\times 10^6$

题解

妙妙交互题。

考虑如何用最小值概括 $\mathrm{mex}$。注意点权是个排列，那么链上 $\mathrm{mex}$ 就是不在这条链上的最小值。

那么如何用两个排列的若干区间覆盖不在一条链上的所有点呢？发现可以将 $p_1$ 设为 dfs 入栈序列，$p_2$ 设为出栈序列，具体区间略。注意特判两个点是祖先后代关系的情况。因为 $\sum n\cdot q\le 3\times 10^6$ 所以可以直接暴力，但是 $O((n+q)\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=1e5+5,inf=0x3f3f3f3f;
int n,q;
vector<int> e[N];
int p1[N],p2[N],cnt1,cnt2;
int dfn[N],dfe[N];
int dpt[N],ff[N];
void dfs(int x,int fa){
    dfn[x]=++cnt1;
    p1[dfn[x]]=x;
    ff[x]=fa;
    dpt[x]=dpt[fa]+1;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
    }
    dfe[x]=++cnt2;
    p2[dfe[x]]=x;
}
int Query(int t,int l,int r){
    if(l>r) return inf;
    cout<<"? "<<t<<' '<<l<<' '<<r<<endl;
    int res;cin>>res;
    return res;
}
void solve(){
    cin>>n>>q;
    forup(i,1,n){
        e[i].clear();
        p1[i]=p2[i]=dfn[i]=dfe[i]=ff[i]=dpt[i]=0;
    }
    cnt1=cnt2=0;
    forup(i,1,n-1){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    forup(i,1,n) cout<<p1[i]<<' ';
    cout<<endl;
    forup(i,1,n) cout<<p2[i]<<' ';
    cout<<endl;
    forup(i,1,q){
        int u,v;cin>>u>>v;
        if(dfn[u]>dfn[v]) swap(u,v);
        int x=u,y=v;
        int ans=n;
        while(dpt[x]!=dpt[y]){
            if(dpt[x]>dpt[y]) x=ff[x];
            else y=ff[y];
        }
        if(x==y){
            ans=min(ans,Query(1,1,dfn[u]-1));
            ans=min(ans,Query(1,dfn[v]+1,n));
            ans=min(ans,Query(2,1,dfe[v]-1));
        }else{
            while(ff[x]!=ff[y]){
                x=ff[x];y=ff[y];
            }
            ans=min(ans,Query(1,1,dfn[ff[x]]-1));
            ans=min(ans,Query(1,dfn[v]+1,n));
            ans=min(ans,Query(1,dfn[u]+1,dfn[y]-1));
            ans=min(ans,Query(2,1,dfe[u]-1));
            ans=min(ans,Query(2,dfe[x]+1,dfe[v]-1));
        }
        cout<<"! "<<ans<<endl;
        int vv;cin>>vv;
    }
}
signed main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
}

CF1585G Poachers

传送门

题意

• 有一个 $n$ 个点的森林，两人在这个森林上进行游戏。
• 两人轮流操作，每个人选择一棵树，再选择一个深度 $d$，要求 $d$ 小于等于这棵树最浅的叶子的深度。将这棵树深度小于等于 $d$ 的部分全部删掉。
• 不能操作者负，问是先手必胜还是后手必胜。
• $1\le n\le 5\times 10^5$，带多测，$\sum n\le 5\times 10^5$

题解

算是典题吧。

首先一眼看出这是一个公平博弈游戏。考虑求出每棵树根处 $sg_u$ 的值。然后异或起来，若非 $0$ 则先手必胜。

那么只考虑一棵树，不难想到 DP，那么转移形如先枚举从哪个深度切开，将从这个地方切开得到的所有树的 $sg_v$ 异或起来，再对异或值求 $\mathrm{mex}$。

由于转移只和深度有关，不难想到长剖优化，设 $f_{i,j}$ 表示考虑点 $i$ 为根的子树，从深度为 $dep_i+j-1$ 的位置切开得到子树的异或和。先暴力合并轻儿子，然后 $f_{i,0}$ 就是后面值的 $\mathrm{mex}$，求 $\mathrm{mex}$ 可以对每条长链维护一个值域上的 ODT 状物，注意特判能一次删完的情况，复杂度 $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,rt[N];
vector<int> e[N];
int pool[N],*sg[N],*cntn;
int len[N],low[N],son[N],dpt[N];
void dfs1(int x){
    len[x]=1;
    son[x]=0;
    low[x]=e[x].size()?n:dpt[x];
    for(auto i:e[x]){
        dpt[i]=dpt[x]+1;
        dfs1(i);
        if(!son[x]||len[i]>len[son[x]]) son[x]=i;
        len[x]=max(len[x],len[i]+1);
        low[x]=min(low[x],low[i]);
    }
}
map<int,int> cnt[N];
set<pii> ss[N];
using sit=set<pii>::iterator;
void add(int p,int x){
    if(!cnt[p].count(x)){
        sit it=ss[p].lower_bound(mkp(x,0));
        int l=x,r=x;
        if(it!=ss[p].begin()&&prev(it)->se==x-1){
            l=prev(it)->fi;ss[p].erase(prev(it));
        }
        if(it!=ss[p].end()&&it->fi==x+1){
            r=it->se;ss[p].erase(it);
        }
        ss[p].insert(mkp(l,r));
    }
    ++cnt[p][x];
}
void del(int p,int x){
    if(cnt[p][x]==1){
        sit it=prev(ss[p].upper_bound(mkp(x,inf)));
        int l=it->fi,r=it->se;ss[p].erase(it);
        if(l!=x) ss[p].insert(mkp(l,x-1));
        if(r!=x) ss[p].insert(mkp(x+1,r));
        cnt[p].erase(x);
    }else{
        --cnt[p][x];
    }
}
void dfs2(int x,bool tp,int hh){
    if(tp){
        sg[x]=cntn+1;
        cntn+=len[x];
        cnt[x].clear();ss[x].clear();
    }
    if(son[x]){
        sg[son[x]]=sg[x]+1;
        dfs2(son[x],0,hh);
        fordown(p,low[son[x]],low[x]+1){
            if(p-dpt[x]+1<len[x]) del(hh,sg[x][p-dpt[x]+1]);
        }
        for(auto i:e[x]){
            if(i==son[x]) continue;
            dfs2(i,1,i);
            forup(j,1,len[i]){
                if(dpt[x]+j<=low[x]+1){
                    del(hh,sg[x][j]);
                }
                sg[x][j]^=sg[i][j-1];
                if(dpt[x]+j<=low[x]+1){
                    add(hh,sg[x][j]);
                }
            }
        }
        if(ss[hh].begin()->fi==0||(low[x]==dpt[x]+len[x]-1&&ss[hh].begin()->fi==1)){
            sg[x][0]=ss[hh].begin()->se+1;
        }else{
            sg[x][0]=0;
        }
        add(hh,sg[x][0]);
    }else{
        sg[x][0]=1;
        add(hh,1);
    }
}
void solve(){
    n=read();
    forup(i,1,n){
        e[i].clear();rt[i]=0;
        pool[i]=0;dpt[i]=0;
    }
    cntn=pool;
    forup(i,1,n){
        int p=read();
        if(p){
            e[p].push_back(i);
        }else{
            rt[i]=1;
        }
    }
    int ans=0;
    forup(i,1,n){
        if(rt[i]){
            dfs1(i);
            dfs2(i,1,i);
            ans^=sg[i][0];
        }
    }
    puts(ans?"YES":"NO");
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

CF772E Verifying Kingdom

传送门

题意

• 交互题。
• 有一棵二叉树，上面有 $n$ 个叶子。
• 你可以进行至多 $10n$ 次以下询问：
  • 你给交互库输入 a b c，交互库返回 $X=\mathrm{lca}(a,b),Y=\mathrm{lca}(b,c),Z=\mathrm{lca}(c,a)$ 中最深的一个（即返回一个字符 X 或 Y 或 Z）。
• 输出这棵树，只要同构即可。
• $1\le n\le 1000$

题解

哎哟我讨厌交互题，写错了还不能对拍。

首先看到操作限制是 $10n$，大致是 $O(n\log n)$ 级别的。

考虑能不能维护 $1\sim i-1$ 叶子的虚树，然后在 $\left\lceil\log n\right\rceil$ 次询问内插入叶子 $i$。

思考一个询问能干什么，对于一个询问 $(x,y,u)$（其中 $x,y$ 已经插入），我们能得到 $u$ 在 $\mathrm{lca}(x,y)$ 的哪个方位。那么不难想到点分治，每次找到中心然后往 $u$ 所在子树递归即可。因为每次只递归一个子树所以时间复杂度是 $O(n)$ 的。于是总时间复杂度 $O(n^2)$，操作数不超过 $n\left\lceil\log n\right\rceil \le 10n$。

参考代码

#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=2005,inf=0x3f3f3f3f;
int n,p[N],dpt[N],ch[N][2],po[N][2],cntn;
int Query(int a,int b,int c){
    if(a==b) return 1;
    if(b==c) return 2;
    if(a==c) return 3;
    cout<<a<<' '<<b<<' '<<c<<endl;
    char x;cin>>x;
    if(x=='X'){
        return 1;
    }else if(x=='Y'){
        return 2;
    }else{
        return 3;
    }
}
void dfs(int x){
    ++dpt[x];
    if(ch[x][0]) dfs(ch[x][0]);
    if(ch[x][1]) dfs(ch[x][1]);
}
int sz[N],mx[N],vis[N],als,rt;
void dfs2(int x,int fa){
    sz[x]=1;mx[x]=0;
    auto to=[&](int i){
        if(!i||i==fa||vis[i]) return;
        dfs2(i,x);
        sz[x]+=sz[i];
        mx[x]=max(mx[x],sz[i]);
    };
    to(ch[x][0]);to(ch[x][1]);to(p[x]);
    mx[x]=max(mx[x],als-sz[x]);
    if(mx[x]<=als/2) rt=x;
}
int Ask(int u,int p){
    if(u<=n) return 1;
    // msg("%d %d|\n",u,p);
    return Query(po[u][0],po[u][1],p);
}
int res;
void dfz(int x,int ss,int u){
    if(vis[x]||!x) return;
    als=ss;
    dfs2(x,0);
    vis[rt]=1;
    // msg("[%d %d %d]\n",x,rt,ss);
    int vv=Ask(rt,u);
    if(vv==1){
        res=rt;
        dfz(p[rt],(sz[p[rt]]<sz[rt]?sz[p[rt]]:als-sz[rt]),u);
    }else if(vv==2){
        res=ch[rt][1];
        dfz(ch[rt][1],(sz[ch[rt][1]]<sz[rt]?sz[ch[rt][1]]:als-sz[rt]),u);
    }else{
        res=ch[rt][0];
        dfz(ch[rt][0],(sz[ch[rt][0]]<sz[rt]?sz[ch[rt][0]]:als-sz[rt]),u);
    }
}
int work(int x,int i){
    forup(j,1,cntn){
        sz[j]=mx[j]=vis[j]=0;
    }
    res=0;
    dfz(1,i,x);
    return res;
}
signed main(){
    cin>>n;
    cntn=n;
    dpt[1]=dpt[2]=1;
    p[1]=p[2]=++cntn;
    forup(i,1,n){
        po[i][0]=po[i][1]=i;
    }
    ch[cntn][0]=1;ch[cntn][1]=2;
    po[cntn][0]=1;po[cntn][1]=2;
    forup(i,3,n){
        int u=work(i,cntn-(n-i+1)),ff=p[u];
        // msg("(%d)\n",u);
        dfs(u);
        ch[ff][u==ch[ff][1]]=++cntn;
        p[cntn]=ff;
        p[u]=p[i]=cntn;
        ch[cntn][0]=u;ch[cntn][1]=i;
        po[cntn][0]=po[u][0];po[cntn][1]=i;
        dpt[cntn]=dpt[ff]+1;dpt[i]=dpt[cntn]+1;
        // forup(i,1,cntn){
        //     msg("%d ",p[i]);
        // }msg("|\n");
    }
    cout<<-1<<endl;
    forup(i,1,cntn){
        if(p[i]){
            cout<<p[i]<<' ';
        }else{
            cout<<-1<<' ';
        }
    }
    cout<<endl;
}

Comments