A. 公路建设

给定 n 个节点，每个节点初始有权值 w_i。进行 n-1 次操作，每次连接一条边 u←v，其中 u 与节点 1 连通，v 与节点 1 不连通。要求计算从 1 到 u 路径上权值的逆序对数量，然后将路径上的权值统一更新为 v 的权值。

使用 Link-Cut Tree (LCT) 解决此问题。每次连接边后执行 access(v) 操作，此时树上每条实链的颜色相同。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+1,W=1e9;
int n,w[MAXN]; ll ans;
struct FenwickTree {
    int tr[MAXN]; ll s;
    vector <int> p;
    inline void add(int x,int v) { for(p.push_back(x);x<=n;x+=x&-x) tr[x]+=v; }
    inline ll qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
    inline void clr() { for(int x:p) for(;x<=n;x+=x&-x) tr[x]=0; p.clear(); }
}    T;
namespace LCT {
int fa[MAXN],ch[MAXN][2],col[MAXN],cov[MAXN],siz[MAXN];
inline void psu(int p) { siz[p]=siz[ch[p][0]]+siz[ch[p][1]]+1; }
inline void adt(int x,int c) { if(x) cov[x]=col[x]=c; }
inline void psd(int x) { if(cov[x]) adt(ch[x][0],cov[x]),adt(ch[x][1],cov[x]),cov[x]=0; }
inline bool nrt(int p) { return ch[fa[p]][0]==p||ch[fa[p]][1]==p; }
inline int son(int x) { return ch[fa[x]][1]==x; }
inline void upd(int p) { if(nrt(p)) upd(fa[p]); psd(p); }
inline void rot(int p) {
    int u=fa[p],v=fa[u],k=son(p);
    if(nrt(u)) ch[v][son(u)]=p;
    fa[ch[u][k]=ch[p][k^1]]=u,fa[fa[ch[p][k^1]=u]=p]=v;
    psu(p),psu(u);
}
inline void splay(int p) {
    for(upd(p);nrt(p);rot(p)) if(nrt(fa[p])) rot(son(p)==son(fa[p])?fa[p]:p);
}
inline int access(int p) {
    int u=0;
    for(ans=0,T.clr();p;u=p,p=fa[p]) {
        splay(p);
        int tmp=1+siz[ch[p][0]];
        ans+=1ll*tmp*T.qry(col[p]-1);
        T.add(col[p],tmp);
        ch[p][1]=u,psu(p);
    }
    return u;
}
}
using namespace LCT;
signed main() {
    scanf("%d",&n);
    vector <int> vals;
    for(int i=1;i<=n;++i) scanf("%d",&w[i]),vals.push_back(w[i]);
    sort(vals.begin(),vals.end()),vals.erase(unique(vals.begin(),vals.end()),vals.end());
    for(int i=1;i<=n;++i) w[i]=lower_bound(vals.begin(),vals.end(),w[i])-vals.begin()+1;
    col[1]=w[1],siz[1]=1;
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        adt(access(u),w[v]);
        printf("%lld\n",ans);
        fa[v]=u,col[v]=w[v],siz[v]=1;
    }
    return 0;
}

C. 栅栏

在一个 n×m 的网格中选择若干格子进行着色并指定方向（上、下、左、右），要求同行或同列的格子方向相对。求满足条件的方案数。

设 dp[i][j] 表示 i×j 网格上的答案。考虑第 i 行的情况：

• 第 i 行无黑色格子：从 dp[i-1][j] 转移
• 第 i 行有一个黑色格子：
  • 若对应列只有一个黑色格子：从 4×j×dp[i-1][j-1] 转移
  • 若对应列有两个黑色格子：从 (i-1)×j×dp[i-2][j] 转移
• 第 i 行有两个黑色格子：从 (j×(j-1)/2)×dp[i-1][j-2] 转移

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3001,MOD=1e9+7;
int dp[MAXN][MAXN];
signed main() {
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<=max(n,m);++i) dp[0][i]=dp[i][0]=1;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
        dp[i][j]=(dp[i-1][j]+4*j*dp[i-1][j-1])%MOD;
        if(i>1) dp[i][j]=(dp[i][j]+(i-1)*j%MOD*dp[i-2][j-1]%MOD)%MOD;
        if(j>1) dp[i][j]=(dp[i][j]+j*(j-1)/2%MOD*dp[i-1][j-2]%MOD)%MOD;
    }
    printf("%lld\n",(dp[n][m]+MOD-1)%MOD);
    return 0;
}

D. 苦行僧

给定 n 和 m，求长度为 n 的排列 p_i 中满足 Σ[i=1 to n-1][p_i > p_{i+1}] = m-1 的排列数量。

使用容斥原理，钦定 k 个位置必须满足 p_i > p_{i+1}。将连续的 > 看作一段，整个序列被分为 n-k 段，方案数为 n!/(Πs_i!)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5,MOD=1e9+7;
ll fac[MAXN],ifac[MAXN];
inline ll ksm(ll a,ll b=MOD-2,ll p=MOD) {
    ll ret=1;
    for(;b;a=a*a%p,b=b>>1) if(b&1) ret=ret*a%p;
    return ret;
}
inline ll binom(int n,int m) { return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD; }
signed main() {
    int n,m;
    scanf("%d%d",&n,&m),--m;
    for(int i=fac[0]=ifac[0]=1;i<=n+1;++i) ifac[i]=ksm(fac[i]=fac[i-1]*i%MOD);
    ll ans=0;
    for(int i=1;i<=n-m;++i) ans=(ans+MOD+((n-m-i)%2?-1:1)*ksm(i,n)*binom(n+1,m+i+1)%MOD)%MOD;
    printf("%lld\n",ans);
    return 0;
}

E. 道路服务

给定一棵 n 个节点的树，增加 k 条无向边，最小化所有点对间最短距离之和。

较优解是将 k 条边连成菊花形状。使用模拟退火算法，每次更改一条边的端点。评估函数采用 Σ[1≤i≤n]dist(rt,i)，其中 rt 是附加边的中心点。

F. 最差记者3

数轴上有 n+1 个人，编号 0~n，第 i 个人初始在 -i 位置。每轮第 0 个人向右移动 1，其他人如果与前一个人距离 < d_i，则移动到前一个人左边。q 次询问 t 秒后 [l,r] 区间内的人数。

每个人运动具有周期性，即每隔 k_i 轮移动 k_i 步。二分 t 秒后位置 ≤ r 和 ≤ l-1 的人数即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+1;
int d[MAXN],k[MAXN];
signed main() {
    int n,q;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i) scanf("%lld",&d[i]);
    d[0]=k[0]=1;
    for(int i=1;i<=n;++i) k[i]=(d[i]+k[i-1]-1)/k[i-1]*k[i-1];
    auto query=[&](int t,int x) {
        int l=0,r=n,res=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if((t/k[mid])*k[mid]-mid>=x) res=mid,l=mid+1;
            else r=mid-1;
        }
        return res+1;
    };
    while(q--) {
        int t,l,r;
        scanf("%lld%lld%lld",&t,&l,&r);
        printf("%lld\n",query(t,l)-query(t,r+1));
    }
    return 0;
}

G. 航线地图

通信题。A.cpp 输入一张 n 个点的图 G，输出点数不超过 n+12 的图 H。交互器任意打乱 H 中点和边的标号得到 H'。B.cpp 输入 H'，还原 G。

使用 12 个额外点表示原图的 n 个点原始标号，采用二进制分组。用 10 个点 v_0~v_9 表示，v_i 连接第 i 个二进制位为 1 的所有点。

H. 比太郎的派对

给定一张 n 个点 m 条边的有向图，q 次询问 x_i 并给定 k_i 个点，求 1~n 中除这些点外到 x_i 的最长距离。

采用根号分治策略，若 k_i ≤ √n，只关心最短的 √n 条路径；k_i > √n 的情况暴力处理。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=2e9;
vector <array<int,2>> P[MAXN];
vector <int> G[MAXN];
int dis[MAXN],mark[MAXN],mp[MAXN];
signed main() {
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    int B=sqrt(n);
    for(int i=1;i<=m;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[v].push_back(u);
    }
    fill(mp+1,mp+n+1,-inf);
    for(int u=1;u<=n;++u) {
        P[u].push_back({0,u});
        for(int v:G[u]) for(auto I:P[v]) mp[I[1]]=max(mp[I[1]],I[0]+1);
        for(int v:G[u]) {
            int ed=P[u].size();
            for(auto I:P[v]) if(mp[I[1]]==I[0]+1) {
                P[u].push_back({mp[I[1]],I[1]}),mp[I[1]]=-inf;
            }
            inplace_merge(P[u].begin(),P[u].begin()+ed,P[u].end(),greater<array<int,2>>());
            if((int)P[u].size()>B) P[u].resize(B);
        }
    }
    for(int T=1;T<=q;++T) {
        int t,y;
        scanf("%d%d",&t,&y);
        for(int i=0,j;i<y;++i) scanf("%d",&j),mark[j]=T;
        for(auto p:P[t]) {
            if(mark[p[1]]<T) {
                printf("%d\n",p[0]);
                goto ok;
            }
        }
        if((int)P[t].size()<B) puts("-1");
        else {
            fill(dis+1,dis+t+1,-inf),dis[t]=0;
            for(int u=t;u;--u) {
                for(int v:G[u]) dis[v]=max(dis[v],dis[u]+1);
            }
            int ans=-1;
            for(int i=1;i<=t;++i) if(mark[i]<T) ans=max(ans,dis[i]);
            printf("%d\n",ans<0?-1:ans);    
        }
        ok:;
    }
    return 0;
}

I. 安全门

定义"好"括号序列：能够将一个可空子串的左右括号反转后得到合法括号序列。给定含空白位置的括号串，求填入左右括号使其成为"好"序列的方案数。

令左括号为 1，右括号为 -1。设翻转区间为 (l,r]。定义翻转：整个序列变为 s_n s_{n-1}...s_1 然后反转括号。

J. 糖果

给定长度为 n 的数轴，每个位置有权值。对于 k=1~⌈n/2⌉，求选 k 个不相邻位置的最大权值和。

观察解的形态，用 0/1 表示位置是否被选。序列能划分为 0,1 交替出现的段且两端为 0。每次操作是将某段 01 取反，然后合并两边段。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+5,INF=1e18;
int pre[MAXN],suf[MAXN],inq[MAXN],c[MAXN];
signed main() {
    int n;
    scanf("%lld",&n);
    for(int i=1;i<=n;++i) scanf("%lld",&c[i]),pre[i]=i-1,suf[i]=i+1,inq[i]=1;
    c[0]=c[n+1]=-INF;
    auto merge=[&](int u) {
        pre[suf[u]]=pre[u];
        suf[pre[u]]=suf[u];
        inq[u]=0;
    };
    priority_queue <array<int,2>> Q;
    for(int i=1;i<=n;++i) Q.push({c[i],i});
    int ans=0;
    for(int i=1;i<=(n+1)/2;++i) {
        while(!inq[Q.top()[1]]) Q.pop();
        int w=Q.top()[0],p=Q.top()[1]; Q.pop();
        printf("%lld\n",ans+=w);
        Q.push({c[p]=c[pre[p]]+c[suf[p]]-w,p});
        merge(pre[p]),merge(suf[p]);
    }
    return 0;
}

K. 图书馆

交互器有一个 1~n 的排列 p，每次可询问 S 里的元素在 p 上构成几个连续段。在 20000 次询问内还原排列。

采用增量法。先用 2n 次询问求出排列的一个端点。然后动态维护已知前缀 P，对于未确定集合 Q，二分成两个集合，询问即可确定前缀的下一个元素。

L. 野猪

给一张 n 个点 m 条边的无向图，定义合法路径为不会连续经过同一条边。动态维护长度为 k 的序列 v_1~v_k，支持 q 次单点修改，每次求顺次经过的最短合法路径。

观察到任何一段 v_i→v_{i+1} 路径的第一条边 s 和最后一条边 t 只有四种可能情况。暴力 Dijkstra 求出边间的全源最短路，预处理四条路径。使用动态规划记录路径类型，修改用矩阵乘法维护。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN=2005,MAXM=4005,MAXL=1e5+1,INF=1e18;
int n,m,q,len,ecnt=0,head[MAXN];
struct Edge {
    int v,w,lst;
}    G[MAXM];
inline void AddEdge(int u,int v,int w) { G[ecnt]={v,w,head[u]},head[u]=ecnt++; }
struct Node {
    int s,t,c;
};
int dist[MAXM][MAXM];
bool vis[MAXM];
inline Node GetPath(int u,int v,int lst,int nxt) {
    Node P={-1,-1,INF};
    for(int s=head[u];s!=-1;s=G[s].lst) {
        for(int t=head[v];t!=-1;t=G[t].lst) {
            if((lst==-1||s!=lst)&&(nxt==-1||(t^1)!=nxt)&&dist[s][t^1]<P.c) {
                P={s,t^1,dist[s][t^1]}; 
            }
        }
    }
    return P;
} 
Node Info[MAXN][MAXN][4];
/* u[0],v[0]: shortest path
 * u[1],v[1]: u[1]!=u[0],v[1]!=v[0]
 * u[2],v[2]: u[2]!=u[0],v[2]!=v[1]
 * u[3],v[3]: u[3]!=u[1],v[3]!=v[0]
 */
struct Matrix {
    int f[4][4];
    Matrix() { memset(f,0x3f,sizeof(f)); }
    inline int* operator [](int i) { return f[i]; }
    inline friend Matrix operator *(Matrix u,Matrix v) {
        Matrix w;
        for(int k:{0,1,2,3}) for(int i:{0,1,2,3}) for(int j:{0,1,2,3}) {
            w[i][j]=min(w[i][j],u[i][k]+v[k][j]);
        }
        return w;
    }
};
int ord[MAXL];
inline Matrix GetMatrix(int idx) {
    Matrix m;
    int a=ord[idx-1],b=ord[idx],c=ord[idx+1];
    for(int u:{0,1,2,3}) for(int v:{0,1,2,3}) {
        if(~Info[a][b][u].t&&~Info[b][c][v].s&&(Info[a][b][u].t^Info[b][c][v].s)!=1) {
            m[u][v]=Info[b][c][v].c;
        }
    }
    return m;
}
Matrix sum[MAXL<<2];
inline void Build(int l=2,int r=len-1,int pos=1) {
    if(l==r) { sum[pos]=GetMatrix(l); return ; }
    int mid=(l+r)>>1;
    Build(l,mid,pos<<1),Build(mid+1,r,pos<<1|1);
    sum[pos]=sum[pos<<1]*sum[pos<<1|1];
}
inline void Modify(int u,int l=2,int r=len-1,int pos=1) {
    if(u<l||u>r) return ;
    if(l==r) { sum[pos]=GetMatrix(l); return ; }
    int mid=(l+r)>>1;
    if(u<=mid) Modify(u,l,mid,pos<<1);
    else Modify(u,mid+1,r,pos<<1|1);
    sum[pos]=sum[pos<<1]*sum[pos<<1|1];
}
signed main() {
    scanf("%lld%lld%lld%lld",&n,&m,&q,&len);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;++i) {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        AddEdge(u,v,w),AddEdge(v,u,w);
    }
    memset(dist,0x3f,sizeof(dist));
    for(int st=0;st<ecnt;++st) {
        priority_queue <array<int,2>,vector<array<int,2>>,greater<array<int,2>>> Q;
        Q.push({dist[st][st]=G[st].w,st});
        memset(vis,false,sizeof(vis));
        while(!Q.empty()) {
            int e=Q.top()[1]; Q.pop();
            if(vis[e]) continue; vis[e]=true;
            for(int f=head[G[e].v];f!=-1;f=G[f].lst) {
                if(dist[st][f]>dist[st][e]+G[f].w&&(e^f)!=1) {
                    Q.push({dist[st][f]=dist[st][e]+G[f].w,f});
                }
            }
        }
    }
    for(int u=1;u<=n;++u) for(int v=1;v<=n;++v) {
        Info[u][v][0]=GetPath(u,v,-1,-1);
        Info[u][v][1]=GetPath(u,v,Info[u][v][0].s,Info[u][v][0].t);
        Info[u][v][2]=GetPath(u,v,Info[u][v][0].s,Info[u][v][1].t);
        Info[u][v][3]=GetPath(u,v,Info[u][v][1].s,Info[u][v][0].t);
    }
    for(int i=1;i<=len;++i) scanf("%lld",&ord[i]);
    if(len==2) {
        while(q--) {
            int x,y;
            scanf("%lld%lld",&x,&y);
            ord[x]=y;
            printf("%lld\n",Info[ord[1]][ord[2]][0].c);
        }
    } else {
        Build();
        while(q--) {
            int x,y;
            scanf("%lld%lld",&x,&y);
            ord[x]=y;
            Modify(x-1),Modify(x),Modify(x+1);
            int ans=INF;
            for(int i:{0,1,2,3}) for(int j:{0,1,2,3}) {
                ans=min(ans,Info[ord[1]][ord[2]][i].c+sum[1][i][j]);
            }
            printf("%lld\n",ans<INF?ans:-1);
        }
    }
    return 0;
}