2024 9 月杂题

真正名义上的开学了，莫名其妙多了好多天假，爽。

[ABC134F] Permutation Oddness

题意

• 求 \(\sum_{i=1}^n|i-p_i|=k\) 的 \(n\) 阶排列数。
• \(1\le n\le 50,0\le k\le n^2\)

题解

看到绝对值先拆绝对值，于是考虑哪些东西产生正的贡献哪些产生负的。

发现假如某个数 \(i\) 填入更大的空格中或者某个空格 \(i\) 中填了更大的数都会产生 \(-i\) 的贡献，如果是往小了搞就会产生 \(i\) 的贡献。

于是考虑一个经典的 DP，设 \(dp_{i,j,p}\) 表示考虑前 \(i\) 个数/空格，有 \(j\) 个数/空格需要和后面的匹配但还没匹配（注意到没匹配的数字和空格的数量必定是相同的），当前总贡献为 \(p\) 的方案数。

转移有五种：

• 当前空格和数自己匹配： \(dp_{i,j,p}\gets dp_{i-1,j,p}\)
• 当空格和数都和后面的匹配：\(dp_{i,j,p}\gets dp_{i-1,j-1,p+2i}\)
• 都和前面的匹配：\(dp_{i,j,p}\gets dp_{i-1,j+1,p-2i}\times (j+1)^2\)
• 数和前面的匹配，空和后面的匹配：\(dp_{i,j,p}\gets dp_{i-1,j,p}\times j\)
• 空和前面的匹配，数和后面的匹配：\(dp_{i,j,p}\gets dp_{i-1,j,p}\times j\)

复杂度 \(O(n^4)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=55,mod=1e9+7;
int n,k,dp[N][N][N*N*2],A;
signed main(){
    n=read();k=read();
    int A=n*n;
    dp[0][0][A]=1;
    forup(i,1,n){
        forup(j,0,i){
            forup(p,-n*n,n*n){
                dp[i][j][p+A]=dp[i-1][j][p+A];
                if(j>0&&p+2*i<=i*i) (dp[i][j][p+A]+=dp[i-1][j-1][p+2*i+A])%=mod;
                if(j<i-1&&p-2*i>=-i*i) (dp[i][j][p+A]+=1ll*dp[i-1][j+1][p-2*i+A]*(j+1)%mod*(j+1)%mod)%=mod;
                (dp[i][j][p+A]+=2ll*dp[i-1][j][p+A]*j%mod)%=mod;
            }
        }
    }
    printf("%d\n",dp[n][0][k+A]);
}

P8162 [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election)

传送门

题意

• 有一个人要参加选举，他需要通过演讲取得 \(n\) 个市中至少 \(k\) 个的支持。
• 每个市有两个参数 \(a,b\)，表示他至少要演讲 \(a\) 小时才能获得支持，而如果演讲超过 \(b\) 小时就能获得一个协助者。协助者可以和它一起演讲（相当于复制一个人），多人同时在同一城市演讲收益会叠加。
• 求所需最少时间，不考虑交通等其它事务消耗的时间。
• \(1\le n\le 5000\)，所有数字在 \(1000\) 以内。

题解

首先有一个贪心：先枚举找了 \(t\) 个协助者，然后将最小的 \(t\) 个 \(b\) 拎出来，再在剩下的 \(a\) 中选最小的。

但这个有个问题：可能某个 \(b\) 对应的 \(a\) 非常小，让它的 \(a\) 取贡献会更优。

那么最小的 \(t\) 个 \(b\) 中不选 \(b\) 的必定选 \(a\)（如果两边都不选显然把更大的的 \(b\) 换车这个会不劣）。

于是想到 DP，设 \(f_{i,j}\) 表示考虑前 \(i\) 小的 \(b\)，其中有 \(j\) 个选择 \(b\)，其余选择 \(a\) 的最小代价，统计答案和后面的拼一下即可，转移是简单的。

复杂度 \(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 ld=long double;
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,k;
ld ans=inf;
struct Node{
    int a,b,pos;
}s[N];
ld dp[2][N],mn[N][N];
signed main(){
    n=read();k=read();
    int cnt=0;
    forup(i,1,n){
        s[i].a=read();s[i].b=read();
        s[i].pos=i;
        ans+=s[i].a;
        if(~s[i].b) ++cnt;
        else s[i].b=inf;
    }
    sort(s+1,s+n+1,[&](Node a,Node b){return a.b<b.b;});
    forup(i,0,n+1){
        forup(j,0,n+1){
            mn[i][j]=inf;
        }
    }
    mn[n+1][0]=0;
    fordown(i,n,1){
        forup(j,0,n-i+1){
            mn[i][j]=min(mn[i+1][j],mn[i+1][j-1]+s[i].a);
        }
    }
    ans=mn[1][k];
    forup(t,0,min(k,cnt)){
        forup(j,0,n){
            dp[0][j]=inf;
        }
        dp[0][0]=0;
        forup(i,1,k){
            int p=i&1,q=p^1;
            forup(j,0,n) dp[p][j]=inf;
            forup(j,0,min(i,t)){
                dp[p][j]=dp[q][j]+1.0*s[i].a/(t+1);
                if(j) dp[p][j]=min(dp[p][j],dp[q][j-1]+1.0*s[i].b/j);
            }
            ans=min(ans,dp[p][t]+mn[i+1][k-i]/(t+1));
        }
    }
    printf("%Lf\n",ans);
}

JOISC 2015 Day1 T3「たのしいたのしい家庭菜園 / Growing Vegetables is Fun 2」

传送门

题意

• 有 \(n\) 棵树，每棵树有一个高度 \(h_i\)，现在你可以砍掉其中一些，砍掉第 \(i\) 棵需要 \(c_i\) 的代价。砍掉相当于把高度变成 \(0\)，若一棵树没被砍掉且高度是对应位置的前缀最大值或后缀最大值则产生 \(p_i\) 的贡献。
• 求贡献减代价的最大值。
• \(3\le n\le 10^5\)，所有数据在 \(10^9\) 以内。

题解

简单 DP，但是蠢了导致浪费一早上。

容易想到必定是一个前缀中产生贡献的单调不减，后缀产生贡献的单调不增。显然必定最大值同时满足两边，于是考虑求出前后缀的答案再枚举最大值统计。

只考虑前缀，容易想到 DP，设 \(f_i\) 表示考虑 \([1,i]\)，且钦定 \(i\) 产生贡献的最大答案。考虑从某个 \(f_j\) 转移，显然 \([1,i]\) 区间内不能出现高于 \(h_i\) 的树所以必然有 \(h_j\le h_i\)。

因为你想从 \(j\) 转移过来，所以其实 \([j+1,i-1]\) 区间内的都不会产生贡献，即高于 \(h_j\) 的都要砍掉，这样显然不会算漏，因为可以从这些地方转移过来。

那么对值域开一棵线段树维护区间最大值即可，复杂度 \(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,h[N],p[N],c[N],sz;
vector<i64> lsh;
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 mx[N<<2],mark[N<<2];
    void PushUp(i64 id){
        mx[id]=max(mx[id<<1],mx[id<<1|1]);
    }
    void PushDown(i64 id){
        mx[id<<1]+=mark[id];
        mark[id<<1]+=mark[id];
        mx[id<<1|1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Build(i64 l=0,i64 r=sz,i64 id=1){
        mx[id]=-inf;
        mark[id]=0;
        if(l==r) return;
        Build(lson);Build(rson);
    }
    void Update(i64 P,i64 X,i64 l=0,i64 r=sz,i64 id=1){
        if(l==r){
            mx[id]=max(mx[id],X);
            return;
        }
        if(mark[id]) PushDown(id);
        if(P<=mid) Update(P,X,lson);
        else       Update(P,X,rson);
        PushUp(id);
    }
    void Modify(i64 L,i64 R,i64 X,i64 l=0,i64 r=sz,i64 id=1){
        if(L<=l&&r<=R){
            mx[id]+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Modify(L,R,X,lson);
        if(mid< R) Modify(L,R,X,rson);
        PushUp(id);
    }
    i64 Query(i64 L,i64 R,i64 l=0,i64 r=sz,i64 id=1){
        if(L<=l&&r<=R){
            return mx[id];
        }
        if(mark[id]) PushDown(id);
        i64 res=-inf;
        if(L<=mid) res=max(res,Query(L,R,lson));
        if(mid< R) res=max(res,Query(L,R,rson));
        return res;
    }
};
SegTree mt;
i64 f[N],g[N];
signed main(){
    n=read();
    forup(i,1,n){
        h[i]=read();p[i]=read();c[i]=read();
        lsh.push_back(h[i]);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    sz=lsh.size();
    forup(i,1,n){
        h[i]=lower_bound(lsh.begin(),lsh.end(),h[i])-lsh.begin()+1;
    }
    forup(i,1,n){
        msg("[%lld]%lld %lld %lld|\n",i,h[i],c[i],p[i]);
    }
    mt.Build();
    mt.Update(0,0);
    forup(i,1,n){
        f[i]=mt.Query(0,h[i])+p[i];
        mt.Modify(0,h[i],-c[i]);
        mt.Update(h[i],f[i]);
        msg("%lld ",f[i]);
    }
    msg("|\n");
    mt.Build();
    mt.Update(0,0);
    fordown(i,n,1){
        g[i]=mt.Query(0,h[i])+p[i];
        mt.Modify(0,h[i],-c[i]);
        mt.Update(h[i],g[i]);
        msg("%lld ",g[i]);
    }
    msg("|\n");
    i64 ans=0;
    forup(i,1,n){
        ans=max(ans,f[i]+g[i]-p[i]);
    }
    printf("%lld\n",ans);
}

LOJ#6191 「美团 CodeM 复赛」配对游戏

传送门

题意

• 有一长度为 \(n\) 的括号序列，每个点等概率是左括号或又括号，求不能匹配的括号的期望数量。
• \(1\le n\le 2000\)

题解

有一堆 \(O(n^3)\) 做法，发现 \(n\le 2000\)，于是直接打表就能过了。

但是有 \(O(n^2)\) 做法，首先考虑计算每个点被留下来的概率。

不妨计算每个点以右括号留下来的概率，左括号是对称的。

设 \(f_i\) 表示第 \(i\) 个点以右括号留下来的概率，考虑枚举上一个留下来的 \(j\)。并且钦定 \([i+1,j-1]\) 中全不留下来。

则 \([i+1,j-1]\) 必定是一段合法括号序列，于是转移为 \(f_i\gets f_j\times Cat(\frac{i-j-1}{2})\times 2^{-(i-j-1)}\times \frac{1}{2}\)，要求 \((i-j-1)\bmod 2=0\)。

然后统计答案就全部加起来即可。复杂度 \(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 ld=long double;
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;
ld Cat[N],f[N],g[N],pw[N];
signed main(){
    n=read();
    Cat[0]=Cat[1]=1;
    forup(i,2,n){
        forup(j,0,i-1){
            Cat[i]+=Cat[j]*Cat[i-j-1];
        }
    }
    f[0]=1;
    pw[0]=1;
    forup(i,1,n) pw[i]=pw[i-1]*0.5;
    forup(i,1,n){
        for(int j=i-1;j>=0;j-=2){
            f[i]+=f[j]*Cat[(i-j-1)/2]*pw[i-j];
        }
        msg("%.3lf ",f[i]);
    }
    msg("|\n");
    ld ans=0;
    forup(i,1,n){
        ans+=f[i]+f[n-i+1];
    }
    printf("%.3Lf\n",ans);
}

LOJ#6177 「美团 CodeM 初赛 Round B」送外卖2

传送门

题意

• 有一个 \(n\) 个点 \(m\) 条边的有向图表示一座城市，每条边有边权表示通过它所需时间。
• 你是一个外卖员，有 \(q\) 个订单，第 \(i\) 个订单从 \(s_i\) 运送到 \(t_i\)，要求在 \(l_i\) 之后取餐，\(r_i\) 之前到达。
• 你 \(0\) 时刻在 \(1\) 号点，求最多能完成多少个订单。
• \(1\le n\le 20,1\le m\le 400,1\le q\le 10\)。

题解

容易想到三进制状压，考虑 DP，设 \(f_{i,msk}\) 表示在点 \(i\) 任务状态为 \(msk\) 的最短时间。

容易想到只有任务的起点终点是重要的，我们只需要关注这些就好了，于是预处理全源最短路然后跑 DP，因为只会从时间小的转移到时间大的所以不需要考虑后效性，转移是简单的。

复杂度 \(O(n^3+nq3^q)\)。

参考代码

#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=25,M=405,Q=15,inf=0x3f3f3f3f;
int n,m,q,dp[N][60000],mx,pw3[N],ans;
int num[60000];
int l[N],r[N],s[N],t[N];
int grp[N][N];
int get(int x,int bt){
    return (x/pw3[bt])%3;
}
signed main(){
    n=read();m=read();q=read();
    forup(i,1,n){
        forup(j,1,n){
            grp[i][j]=inf;
            if(i==j) grp[i][j]=0;
        }
    }
    forup(i,1,m){
        int u=read(),v=read(),w=read();
        grp[u][v]=min(grp[u][v],w);
    }
    forup(k,1,n){
        forup(i,1,n){
            forup(j,1,n){
                grp[i][j]=min(grp[i][j],grp[i][k]+grp[k][j]);
            }
        }
    }
    pw3[0]=1;
    forup(i,1,q){
        pw3[i]=pw3[i-1]*3;
    }
    forup(i,0,q-1){
        s[i]=read();t[i]=read();l[i]=read();r[i]=read();
        mx=max(mx,r[i]);
    }
    int al=0;
    forup(i,0,q-1) al+=pw3[i]*2;
    forup(i,0,al){
        forup(j,0,q-1){
            if(get(i,j)==2) ++num[i];
        }
    }
    mem(dp,0x3f);
    dp[1][0]=0;
    forup(i,0,al){
        forup(j,1,n){
            if(dp[j][i]==inf) continue;
            ans=max(ans,num[i]);
            forup(k,0,q-1){
                int v=get(i,k);
                if(v==0){
                    int tt=dp[j][i]+grp[j][s[k]],nxt=i+pw3[k];
                    if(tt<=r[k]) dp[s[k]][nxt]=min(dp[s[k]][nxt],max(tt,l[k]));
                }else if(v==1){
                    int tt=dp[j][i]+grp[j][t[k]],nxt=i+pw3[k];
                    if(tt<=r[k]) dp[t[k]][nxt]=min(dp[t[k]][nxt],tt);
                }
            }
        }
    }
    printf("%d\n",ans);
}

QOJ#6355 5

是的这道题真的就叫阿拉伯数字 “\(5\)”。

题意

• 给定一个长度为 \(n\)，总和为 \(s\) 的非负整数序列 \(a_i\)，其中 \(1\) 的数量大于等于 \(\frac{s}{5}\)。
• 称一个二元组 \((k,t)\) 合法当且仅当存在一个长度恰好为 \(k\) 的子序列总和恰好为 \(t\)。
• 求合法二元组数量。
• \(1\le n,s\le 2\times 10^5,0\le a_i\le s\)

题解

首先这个问题显然与序列的顺序无关，可以看成可重集。

首先容易想到一些和 \(1\) 的数量的性质无关的做法。比如一个想法是二维背包，设 \(g_{p,i,j}\) 表示只考虑前 \(p\) 种数（即将相同的数分为一组考虑），是否存在选了 \(i\) 个数的可重集总和为 \(j\)。容易发现第一维是 \(O(\sqrt{n})\) 级别的，大概能做到 \(O(n^2\sqrt{n})\)，并且显然第一维可以压掉。

这时候考虑“\(1\) 很多”这个条件。容易发现这样会使得 DP 中 \(1\) 的形状形如若干条斜向线段，因为每加一个一会使得两维都恰好 \(+1\)。那么不妨设 \(g_{i,j}\) 表示（考虑前 \(p\) 种数）总和减去数量的值为 \(i\)，数量为 \(j\) 的可重集是否存在。这样的话 \(1\) 的形状就形如每一行有若干区间了。

先不考虑 \(1\) 会得到若干个点，因为 \(1\) 至少有 \(\frac{s}{5}\) 个，那么假如同一行两个点的横向距离小于等于 \(\frac{s}{5}\) 它们就会连成一段区间。换句话说，每一行至多有 \(\frac{5n}{s}\) 个连续段。

因为至多有 \(\sqrt{s}\) 种不同的数，那么搞一下二进制拆分完全背包即可得到只需要转移 \(\sqrt{s}\log s\) 次。

然后行数是 \(O(s)\)，每次转移要遍历每一行的至多 \(O(\frac{n}{s})\) 个连续段，于是复杂度 \(O(n\sqrt{s}\log s)\)（据说其实二进制拆分不带 \(\log\)，但是我不确定），然后可以用 std::vector 维护连续段，转移的时候暴力重构即可，复杂度还是对的，因为反正你都要遍历一遍，重构的时候再遍历无伤大雅。

参考代码

#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;
int n,s,a[N],sum,A,mx;
int cnt[N];
vector<pair<pii,int> > ss[N<<1];
using mit=map<pii,int>::iterator;
void maintain(int p,int l,int r){
    vector<pair<pii,int> > v1=ss[p+A];ss[p+A].clear();
    for(auto i:v1){
        if(i.fi.se<l||r<i.fi.fi){
            ss[p+A].push_back(i);continue;
        }else{
            if(i.fi.fi<=l&&l<=i.fi.se){
                if(i.se){
                    l=i.fi.fi;
                }else{
                    if(i.fi.fi<l) ss[p+A].push_back(mkp(mkp(i.fi.fi,l-1),0));
                }
            }
            if(i.fi.fi<=r&&r<=i.fi.se){
                if(i.se){
                    r=i.fi.se;
                    ss[p+A].push_back(mkp(mkp(l,r),1));
                }else{
                    ss[p+A].push_back(mkp(mkp(l,r),1));
                    if(r<=i.fi.se) ss[p+A].push_back(mkp(mkp(r+1,i.fi.se),0));
                }
            }
        }
    }
    mx=max(mx,p);
}
void upd(int val,int cnt){
    fordown(p,min(mx,sum-val),0){
        for(auto j:ss[p+A]){
            if(!j.se) continue;
            maintain(p+val,j.fi.fi+cnt,j.fi.se+cnt);
        }
    }
}
signed main(){
    n=read();s=read();
    sum=0;
    forup(i,1,n){
        a[i]=read();
        ++cnt[a[i]];
        if(a[i]>1) sum+=a[i]-1;
        if(a[i]==0) ++A;
    }
    forup(i,-A,sum){
        ss[i+A].push_back(mkp(mkp(0,n),0));
    }
    maintain(0,0,cnt[1]);
    forup(i,2,s){
        if(!cnt[i]) continue;
        int w=1;
        while(cnt[i]>w){
            upd((i-1)*w,w);
            cnt[i]-=w;w<<=1;
        }
        upd((i-1)*cnt[i],cnt[i]);
    }
    i64 ans=0;
    int w=1;
    while(cnt[0]>w){
        int val=-w,cc=w;
        forup(p,-A+cc,sum){
            for(auto j:ss[p+A]){
                if(!j.se) continue;
                maintain(p+val,j.fi.fi+cc,j.fi.se+cc);
            }
        }
        cnt[0]-=w;w<<=1;
    }
    int val=-cnt[0],cc=cnt[0];
    forup(p,-A+cc,sum){
        for(auto j:ss[p+A]){
            if(!j.se) continue;
            maintain(p+val,j.fi.fi+cc,j.fi.se+cc);
        }
    }
    forup(p,-A,sum){
        for(auto j:ss[p+A]){
            if(j.se) ans+=(j.fi.se-j.fi.fi+1);
        }
    }
    printf("%lld\n",ans);
}

P10008 [集训队互测 2022] Range Minimum Element

传送门

题意

• 有一个长度为 \(n\)，值域为 \([1,c]\) 的整数序列 \(a_i\)，有一个长度为 \(m\) 整数序列 \(b_i\)，其中 \(b_i=\min_{j=l_i}^{r_i}\begin{Bmatrix}a_j\end{Bmatrix}\)，其中 \(l_i,r_i\) 是给定的 \(m\) 个二元组。
• 求有多少种不同的 \(b\)。
• \(1\le n\le 100,1\le m\le \binom{n}{2},1\le c < 998244353\)，答案对 \(998244353\) 取模。

题解

神秘思路。

容易发现顺着序列填数不好做，于是考虑能不能从小到大填数。思考一下可以发现假如在 \(i\) 处填了一个数那么左侧和右侧会变成两个独立的子问题，于是考虑区间 DP。

设 \(f_{i,j,k}\) 表示考虑区间 \([i,j]\)（并且只考虑 \([i,j]\) 包含的区间 \([l_i,r_i]\)），能填的最小的数为 \(k\)（就是值域为 \([k,c]\)，不一定取满）的方案数。于是枚举转移点 \(p\)，并且钦定 \(p\) 是区间内第一个恰好等于 \(k\) 的点，于是有 \(f_{i,j,k}\gets f_{i,p-1,k+1}\times f_{p+1,j,k}\)。注意到若 \(p\) 不被任何一个 \([l_i,r_i]\) 包含则这个钦定是没有意义的，于是我们可以只考虑被包含的情况。

然后又出现了一些问题，就是这个转移会算重。假设有两个转移点 \(p_1,p_2\)，并且包含它们的所有 \([l_i,r_i]\) 构成的集合分别是 \(S_1,S_2\)，容易发现若 \(S_1\subseteq S_2\)，那么在 \(p_1\) 算过的所有情况都会在 \(p_2\) 再算一遍（即所有 \(S_2\) 全取 \(k\) 的情况），这也能解释为什么不能从不被任何区间覆盖的转移点转移。

怎么解决呢？只要每次从 \(p_1\) 跳到最小的不满足 \(S_1\subseteq S_2\) 的 \(p_2\) 即可，其实找到包含 \(p_1\) 的最小的 \(r_i\) 就行了，这个可以对于每一对 \((i,j)\) 暴力 \(O(n^2)\) 预处理。

然后对这个东西做一遍后缀和即可求出 \(f\) 的值了。

这样复杂度大约是 \(O(n^3c)\) 的，显然就寄了嘛。但是注意到最多只会用到 \(n\) 个不同的数，于是考虑能否对于 \(1\le n'\le n\) 求出恰好使用 \(n'\) 种不同的数的序列，然后组合数一下就搞定了。

一个想法是将第三维的意义改为至多使用 \(k\) 个不同的数，转移是类似的，这样对 \(f_{1,n,\ast}\) 二项式反演一下即可得到想要的答案了。

于是复杂度 \(O(n^4)\)，随便过。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f,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,c;
int dp[N][N][N];
pii rg[N*N];
int mn[N];
int binom[N][N];
int C[N],f[N];
signed main(){
    n=read();m=read();c=read();
    forup(i,0,n){
        binom[i][0]=1;
        forup(j,1,i){
            binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
        }
    }
    C[0]=1;
    forup(i,1,min(n,c)){
        C[i]=1ll*C[i-1]*(c+1-i)%mod*ksm(i,mod-2)%mod;
    }
    forup(i,1,m){
        rg[i].fi=read();rg[i].se=read();
    }
    sort(rg+1,rg+m+1,[&](pii a,pii b){return a.se>b.se;});
    forup(i,1,n+1){
        forup(j,1,n){
            dp[i][i-1][j]=1;
        }
    }
    forup(len,1,n){
        forup(L,1,n-len+1){
            int R=L+len-1;
            forup(i,1,m){
                if(L<=rg[i].fi&&rg[i].se<=R){
                    forup(j,rg[i].fi,rg[i].se){
                        mn[j]=rg[i].se;
                    }
                }
            } 
            dp[L][R][1]=1;
            forup(i,2,n){
                forup(j,L,R){
                    if(mn[j]==0) continue;
                    (dp[L][R][i]+=1ll*dp[L][j-1][i-1]*dp[j+1][R][i]%mod)%=mod;
                    j=mn[j];
                }
            }
            forup(i,2,n){
                (dp[L][R][i]+=dp[L][R][i-1])%=mod;
            }
            forup(i,L,R) mn[i]=0;
        }
    }
    int ans=0;
    forup(i,1,min(n,c)){
        forup(j,1,i){
            (f[i]+=1ll*binom[i][j]*((i-j)&1?mod-1:1)%mod*dp[1][n][j]%mod)%=mod;
        }
        (ans+=1ll*f[i]*C[i]%mod)%=mod;
    }
    printf("%d\n",ans);
}

P4216 [SCOI2015] 情报传递

传送门

题意

• 给定一棵 \(n\) 个点的树，有两种操作共 \(q\) 次： - 将一个点激活。设它是在第 \(k\) 个操作激活的，那么在第 \(p\) 次操作（\(p\ge k\)）时，它的权值为 \(p-k\)。 - 求某条路径的长度以及上面有多少个点的权值严格大于 \(c\)。
• \(1\le n,q\le 2\times 10^5\)

题解

你好，一眼离线主席树，刚准备开始写发现可以单 \(\log\)。

其实就是相当于每次链查有多少个激活时间小于等于某个值的点。

于是离线下来直接树上差分维护即可，复杂度 \(O(n\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#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,q,ans[N],cntn,rt,len[N],ff[N];
vector<int> e[N];
struct query{
    int u,v,c,pos,ll;
}s[N];
int dfn[N],sz[N],Tm,dpt[N];
int st[19][N];
void dfs(int x){
    dfn[x]=++Tm;
    sz[x]=1;
    for(auto i:e[x]){
        dpt[i]=dpt[x]+1;
        ff[i]=x;
        dfs(i);
        sz[x]+=sz[i];
        st[0][dfn[i]]=x;
    }
}
int lca(int u,int v){
    if(u==v) return u;
    u=dfn[u];v=dfn[v];
    if(u>v) swap(u,v);
    ++u;
    int len=31^__builtin_clz(v-u+1);
    return dfn[st[len][u]]<dfn[st[len][v-(1<<len)+1]]?st[len][u]:st[len][v-(1<<len)+1];
}
struct BIT{
    int c[N];
    void upd(int x,int k){for(;x<=Tm;x+=x&-x)c[x]+=k;}
    int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
signed main(){
    n=read();
    forup(i,1,n){
        int f=read();
        if(f) e[f].push_back(i);
        else rt=i;
    }
    dfs(rt);
    forup(i,0,17){
        forup(j,1,n-(1<<(i+1))+1){
            st[i+1][j]=dfn[st[i][j]]<dfn[st[i][j+(1<<i)]]?st[i][j]:st[i][j+(1<<i)];
        }
    }
    q=read();
    forup(i,1,q){
        int op=read();
        if(op==1){
            s[i].u=read();s[i].v=read();s[i].c=i-read();
            s[i].ll=lca(s[i].u,s[i].v);
            len[i]=dpt[s[i].u]+dpt[s[i].v]-2*dpt[s[i].ll]+1;
        }else{
            s[i].u=read();s[i].v=-1;s[i].c=i;
        }
        s[i].pos=i;
    }
    sort(s+1,s+q+1,[&](query a,query b){return a.c<b.c;});
    int L=1;
    forup(i,1,q){
        if(s[i].v!=-1){
            while(L<=n&&s[L].c<s[i].c){
                if(s[L].v==-1){
                    mt.upd(dfn[s[L].u],1);
                    mt.upd(dfn[s[L].u]+sz[s[L].u],-1);
                }
                ++L; 
            }
            ans[s[i].pos]=mt.sum(dfn[s[i].u])+mt.sum(dfn[s[i].v])-mt.sum(dfn[s[i].ll])-(s[i].ll==rt?0:mt.sum(dfn[ff[s[i].ll]]));
        }
    }
    forup(i,1,q){
        if(len[i]){
            printf("%d %d\n",len[i],ans[i]);
        }
    }
}

QOJ#2562 Fake Plastic Trees 2

传送门

题意

• 有一棵 \(n\) 个点的树，点有点权。
• 给定 \(L,R,K\)，问是否有一个恰好隔开 \(K\) 条边的方案，使得割出来的每个连通块垫圈和均在 \([L,R]\) 中。
• \(1\le n\le 2\times 10^5\) 所有数在 \([0,10^{18}]\) 中。

题解

神秘做法。

首先考虑一个平凡的 DP，设 \(dp_{i,j,k}\) 表示考虑 \(i\) 及其子树，割 \(j\) 刀，\(i\) 所在连通块总和为 \(j\) 的方案是否存在，这样显然就不对啊，光是第三维就炸了。

这时候考虑一个我把头塞进马桶里都想不到的性质：有效的 \(k\) 是不多的。

具体来说，假如 \(dp_{i,j,a}=dp_{i,j,b}=dp_{i,j,c}=1(a < b < c)\)，若 \(c-a\le R-L+1\)，那么其实可以不管 \(b\)，考虑最终 \(i\) 所在的连通块，假设存在 \(i\) 上传 \(b\) 的方案，那么容易发现 \(i\) 子树能提供的合法大小是一个长度为 \(R-L+1\) 的区间，那么因为 \(b\) 在这个区间内，则 \(a,c\) 中必定有至少一个在这个区间内。于是把 \(b\) 删掉不会影响答案。

考虑 \(i\) 的子树点权和为 \(S\)，切下来的 \(j\) 刀总和应在 \([j\cdot L,j\cdot R]\) 之间，说明剩下的这一块值域应该是 \([S-j\cdot R,S-j\cdot L]\)，所以有效点数上界大致和 \(j\) 是同级别的，带个二倍常数。

于是对每个 \(dp_{i,j}\) 开一个 std::vector 存储所有合法的 \(k\)，转移就暴力合并，我觉得复杂度是 \(O(nk^4)\) 的，但貌似可以用树形背包的套路分析成 \(O(nk^3)\) 的，感觉很神奇，总之能过就对了。

参考代码

#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=2e5+5,inf=1e18;
i64 n,m,L,R,a[N];
vector<i64> e[N];
vector<i64> dp[N][55];
i64 sz[N];
void dfs(i64 x,i64 fa){
    sz[x]=1;
    dp[x][0].push_back(a[x]);
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
        vector<vector<i64> > ff(m+5);
        fordown(k,min(sz[x],m),0){
            forup(j,0,min(sz[i],m)){
                if(k+j>m) break;
                for(auto p:dp[i][j]){
                    for(auto q:dp[x][k]){
                        if(p+q<=R){
                            ff[k+j].push_back(p+q);
                        }
                        if(L<=p&&p<=R&&k+j+1<=m){
                            ff[k+j+1].push_back(q);
                        }
                    }
                }
            }
        }
        sz[x]+=sz[i];
        forup(k,0,min(sz[x],m)){
            vector<i64> vv;
            dp[x][k].clear();
            swap(vv,ff[k]);
            sort(vv.begin(),vv.end());
            vv.erase(unique(vv.begin(),vv.end()),vv.end());
            if(vv.empty()) continue;
            i64 sz=vv.size();
            dp[x][k].push_back(vv[0]);
            i64 lst=vv[0];
            forup(i,2,sz-1){
                if(vv[i]-lst>R-L+1){
                    dp[x][k].push_back(vv[i-1]);
                    lst=vv[i-1];
                }
            }
            if(vv.size()>1) dp[x][k].push_back(vv.back());
        }
    }
    // forup(i,0,min(sz[x],m)){
    //     msg("%d %d|",x,i);
    //     for(auto j:dp[x][i]){
    //         msg("%d ",j);
    //     }
    //     msg("|\n");
    // }
}
void solve(){
    n=read();m=read();L=read();R=read();
    i64 mx=0;
    forup(i,1,n){
        a[i]=read();
        mx=max(mx,a[i]);
        e[i].clear();
        forup(j,0,m) dp[i][j].clear();
    }
    forup(i,1,n-1){
        i64 u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    if(mx>R){
        forup(i,0,m){
            putchar('0');
        }
        puts("");
        return;
    }
    dfs(1,0);
    forup(i,0,m){
        if(lower_bound(dp[1][i].begin(),dp[1][i].end(),L)!=dp[1][i].end()){
            putchar('1');
        }else{
            putchar('0');
        }
    }
    puts("");
}
signed main(){
    i64 t=read();
    while(t--){
        solve();
    }
}

P3591 [POI2015] ODW

传送门

题意

你妈的波兰人真的不会写题意吗？垃圾题意谁写的。

• 有一棵 \(n\) 个点的树，点带权，\(n-1\) 次询问两点之间简单路径上每次跳 \(c_i\) 步经过的点权值和。
• \(1\le n\le 50000\)，点券在 \(10000\) 以内。

题解

根号分治，小的对每个倍数维护前缀和，大的暴力跳即可。复杂度可以做到 \(O(n\sqrt{n})\)，但是我因为不会长剖所以写的带 \(\log\)。

复杂度 \(O(n\sqrt{n}\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#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=5e4+5,B=230,inf=0x3f3f3f3f;
int n,a[N],b[N],c[N];
vector<int> e[N];
int hig[N],dfn[N],dpt[N],Tm,sz[N],son[N],mp[N],ff[N];
int sum[N][B+5];
void dfs1(int x,int fa){
    sz[x]=1;
    ff[x]=fa;
    int f=x;
    forup(i,1,B){
        f=ff[f];
        sum[x][i]=sum[f][i]+a[x];
    }
    dpt[x]=dpt[fa]+1;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs1(i,x);
        sz[x]+=sz[i];
        if(son[x]==0||sz[i]>sz[son[x]]) son[x]=i;
    }
}
void dfs2(int x,int fa,int hh){
    dfn[x]=++Tm;mp[dfn[x]]=x;
    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);
    }
}
int lca(int u,int v){
    while(hig[u]!=hig[v]){
        if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
        u=ff[hig[u]];
    }
    if(dpt[u]<dpt[v]) swap(u,v);
    return v;
}
int kth(int u,int k){
    if(k>=dpt[u]) return 0;
    while(dpt[u]-dpt[hig[u]]+1<=k){
        k-=dpt[u]-dpt[hig[u]]+1;
        u=ff[hig[u]];
    }
    return mp[dfn[u]-k];
}
signed main(){
    n=read();
    forup(i,1,n){
        a[i]=read();
    }
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    forup(i,1,n) b[i]=read();
    forup(i,1,n-1) c[i]=read();
    dfs1(1,0);
    dfs2(1,0,1);
    forup(i,1,n-1){
        int u=b[i],v=b[i+1];
        if(c[i]<=B){
            int p=lca(u,v),res=0;
            int t=((dpt[u]-dpt[p])/c[i]+1)*c[i];
            res+=sum[u][c[i]]-sum[kth(u,t)][c[i]];
            t=(dpt[v]-dpt[p]+c[i]-1)/c[i]*c[i];
            res+=sum[v][c[i]]-sum[kth(v,t)][c[i]];
            printf("%d\n",res);
        }else{
            int p=lca(u,v),res=0;
            while(dpt[u]>dpt[p]){
                res+=a[u];
                u=kth(u,c[i]);
            }
            while(dpt[v]>=dpt[p]){
                res+=a[v];
                v=kth(v,c[i]);
            }
            printf("%d\n",res);
        }
    }
}

QOJ#8822 Guess The Sequence 2

传送门

题意

• 给定一个长度为 \(n\) 的排列 \(a_i\)，小明可以选择其中一些区间并得知其每个区间的区间最大值，设这样得到若干个三元组 \((l,r,v)\)。
• 问在所有 \(2^{\frac{n(n-1)}{2}}\) 中询问方式中，有多少种可以让小明猜出整个排列。
• \(1\le n\le 5\times 10^5\)，保证数据随机，答案对 \(998244353\) 取模。

题解

什么神秘东西，阿拜多斯的小鸟游星野都没你神秘。

首先考虑假如你是小明你应该怎么猜出这个排列。考虑从小往大确定，那么不妨设在确定 \(x\) 之前所有 \(y < x\) 都被确定了，那么此时只要有一个区间 \((l,r,x)\) 就能唯一确定 \(x\) 所在位置，因为区间 \([l,r]\) 中只有小于等于 \(x\) 的数，而所有小于 \(x\) 的数都被确定了。

如果只有这种情况是非常好做的（下文称这样是被自己确定），因为只需要单调栈预处理左右第一个大于 \(a_i\) 的位置 \(L_i,R_i\)（后文会复用这个变量名，表达相同含义），每次乘 \(2^{(R_i-i)\times(i-L_i)}-1\) 即可。问题就在于还有其它情况。

若小于等于 \(i\) 的数除了 \(x\) 以外都被确定了，那么这时候我们再询问一个区间 \([l,r]\) 同时包含 \(i\) 和 \(x\)，那么我们是可以确定 \(x\) 的，因为你知道序列上有一个空位，三元组 \((l,r,i)\) 可以说明这个空位的值域是 \([1,i]\)，但是值域内其它数都被用过了。特别地，因为整个过程自带一个全局询问 \((1,n,n)\)（显然不管你问不问你都知道这个三元组），所以假如有一个空位留到了最后也是可以确定的。

这个怎么做呢？不妨对空位进行 DP。因为需要“除了 \(x\) 以外的数都被确定了”所以同时最多只有一个空位。设 \(dp_x\) 表示考虑所有满足 \(j\le x\) 的三元组 \((l,r,j)\)，能确定所有 \(j < x\) 但是不能确定 \(x\) 的方案数。

首先 DP 初值是简单的，就是前面“非常好做”的那种情况，那么如何转移和统计答案呢？

考虑使用 DP 进行转移，先枚举 \(x\) 后，设 \(f_{i,0/1}\) 表示考虑所有三元组 \((l,r,j)(j\le i)\)，钦定 \(x\) 是最后一个没有被自己确定的点，\(x\) 是/否被确定的方案数。

容易发现假如 \(L_i < p_x <R_i\)（\(p_x\) 代表 \(x\) 在排列中的位置），那么 \(a_i\) 是可以确定 \(x\) 的，反之则不行，于是分 \(i\) 能否确定 \(x\) 两种情况来转移。

首先是不能确定，那么显然 \(f_{i,0}\gets f_{i-1,0}\times (2^{(R_{p_i}-p_i)\cdot(p_i-L_{p_i})}-1),f_{i,1}\gets f_{i-1,1}\times (2^{(R_{p_i}-p_i)\cdot(p_i-L_{p_i})}-1)\)。

然后是能确定的，那么 \(f_0\to f_0\) 的转移不能有包含 \(p_x\) 的区间，\(f_1\) 的还是随意。然后还要考虑在这里确定 \(x\) 的。不妨设 \(p_x<p_i\)（反过来是对称的），则 \(f_{i,0}\gets f_{i-1,0}\times (2^{(p_i-p_x)\cdot (R_{p_i}-p_i)}-1)\)，\(f_1\) 的转移和上面一样。再加上 \(f_{i,1}\gets f_{i,0}\times (2^{(p_x-L_{p_i})\cdot (R_{p_i}-p_i)}-1)\)，注意这个转移应该最后做。

根据定义，显然在任何位置都有转移 \(f_{i,1}\to dp_{i+1}\)。并且显然 \(f_{n,0}\) 和 \(f_{n,1}\) 应累加进答案里。

这样我们就会 \(O(n^2)\) 做法了。

怎么优化呢？注意保证数据随机，那么这个序列的笛卡尔树深度是 \(O(\log n)\) 的。换句话说，能确定 \(x\) 的转移点只有 \(O(\log)\) 个（这个可以用笛卡尔树求出），而其它转移点可以用前缀和 \(+\) 差分搞定。于是复杂度可以容易地优化到 \(O(n\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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,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,a[N],pos[N],rt,ans;
const int B=1<<15;
int p2[N],pt2[N];
int pow2(i64 x){
    x%=(mod-1);
    return 1ll*pt2[x>>15]*p2[x-((x>>15)<<15)]%mod;
}
int ff[N],L[N],R[N];
void buildtree(){
    a[0]=a[n+1]=inf;
    stack<int> stk;
    stk.push(0);
    forup(i,1,n){
        int pl=0;
        while(a[stk.top()]<a[i]){
            pl=stk.top();
            stk.pop();
        }
        if(pl) ff[pl]=i;
        L[i]=stk.top();
        stk.push(i);
    }
    while(stk.size()) stk.pop();
    stk.push(n+1);
    fordown(i,n,1){
        int pl=0;
        while(a[stk.top()]<a[i]){
            pl=stk.top();
            stk.pop();
        }
        if(pl) ff[pl]=i;
        R[i]=stk.top();
        stk.push(i);
    }
}
int dp[N];
int pre[N],invp[N],sum[N],val[N];
void solve(){
    n=read();
    forup(i,1,n){
        a[i]=read();
        pos[a[i]]=i;
        if(a[i]==n) rt=i;
        ff[i]=dp[i]=sum[i]=0;
    }
    if(n==1) return puts("2"),void();
    if(n==2) return puts("6"),void();
    buildtree();
    pre[0]=1;
    forup(i,1,n){
        int p=pos[i];
        val[i]=pow2(1ll*(p-L[p])*(R[p]-p))-1;
        pre[i]=1ll*pre[i-1]*val[i]%mod;
    }
    invp[n]=ksm(pre[n],mod-2);
    fordown(i,n-1,1){
        invp[i]=1ll*invp[i+1]*val[i+1]%mod;
    }
    ans=0;
    int nw=1;
    forup(i,1,n){
        (sum[i]+=sum[i-1])%=mod;
        (dp[i]+=nw)%=mod;
        (dp[i]+=1ll*sum[i]*pre[i-1]%mod)%=mod;
        int p=pos[i];
        nw=1ll*nw*val[i]%mod;
        int j=p,f0=dp[i],f1=0;
        while(ff[j]){
            int k=ff[j];
            (sum[a[j]+1]+=1ll*f1*invp[a[j]]%mod)%=mod;
            (sum[a[k]+1]+=(mod-1ll*f1*invp[a[j]]%mod))%=mod;
            f0=1ll*f0*pre[a[k]-1]%mod*invp[a[j]]%mod;
            f1=1ll*f1*pre[a[k]-1]%mod*invp[a[j]]%mod;
            f1=1ll*f1*val[a[k]]%mod;
            if(p<k){
                f0=1ll*f0*(pow2(1ll*(k-p)*(R[k]-k))-1)%mod;
                (f1+=1ll*f0*(pow2(1ll*(p-L[k])*(R[k]-k))-1)%mod)%=mod;
            }else{
                f0=1ll*f0*(pow2(1ll*(k-L[k])*(p-k))-1)%mod;
                (f1+=1ll*f0*(pow2(1ll*(k-L[k])*(R[k]-p))-1)%mod)%=mod;
            }
            j=k;
        }
        (ans+=f0)%=mod;
        (ans+=f1)%=mod;
    }
    (ans+=nw)%=mod;
    printf("%d\n",ans);
}
signed main(){
    p2[0]=1;
    forup(i,1,B){
        p2[i]=2ll*p2[i-1]%mod;
    }
    pt2[0]=1;
    forup(i,1,B){
        pt2[i]=1ll*pt2[i-1]*p2[B]%mod;
    }
    solve();
}

P3588 [POI2015] PUS

传送门

不是这他妈是波兰人的问题还是翻译的问题啊。什么狗屎题面。

题意

• 有一个长度为 \(n\) 值域为 \([1,10^9]\) 的序列，其中 \(s\) 个值已经给定了。
• 现在再给你 \(m\) 个限制，第 \(i\) 个限制 \((l_i,r_i,k_i,x_i)\)（其中 \(x_i\) 是一个长度为 \(k_i\) 的序列，其余均为正整数）表示区间 \([l_i,r_i]\) 中前 \(k_i\) 大的下标集合为 \(x_i\)，保证给定的 \(x_i\) 单调递增。
• 构造序列或报告无解。
• \(1\le s\le n\le 10^5,1\le m\le 2\times 10^5,0\le\sum k\le 3\times 10^5\)。

题解

一眼线段树优化建图然后按拓扑序 DP，点数 \(O(n+m+k)\)，边数 \(O(k\log n+n)\)。

除去优化建图外其它都是平凡的，建图即从大向小连边，即 \(k\) 个点向它们之间的缝隙连边，显然不能直接暴力连，那么建个虚点就完了。

然后 DP 状态就是这个点能取到的最大值，转移是简单的，得到 DP 后构造答案也是简单的。注意判断值域下界为 \(1\)。

复杂度 \(O(n+m+k\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
#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,s,m,a[N],mx[N*10],cntn,rd[N*10];
vector<int> e[N*10];
void adde(int u,int v){
    e[u].push_back(v);
    ++rd[v];
}
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int nd[N<<2];
    void Build(int l=1,int r=n,int id=1){
        if(l==r){
            nd[id]=l;
            return;
        }
        nd[id]=++cntn;
        Build(lson);Build(rson);
        adde(nd[id],nd[id<<1]);
        adde(nd[id],nd[id<<1|1]);
    }
    void Link(int P,int L,int R,int l=1,int r=n,int id=1){
        if(L<=l&&r<=R){
            adde(P,nd[id]);
            return;
        }
        if(L<=mid) Link(P,L,R,lson);
        if(mid< R) Link(P,L,R,rson);
    }
}mt;
signed main(){
    n=read();s=read();m=read();
    forup(i,1,s){
        int p=read(),d=read();
        a[p]=d;
    }
    cntn=n;
    mt.Build();
    forup(i,1,m){
        int l=read(),r=read(),k=read();
        int dd=++cntn;
        int lst=l;
        vector<pii> vv;
        forup(j,1,k){
            int x=read();
            if(x>lst){
                vv.push_back(mkp(lst,x-1));
            }
            lst=x+1;
            adde(x,dd);
        }
        if(lst<=r){
            vv.push_back(mkp(lst,r));
        }
        for(auto j:vv){
            mt.Link(dd,j.fi,j.se);
        }
    }
    queue<int> q;
    int cc=0;
    forup(i,1,cntn){
        if(!rd[i]) q.push(i);
        mx[i]=1e9;
    }
    while(q.size()){
        int u=q.front();q.pop();
        ++cc;
        if(u<=n){
            if(mx[u]<a[u]){
                puts("NIE");
                return 0;
            }
            if(!a[u]) a[u]=mx[u];
        }
        for(auto v:e[u]){
            --rd[v];
            if(u<=n){
                mx[v]=min(mx[v],a[u]-1);
            }else{
                mx[v]=min(mx[v],mx[u]);
            }
            if(!rd[v]) q.push(v);
        }
    }
    if(cc!=cntn){
        puts("NIE");
        return 0;
    }
    forup(i,1,n){
        if(a[i]<1){
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    forup(i,1,n){
        printf("%d ",a[i]);
    }
    puts("");
}

QOJ#7605 Yet Another Mex Problem

传送门

题意

• 给定一个长度为 \(n\) 的序列 \(a_i\)，值域为 \([0,n]\)。
• 给定常数 \(k\)，你可以将序列划分为若干段，每一段长度均不能大于 \(k\)，为方便叙述，我们用一个序列 \(s_0,s_1,s_2\dots s_p(s_i < s_{i+1} \le s_i+k,s_0=0,s_p=n)\) 表示一个 \(p\) 段的划分，我们定义划分的权值为 \(\sum_{i=1}^{p-1}\left(\mathrm{mex}_{j=s_i+1}^{s_{i+1}}a_i\right)\times \left(\sum_{j=s_i+1}^{s_{i+1}}a_i\right)\)，求划分的最大权值。
• \(1\le n\le 2\times 10^5\)

题解

心魔击溃！去年 \(11\) 月份就写上 Todo list 了现在才搞完。

首先容易想到一个 \(O(n^2)\) DP，设 \(f_i\) 表示考虑 \([1,i]\)，在 \(i\) 处切一刀的最大权值，转移就枚举上一刀即可。

考虑 DP 如何优化，设 \(sum_i=\sum_{j=1}^i a_j\)，转移即为：

\[ f_i=\max_{j=1}^{i-1}\begin{Bmatrix}f_j+\left(\mathrm{mex}_{j=s_i+1}^{s_{i+1}}a_i\right)\times (sum_i-sum_j)\end{Bmatrix} \]

那么我们无论如何都需要把这个 \(\mathrm{mex}\) 拆开。

考虑一个 \(\mathrm{mex}\) 的经典性质：在一个序列上，对于同一个左端点，区间 \(\mathrm{mex}\) 随着右端点右移单调不减。证明显然，因为一个集合超集的 \(\mathrm{mex}\) 不会比它更小。

注意到随着右端点右移，对于所有左端点的 \(\mathrm{mex}\) 应该是若干个相等的区间。然后又能瞪出一个新的性质：这样的左端点区间至多更新 \(O(n)\) 次（这么说比较抽象啊，可以把它看成若干个区间覆盖问题，这样的区间覆盖至多进行 \(O(n)\) 次）。

证明也比较简单，不妨先以 \(n\) 为右端点每次左移。那么初始至多有 \(O(n)\) 个区间，然后假设要将右端点从 \(i\) 移动到 \(i-1\)，设 \(a_i\) 上一次出现为 \(p_i\)，那么就是将 \([p_i+1,i]\) 中所有数和 \(a_i\) 取 \(\min\)。因为 \(\mathrm{mex}\) 随着左端点左移单调不减，那么这就相当于将一个连续的区间修改为 \(a_i\)。于是右端点每左移一次至多新增一个区间，所以区间至多更新 \(O(n)\) 次。

所以我们只需要找出每次更新的区间，然后去区间赋值就能一定程度上解决 \(\mathrm{mex}\) 问题了。

然后考虑拆 DP 式子，因为是一些和 \(i,j\) 均有关的东西相乘所以容易想到类似斜率优化 DP 的思路，设 \(M=\mathrm{mex}_{j=s_i+1}^{s_{i+1}}a_i\)，于是：

\[ \begin{aligned} f_i&=f_j+M\times (sum_i-sum_j)\\ &=f_j+M\cdot sum_i-M\cdot sum_j\\ &=(f_j-M\cdot sum_j)+M\cdot sum_i\\ \end{aligned} \]

那么就相当于要在两个地方做斜率优化，第一个是用 \(M\) 去更新 \(j\) 的时候需要求出 \(f_j-M\cdot sum_j\) 的最大值，第二个是更新 \(f_i\) 的时候括号内相当于一个常数，也能斜率优化解决。

有一个极其复杂的 \(O(n\log^2 n)\) 写法，大概就是写几棵线段树套李超树，此处略过。我们不妨来讨论一个更好写（而且通常更快）的分块做法，设块长为 \(B\)。

首先考虑如何用 \(M\) 去更新，那么分整块和散块解决（整块就是被 \(M\) 区间完全覆盖的块，散块则是有交但未被完全覆盖的块）。整块就相当于在凸包上查询，由于 \(\mathrm{mex}\) 单调不减所以可以用双端队列去维护凸包。总复杂度 \(O(nB+\frac{n^2}{B})\)，称这样的块为“纯色块”。

然后是散块，容易发现 \(sum_i\) 单调递增，所以也可以用双端队列维护凸包来做，更新 \(M\) 时暴力重构即可。复杂度 \(O(nB)\)，称这样的块为“混色块”。

然后查询是比较平凡的，散块暴力扫，整块则要分纯色块和混色块分别维护，复杂度 \(O(nB+\frac{n^2}{B})\)。

容易发现空间复杂度是 \(O(n)\) 的，于是做完了。理论上 \(B\) 取 \(450\) 左右会比较优，实测发现由于扫整个块的操作会进行比较多次，所以 \(B\) 取小一点会更优，我调了下块长认为 \(200\) 最好。复杂度 \(O(n\sqrt{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 i128=__int128;
using pii=pair<i64,i64>;
#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,B=200,T=1005;
i64 inf=1e18;
int n,m,a[N];
i64 sum[N];
int L[T],R[T],blg[N];
deque<pii> conv[T];
i128 cross(pii a,pii b){
    return a.fi*b.se-a.se*b.fi;
}
pii operator -(const pii a,const pii b){
    return mkp(a.fi-b.fi,a.se-b.se);
}
bool slp(pii a,pii b,pii c){
    return cross(b-a,c-b)<=0;
}
bool slp(pii a,pii b,i64 k){
    return (b.se-a.se)<=(i128)(b.fi-a.fi)*k;
}
i64 dp[N];
int mex[N],tag[T];
deque<pii> c2[T];
i64 mxv[T];
void work(int b){
    deque<pii> &q=c2[b];
    fordown(i,R[b],L[b]){
        pii nw=mkp(-sum[i],-dp[i]);
        if(q.size()&&nw.fi==q.back().fi) continue;
        while(q.size()>=2&&slp(q[q.size()-2],q[q.size()-1],nw)) q.pop_back();
        q.push_back(nw);
    }
}
void update(int b,int v){
    deque<pii> &q=c2[b];
    while(q.size()>=2&&slp(q[0],q[1],v)) q.pop_front();
    mxv[b]=q.front().fi*v-q.front().se;
}
void getconv(int j){
    if(~tag[j]){
        forup(k,L[j],R[j]){
            mex[k]=tag[j];
        }
        tag[j]=-1;
    }
    deque<pii> &q=conv[j];
    q.clear();
    vector<pii> vv;
    fordown(k,R[j],L[j]){
        pii nw;
        nw.fi=mex[k];nw.se=mex[k]*sum[k]-dp[k];
        vv.push_back(nw);
    }
    sort(vv.begin(),vv.end());
    for(auto i:vv){
        if(q.size()&&i.fi==q.back().fi) continue;
        while(q.size()>=2&&slp(q[q.size()-2],q[q.size()-1],i)) q.pop_back();
        q.push_back(i);
    }
}
int tt[N],m0,lst[N],pp[N];
vector<pair<pii,int> > modi[N];
map<pii,int> odt;
using mit=map<pii,int>::iterator;
mit split(int x){
    mit it=odt.lower_bound(mkp(x,0));
    if(it->fi.fi==x) return it;
    --it;
    int l=it->fi.fi,r=it->fi.se,c=it->se;
    odt.erase(it);
    odt.insert(mkp(mkp(l,x-1),c));
    return odt.insert(mkp(mkp(x,r),c)).fi;
}
signed main(){
    n=read();m=read();
    forup(i,1,n){
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
        pp[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    int t=n/B;
    forup(i,1,t){
        L[i]=R[i-1]+1;R[i]=i*B;
        forup(j,L[i],R[i]) blg[j]=i;
    }
    if(R[t]!=n){
        ++t;
        L[t]=R[t-1]+1;R[t]=n;
        forup(j,L[t],R[t]) blg[j]=t;
    }
    forup(i,1,t) tag[i]=-1;
    fordown(i,n,0){
        mex[i]=mex[i+1];
        while(tt[mex[i]]) ++mex[i];
        ++tt[a[i]];
    }
    forup(i,0,n) tt[i]=0;
    int lpos=0;
    forup(i,1,n){
        if(mex[i]!=mex[i-1]){
            odt.insert(mkp(mkp(lpos,i-1),mex[i-1]));
            lpos=i;
        }
    }
    odt.insert(mkp(mkp(lpos,n),mex[n]));
    fordown(i,n,1){
        mit st=split(pp[i]);
        int r=pp[i]-1;
        for(mit it=st;it!=odt.end()&&it->se>=a[i];odt.erase(prev(++it))){
            modi[i].push_back(*it);
            r=it->fi.se;
        }
        if(r>=pp[i])odt.insert(mkp(mkp(pp[i],r),a[i]));
        mex[i]=0;
    }
    mex[0]=0;
    forup(i,1,n){
        ++tt[a[i]];
        while(tt[m0]) ++m0;
        dp[i]=0;
        if(i<=m){
            dp[i]=max(dp[i],m0*sum[i]);
        }
        vector<int> sv;
        for(auto j:modi[i]){
            int l=j.fi.fi,r=j.fi.se,c=j.se;
            if(r==0) continue;
            if(l==0) l=1;
            if(blg[r]==blg[l]){
                if(~tag[blg[l]]){
                    int p=blg[l];
                    forup(k,L[p],R[p]) mex[k]=tag[p];
                    tag[p]=-1;
                }
                forup(k,l,r){
                    mex[k]=c;
                }
                sv.push_back(blg[l]);
            }else{
                if(~tag[blg[l]]){
                    int p=blg[l];
                    forup(k,L[p],R[p]) mex[k]=tag[p];
                    tag[p]=-1;
                }
                if(~tag[blg[r]]){
                    int p=blg[r];
                    forup(k,L[p],R[p]) mex[k]=tag[p];
                    tag[p]=-1;
                }
                forup(k,l,R[blg[l]]) mex[k]=c;
                forup(k,L[blg[r]],r) mex[k]=c;
                sv.push_back(blg[l]);sv.push_back(blg[r]);
                forup(j,blg[l]+1,blg[r]-1) tag[j]=c;
            }
        }
        fordown(j,i-1,max(L[blg[i]],i-m)){
            int mm=mex[j];
            if(~tag[blg[j]]) mm=tag[blg[j]];
            dp[i]=max(dp[i],dp[j]+mm*(sum[i]-sum[j]));
        }
        sort(sv.begin(),sv.end());
        sv.erase(unique(sv.begin(),sv.end()),sv.end());
        for(auto j:sv){
            getconv(j);
        }
        if(i-m>=1&&blg[i]!=blg[i-m]){
            fordown(j,blg[i]-1,blg[i-m]+1){
                if(~tag[j]){
                    update(j,tag[j]);
                    dp[i]=max(dp[i],tag[j]*sum[i]+mxv[j]);
                }else{
                    while(conv[j].size()>=2&&slp(conv[j][0],conv[j][1],sum[i])) conv[j].pop_front();
                    dp[i]=max(dp[i],conv[j].front().fi*sum[i]-conv[j].front().se);
                }
            }
            fordown(j,R[blg[i-m]],i-m){
                int mm=mex[j];
                if(~tag[blg[j]]) mm=tag[blg[j]];
                dp[i]=max(dp[i],dp[j]+mm*(sum[i]-sum[j]));
            }
        }
        if(i==R[blg[i]]){
            work(blg[i]);
            getconv(blg[i]);
        }
    }
    printf("%lld\n",dp[n]);
}

P6822 [PA2012] Tax

传送门

题意

• 给定一张 \(n\) 个点 \(m\) 条边的边带权无向图。
• 定义一条路径的代价为每个点的花费之和，每个点（出去起点终点）的花费为路径上和它相连的两条边的边权较大值，起点和终点的花费为和它相连的边的边权。
• 求从 \(1\) 到 \(n\) 的最小花费。
• \(1\le n\le 10^5,1\le m\le 2\times 10^5\)，边权在 \([1,10^6]\) 以内。

题解

看了一眼感觉像建分层图将贡献挪到边上然后跑最短路，仔细想想发现确实是这样的。

首先完全不考虑复杂度，可以将每个点拆成 \(c\) 个点（\(c\) 是值域上界），将每个点边权为 \(p\) 的出边扔到对应的点上，然后对于边 \((u,v,p)\)，若下一条边（即 \(v\) 的出边）的边权 \(q\) 小于 \(p\) 则点 \(v\) 产生 \(p\) 的贡献，若大于等于 \(p\) 则点 \(v\) 产生 \(q\) 的贡献。

那么边 \((u,v,p)\) 则从点 \(u_p\)（这样写应该能看懂）向点 \(v_1\sim v_{p-1}\) 连边权为 \(p\) 的边，向 \(v_{p}\sim v_{c}\) 连边权为 \(v\) 下标的边。这个可以前缀和优化建图。

但是点数仍然超标。容易发现我们其实只关注和一个点相邻的边，所以每个点只需要拆成出边个数个点即可。

于是点数边数均为 \(O(n+m)\)，复杂度 \(O((n+m)\log (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=1e5+5;
const i64 inf=1e18;
int n,m,cntn;
i64 dis[N*15];
int vis[N*15];
vector<pii> e[N*15],nd[N];
vector<int> pre[N],suf[N];
struct edge{
    int u,v,w;
    bool operator<(const edge &r)const{return w<r.w;}
}s[N*2];
struct Node{
    i64 u,dis;
    bool operator<(const Node &r)const{return dis>r.dis;}
};
void dijkstra(){
    forup(i,1,cntn) dis[i]=inf;
    priority_queue<Node> q;
    dis[suf[1][0]]=0;
    q.push(Node{suf[1][0],0});
    while(q.size()){
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:e[u]){
            int v=i.fi,w=i.se;
            if(dis[v]<=dis[u]+w) continue;
            dis[v]=dis[u]+w;
            q.push(Node{v,dis[v]});
        }
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        s[i].u=read();s[i].v=read();s[i].w=read();
    }
    sort(s+1,s+m+1);
    nd[n].push_back(mkp(0,++cntn));
    forup(i,1,m){
        int u=s[i].u,v=s[i].v,w=s[i].w;
        if(nd[u].empty()||w!=nd[u].back().fi) nd[u].push_back(mkp(w,++cntn));
        if(nd[v].empty()||w!=nd[v].back().fi) nd[v].push_back(mkp(w,++cntn));
    }
    forup(i,1,n){
        int sz=nd[i].size();
        pre[i].resize(sz);
        suf[i].resize(sz);
        forup(j,0,sz-1){
            pre[i][j]=++cntn;
            e[pre[i][j]].push_back(mkp(nd[i][j].se,0));
            if(j) e[pre[i][j]].push_back(mkp(pre[i][j-1],0));
        }
        fordown(j,sz-1,0){
            suf[i][j]=++cntn;
            e[suf[i][j]].push_back(mkp(nd[i][j].se,nd[i][j].fi));
            if(j<sz-1) e[suf[i][j]].push_back(mkp(suf[i][j+1],0));
        }
    }
    forup(i,1,m){
        int u=s[i].u,v=s[i].v,w=s[i].w;
        int pu=lower_bound(nd[u].begin(),nd[u].end(),mkp(w,0))-nd[u].begin(),
            pv=lower_bound(nd[v].begin(),nd[v].end(),mkp(w,0))-nd[v].begin();
        e[nd[u][pu].se].push_back(mkp(pre[v][pv],w));
        if(pv<(int)nd[v].size()-1) e[nd[u][pu].se].push_back(mkp(suf[v][pv+1],0));
        e[nd[v][pv].se].push_back(mkp(pre[u][pu],w));
        if(pu<(int)nd[u].size()-1) e[nd[v][pv].se].push_back(mkp(suf[u][pu+1],0));
    }
    dijkstra();
    printf("%lld\n",dis[pre[n][0]]);
}

CF1007D Ants

传送门

题意

• 有一棵 \(n\) 个点的树，有 \(m\) 个路径对，你要在每一对中选一条涂黑，要求一条边不能被涂黑超过一次，求出一组解。
• \(1\le n\le 10^5,1\le m\le 10^4\)

题解

感觉就很 2-SAT，但是有个问题是假如直接树剖用线段树优化建图会连出自环。

怎么办呢？考虑扫描，每次把一条链和之前的连边，然后把它加到线段树上，这个使用标记永久化，并且在线段树每个结点上维护时间轴的前缀和优化建图。

因为每个点需要向前向后都连边，所以正着扫一次反着扫一次即可。

边数 \(O(n\log^2 n)\)，复杂度也是这个。注意数组适当开大一点，不要用 std::vector 存图，不然容易 MLE。

参考代码

#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,m,cntn;
vector<int> e[N];
void adde(int u,int v){
    e[u].push_back(v);
}
int sz[N],son[N],dfn[N],Tm,hig[N],dpt[N],ff[N];
void dfs1(int x,int fa){
    sz[x]=1;
    dpt[x]=dpt[fa]+1;
    ff[x]=fa;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs1(i,x);
        sz[x]+=sz[i];
        if(son[x]==0||sz[i]>sz[son[x]]) son[x]=i;
    }
}
void dfs2(int x,int fa,int hh){
    hig[x]=hh;
    dfn[x]=++Tm;
    if(son[x]){
        dfs2(son[x],x,hh);
    }
    for(auto i:e[x]){
        if(i==fa||i==son[x]) continue;
        dfs2(i,x,i);
    }
}
namespace Tarjan{
    struct edge{
        int v,nxt;
    }e[N*270];
    int head[N*135],cnte;
    void adde(int u,int v){
        e[++cnte]=edge{v,head[u]};head[u]=cnte;
    }
    int dfn[N*135],low[N*135],blg[N*135],Tm,csc;
    bitset<N*135> ist;
    stack<int> stk;
    void Tarjan(int x){
        dfn[x]=low[x]=++Tm;
        stk.push(x);ist[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].v;
            if(!dfn[v]){
                Tarjan(v);
                low[x]=min(low[x],low[v]);
            }else if(ist[v]){
                low[x]=min(low[x],dfn[v]);
            }
        }
        if(dfn[x]==low[x]){
            ++csc;
            for(int v=0;v!=x;){
                v=stk.top();
                blg[v]=csc;
                ist[v]=0;
                stk.pop();
            }
        }
    }
    void solve(){
        forup(i,1,cntn){
            if(!dfn[i]) Tarjan(i);
        }
        forup(i,1,m){
            if(blg[i*2]==blg[i*2-1]){
                puts("NO");
                exit(0);
            }
        }
    }
}
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int nd[N<<2],mk[N<<2];
    void Build(int l=1,int r=n,int id=1){
        nd[id]=mk[id]=0;
        if(l==r) return;
        Build(lson);Build(rson);
    }
    void Update(int L,int R,int X,int l=1,int r=n,int id=1){
        int nw=++cntn;
        Tarjan::adde(nw,X);
        if(nd[id]) Tarjan::adde(nw,nd[id]);
        nd[id]=nw;
        if(L<=l&&r<=R){
            int nw=++cntn;
            Tarjan::adde(nw,X);
            if(mk[id]) Tarjan::adde(nw,mk[id]);
            mk[id]=nw;
            return;
        }
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
    }
    void Link(int L,int R,int X,int l=1,int r=n,int id=1){
        if(mk[id]) Tarjan::adde(X,mk[id]);
        if(L<=l&&r<=R){
            if(nd[id]) Tarjan::adde(X,nd[id]);
            return;
        }
        if(L<=mid) Link(L,R,X,lson);
        if(mid< R) Link(L,R,X,rson);
    }
};
SegTree mt;
void Update(int u,int v,int nw){
    while(hig[u]!=hig[v]){
        if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
        mt.Update(dfn[hig[u]],dfn[u],nw);
        u=ff[hig[u]];
    }
    if(dpt[u]>dpt[v]) swap(u,v);
    if(dfn[u]!=dfn[v]) mt.Update(dfn[u]+1,dfn[v],nw);
}
void Link(int u,int v,int nw){
    while(hig[u]!=hig[v]){
        if(dpt[hig[u]]<dpt[hig[v]]) swap(u,v);
        mt.Link(dfn[hig[u]],dfn[u],nw);
        u=ff[hig[u]];
    }
    if(dpt[u]>dpt[v]) swap(u,v);
    if(dfn[u]!=dfn[v]) mt.Link(dfn[u]+1,dfn[v],nw);
}
struct opr{
    int u1,v1,u2,v2;
}s[N];
signed main(){
    n=read();
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0,1);
    m=read();
    cntn=m*2;
    forup(i,1,m){
        int u1=read(),v1=read(),u2=read(),v2=read();
        s[i]=opr{u1,v1,u2,v2};
        int n1=i*2,n2=n1-1;
        Link(u1,v1,n1);Link(u2,v2,n2);
        Update(u1,v1,n2);Update(u2,v2,n1);
    }
    mt.Build();
    fordown(i,m,1){
        int u1=s[i].u1,v1=s[i].v1,u2=s[i].u2,v2=s[i].v2;
        int n1=i*2,n2=n1-1;
        Link(u1,v1,n1);Link(u2,v2,n2);
        Update(u1,v1,n2);Update(u2,v2,n1);
    }
    Tarjan::solve();
    puts("YES");
    forup(i,1,m){
        puts(Tarjan::blg[i*2]<Tarjan::blg[i*2-1]?"1":"2");
    }
}

[ABC217F] Make Pair

传送门

题意

• 有 \(2n\) 个人排成一排，其中有 \(m\) 对好朋友。
• 每次要选一对相邻的好朋友出列，然后两侧的人就变成相邻的。
• 问有多少种出列方案，称两方案不同当且仅当存在某一对配对的人不同或存在某两对出列顺序不同。
• \(1\le n\le 200,1\le m\le n(2n-1)\)。

题解

容易想到区间 DP，类似于石子合并。设 \(f_{l,r}\) 表示 \([l,r]\) 的人全部出列的方案数，转移有两种，若 \(l,r\) 是一对好朋友则 \(f_{l,r}\gets f_{l+1,r-1}\)，另外还可以枚举一个分界点 \(k\)，然后 \(f_{l,r}\gets f_{l,k-1}\times f_{k,r}\times \binom{\frac{r-l+1}{2}}{\frac{r-len}{2}}\)。

但是有一个 BUG，一个方案可能有多个分界点，显然从每个分界点都可能转移，怎么办呢？我们可以钦定 \(k\) 是最后一个分界点，那么 \((k,r)\) 必定是一对好朋友，于是转移改为 \(f_{l,r}\gets f_{l,k-1}\times f_{k+1,r-1}\times \binom{\frac{r-l+1}{2}}{\frac{r-len}{2}}\)（注意要求 \(k,r\) 是一对好朋友）。

复杂度 \(O(n^3)\)，我写的时候没带脑子所以带了个 \(\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=405,inf=0x3f3f3f3f,mod=998244353;
int n,m,binom[N][N];
set<int> pi[N];
int dp[N][N];
signed main(){
    n=read();m=read();
    forup(i,0,n*2){
        binom[i][0]=1;
        forup(j,1,i){
            binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%mod;
        }
        dp[i][i-1]=1;
    }
    forup(i,1,m){
        int l=read(),r=read();
        pi[r].insert(l);
    }
    for(int len=2;len<=2*n;len+=2){
        forup(l,1,n*2-len+1){
            int r=l+len-1;
            if(pi[r].count(l)){
                (dp[l][r]+=dp[l+1][r-1])%=mod;
            }
            for(int i=l+2;i<=r-1;i+=2){
                if(pi[r].count(i)){
                    (dp[l][r]+=1ll*dp[l][i-1]*dp[i+1][r-1]%mod*binom[(r-l+1)/2][(i-l)/2]%mod)%=mod;
                }
            }
        }
    }
    printf("%d\n",dp[1][n*2]);
}

QOJ#2606 Gachapon

传送门

题意

• 有一个抽卡游戏，里面有的物品有从 \(0\) 到 \(m\) 共 \(m+1\) 种星级，一抽抽出 \(i\) 星物品的概率是 \(\frac{a_i}{\sum a}\)。
• 此游戏和原神一样设有保底机制，即在一个 \(i\) 级抽卡中至少抽出一个大于等于 \(i\) 星的物品。我们这样定义 \(i\) 级抽卡： - \(0\) 级抽卡为一抽。 - \(i\) 级抽卡为 \(b_i\) 个 \(i-1\) 级抽卡。 - 称一个 \(i\) 级抽卡是合法的（非常巧的是，在我国没有保底/井/兑换机制的抽卡游戏确实是违反法律的）当且仅当其中抽出了至少一个 \(i\) 星物品，且构成这个 \(i\) 级抽卡的 \(i-1\) 级抽卡均为合法的。
• 设 \(q\) 为一次 \(n\) 级抽卡是合法的的概率，\(p_i\) 为一次合法的 \(n\) 级抽卡中抽出 \(i\) 星物品的期望个数，对于 \(i\in[0,m]\)，求出 \(p_i\cdot q\)。
• \(1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000\)，答案对 \(998244353\) 取模。

题解

感觉没什么思路，不如我们先想想怎么求合法的概率。

容易想到 DP，设 \(f_{i,j}\) 表示合法的 \(i\) 级抽卡中抽出的物品最大不超过 \(j\) 星的方案数，转移就是一个简单容斥，随便搞一搞就行了。

然后怎么求抽出每个物品的期望呢？考虑求出 \(i\) 星物品的 \(0\) 级抽卡有多大概率成为一个合法 \(n\) 级抽卡的组成部分，不妨设这个概率为 \(g_{0,i}\)，于是答案就是 \(p_i=g_{0,i}\times\frac{a_i}{\sum a}\times \prod b\)。

那么 \(g\) 可以从上往下 DP 求出，转移还是比较简单的，就是考虑这个 \(i\) 级抽卡是不是 \(i+1\) 级抽卡中的最大值计算即可。

复杂度 \(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=4005,inf=0x3f3f3f3f,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,a[N],b[N],f[N][N],g[N][N],sum,inv;
signed main(){
    m=read();n=read();
    forup(i,0,m){
        a[i]=read();
        sum+=a[i];
    }
    inv=ksm(sum,mod-2);
    forup(i,1,n){
        b[i]=read();
    }
    forup(i,0,m){
        f[0][i]=1ll*a[i]*inv%mod;
    }
    forup(i,1,m){
        (f[0][i]+=f[0][i-1])%=mod;
    }
    forup(i,1,n){
        forup(j,i,m){
            f[i][j]=(ksm(f[i-1][j],b[i])-ksm(f[i-1][j-1],b[i])+mod)%mod;
            (f[i][j]+=f[i][j-1])%=mod;
        }
    }
    forup(i,n,m) g[n][i]=1;
    fordown(i,n-1,0){
        int sum=0;
        fordown(j,m,i+1){
            g[i][j]=(sum+1ll*g[i+1][j]*ksm(f[i][j],b[i+1]-1)%mod)%mod;
            (sum+=1ll*g[i+1][j]*(ksm(f[i][j],b[i+1]-1)+mod-ksm(f[i][j-1],b[i+1]-1))%mod)%=mod;
        }
        g[i][i]=sum;
    }
    int mul=1;
    forup(i,1,n) mul=1ll*mul*b[i]%mod;
    forup(i,0,m){
        int ans=1ll*g[0][i]*a[i]%mod*inv%mod*mul%mod;
        printf("%d\n",ans);
    }
}

模拟赛神秘题目 【0907 B组】 D 绳网委托

《》

题意

• 有一个 \(01\) 序列，你可以进行翻转 （相当于 std::reverse）一个区间的操作。
• 对于 \(0\le i\le n\)，求进行恰好 \(i\) 次操作所能得到的最长不下降子序列长度。
• 给出序列的方式是 \(n\) 个二元组 \((0/1,x_i)\)，表示将这个二元组替换为 \(x_i\) 个对应数字。
• \(1\le n\le 2\times 10^5\)

题解

愿天堂没有和题目完全无关的题目背景。

首先一次反转肯定不能把某一段裂开，所以相当于把序列长度缩减到 \(n\)。

考虑如何求答案，容易想到将 \(1\) 替换成 \(-1\)，\(0\) 替换成 \(1\)，答案就是 \(1\) 的个数加上最大的前缀和（即这个前缀的 \(0\) 产生贡献，后面的 \(1\) 产生贡献）。

考虑最优策略肯定是每次把某一段接到最大前缀后面，这样最大前缀和就会变大。

于是考虑这样一个经典的反悔贪心，用线段树维护最大区间和，每次取出最大区间计入答案，然后区间乘 \(-1\)，这样假如以后的区间和这个区间有交就相当于把相交部分反悔。

注意一开始也要把选到的前缀乘 \(-1\)。

复杂度 \(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=2e5+5;
i64 n,v[N];
struct Node{
    i64 l,r,v;
    bool operator<(const Node &p)const{return v<p.v;}
    bool operator>(const Node &p)const{return v>p.v;}
    Node operator+(const Node &p){
        if(l==0) return p;
        if(p.l==0) return *this;
        return Node{min(l,p.l),max(r,p.r),v+p.v};
    }
    Node operator-(){
        return Node{l,r,-v};
    }
};
Node min(Node a,Node b){
    if(a<b) return a;
    return b;
}
Node max(Node a,Node b){
    if(a>b) return a;
    return b;
}
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    Node mx[N<<2],lmx[N<<2],rmx[N<<2];
    Node mn[N<<2],rmn[N<<2],lmn[N<<2];
    Node sum[N<<2];
    i64 mark[N<<2];
    void PushUp(i64 id){
        sum[id]=sum[id<<1]+sum[id<<1|1];
        mx[id]=max(max(mx[id<<1],mx[id<<1|1]),rmx[id<<1]+lmx[id<<1|1]);
        mn[id]=min(min(mn[id<<1],mn[id<<1|1]),rmn[id<<1]+lmn[id<<1|1]);
        lmn[id]=min(lmn[id<<1],sum[id<<1]+lmn[id<<1|1]);
        lmx[id]=max(lmx[id<<1],sum[id<<1]+lmx[id<<1|1]);
        rmn[id]=min(rmn[id<<1|1],rmn[id<<1]+sum[id<<1|1]);
        rmx[id]=max(rmx[id<<1|1],rmx[id<<1]+sum[id<<1|1]);
    }
    void modi(i64 id){
        mark[id]^=1;
        swap(mx[id],mn[id]);
        swap(lmx[id],lmn[id]);
        swap(rmx[id],rmn[id]);
        mx[id]=-mx[id];mn[id]=-mn[id];
        lmx[id]=-lmx[id];lmn[id]=-lmn[id];
        rmx[id]=-rmx[id];rmn[id]=-rmn[id];
        sum[id]=-sum[id];
    }
    void PushDown(i64 id){
        modi(id<<1);modi(id<<1|1);
        mark[id]=0;
    }
    void Build(i64 l=1,i64 r=n,i64 id=1){
        mark[id]=0;
        if(l==r){
            mx[id]=lmx[id]=rmx[id]=v[l]>0?Node{l,r,v[l]}:Node{0,0,0};
            mn[id]=lmn[id]=rmn[id]=v[l]<0?Node{l,r,v[l]}:Node{0,0,0};
            sum[id]=Node{l,r,v[l]};
            return;
        }
        Build(lson);Build(rson);
        PushUp(id);
    }
    void Update(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
        if(L>R) return;
        if(L<=l&&r<=R){
            modi(id);
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,lson);
        if(mid< R) Update(L,R,rson);
        PushUp(id);
    }
    Node Query(){
        return mx[1];
    }
};
SegTree mt;
i64 mx=0,val=0,sum=0,p=0;
signed main(){
    n=read();
    forup(i,1,n){
        i64 c=read();
        v[i]=read();
        if(c) v[i]*=-1,val-=v[i];
        sum+=v[i];
        if(sum>mx){
            mx=sum;
            p=i;
        }
    }
    mt.Build();
    mt.Update(1,p);
    val+=mx;
    printf("%lld\n",val);
    forup(i,1,n){
        Node res=mt.Query();
        if(res.v>0){
            val+=res.v;
            mt.Update(res.l,res.r);
        }
        printf("%lld\n",val);
    }
}

P3734 [HAOI2017] 方案数

传送门

题意

• 对于两非负整数 \(x,y\)，我们用 \(x\subseteq y\) 表示 \(x\And y=x\)，其中 \(\And\) 代表按位与。
• 有一个三维坐标系，你最初在 \((0,0,0)\)，每次可以选择一维，设这一维当前的值为 \(a\)，可以一步走到任何 \(a'\ne a\) 满足 \(a\subseteq a'\)。
• 坐标中有 \(n\) 个障碍物，你不能在这些点逗留，求从 \((0,0,0)\) 到 \((X,Y,Z)\) 的方案数。
• \(1\le X,Y,Z\le 10^{18},1\le n\le 10^4\)，保证所有坐标都小于等于对应维度的终点，障碍物坐标互不相同，且起点和终点不是障碍物，答案对 \(998244353\) 取模。

题解

难点在于勇敢地对 \(10^4\) 写 \(O(n^2)\) 做法，但是全机房几乎没有一发过的。

首先没有障碍物怎么做呢？注意到每走一步相当于把某维坐标中的若干个 \(0\) 改成 \(1\)。那么容易发现方案数只和每一维（起点和终点的差中） \(1\) 的个数有关。于是设 \(f_{i,j,k}\) 表示三维 \(1\) 的个数分别是 \(i,j,k\) 的方案数，可以简单转移，乘个组合数即可，复杂度 \(O(\log^4 V)\)，其中 \(V\) 是值域。

然后就是经典容斥了，设 \(dp_i\) 表示不经过其它障碍走到 \(i\) 障碍的方案数，这个很经典就不多赘述了，复杂度 \(O(n^2)\)，注意转移顺序，考虑升序排列即可。

fun fact：__builtin_popcountll 是 \(O(1)\) 的。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--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=1e4+5,mod=998244353;
i64 X,Y,Z,n;
i64 f[70][70][70],binom[70][70],dp[N];
struct Node{
    i64 x,y,z;
}p[N];
i64 calc(Node a,Node b){
    if(((a.x&b.x)!=a.x)||((a.y&b.y)!=a.y)||((a.z&b.z)!=a.z)) return 0;
    int px=__builtin_popcountll(b.x^a.x),py=__builtin_popcountll(b.y^a.y),pz=__builtin_popcountll(b.z^a.z);
    return f[px][py][pz];
}
signed main(){
    X=read();Y=read();Z=read();
    n=read();
    forup(i,1,n){
        p[i].x=read();p[i].y=read();p[i].z=read();
    }
    ++n;
    p[n].x=X;p[n].y=Y;p[n].z=Z;
    forup(i,0,60){
        binom[i][0]=1;
        forup(j,1,i){
            binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%mod;
        }
    }
    f[0][0][0]=1;
    forup(i,0,60){
        forup(j,0,60){
            forup(k,0,60){
                if(!i&&!j&&!k) continue;
                forup(p,0,60){
                    if(p<i) (f[i][j][k]+=f[p][j][k]*binom[i][p]%mod)%=mod;
                    if(p<j) (f[i][j][k]+=f[i][p][k]*binom[j][p]%mod)%=mod;
                    if(p<k) (f[i][j][k]+=f[i][j][p]*binom[k][p]%mod)%=mod;
                }
            }
        }
    }
    sort(p+1,p+n+1,[&](Node a,Node b){
        if(a.x!=b.x) return a.x<b.x;
        if(a.y!=b.y) return a.y<b.y;
        return a.z<b.z;
    });
    forup(i,1,n){
        dp[i]=calc(Node{0,0,0},p[i]);
        forup(j,1,i-1){
            dp[i]=(dp[i]+mod-dp[j]*calc(p[j],p[i])%mod)%mod;
        }
    }
    printf("%lld\n",dp[n]);
}

P4302 [SCOI2003] 字符串折叠

传送门

题意

• 定义字符串的折叠 x(S) 表示 \(x\) 个 \(S\) 字符顺次连接。特别地，当 \(x=1\) 时，数字 \(x\) 和括号可以省略。
• 给定字符串 \(T\)，求最短折叠的长度（比如 abbbbabbbb 的最短折叠是 2(a4(b))，长度为 \(8\)）。
• \(|T|\le 100\)。

题解

一眼 DP，容易想到区间 DP，设 \(f_{l,r}\) 表示区间 \([l,r]\) 的最短折叠。

转移可以把两段拼接起来或者将整个区间折叠起来，将整个区间折叠起来可以暴力枚举因数再 \(O(len)\) 暴力 check，总复杂度 \(O(n^3\tau(n))\)，其中 \(\tau\) 是约数个数函数，大约是 \(O(\sqrt{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=105,inf=0x3f3f3f3f;
int n;
char str[N];
int getlen(int x){
    int p=0;
    while(x){
        x=x/10;
        ++p;
    }
    return p;
}
bool chk(int len,int l,int r){
    if((r-l+1)%len) return false;
    forup(i,l+len,r){
        if(str[i]!=str[(i-l)%len+l]) return false;
    }
    return true;
}
int dp[N][N];
signed main(){
    scanf(" %s",str+1);
    n=strlen(str+1);
    forup(i,1,n){
        dp[i][i]=1;
    }
    forup(len,2,n){
        forup(l,1,n-len+1){
            int r=l+len-1;
            dp[l][r]=(r-l+1);
            forup(k,l,r-1){
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
            forup(k,1,r-l+1){
                if(chk(k,l,r)){
                    dp[l][r]=min(dp[l][r],dp[l][l+k-1]+2+getlen((r-l+1)/k));
                }
            }
        }
    }
    printf("%d\n",dp[1][n]);
}

UniversalOJ #884 509 号迷宫

传送门

唉，跳蚤题。

题意

• 有一张 \((n+1)\times (n+1)\) 的网格图（下标范围 \([0,n]\)），上面除了第 \(0\) 行外每一行都有一个障碍不能经过。
• 求从 \((0,0)\) 到 \((n,n)\) 的路径数，答案对 \(509\) 取模，且保证 \(n\) 是 \(509\) 的倍数（除去样例一），保证起点和终点不是障碍物。
• \(1\le n\le 509\times 500\)。

题解

跳蚤题，太神秘，不看题解做不起。

令 \(p=509\)。

首先不考虑障碍是经典中的经典，答案是 \(\binom{n+m-2}{n-1}\)。

注意到一个组合数的性质，若 \(n \ge p\)，则 \(\binom{n}{m}\bmod p\) 只在 \(m=0,m=n\) 时取 \(1\)，其余均为 \(0\)。感觉这个结论在这道题看起来非常有用的样子。

然后 看一眼题解 就能想到对 \(x+y\) 设状态，设 \(dp_{i,x}\) 表示从起点到点 \((x,i\times p-x)\) 的路径数。即每隔 \(P\) 条斜杠拿一条出来当成关键点进行 DP，因为 \(n\) 是 \(p\) 的倍数所以必然是关键点。于是有转移 \(dp_{i+1,x}\gets dp_{i,x},dp_{i+1,x+p}\gets dp_{i,x}\)，状态数 \(O(\frac{n^2}{p})\)

然后考虑两条斜杠之间的障碍，这个直接暴力是 \(O(n^2)\) 的，注意到对于每个障碍只有一小部分（大致是一个三角形，但是直接搞成矩形也没啥影响）点能转移到它（其它因为上面的结论只会产生 \(0\) 的贡献），因为每一行至多有一个障碍，而一条斜线在每一行也只有 \(1\) 个点。所以只需要遍历这些点就行了。然后障碍往后转移到下一条斜线的关键点也是同理。复杂度 \(O(np)\)。

于是总复杂度 \(O(\frac{n^2}{p}+np)\)。

参考代码

#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=260000,P=520,inf=0x3f3f3f3f,p=509;
int n,binom[P<<1][P<<1],dp[P<<1][N],f[N],a[N];
signed main(){
    n=read();
    forup(i,1,n){
        a[i]=read();
    }
    forup(i,0,p*2){
        binom[i][0]=1;
        forup(j,1,i){
            binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%p;
        }
    }
    dp[0][0]=1;
    forup(t,0,2*n/p-1){
        forup(j,0,n){
            if(!dp[t][j]) continue;
            int k=(t+1)*p;
            if(0<=k-j&&k-j<=n) (dp[t+1][j]+=dp[t][j])%=p;
            if(j+p<=n&&0<=k-j-p&&k-j-p<=n) (dp[t+1][j+p]+=dp[t][j])%=p;
        }
        mem(f,0);
        forup(i,1,n){
            if(t*p<=i+a[i]&&i+a[i]<=(t+1)*p){
                forup(x,i-p,i){
                    if(x<0) continue;
                    int y=t*p-x;
                    if(0<=y&&y<=a[i]){
                        f[i]+=dp[t][x]*binom[i-x+a[i]-y][i-x]%p;
                    }
                    if(x<i&&f[x]&&a[x]<=a[i]){
                        f[i]=(f[i]+p-f[x]*binom[i-x+a[i]-a[x]][i-x]%p)%p;
                    }
                }
                forup(x,i,i+p){
                    if(x>n) continue;
                    int y=(t+1)*p-x;
                    if(y<a[i]||y>n) continue;
                    dp[t+1][x]=(dp[t+1][x]+p-f[i]*binom[x-i+y-a[i]][x-i]%p)%p;
                }
            }
        }
    }
    printf("%d\n",dp[2*n/p][n]);
}

CF1572C Paint

传送门

题意

• 有一个长度为 \(n\) 的序列，上面每个点有颜色 \(a_i\)。你每次可以选择一段极长连续同色段变成另一种颜色。
• 求把整个序列变成同一种颜色至少需要操作多少次。
• 带多测，\(1\le \sum n\le 3000,1\le a_i\le n\)，每种颜色至多出现 \(20\) 次。

题解

首先答案有一个显然的上界：\(n-1\)，把颜色挨个变成某一种即可。考虑怎么让这个答案变小。

容易发现假如 \(a_l=a_r\)，那么在将 \([l+1,r-1]\) 全部变为 \(a_l\) 后，只需要一次操作就可以将这两个颜色同时改变，那么我们就要最大化这个的数量。容易想到区间 DP。

设 \(f_{l,r}\) 表示将 \([l,r]\) 变为同色最多能减少多少次操作，首先假如最后一次减少和 \(l\) 无关则有转移 \(f_{l,r}\gets f_{l+1,r}\)，否则枚举最后一次减少和 \(l\) 配对的点 \(k\)，那么 \(f_{l,r}\gets f_{l+1,k-1}+1+f_{k,r}\)（注意 \(a_l=a_k\)），为什么是从 \(f_{k,r}\) 转移过来呢？容易发现 \(l,k\) 的减少可能和 \(k,r\) 的减少同时进行，于是从 \(f_{k,r}\) 而非 \(f_{k+1,r}\) 转移过来就不会算漏这种情况了。

复杂度 \(O(n^2)\)，显然你只需要枚举和 \(l\) 同色的 \(k\)，所以每次转移至多枚举 \(20\) 个。

参考代码

#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=3005,inf=0x3f3f3f3f;
int n,a[N],dp[N][N];
vector<int> pos[N];
void solve(){
    n=read();
    forup(i,1,n){
        a[i]=read();
        pos[i].clear();
    }
    forup(i,1,n){
        pos[a[i]].push_back(i);
    }
    forup(len,2,n){
        forup(l,1,n-len+1){
            int r=l+len-1;
            dp[l][r]=dp[l+1][r];
            for(auto p:pos[a[l]]){
                if(p<=l||p>r) continue;
                dp[l][r]=max(dp[l][r],dp[l+1][p-1]+1+dp[p][r]);
            }
        }
    }
    printf("%d\n",n-1-dp[1][n]);
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

P3736 [HAOI2016] 字符合并

传送门

题意

• 给定一长度为 \(n\) 的 \(01\) 序列，每次你可以选择长度恰好为 \(k\) 的一段，替换为某个指定字符（\(0\) 或 \(1\)）并产生一定贡献。具体替换成什么和产生什么贡献在题目上给定。
• 求最大能获得多少贡献。
• \(1\le n\le 300,1 < k\le 8\)

题解

看着就很区间 DP 吧？很像石子合并。然后因为 \(k\le 8\) 容易想到状压，并且最大贡献肯定是缩到不能缩为止。

具体来说，设 \(f_{l,r,msk}\) 表示区间 \([l,r]\) 得到序列 \(msk\) 能获得的最大贡献，直接做大约是 \(O(n^32^{k-1})\) 的，枚举第一个字符占了多长即可。这个不太能过，怎么优化呢？

容易发现因为能缩必缩，所以长度为 \(len\) 的序列缩出来长度必定为 \(len\bmod (k-1)+1\)，那么其实只需要隔 \(k-1\) 个枚举一个即可，复杂度 \(O(\frac{n^3}{k}2^{k-1})\)，然后就比较好过了。

参考代码

#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=305,inf=1e18;
i64 n,m,to[N],val[N],a[N];
char str[N];
i64 dp[N][N][N];
signed main(){
    n=read();m=read();
    scanf(" %s",str+1);
    forup(i,1,n) a[i]=str[i]-'0';
    forup(i,0,(1<<m)-1){
        to[i]=read();val[i]=read();
    }
    forup(i,1,n){
        forup(j,i,n){
            forup(k,0,(1<<m)-1){
                dp[i][j][k]=-inf;
            }
            if(i==j) dp[i][j][a[i]]=0;
        }
    }
    forup(len,2,n){
        forup(l,1,n-len+1){
            i64 r=l+len-1,dd=(r-l-1)%(m-1)+1;
            forup(k,0,(1<<dd)-1){
                dp[l][r][k+(a[l]<<dd)]=dp[l+1][r][k];
            }
            for(i64 k=l;k<r;k+=m-1){
                i64 dd=(r-k-1)%(m-1)+1;
                forup(p,0,(1<<dd)-1){
                    dp[l][r][p+(1<<dd)]=max(dp[l][r][p+(1<<dd)],dp[l][k][1]+dp[k+1][r][p]);
                    dp[l][r][p]=max(dp[l][r][p],dp[l][k][0]+dp[k+1][r][p]);
                }
            }
            if((r-l)%(m-1)==0){
                i64 mx0=-inf,mx1=-inf;
                forup(k,0,(1<<m)-1){
                    if(to[k]){
                        mx1=max(mx1,dp[l][r][k]+val[k]);
                    }else{
                        mx0=max(mx0,dp[l][r][k]+val[k]);
                    }
                    dp[l][r][k]=-inf;
                }
                dp[l][r][0]=mx0;dp[l][r][1]=mx1;
            }
        }
    }
    i64 ans=-inf,dd=(n-1)%(m-1)+1;
    forup(i,0,(1<<dd)-1){
        ans=max(ans,dp[1][n][i]);
    }
    printf("%lld\n",ans);
}

P9907 [COCI 2023/2024 #1] Mostovi

传送门

题意

• 有一张 \(n\) 个点 \(m\) 条边的简单无向连通图，求有多少条边，使得删掉这条边及其两端点后图不连通。
• \(1\le n\le 10^5,1\le m\le 3\times 10^5\)

题意

不算难，但是细节巨多。下文称“删掉这条边及其两端点后图不连通”的边为“合法”

考虑在一棵 dfs 生成树上做，首先考虑树边 \((u,f)\) 是否合法（\(f\) 是 \(u\) 的父亲），容易发现它合法说明从 \(u\) 或者 \(f\) 的某个子树没有指向 \(f\) 的祖先的返祖边，那么不妨对每个子树维护 \(mn_i\) 表示这个子树能通过返祖边到达的点深度最小是多少，那么边 \((u,f)\) 合法当且仅当 \(u\) 和 \(f\) 的子树中 \(mn\) 的最大值大于等于 \(dpt_f\)（注意考虑 \(f\) 的子树）。

然后考虑非树边 \((u,v)\)（\(dpt_v<dpt_u\)，dfs 树上只有返祖边），那么点大致能分为四类：\(v\) 的外子树 \(S_1\)，\(u\) 的外子树减去 \(v\) 的外子树 \(S_2\)，\(u\) 的子树 \(S_3\)，\(v\) 的子树减去 \(u\) 所在的那个。这种时候显然算不合法的会好算一点。

不合法即删掉这两个点仍然连通，那么 \(u,v\) 的每个子树必然都有朝 \(S_1\) 或 \(S_2\) 的连边（这个我用的启发式合并维护），然后 \(S_1\) 还必须和 \(S_2\) 连通，那么有可能 \(S_1,S_2\) 之间本来就有连边，或者 \(u\) 的某个子树同时连向了 \(S_1,S_2\)，维护方法有很多，前者我直接倍增维护，后者我用每个 \(u\) 的子树做了一个区间涂色，总之方法很多。然后我代码写的比较丑，判 \(S_4\) 要和 \(S_1\) 连通的部分写的很屎，没什么参考价值。

复杂度 \(O(n\log^2 n)\)，瓶颈在启发式合并。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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,m,ans,cc[N];
vector<int> e[N],son[N],ntr[N],ntr_[N];;
int vis[N],dpt[N],sz[N],ff[N];
int mn[N],smn[N];
set<int> to[N];
bool flag[N];
void dfs(int x,int fa){
    vis[x]=1;
    dpt[x]=dpt[fa]+1;
    mn[x]=dpt[x];
    smn[x]=inf;
    sz[x]=1;ff[x]=fa;
    for(auto i:e[x]){
        if(i==fa) continue;
        if(vis[i]){
            if(dpt[i]<dpt[x]){
                to[x].insert(dpt[i]);
                ntr[x].push_back(i);
                ntr_[i].push_back(x);
                ++cc[i];
            }
            continue;
        }
        son[x].push_back(i);
        dfs(i,x);
        if(mn[i]<mn[x]){
            smn[x]=mn[x];mn[x]=mn[i];
        }else if(mn[i]<smn[x]){
            smn[x]=mn[i];
        }
        sz[x]+=sz[i];
    }
    if(to[x].size()){
        // msg("(%d %d)|||||\n",x,*to[x].begin());
        int p=*to[x].begin();
        if(p<mn[x]){
            smn[x]=mn[x];mn[x]=p;
        }else if(p<smn[x]){
            smn[x]=p;
        }
    }
}
int f[18][N],gmn[18][N];
void dfs2(int x){
    forup(j,1,17){
        f[j][x]=f[j-1][f[j-1][x]];
        gmn[j][x]=min(gmn[j-1][x],gmn[j-1][f[j-1][x]]);
    }
    for(auto i:son[x]){
        if(mn[i]==mn[x]){
            gmn[0][i]=smn[x];
        }else{
            gmn[0][i]=mn[x];
        }
        f[0][i]=x;
        dfs2(i);
    }
}
int Query(int u,int d){
    int res=inf;
    fordown(i,17,0){
        if(dpt[f[i][u]]>=d){
            res=min(res,gmn[i][u]);
            u=f[i][u];
        }
    }
    return res;
}
struct BIT{
    int c[N];
    void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
    void Update(int L,int R,int k){upd(L,k);upd(R+1,-k);}
    int ask(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
void dfs3(int x){
    set<int> inva;
    flag[x]=false;
    vector<pii> vv;
    for(auto i:son[x]){
        dfs3(i);
        to[i].erase(to[i].lower_bound(dpt[x]),to[i].end());
        if(to[i].empty()&&(x!=1||son[x].size()>1)) flag[x]=true;
        if(to[i].size()==1){
            inva.insert(*to[i].begin());
        }
        if(to[i].size()>1){
            vv.push_back(mkp(*to[i].begin()+1,*prev(to[i].end())-1));
        }
        if(to[x].size()<to[i].size()) swap(to[x],to[i]);
        for(auto j:to[i]) to[x].insert(j);
    }
    for(auto i:vv){
        mt.Update(i.fi,i.se,1);
    }
    if(flag[x]){
        ans+=ntr[x].size()+cc[x];
        msg("E %d (%d)",x,cc[x]);
        for(auto i:ntr[x]){
            --cc[i];
            msg("C %d %d|\n",x,i);
        }
    }else{
        for(auto i:ntr[x]){
            if(flag[i]){continue;}
            if(inva.count(dpt[i])){
                msg("A %d %d|\n",x,i);
                --cc[i];
                ++ans;
                continue;
            }
            if(i==1||dpt[i]>Query(x,dpt[i]+1)) continue;
            if(mt.ask(dpt[i])) continue;
            msg("%d %d|%d|",dpt[i],Query(x,dpt[i]+1),mt.ask(dpt[i]));
            ++ans;
            --cc[i];
            msg("B %d %d|\n",x,i);
        }
    }
    for(auto i:vv){
        mt.Update(i.fi,i.se,-1);
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,m){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    forup(x,2,n){
        int mxn=0;
        for(auto i:son[x]){
            mxn=max(mxn,mn[i]);
        }
        for(auto i:son[ff[x]]){
            if(i==x) continue;
            mxn=max(mxn,mn[i]);
        }
        // msg("[%d %d]\n",x,mxn);
        if(son[x].size()+son[ff[x]].size()-1+(ff[x]!=1)>1&&mxn>=dpt[x]-1){
            ++ans;
            msg("D %d %d|\n",x,ff[x]);
        }
    }
    dfs2(1);
    dfs3(1);
    printf("%d\n",ans);
}

[AGC062B] Split and Insert

传送门

题意

• 有一个 \(n\) 阶排列 \(a_i\)，初始单调上升，你每次可以选择一个数字 \(k\)，然后将末尾 \(k\) 个元素插入前面。形式化的，操作后的序列需要满足 \((a_1,a_2,\dots a_{n-k})\) 和 \((a_{n-k+1},a_{n-k+1},\dots a_n)\) 是新序列的两个子序列。
• 给定一长度为 \(m\) 的数组 \(c_i\)，第 \(i\) 次操作的代价为 \(k\times c_i\)，求能否在 \(m\) 次操作中将 \(a\) 变成一个指定排列 \(p\)，并求出最小代价。
• \(1\le n,m\le 100\)，所有数小于等于 \(10^9\)。

题解

妙妙题。

首先正着做不好搞，考虑倒过来，就是每次选一个子序列扔到序列末尾。

因为每次肯定要操作值域的一个区间，并且显然一个方案中区间要么相离要么包含，于是考虑区间 DP。

具体来说，设 \(dp_{t,l,r}\) 表示在 \([t,k]\) 操作中值域区间 \([l,r]\) 已经排成升序的最小代价。转移和初值是简单的，转移就要么不操作，要么枚举这个区间是由上一次操作后的哪两个区间拼起来得到的，“拼起来”就是把更大的那个扔到序列末尾，代价是好算的。

复杂度 \(O(n^3k)\)

参考代码

#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=105,inf=1e18;
i64 n,m,c[N],a[N],p[N];
i64 dp[N][N][N];
signed main(){
    n=read();m=read();
    forup(i,1,m) c[i]=read();
    forup(i,1,n){
        a[i]=read();
        p[a[i]]=i;
    }
    forup(i,1,n){
        forup(j,1,n){
            forup(k,1,m+1){
                dp[k][i][j]=inf;
            }
        }
    }
    forup(i,1,n){
        forup(j,i,n){
            dp[m+1][i][j]=0;
            if(p[j]>p[j+1]) break;
        }
    }
    forup(len,1,n){
        forup(l,1,n-len+1){
            i64 r=l+len-1;
            fordown(t,m,1){
                dp[t][l][r]=dp[t+1][l][r];
                forup(k,l,r-1){
                    dp[t][l][r]=min(dp[t][l][r],dp[t+1][l][k]+dp[t+1][k+1][r]+c[t]*(r-k));
                }
            }
        }
    }
    if(dp[1][1][n]!=inf){
        printf("%lld\n",dp[1][1][n]);
    }else{
        puts("-1");
    }
}

P4585 [FJOI2015] 火星商店问题

传送门

题意

• 有一些商品，每个商品有一个类型 \(x\)，每个人有一个倾向 \(y\)，我们认为 \(x\oplus y\) 代表这个人对这个商品的喜爱度，这个数越大这个人越喜欢这个商品，其中 \(\oplus\) 表示按位异或。
• 有 \(n\) 个商店，每个商店有一种特产，任何时候都能买，每天某一个商店会进货（即每次进货视为进入下一天）。有一些人会逛商场，具体地，他会进入区间 \([l,r]\) 的所有商场，并且买他最喜欢的物品。并且对于不是特产的物品，他只会买最近 \(d\) 天进货的（即左开右闭区间 \((t-d,t]\)，其中 \(t\) 是当前日期）。
• 输出每一次逛商场的最大喜爱度。
• 所有数都在 \([0,10^5]\) 范围内。

题解

线段树套 Trie 树，Trie 的每个结点维护节点内最后加入的时间，特产视为在无限大时间加入。

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

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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;
int n,m,sp[N];
struct Trie{
    int tr[N*250][2],mx[N*250],cntn;
    void insert(int x,int Tm,int rt){
        int p=rt;
        fordown(i,19,0){
            int c=(x>>i)&1;
            if(!tr[p][c]) tr[p][c]=++cntn;
            p=tr[p][c];
            mx[p]=max(mx[p],Tm);
        }
    }
    int calcXOR(int x,int Tm,int rt){
        int p=rt,res=0;
        fordown(i,19,0){
            int c=(x>>i)&1;
            if(tr[p][!c]&&mx[tr[p][!c]]>=Tm){
                res+=(1<<i);
                p=tr[p][!c];
            }else if(tr[p][c]&&mx[tr[p][c]]>=Tm){
                p=tr[p][c];
            }else{
                return -inf;
            }
        }
        return res;
    }
}tr;
struct SegTree{
    int root[N<<1];
    void Build(){
        forup(i,1,N+n){
            root[i]=++tr.cntn;
        }
    }
    void Update(int P,int X,int Tm){
        for(int i=P+N;i;i>>=1){
            tr.insert(X,Tm,root[i]);
        }
    }
    int Query(int l,int r,int x,int Tm){
        int res=0;
        for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1){
            if(!(l&1)) res=max(res,tr.calcXOR(x,Tm,root[l^1]));
            if(  r&1 ) res=max(res,tr.calcXOR(x,Tm,root[r^1]));
        }
        return res;
    }
}mt;
signed main(){
    n=read();m=read();
    mt.Build();
    forup(i,1,n){
        sp[i]=read();
        mt.Update(i,sp[i],inf);
    }
    int Tm=0;
    forup(i,1,m){
        int op=read();
        if(op==0){
            ++Tm;
            int u=read(),v=read();
            mt.Update(u,v,Tm);
        }else{
            int l=read(),r=read(),x=read(),d=read();
            printf("%d\n",mt.Query(l,r,x,Tm-d+1));
        }
    }
}

CF1521D Nastia Plays with a Tree

传送门

题意

• 有一棵 \(n\) 个点的树，每次操作你要断一条边连一条边，不需要时刻保证这张图是树。
• 求把这棵树变成一条链的最小操作数，并构造方案。
• \(1\le \sum n\le 10^5\)

题解

考虑先把这棵树断成若干条链再依次连接。

容易想到若一个点只有不超过一个儿子就不操作它，否则将其和父亲之间的边断掉，再把多余的儿子断掉。这些边不断必然有一个结点度数大于 \(2\)，断它和父亲的是为了尽可能让父亲的儿子变少。

复杂度 \(O(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,lf[N];
vector<int> e[N];
vector<pii> del;
vector<pii> lk;
void dfs(int x,int fa){
    lf[x]=x;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
        if(!lf[i]) continue;
        if(lf[x]==x){
            lf[x]=lf[i];
        }else if(lf[x]){
            if(fa){
                del.push_back(mkp(x,fa));
            }
            lk.push_back(mkp(lf[x],lf[i]));
            lf[x]=0;
        }else{
            del.push_back(mkp(i,x));
            lk.push_back(mkp(i,lf[i]));
        }
    }
}
void solve(){
    n=read();
    lk.clear();del.clear();
    forup(i,1,n) e[i].clear();
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    if(lf[1]){
        lk.push_back(mkp(1,lf[1]));
    }
    printf("%d\n",(int)del.size());
    int pre=lk.back().fi;
    int sz=del.size();
    forup(i,0,sz-1){
        printf("%d %d %d %d\n",del[i].fi,del[i].se,pre,lk[i].fi);
        pre=lk[i].se;
    }
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

[ARC121E] Directed Tree

传送门

题意

• 给定一棵 \(n\) 个点的树，根为 \(1\)，每条边从父亲指向儿子。
• 求排列 \(p_i\) 的数量，满足不存在 \(p_i\to i\) 且经过至少一条边的路径。
• \(1\le n\le 2000\)

题解

挺有意思的容斥题。

首先题目条件相当于 \(p_i\) 不能是 \(i\) 的祖先，但是祖先不太好做，因为不存在偏序关系，考虑求逆排列 \(p'\)，那么就是 \(p_i'\) 不能是 \(i\) 的后代。

容易想到容斥，具体来说，设 \(dp_{u,i}\) 表示考虑 \(u\) 及其子树，钦定有 \(i\) 个点不合法的方案数，转移就是简单树形背包，还是比较好做的就略过了。

设 \(f_i\) 表示恰好 \(i\) 个点不合法的方案数，\(g_i\) 表示钦定 \(i\) 个点不合法的方案数（即 \(dp_{1,i}\)），容易发现 \(g_i=\sum_{j=i}^n\binom{j}{i}(-1)^{j-i}f_j\)，那么根据二项式反演，答案即为 \(f_0=\sum_{i=0}^n g_i(-1)^i\)。

复杂度 \(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=2005,inf=0x3f3f3f3f,mod=998244353;
int n,dp[N][N],sz[N];
vector<int> son[N];
int fact[N];
void dfs(int x){
    sz[x]=1;
    dp[x][0]=1;
    for(auto i:son[x]){
        dfs(i);
        fordown(j,sz[x],0){
            forup(k,1,sz[i]){
                (dp[x][j+k]+=1ll*dp[x][j]*dp[i][k]%mod)%=mod;
            }
        }
        sz[x]+=sz[i];
    }
    fordown(i,sz[x],1){
        (dp[x][i]+=1ll*dp[x][i-1]*(sz[x]-i)%mod)%=mod;
    }
}
signed main(){
    n=read();
    forup(i,2,n){
        int f=read();
        son[f].push_back(i);
    }
    fact[0]=1;
    forup(i,1,n){
        fact[i]=1ll*fact[i-1]*i%mod;
    }
    dfs(1);
    int res=0;
    forup(i,0,n){
        (res+=1ll*(i&1?mod-1:1)*dp[1][i]%mod*fact[n-i]%mod)%=mod;
    }
    printf("%d\n",res);
}

[ARC121F] Logical Operations on Tree

传送门

题意

• 给定一棵树，求所有给点赋值 \(0/1\)，给边赋逻辑运算 与/或 的 \(2^{2n-1}\) 种方案中，有多少种存在一种缩边顺序（缩边即将两端点按边上的运算得到一个新点）使得最后得到一个权值为 \(1\) 的点。
• \(1\le n\le 10^5\)

题解

这种题肯定先考虑缩边策略，那么显然是先缩其中一种边再缩另一种，考虑应该先缩与还是或。

如果先缩或边，那么充分条件就是所有“或”连通块中都至少有一个 \(1\)。但这个显然就不必要，因为有可能缩起一条与边将两个或连通块并在一起，就删掉了一个没有 \(1\) 的连通块。

如果先缩与边，那么充分条件就是存在一个“与”连通块内部全是 \(1\)。这个就必要了，假设所有与连通块都不是全 \(1\)，那么考虑缩一条或边将两个与连通块并起来，枚举这条或边端点的几种情况即可发现无论如何都不能凑出全 \(1\) 的与连通块。

于是简单树形 DP 即可，注意到“存在一个 \(1\)”是不好算的，不妨算“全都是 \(0\)”的方案，减掉即可。

复杂度 \(O(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,mod=998244353;
int n,dp[N][2];
vector<int> e[N];
void dfs(int x,int fa){
    dp[x][0]=dp[x][1]=1;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
        dp[x][0]=(1ll*dp[x][1]*dp[i][0]%mod+2ll*dp[x][0]*dp[i][0]%mod+1ll*dp[x][0]*dp[i][1]%mod)%mod;
        dp[x][1]=(1ll*dp[x][1]*dp[i][0]%mod+1ll*dp[x][1]*dp[i][1]%mod)%mod;
    }
}
signed main(){
    n=read();
    forup(i,1,n-1){
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    int p2=1;
    forup(i,1,n*2-1){
        p2=2ll*p2%mod;
    }
    printf("%d\n",(p2+mod-dp[1][0])%mod);
}

[ABC135F] Strings of Eternity

传送门

题意

• 给定字符串 \(S,T\)，求出最大的 \(k\)，使得 \(T\) 重复 \(k\) 遍首尾相接能在无限个 \(S\) 首尾相接中匹配，若 \(k\) 取无限大输出 \(-1\)。
• \(|S|,|T|\le 5\times 10^5\)。

题解

首先容易发现若答案不为 \(-1\)，则若 \(S \ge T\)，则 \(T\) 最多在两个 \(S\) 的相连处得到最大的 \(k\)（考虑若连续 \(k\) 个 \(T\) 覆盖了整个 \(S\)，那么要么 \(|S|\) 恰好是 \(|T|\) 的倍数，要么 \(T\) 等于自己的某个前缀加某个后缀，容易发现显然都能无限），若 \(S < T\)，则最多匹配一次（否则显然无限）。

那么无论如何，将 \(\left\lfloor\frac{|T|}{|S|}\right\rfloor+2\) 个 \(S\) 顺次连接得到 \(S'\)，那么让 \(T\) 在 \(S'\) 中匹配即可得到 \(k\)。

于是考虑何时答案为 \(-1\)，容易发现假如在上面的步骤中算出的 \(k\) 满足 \(k\times (|T|+1) \ge |S'|\)，那么答案就是 \(-1\)。

复杂度 \(O(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;
char s[N<<5],t[N];
int nxt[N],dp[N<<5],ans;
signed main(){
    scanf(" %s %s",s,t);
    n=strlen(s);m=strlen(t);
    int p=(m*2/n)+1;
    forup(i,0,n-1){
        forup(j,1,p){
            s[i+j*n]=s[i];
        }
    }
    nxt[0]=0;
    int j=0;
    forup(i,1,m-1){
        while(j>0&&t[i]!=t[j]) j=nxt[j-1];
        if(t[i]==t[j]) ++j;
        nxt[i]=j;
    }
    j=0;
    forup(i,0,n*(p+1)-1){
        while(j>0&&(j==m||s[i]!=t[j])) j=nxt[j-1];
        if(s[i]==t[j]) ++j;
        if(j==m){
            dp[i]=1;
            if(i>=m) dp[i]+=dp[i-m];
            ans=max(ans,dp[i]);
        }
    }
    if((ans+1)*m>=n*(p+1)){
        puts("-1");
    }else{
        printf("%d\n",ans);
    }
}

[ABC136F] Enclosed Points

传送门

题意

• 给定一个平面上的点集 \(S\)，所有点 \((x_i,y_i)\) 均是整点，且保证所有点横坐标互不相同，纵坐标互不相同。
• 定义 \(f(T)\)（其中 \(T\subseteq S\)）表示满足 \(a\le x_i\le b,c\le y_i\le c,(x_i,y_i)\in S\) 的点数，其中 \(a,b,c,d\) 分别是 \(T\) 中 \(x\) 的最小值，最大值，\(y\) 的最小值，最大值。
• 求 \(\sum_{T\subseteq S}f(T)\)。
• \(1\le |S|\le 2\times 10^5\)

题解

远古 abc 水紫，单纯不想写专题才来写的。

考虑计算每个点产生贡献的次数。

显然一个点产生贡献，要么它就在集合 \(T\) 中，要么某个 \(T\) 的矩形将其覆盖了。前者是好算的，总贡献为 \(n\times 2^{n-1}\)，考虑后者。

那么就是要算左上方和右下方均有至少一个点，或者左下方和右上方均有至少一个点，那么先二维数点统计完了再考虑怎么做。注意到剩下两个方向的点可以任意选，但是直接 \(2^k\) 会算重，仔细思考一下发现只有四个方向均有点的情况会被统计两次，那么简单容斥一下减掉即可。

复杂度 \(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,mod=998244353;
int n,p2[N],ld[N],rd[N],lu[N],ru[N],ans;
vector<int> lsh;
struct Node{
    int x,y;
}s[N];
struct BIT{
    int c[N];
    void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
    int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
signed main(){
    n=read();
    p2[0]=1;
    forup(i,1,n){
        p2[i]=2ll*p2[i-1]%mod;
        s[i].x=read();s[i].y=read();
        lsh.push_back(s[i].y);
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    forup(i,1,n){
        s[i].y=lower_bound(lsh.begin(),lsh.end(),s[i].y)-lsh.begin()+1;
    }
    sort(s+1,s+n+1,[&](Node a,Node b){return a.x<b.x;});
    forup(i,1,n){
        ld[i]=mt.sum(s[i].y);lu[i]=i-1-mt.sum(s[i].y);
        mt.upd(s[i].y,1);
    }
    mem(mt.c,0);
    fordown(i,n,1){
        rd[i]=mt.sum(s[i].y);ru[i]=n-i-mt.sum(s[i].y);
        mt.upd(s[i].y,1);
    }
    ans=1ll*n*p2[n-1]%mod;
    forup(i,1,n){
        (ans+=(1ll*(p2[ld[i]]-1)*(p2[ru[i]]-1)%mod*(p2[lu[i]+rd[i]])%mod
             +1ll*(p2[rd[i]]-1)*(p2[lu[i]]-1)%mod*(p2[ru[i]+ld[i]])%mod
             -1ll*(p2[rd[i]]-1)*(p2[lu[i]]-1)%mod*(p2[ru[i]]-1)%mod*(p2[ld[i]]-1)%mod)%mod)%=mod;
        (ans+=mod)%=mod;
    }
    printf("%d\n",ans);
}

P3991 [BJOI2017] 喷式水战改

传送门

题意

• 有一架战斗机，战斗机有三种模式 \(A,B,C\)，三种模式消耗同一种燃料的效率不同，具体来说，每种燃料有三个参数 \(a_i,b_i,c_i\)，表示三种模式消耗一单位燃料的飞行距离。要求一次任务中途的模式依次是 \(A,B,C,A\)，四段均可以为空（即你不能进行形如先搞一段 \(C\) 再搞一段 \(B\) 之类的操作）。
• 有 \(n\) 次添加燃料操作，你可以将燃料舱假想为一个序列，第 \(i\) 次会在第 \(p_i\) 单位燃料后插入 \(x_i\) 单位燃料 \((a_i,b_i,c_i)\)。
• 每次添加操作后求最远飞行距离相比上一次添加增加了多少。

题解

哎哟出题人不会出题只能在码长上恶心人了，最后还让不认真读题的人怀疑自己是不是写错了，差评。

平衡树直接维护，完了。

注意插入时可能需要裂开某个点，这就能体现 FHQ 的优点了，可以非常自然地实现这个东西。

我不知道带旋 Treap 和 Splay 怎么做。

居然是洛谷非匿名最优解。

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

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--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;
struct Trible{
    i64 a,b,c,num;
};
struct Sum{
    i64 a,b,c,num;
    i64 ab,bc,ca;
    i64 abc,bca;
    i64 abca;
    Sum operator+(const Sum &r)const{
        Sum res;
        res.a=a+r.a;
        res.b=b+r.b;
        res.c=c+r.c;
        res.ab=max({ab+r.b,a+r.b,a+r.ab});
        res.bc=max({bc+r.c,b+r.c,b+r.bc});
        res.ca=max({ca+r.a,c+r.a,c+r.ca});
        res.abc=max({abc+r.c,ab+r.c,ab+r.bc,a+r.bc,a+r.abc});
        res.bca=max({bca+r.a,bc+r.a,bc+r.ca,b+r.ca,b+r.bca});
        res.abca=max({abca+r.a,abc+r.a,abc+r.ca,ab+r.ca,ab+r.bca,a+r.bca,a+r.abca});
        return res;
    }
    void operator=(const Trible &r){
        num=r.num;
        a=r.a*num;b=r.b*num,c=r.c*num;
        ab=max(a,b);bc=max(b,c);ca=max(c,a);
        abc=max({a,b,c});bca=max({b,c,a});
        abca=max({a,b,c});
    }
};
mt19937 mr(20071221);
struct Treap{
    i64 sz[N*2],cnt[N*2],ls[N*2],rs[N*2],hv[N*2],cntn,root;
    Trible tv[N*2];
    Sum ss[N*2];
    i64 New(i64 a,i64 b,i64 c,i64 num){
        i64 nw=++cntn;
        sz[nw]=cnt[nw]=num;
        ls[nw]=rs[nw]=0;
        hv[nw]=mr();
        tv[nw]=Trible{a,b,c,num};
        ss[nw]=tv[nw];
        return nw;
    }
    void PushUp(i64 id){
        sz[id]=sz[ls[id]]+cnt[id]+sz[rs[id]];
        ss[id]=tv[id];
        ss[id]=ss[ls[id]]+ss[id];
        ss[id]=ss[id]+ss[rs[id]];
    }
    void Split(i64 id,i64 key,i64 &x,i64 &y){
        if(!id){
            x=y=0;
            return;
        }
        if(sz[ls[id]]>=key){
            y=id;
            Split(ls[id],key,x,ls[y]);
            PushUp(id);
        }else if(sz[ls[id]]+cnt[id]>key){
            key-=sz[ls[id]];
            i64 at=New(tv[id].a,tv[id].b,tv[id].c,cnt[id]-key);
            rs[at]=rs[id];PushUp(at);
            rs[id]=0;cnt[id]=tv[id].num=key;PushUp(id);
            x=id;y=at;
            return;
        }else{
            x=id;
            Split(rs[id],key-sz[ls[id]]-cnt[id],rs[x],y);
            PushUp(id);
        }
    }
    i64 Merge(i64 x,i64 y){
        if(!x||!y) return x|y;
        if(hv[x]>hv[y]){
            rs[x]=Merge(rs[x],y);
            PushUp(x);
            return x;
        }else{
            ls[y]=Merge(x,ls[y]);
            PushUp(y);
            return y;
        }
    }
    void Insert(i64 key,i64 a,i64 b,i64 c,i64 num){
        i64 x,y;
        Split(root,key,x,y);
        root=Merge(Merge(x,New(a,b,c,num)),y);
    }
    i64 Query(){
        return ss[root].abca;
    }
}mt;
signed main(){
    n=read();
    i64 pre=0;
    forup(i,1,n){
        i64 p=read(),a=read(),b=read(),c=read(),num=read();
        mt.Insert(p,a,b,c,num);
        i64 nw=mt.Query();
        printf("%lld\n",nw-pre);
        pre=nw;
    }
}

P2473 [SCOI2008] 奖励关

传送门

题意

• 有 \(n\) 种物品，第 \(i\) 中物品只有在拿完集合 \(S_i\) 后才能拿，每拿一个第 \(i\) 种物品会获得 \(p_i\) 的分数。
• 现在会 \(m\) 次给你一个物品，每次给的物品在 \(n\) 个中均匀随机，你可以选择拿或者不拿。
• 求最优策略下的期望分数。
• \(1\le m\le 100,1\le n\le 15,-10^6\le p_i\le 10^6\)

题解

一看就是状压 DP。但是这个期望 DP 正着做很复杂，考虑能不能倒着做。

具体来说，设 \(f_{i,msk}\) 表示拿完 \(msk\) 中的物品后，\([i,k]\) 次选择物品能获得的期望分数。转移就枚举这次给你哪个物品，然后在是否选择这个物品的两个后继状态中取 \(\max\) 转移即可。因为求的是期望所以还要除以 \(n\)。

复杂度 \(O(m2^nn)\)。

参考代码

#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 db=double;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=20,inf=0x3f3f3f3f;
int m,n;
int pre[N],val[N];
db dp[105][1<<15];
signed main(){
    m=read();n=read();
    forup(i,1,n){
        val[i]=read();
        while(1){
            int u=read();
            if(u==0) break;
            pre[i]|=(1<<(u-1));
        }
    }
    fordown(i,m,1){
        forup(j,0,(1<<n)-1){
            forup(k,1,n){
                db nw=dp[i+1][j];
                if((j&pre[k])==pre[k]){
                    nw=max(nw,dp[i+1][j|(1<<(k-1))]+val[k]);
                }
                dp[i][j]+=nw;
            }
            dp[i][j]=dp[i][j]/n;
        }
    }
    printf("%.6lf\n",dp[1][0]);
}

P5492 [PKUWC2018] 随机算法

传送门

题意

• 对于一张 \(n\) 个点 \(m\) 条边的简单无向图，考虑以下的最大独立集算法： - 将 \(n\) 个点均匀随机排列（认为所有 \(n!\) 种排列的出现概率是相等的）得到一个排列 \(p_i\)。 - 维护一个集合 \(S\)，最初为空集，从 \(p_1\) 开始遍历排列，假如 \(p_i\) 和 \(S\) 中所有点都没有连边则加入 \(S\)。
• 对于给定的图，求这个算法的正确率。我们认为这个算法正确当且仅当求出的 \(|S|\) 等于最大独立集大小。
• \(1\le n\le 20,0\le m\le \binom{n}{2}\)。

题解

容易想到对能求出正解的排列计数来算概率。一眼能看出 \(O(3^nn)\) 的状压 DP，就是设 \(f_{msk}\) 表示得到状态 \(msk\) 的方案数，其中 \(msk\) 是一个三进制数，每一位表示每个点的三种状态，转移枚举下一个点即可。最终统计答案只需遍历所有状态找到独立集最大的全部加起来。

仔细想想为什么要 \(3^n\)，因为每个点有三个状态：已经被遍历过了并且在 \(S\) 中，已经被遍历过并且不在 \(S\) 中，还没被遍历过。这个非常不好优化，因为转移时需要确定每个点的状态才能知道新点是否加入 \(S\) 集合。

考虑能不能将一些东西捆绑在一起转移，因为我们统计答案时只关注独立集的大小，不难想到对没被遍历过的点做文章，将点分为三种：已经被遍历过（第一类），和 \(S\) 有边并且没被遍历过（第二类），和 \(S\) 没有边并且没被遍历过（第三类）。

这样有什么用呢？容易发现此时我们加入一个第二类的点时并不关心这个点具体是什么，因为它不会加入集合 \(S\)，在序列中可以任意排列不产生影响，所以我们只需要记录它的数量就可以转移了！这就做到了我们期望的“捆绑在一起转移”。

于是设 \(f_{msk,i}\) 表示一二类点的并集为 \(msk\)，其中有 \(i\) 个二类点的最大独立集大小，\(g_{msk,i}\) 表示能得到这个状态的排列数，转移要么消耗一个三类点，要么消耗一个二类点，具体见代码。

初始状态是 \(f_{0,0}=0,g_{0,0}=1\)，最后合法的排列数就是 \(g_{n,0}\)。

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

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=25,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;
int grp[N],f[1<<20][N],g[1<<20][N];
signed main(){
    n=read();m=read();
    forup(i,0,n-1) grp[i]|=1<<i;
    forup(i,1,m){
        int u=read()-1,v=read()-1;//下标从 0 开始方便状态压缩。
        grp[u]|=(1<<v);
        grp[v]|=(1<<u);
    }
    f[0][0]=0;g[0][0]=1;
    forup(msk,0,(1<<n)-1){
        fordown(i,__builtin_popcount(msk),0){
            if(!g[msk][i]) continue;
            if(i){//消耗一个二类点，只影响 i。
                if(f[msk][i]>f[msk][i-1]){
                    f[msk][i-1]=f[msk][i];
                    g[msk][i-1]=1ll*g[msk][i]*i%mod;//注意有 i 种选法。
                }else if(f[msk][i]==f[msk][i-1]){
                    (g[msk][i-1]+=1ll*g[msk][i]*i%mod)%=mod;
                }
            }
            forup(j,0,n-1){//消耗一个三类点，更新 msk 和 i。
                if(msk&(1<<j)) continue;
                int nxt=msk|grp[j],ni=i+__builtin_popcount(nxt^msk)-1;
                if(f[msk][i]+1>f[nxt][ni]){
                    f[nxt][ni]=f[msk][i]+1;
                    g[nxt][ni]=g[msk][i];
                }else if(f[msk][i]+1==f[nxt][ni]){
                    (g[nxt][ni]+=g[msk][i])%=mod;
                }
            }
        }
    }
    int ff=1;
    forup(i,1,n) ff=1ll*ff*i%mod;//计算排列总数，即阶乘，答案记得除以阶乘。
    printf("%lld\n",1ll*g[(1<<n)-1][0]*ksm(ff,mod-2)%mod);
}

CF827D Best Edge Weight

传送门

题意

• 给定一张 \(n\) 个点 \(m\) 条边的简单连通无向图，边有边权。
• 对于每条边，求出在其它边权不变的情况下，它的边权最大变为多少能使得它在所有最小生成树中。
• \(1\le n\le 2\times 10^5\)，边权在 \([1,10^9]\) 区间内。

题解

简单题，但是想复杂了。

容易发现一条边在最小生成树中当且仅当它在任意一个环中都不是最大值，即小于它所在的所有环中最大值的最小值。

考虑一些最小生成树的性质，容易发现对于一条非树边，这个“最大值的最小值”就是它在最小生成树上围出的环中的最大值（除去它），对于一条树边，这个“最大值的最小值”就是所有围住它的树边的最小值。

于是随便维护一下即可，最优应该能做到 \(O(n\log n)\)，但是我写的 \(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=2e5+5,inf=0x3f3f3f3f;
int n,m,ans[N];
struct edge{
    int u,v,w,pos;
}s[N];
vector<int> sv;
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
vector<pii> e[N];
int f[N][18],g[N][18],dpt[N];
void dfs(int x,int fa){
    f[x][0]=fa;
    dpt[x]=dpt[fa]+1;
    forup(i,1,17){
        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=s[i.se].w;
        if(v==fa) continue;
        g[v][0]=w;
        dfs(v,x);
    }
}
pii lca(int u,int v){
    int res=0;
    if(dpt[u]>dpt[v]) swap(u,v);
    fordown(i,17,0){
        if(dpt[f[v][i]]>=dpt[u]){
            res=max(res,g[v][i]);
            v=f[v][i];
        }
    }
    if(u==v) return mkp(u,res);
    fordown(i,17,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 mkp(f[u][0],res);
}
vector<int> add[N],del[N];
multiset<int> ss[N];
void dfs2(int x,int fa){
    for(auto i:e[x]){
        int v=i.fi,p=i.se;
        if(v==fa) continue;
        dfs2(v,x);
        if(ss[v].size()){
            ans[s[p].pos]=*ss[v].begin()-1;
        }else{
            ans[s[p].pos]=-1;
        }
        if(ss[x].size()<ss[v].size()){
            swap(ss[x],ss[v]);
        }
        for(auto i:ss[v]) ss[x].insert(i);
    }
    for(auto i:add[x]) ss[x].insert(i);
    for(auto i:del[x]){
        ss[x].erase(ss[x].find(i));
        ss[x].erase(ss[x].find(i));
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,n){
        fa[i]=i;
    }
    forup(i,1,m){
        s[i].u=read(),s[i].v=read(),s[i].w=read();s[i].pos=i;
    }
    sort(s+1,s+m+1,[&](edge a,edge b){return a.w<b.w;});
    forup(i,1,m){
        int u=getfa(s[i].u),v=getfa(s[i].v);
        if(u==v){
            sv.push_back(i);
            continue;
        }
        fa[u]=v;
        e[s[i].u].push_back(mkp(s[i].v,i));
        e[s[i].v].push_back(mkp(s[i].u,i));
    }
    dfs(1,0);
    for(auto i:sv){
        int u=s[i].u,v=s[i].v;
        pii rr=lca(u,v);
        ans[s[i].pos]=rr.se-1;
        add[u].push_back(s[i].w);add[v].push_back(s[i].w);
        del[rr.fi].push_back(s[i].w);
    }
    dfs2(1,0);
    forup(i,1,m){
        printf("%d ",ans[i]);
    }
}

模拟赛神秘题目 【0914 B组】A 神灵庙

《》

题意

• 你需要构造一棵 \(n\) 个叶子的二叉树，每个结点与左儿子的连边长为 \(1\)，与右儿子为 \(2\)，你还要将 \(n\) 个权值 \(a_i\) 分配给叶子，最小化 \(\sum a_i\times dep_i\)，其中 \(dep_i\) 是结点与树根的距离。
• \(1\le n\le 750,1\le a_i\le 10^5\)。

题解

神秘。赛时只想到指数做法数组还开小了。

首先一个显然的性质是越小的数会放进深度越大的叶子。

考虑每个非叶子都会提供一个深度 \(+1\) 和一个深度 \(+2\) 的结点，于是不妨把这两层都放进状态。设 \(f_{i,m,j,k}\)，表示放完了前 \(i\) 大的数，第 \(m\) 层还有 \(j\) 个没用过（即将来会变成非叶子或者放入一个 \(a_i\)）的结点，第 \(m+1\) 层有 \(j\) 个连向 \(m-1\) 层的结点的最小代价，然后转移有两个 \(f_{i,m,j,k}+a_i\times m\to f_{i+1,m,j-1,k}\) 和 \(f_{i,m,j,k}\to f_{i,m+1,j+k,j}\)。

怎么优化呢？我们可以拆贡献，容易发现每往后一层，每个没用过的数都会增加 \(a_i\) 的贡献，于是可以不记 \(m\)，转移变成 \(f_{i,j,k}\to f_{i+1,j-1,k}\) 和 \(f_{i,j,k}+s_{n-i}\to f_{i,j+k,j}\)，其中 \(s_i\) 表示前 \(i\) 小数的和。

复杂度 \(O(n^3)\)，需要滚动数组优化空间。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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=755,inf=0x3f3f3f3f;
int n,a[N],ans,sum[N];
int dp[2][N][N];
signed main(){
    n=read();
    forup(i,1,n){
        a[i]=read();
    }
    sort(a+1,a+n+1);
    forup(i,1,n){
        sum[i]=sum[i-1]+a[i];
    }
    mem(dp[0],0x3f);
    ans=inf;
    dp[0][1][0]=0;
    forup(k,0,n){
        int p=k&1,q=p^1;
        mem(dp[q],0x3f);
        forup(i,0,n){
            forup(j,0,n){
                if(dp[p][i][j]==inf) continue;
                if(k<n&&i) dp[q][i-1][j]=min(dp[q][i-1][j],dp[p][i][j]);
                if(i+j<=n) dp[p][i+j][i]=min(dp[p][i+j][i],dp[p][i][j]+sum[n-k]);
            }
        }
    }
    printf("%d\n",dp[n&1][0][0]);
}

P7606 [THUPC2021] 混乱邪恶

传送门

真就混乱邪恶啊。

题意

• 有两个坐标系，你有 \(n\) 次选择的机会，每次可以在六个方向中选择一个，选择一个可以让你在第一个坐标系中走一个特定方向（自己去看题面），并且每次给出这次会让你在第二个坐标系中走的方向，在第二个坐标系中行走对 \(p\) 取模。
• 初始两个坐标系均在 \((0,0)\)，求 \(n\) 步后能不能在恰好第一个坐标系回到原点时在第二个坐标系到达指定位置。
• \(1\le n,p\le 100\)。

题解

逆天题目。

容易想到一个 \(O(\frac{n^3p^2}{\omega})\) 的做法。

注意到在二维平面上每次选一个方向随机游走 \(n\) 次后与原点的期望切比雪夫距离为 \(O(\sqrt{n})\)。

于是第一个坐标系就能压成 \(O(\sqrt{n})\times O(\sqrt{n})\) 的。

于是复杂度变成 \(O(\frac{n^2p^2}{\omega})\)。

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

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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,mod,L,G;
int nxt[6][2]={{-1,2},{-2,0},{-1,-2},{1,-2},{2,0},{1,2}};
bitset<N> dp[2][55][55][N],al;
struct Node{
    vector<int> x,y;
}s[N];
mt19937 mr(20071221);
signed main(){
    n=read();mod=read();
    forup(i,0,mod-1){
        al.flip(i);
    }
    forup(i,0,n-1){
        s[i].x.resize(6);s[i].y.resize(6);
        forup(j,0,5){
            s[i].x[j]=read();s[i].y[j]=read();
        }
    }
    shuffle(s,s+n,mr);
    dp[0][25][25][0][0]=1;
    forup(w,0,n-1){
        int p=w&1,q=p^1;
        forup(i,0,50){
            forup(j,0,50){
                forup(k,0,mod-1){
                    dp[q][i][j][k].reset();
                }
            }
        }
        forup(i,max(25-n,0),min(25+n,50)){
            forup(j,max(25-n,0),min(25+n,50)){
                forup(k,0,mod-1){
                    if(dp[p][i][j][k].none()) continue;
//                  msg("%d %d %d|\n",i,j,k);
                    forup(l,0,5){
                        int ni=i+nxt[l][0],nj=j+nxt[l][1];
                        if(ni<0||ni>50||nj<0||nj>50) continue;
                        dp[q][ni][nj][(k+s[w].x[l])%mod]=dp[q][ni][nj][(k+s[w].x[l])%mod]|(((dp[p][i][j][k]<<s[w].y[l])|(dp[p][i][j][k]>>(mod-s[w].y[l])))&al);
                    }
                }
            }
        }
    }
    L=read(),G=read();
    if(dp[n&1][25][25][L][G]){
        puts("Chaotic Evil");
    }else{
        puts("Not a true problem setter");
    }
}

///

P10768 「CROI · R2」落月摇情

传送门

题意

• 给定一张 \(n\) 个点的完全图，其中每条边的边权为其两端点的点权 \(a_i\) 之积。
• 求这张图恰有 \(m\) 条边的连通子图边权和最小是多少。
• \(1\le n\le 10^6,n-1\le m\le \min(\binom{n}{2},10^6),|a_i|\le 10^6\)

题解

显然是把最小生成树求出来再加上最短的 \(m-n+1\) 条边，因为假如两个连通块之间不是靠最小生成树边相连那么换成最小生成树的树边必定不劣。

然后一眼 Boruvka，但是仔细想想发现并不需要，容易发现 Brovka 只会做一轮，在这一轮中所有 \(a_i\ge 0\) 的会连向最小值，所有 \(a_i < 0\) 的会连向最大值，随便搞一下就行了。

然后剩下的怎么办呢？可以对每个点存最小的还没用过的出边（可以用 std::unordered_set 维护用过的出边），然后塞进一个优先队列里，每次取出最小的再更新即可，保证时刻优先队列里面只有 \(n\) 条边复杂度就绝对不会错。

复杂度 \(O(n\log n)\)，不知道为什么要卡常。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--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=1e6+5,inf=1e18;
i64 n,m;
i64 a[N],res;
vector<pii> ans;
i64 fa[N];
i64 getfa(i64 x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool merge(i64 u,i64 v){
    u=getfa(u);v=getfa(v);
    if(u==v) return false;
    fa[u]=v;
    return true;
}
vector<pii> ve;
unordered_set<i64> to;
void Insert(i64 u,i64 v){
    if(u>v) swap(u,v);
    to.insert(u*(n+1)+v);
}
bool Exist(i64 u,i64 v){
    if(u>v) swap(u,v);
    return to.count(u*(n+1)+v);
}
i64 pl[N];
priority_queue<pair<i64,i64>,vector<pair<i64,i64>>,greater<pair<i64,i64>>> q;
vector<pii> at;
void work(i64 u){
    if(a[u]>=0){
        while(pl[u]<n&&Exist(u,ve[pl[u]].se)){
            ++pl[u];
        }
        if(pl[u]<n){
            q.push(mkp(a[u]*ve[pl[u]].fi,u));
        }
    }else{
        while(pl[u]>=0&&Exist(u,ve[pl[u]].se)){
            --pl[u];
        }
        if(pl[u]>=0){
            q.push(mkp(a[u]*ve[pl[u]].fi,u));
        }
    }
}
signed main(){
    n=read();m=read();
    if(n==1){
        puts("0");
        return 0;
    }
    i64 mx=0,mn=0;
    forup(i,1,n){
        a[i]=read();
        fa[i]=i;
        ve.push_back(mkp(a[i],i));
        Insert(i,i);
        if(mx==0||a[i]>a[mx]) mx=i;
        if(mn==0||a[i]<a[mn]) mn=i;
    }
    sort(ve.begin(),ve.end());
    i64 cc=0;
    forup(i,1,n){
        if(i==mx||i==mn) continue;
        if(a[i]>=0){
            ans.push_back(mkp(mn,i));
            res+=a[i]*a[mn];
            ++cc;
            Insert(i,mn);
        }else{
            ans.push_back(mkp(mx,i));
            res+=a[i]*a[mx];
            ++cc;
            Insert(i,mx);
        }
    }
    ans.push_back(mkp(mn,mx));
    res+=a[mx]*a[mn];
    ++cc;
    Insert(mx,mn);
    forup(i,1,n){
        if(a[i]>=0){
            pl[i]=0;
        }else{
            pl[i]=n-1;
        }
        work(i);
    }
    for(auto i:at){
        if(cc==m) break;
        i64 u=i.fi,v=i.se;
        msg("[%lld %lld]\n",u,v);
        ans.push_back(i);
        res+=a[u]*a[v];
        ++cc;
    }
    while(cc<m){
        i64 val=q.top().fi,u=q.top().se,v=ve[pl[u]].se;q.pop();
        if(Exist(u,v)){
            work(u);
            continue;
        }
        ans.push_back(mkp(u,v));
        res+=val;
        ++cc;
        Insert(u,v);
        work(u);
    }
    printf("%lld\n",res);
    i64 val=0;
    for(auto i:ans){
        printf("%lld %lld\n",i.fi,i.se);
        val+=a[i.fi]*a[i.se];
    }
}

模拟赛神秘题目 【0916 B组】C 徽章

题意

• 有一个长度为 \(n\) 的序列，初始全为 \(0\)，再给定 \(n\) 个关键区间。
• 有 \(q\) 次询问，每次给出 \(m\) 个单点 \(+1\) 操作，求进行这些操作后有多少个关键区间的区间和为奇数，询问间独立。
• \(1\le n,q\le 5\times 10^5,1\le \sum m\le n\)

题解

神秘根号分治。

容易想到根号分治，先设一个阈值 \(B\)。

若 \(m > B\)，则直接暴力前缀和维护，复杂度 \(O(\frac{n^2}{B})\)。

若 \(m < B\)，注意到合法的区间就是跨越奇数个黑点的区间，那么可以拆成 \(O(m^2)\) 个二维数点。注意到 \(\sum m^2\le \sum mB\le nB\)，所以查询数是 \(O(nB)\) 的，又因为区间只有 \(n\) 个，所以用一些 \(O(B)-O(1)\) 的数据结构即可维护。

复杂度 \(O(n\sqrt{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,B=720,inf=0x3f3f3f3f;
int n,m,ans[N];
struct range{
    int l,r;
}s[N];
struct query{
    int l,r,val,pos;
};
vector<query> q[N];
int p[N],sum[N];
struct block{
    int L[1000],R[1000],blg[N],cblk[1000],inb[N],t;
    void init(){
        t=n/B;
        forup(i,1,t){
            L[i]=R[i-1]+1;R[i]=i*B;
            forup(j,L[i],R[i]){
                blg[j]=i;
            }
        }
        if(R[t]!=n){
            ++t;
            L[t]=R[t-1]+1;R[t]=n;
            forup(j,L[t],R[t]){
                blg[j]=t;
            }
        }
    }
    void upd(int x,int k){
        int p=blg[x];
        forup(i,x,R[p]){
            inb[i]+=k;
        }
        forup(i,p+1,t){
            cblk[i]+=k;
        }
    }
    int sum(int x){
        return cblk[blg[x]]+inb[x];
    }
}mt;
signed main(){
    n=read();m=read();
    forup(i,1,n){
        s[i].l=read();s[i].r=read();
        q[s[i].l].push_back(query{s[i].r,0,0,0});
    }
    forup(i,1,m){
        int k=read();
        if(k<B){
            forup(i,1,k){
                p[i]=read();
            }
            sort(p+1,p+k+1);
            p[0]=0;p[k+1]=n+1;
            forup(l,1,k){
                for(int j=l;j<=k;j+=2){
                    if(p[l-1]<p[l]&&p[j]<p[j+1]){
                        q[p[l]].push_back(query{p[j],p[j+1]-1,1,i});
                        q[p[l-1]].push_back(query{p[j],p[j+1]-1,-1,i});
                        msg("%d %d %d %d|\n",p[l-1]+1,p[l],p[l],p[l+1]-1);
                    }
                }
            }
        }else{
            forup(i,1,k){
                int p=read();
                ++sum[p];
            }
            forup(i,1,n){
                sum[i]+=sum[i-1];
            }
            int res=0;
            forup(i,1,n){
                if((sum[s[i].r]-sum[s[i].l-1])&1){
                    ++res;
                }
            }
            forup(i,1,n){
                sum[i]=0;
            }
            ans[i]=res;
        }
    }
    mt.init();
    forup(i,1,n){
        for(auto j:q[i]){
            if(!j.pos){
                msg("%d %d||\n",i,j.l);
                mt.upd(j.l,1);
            }else{
                msg("%d %d %d[%d]|%d\n",i,j.l,j.r,j.val*(mt.sum(j.r)-mt.sum(j.l-1)),j.pos);
                ans[j.pos]+=j.val*(mt.sum(j.r)-mt.sum(j.l-1));
            }
        }
    }
    forup(i,1,m){
        printf("%d\n",ans[i]);
    }
}

P6622 [省选联考 2020 A/B 卷] 信号传递

传送门

题意

• 有 \(m\) 个信号站排成一列，其间以某种方式连了 \(n-1\) 条有向边，表示进行 \(n-1\) 次信号传递。
• 一次从 \(p_1\to p_2\)（\(p_1,p_2\) 均为信号站的位置）的信号传递需要一定代价，当 \(p_1\le p_2\)，代价为 \(p_2-p_2\)，当 \(p_1 > p_2\)，代价为 \(k(p_1+p_2)\)，其中 \(k\) 是一给定常数。
• 你可以任意排列信号站，求传递 \(n-1\) 次信号的最小代价。
• \(1\le n\le 10^5,1\le k\le 100,1\le m\le 23\)

题解

还是挺简单的。

考虑拆贡献，即将贡献中属于 \(p_1,p_2\) 的分别分给两个信号站来计算。

容易想到状压 DP，并且又容易发现只要知道了哪些信号站在左边，剩下的都在右边即可算出某信号站的贡献。

于是设 \(f_{msk}\) 表示从前往后依次排列完 \(msk\) 的最小代价，新加一个信号站的代价是可以算的。

但是代价直接应算复杂度不太对的样子，大约是 \(O(2^mm^2)\)，考虑预处理。

预处理具体方法是简单的，每次新加入 \(lowbit\) 即可，但是空间会炸，于是考虑如何解决空间问题，一个方法是将集合砍成两半计算，空间就对了。

复杂度 \(O(m2^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=23,inf=0x3f3f3f3f;
int n,m,pm,t,grp[N+5][N+5];
int s[100005];
int val[2][N+5][1<<14];
int dp[1<<N|5];
int calc(int msk,int p){
    int res=0;
    res+=val[0][p][msk&((1<<pm)-1)];
    res+=val[1][p][msk>>pm];
    return res*(__builtin_popcount(msk)+1);
}
signed main(){
    n=read();m=read();t=read();
    pm=m>>1;
    forup(i,1,n){
        s[i]=read();
        if(i>1){
            ++grp[s[i-1]][s[i]];
        }
    }
    forup(i,1,m){
        forup(k,1,pm){
            if(i!=k) val[0][i][0]+=t*grp[k][i]-grp[i][k];
        }
        forup(j,1,(1<<pm)-1){
            if(i<=pm&&(j&(1<<(i-1)))) continue;
            val[0][i][j]=val[0][i][j-(j&-j)];
            int p=__builtin_ctz(j)+1;
            val[0][i][j]=val[0][i][j]-(t*grp[p][i]-grp[i][p])+(grp[p][i]+t*grp[i][p]);
        }
        forup(k,pm+1,m){
            if(i!=k) val[1][i][0]+=t*grp[k][i]-grp[i][k];
        }
        forup(j,1,(1<<(m-pm))-1){
            if(i>pm&&(j&(1<<(i-pm-1)))) continue;
            val[1][i][j]=val[1][i][j-(j&-j)];
            int p=__builtin_ctz(j)+pm+1;
            val[1][i][j]=val[1][i][j]-(t*grp[p][i]-grp[i][p])+(grp[p][i]+t*grp[i][p]);
        }
    }
    mem(dp,0x3f);
    dp[0]=0;
    forup(i,0,(1<<m)-1){
        forup(j,1,m){
            if(i&(1<<(j-1))) continue;
            int nxt=i|(1<<(j-1));
            dp[nxt]=min(dp[nxt],dp[i]+calc(i,j));
        }
    }
    printf("%d\n",dp[(1<<m)-1]);
}

P4027 [NOI2007] 货币兑换

传送门

题意

• 有两支金券 \(A,B\)，第 \(i\) 天它们的价格分别是 \(A_i,B_i\) 元/单位金券。
• 每天金券市场规定你买的 \(A\) 金券必须是 \(B\) 金券的 \(R_i\) 倍。
• 你初始有 \(S\) 元，你能在任意天数买入或卖出金券，你每次卖出必须同时卖出 \(A,B\) 同样比例的金券（比如卖出 \(5\%\) 的 \(A\) 同时必须卖出 \(5\%\) 的 \(B\)）。
• 求 \(n\) 天后的最大收益。
• \(1\le n\le 10^5,0 < A_1,B_i\le 10,0< R_i\le 100\)，其中 \(A_i,B_i,R_i\) 是实数。

题解

感觉对斜优的理解更上一层楼了。

很难不发现每次必定要么把钱花光要么把金券卖光，然后就容易想到 DP 了。设 \(f_i\) 表示第 \(i\) 天手上最多有多少钱，转移要么 \(f_i=f_{i-1}\)，要么前面找一天把钱花完再在这一天把金券卖完。

前一种是简单的，于是我们只考虑第二种，如果从 \(j\) 转移过来贡献即为：

\[ f_{i}=A_i\times(f_j\frac{R_j}{A_jR_j+B_j})+B_i\times(f_j\frac{1}{A_jR_j+B_j}) \]

看着很繁琐，不妨设 \(a_j=f_j\frac{R_j}{A_jR_j+B_j},b_j=f_j\frac{1}{A_jR_j+B_j}\)，于是有：

\[ f_{i}=A_ia_j+B_ib_j \]

考虑何时一个转移点 \(j\) 优于 \(k\)，于是：

\[ \begin{aligned} A_ia_j+B_ib_j &> A_ka_k+B_kb_k\\ A_i(a_j-a_k) &> -B_i(b_j-b_k)\\ -\frac{A_i}{B_i} &< \frac{b_j-b_k}{a_j-a_k} \end{aligned} \]

即对 \((a_j,b_j)\) 建出上凸壳后找到第一个斜率大于等于 \(-\frac{A_i}{B_i}\) 的位置。

但是 \(a_j\) 不单调，而且查询位置还不是离散的不好用李超树，怎么办呢？容易发现 CDQ 优化 DP 转移就行了，因为每一层要对右半边按 \(-\frac{A_i}{B_i}\) 排序，或者对凸包二分所以无论如何复杂度都是 \(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 db=long double;
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;
const db eps=1e-7;
int n;
db dp[N];
struct Node{
    db A,B,R;
    int pos;
}s[N];
struct node{
    db a,b;
    node operator-(const node &r){
        return node{a-r.a,b-r.b};
    }
}q[N];
db cross(node a,node b){
    return a.a*b.b-a.b*b.a;
}
bool slp(node a,node b,node c){
    return cross(b-a,c-b)>0;
}
void cdq(int l,int r){
    if(l==r){
        if(dp[l-1]>dp[l]){
            dp[l]=dp[l-1];
            q[l].b=dp[l]/(s[l].R*s[l].A+s[l].B);
            q[l].a=s[l].R*q[l].b;
        }
        return;
    }
    int mid=(l+r)>>1;
    cdq(l,mid);
    vector<Node> vec;
    forup(i,mid+1,r) vec.push_back(s[i]);
    sort(vec.begin(),vec.end(),[&](Node a,Node b){
        return -a.A*b.B>-b.A*a.B;
    });
    deque<node> conv;
    forup(i,l,mid){
        if(i>l&&q[i].a==q[i-1].a) continue;
        while(conv.size()>=2&&slp(conv[conv.size()-2],conv[conv.size()-1],q[i])) conv.pop_back();
        conv.push_back(q[i]);
    }
    for(auto i:vec){
        while(conv.size()>=2&&(conv[1].b-conv[0].b)*i.B>i.A*(conv[0].a-conv[1].a)) conv.pop_front();
        db val=conv[0].a*i.A+conv[0].b*i.B;
        if(val>dp[i.pos]){
            dp[i.pos]=val;
            q[i.pos].b=val/(i.R*i.A+i.B);
            q[i.pos].a=i.R*q[i.pos].b;
        }
    }
    cdq(mid+1,r);
    inplace_merge(q+l,q+mid+1,q+r+1,[&](node a,node b){
        if(a.a!=b.a) return a.a<b.a;
        return a.b>b.b;
    });
}
signed main(){
    n=read();dp[0]=read();
    forup(i,1,n){
        scanf(" %Lf %Lf %Lf",&s[i].A,&s[i].B,&s[i].R);
        s[i].pos=i;
    }
    cdq(1,n);
    printf("%Lf\n",dp[n]);
}

P4886 快递员

传送门

题意

• 有一棵 \(n\) 个点的树，边带权，其上有 \(m\) 个点对 \((u,v)\)。
• 定义一个点 \(p\) 的权值为 \(\max_{(u,v)} \begin{Bmatrix}dis(u,p)+dis(v,p)\end{Bmatrix}\)
• 求权值最小的点权值是多少。
• \(1\le n\le 10^5\)。

题解

很厉害的一道题。

考虑每次随便选一个点算出答案，容易发现若它就在最大值的那条链上那么答案就是它。又容易发现如果它有超过一个子树中有产生最大值的点对那么答案也是它，因为不管怎么挪答案都不可能变小了。

考虑只有一个子树内有最大值点对那么只有这个子树可能更小了，于是进去这个子树递归解决。

然后跟点分治一样，每次取重心就能 \(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,ans=inf;
vector<pii> e[N];
vector<i64> pos[N];
i64 dis[N],fr[N],vis[N];
i64 sz[N],rt,mx[N],als;
void dfs1(i64 x,i64 fa){
    sz[x]=1;
    mx[x]=0;
    for(auto i:e[x]){
        i64 v=i.fi;
        if(v==fa||vis[v]) continue;
        dfs1(v,x);
        sz[x]+=sz[v];
        mx[x]=max(mx[x],sz[v]);
    }
    mx[x]=max(mx[x],als-sz[x]);
    if(mx[x]<=als/2) rt=x;
}
void dfs2(i64 x,i64 fa,i64 rr,i64 d){
    for(auto i:pos[x]){
        if(!fr[i]||fr[i]==rr){
            fr[i]=rr;
        }else{
            fr[i]=-1;
        }
        dis[i]+=d;
    }
    for(auto i:e[x]){
        i64 v=i.fi,w=i.se;
        if(v==fa) continue;
        dfs2(v,x,rr,d+w);
    }
}
void solve(i64 x,i64 ps){
    vis[x]=1;
    forup(i,1,m){
        dis[i]=0,fr[i]=0;
    }
    for(auto i:pos[x]){
        fr[i]=x;
    }
    for(auto i:e[x]){
        i64 v=i.fi,w=i.se;
        dfs2(v,x,v,w);
    }
    i64 mx=0,mr=0;
    forup(i,1,m){
        mx=max(mx,dis[i]);
    }
    forup(i,1,m){
        if(dis[i]!=mx) continue;
        if(fr[i]==-1){
            ans=min(ans,mx);
            return;
        }
        if(mr==0||mr==fr[i]){
            mr=fr[i];
        }else{
            ans=min(ans,mx);
            return;
        }
    }
    ans=min(ans,mx);
    if(vis[mr]){
        return;
    }else{
        als=sz[mr]<sz[x]?sz[mr]:ps-sz[x];rt=0;
        dfs1(mr,x);
        solve(rt,als);
    }
}
signed main(){
    n=read();m=read();
    forup(i,1,n-1){
        i64 u=read(),v=read(),w=read();
        e[u].push_back(mkp(v,w));
        e[v].push_back(mkp(u,w));
    }
    forup(i,1,m){
        i64 u=read(),v=read();
        pos[u].push_back(i);
        pos[v].push_back(i);
    }
    rt=0;als=n;
    dfs1(1,0);
    solve(rt,n);
    printf("%lld\n",ans);
}

P6349 [PA2011] Kangaroos

传送门

题意

• 有 \(n\) 个区间 \([l_i,r_i]\) 排成一个序列，有 \(m\) 个询问，每次询问与区间 \([A,B]\) 有交的区间在序列上的最长连续段有多长。
• \(1\le n\le 5\times 10^4,1\le m\le 2\times 10^5\)

题解

看到数据范围 \(5\times 10^4\)，容易想到一些根号的算法。

先考虑怎么判断一个区间 \([l,r]\) 是否和 \([A,B]\) 有交，容易发现有交的充要条件是 \(l_i\le B\land A\le r_i\)。

容易想到莫队，按左端点和右端点分别对区间排序得到序列 \(L,R\)，前一个条件相当于标记 \(L\) 的一个前缀，后一个相当于标记 \(R\) 的一个后缀，然后查询打了两个标记的最长连续段即可，可以用莫队移动指针后线段树维护。

复杂度 \(O(n\sqrt{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=5e4+5,M=2e5+5,B=120,inf=0x3f3f3f3f;
int n,m,ans[M];
struct range{
    int l,r,pos;
}sl[N],sr[N],q[M];
int cnt[N];
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    int lmx[N<<2],rmx[N<<2],mx[N<<2];
    void PushUp(int id,int l,int r){
        if(mx[id<<1]==mid-l+1) lmx[id]=mx[id<<1]+lmx[id<<1|1];
        else lmx[id]=lmx[id<<1];
        if(mx[id<<1|1]==r-mid) rmx[id]=rmx[id<<1]+mx[id<<1|1];
        else rmx[id]=rmx[id<<1|1];
        mx[id]=max(max(mx[id<<1],mx[id<<1|1]),rmx[id<<1]+lmx[id<<1|1]);
    }
    void Modify(int P,int X,int l=1,int r=n,int id=1){
        if(l==r){
            mx[id]=rmx[id]=lmx[id]=X;
            return;
        }
        if(P<=mid) Modify(P,X,lson);
        else       Modify(P,X,rson);
        PushUp(id,l,r);
    }
    int Query(){
        return mx[1];
    }
}mt;
signed main(){
    n=read();m=read();
    forup(i,1,n){
        range nw;
        nw.l=read();nw.r=read();nw.pos=i;
        sl[i]=sr[i]=nw;
    }
    sort(sl+1,sl+n+1,[&](range a,range b){return a.l<b.l;});
    sort(sr+1,sr+n+1,[&](range a,range b){return a.r<b.r;});
    forup(i,1,m){
        int l=read(),r=read();
        int ll=1,rr=n+1;
        while(ll<rr){
            int mm=(ll+rr)>>1;
            if(sr[mm].r<l) ll=mm+1;
            else rr=mm;
        }
        l=ll;
        ll=0,rr=n;
        while(ll<rr){
            int mm=(ll+rr+1)>>1;
            if(sl[mm].l>r) rr=mm-1;
            else ll=mm;
        }
        r=ll;
        q[i]=range{l,r,i};
    }
    sort(q+1,q+m+1,[&](range a,range b){
        int ba=a.l/B,bb=b.l/B;
        if(ba==bb){
            if(ba&1){
                return a.r>b.r;
            }else{
                return a.r<b.r;
            }
        }else{
            return ba<bb;
        }
    });
    int l=n+1,r=0;
    forup(i,1,m){
        while(r<q[i].r){
            ++r;++cnt[sl[r].pos];
            msg("+%d|",sl[r].pos);
            if(cnt[sl[r].pos]==2) mt.Modify(sl[r].pos,1);
        }
        while(l>q[i].l){
            --l;++cnt[sr[l].pos];
            msg("+%d|",sr[l].pos);
            if(cnt[sr[l].pos]==2) mt.Modify(sr[l].pos,1);
        }
        while(r>q[i].r){
            if(cnt[sl[r].pos]==2) mt.Modify(sl[r].pos,0);
            msg("-%d|",sl[r].pos);
            --cnt[sl[r].pos];--r;
        }
        while(l<q[i].l){
            if(cnt[sr[l].pos]==2) mt.Modify(sr[l].pos,0);
            msg("-%d|",sr[l].pos);
            --cnt[sr[l].pos];++l;
        }
        forup(i,1,n){
            msg("%d ",cnt[i]);
        }msg("|\n");
        ans[q[i].pos]=mt.Query();
    }
    forup(i,1,m){
        printf("%d\n",ans[i]);
    }
}

CF2013E Prefix GCD

传送门

题意

• 给定一个长度为 \(n\) 的非负数序列 \(a\)，你可以任意排列 \(a\) 的顺序，求 \(\sum_{i=1}^n\sum_{j=1}^i\gcd\begin{Bmatrix}a_j\end{Bmatrix}\)。
• \(1\le a_i,\sum n\le 10^5\)，带多测。

题解

很厉害的一道题。

容易想到一个 \(O(n^3\log V)\) 的贪心：枚举第一个数，然后每次贪心选能使 \(\gcd\) 变得最小的下一个数。

容易发现这个做法其实是 \(O(n^2\log^2 V)\) 的，因为你的 \(\gcd\) 至多变小 \(\log\) 次就能变成整个序列的 \(\gcd\) 了，而显然在 \(\gcd\) 到达最小值前的操作必定每次都让 \(\gcd\) 变小否则显然不优，我们在质因数个数较多时能取到这个上界。

考虑一个很厉害的剪枝，若 \(a < b\) 但是 \(\gcd(a,b) < a\)，那么容易发现 \(a+\gcd(a,b) \le b\)，因为 \(a\) 至少是 \(p\gcd(a,b)(p\ge 2)\)，而 \(b\) 的那个系数必须大于 \(p\)。这时候我们发现无论如何选 \(b\) 都不优了，因为序列由 \(a,b,\dots\) 开头都小于 \(b\) 了。

所以一个数有用当且仅当所有小于等于它的数都是它的因数，那么显然有用的数不会超过 \(O(\log V)\) 个，在全取 \(2^k\) 时能达到这个上界。

所以复杂度就变成 \(O(n\log^3 V)\) 的了。但是注意到这两个 \(\log\) 在其中一个变大时另一个会变小，实际复杂度上界应该比这个更紧，但是我算不来。

参考代码

#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,a[N],gg,vis[N],ans,tag[N];
i64 gcd(i64 a,i64 b){return b==0?a:gcd(b,a%b);}
void work(i64 st){
    vector<i64> vec;
    vec.push_back(st);
    vis[st]=1;
    i64 nw=a[st],res=a[st],p=1;
    while(nw!=gg){
        if((n-p)*gg+res>=ans){
            for(auto i:vec) vis[i]=0;
            return;
        }
        i64 mn=inf,mp=0;
        forup(i,1,n){
            if(vis[i]) continue;
            int p=gcd(nw,a[i]);
            if(p<nw) tag[i]=1;
            if(p<mn){
                mn=p;mp=i;
            }
        }
        nw=mn;vec.push_back(mp);vis[mp]=1;
        res+=nw;++p;
    }
    res+=(n-p)*gg;
    ans=min(ans,res);
    for(auto i:vec) vis[i]=0;
}
void solve(){
    n=read();
    gg=0;
    forup(i,1,n){
        a[i]=read();
        tag[i]=0;
        gg=gcd(gg,a[i]);
    }
    sort(a+1,a+n+1);
    ans=inf;
    forup(st,1,n){
        if(a[st]==a[st-1]||tag[st]) continue;
        work(st);
    }
    printf("%lld\n",ans);
}
signed main(){
    i64 t=read();
    while(t--){
        solve();
    }
}

[ABC137F] Polynomial Construction

传送门

题意

• 给定一个 \(p-1\) 次多项式在模 \(p\) 意义下 \(0\sim p-1\) 的点值，每个点的值不是 \(0\) 就是 \(1\)。
• 求出多项式的系数。
• \(2\le p\le 2999\)，保证 \(p\) 是指数。

题解

拉格朗日插值板题。

考虑暴力 \(O(p^3)\) 显然过不了，于是我们不得不学习 \(O(p^2)\) 的做法。

具体来说，考虑答案为 \(\sum_{i=0}^{p-1}a_i\prod_{j\ne i} \frac{x-j}{i-j}=\sum_{i=0}^{p-1}a_i\prod_{j\ne i} \frac{1}{i-j}\prod_{j\ne i} (x-j)\)，即一个可以 \(O(p)\) 算出的常数乘以一个多项式，那么先算出 \(\prod (x-j)\)，每次除以二项式 \(x-i\) 即可得到 \(\prod_{j\ne i} (x-j)\)，可以大除法。

复杂度 \(O(p^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=3005,inf=0x3f3f3f3f;
int p,a[N],inv[N];
int f[N],res[N];
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return c;
}
signed main(){
    p=read();
    f[0]=1;
    forup(i,1,p-1){
        inv[i]=ksm(i,p-2);
    }
    forup(i,0,p-1){
        a[i]=read();
        fordown(j,p,0){
            f[j]=1ll*(p-i)*f[j]%p;
            if(j) (f[j]+=f[j-1])%=p;
        }
    }
    forup(i,0,p-1){
        if(!a[i]) continue;
        fordown(j,p,1){
            (f[j-1]+=1ll*f[j]*i%p)%=p;
        }
        forup(j,0,p-1) f[j]=f[j+1];
        f[p]=0;
        int val=1;
        forup(j,0,p-1){
            if(j==i) continue;
            if(i>j){
                val=1ll*val*inv[i-j]%p;
            }else{
                val=1ll*val*inv[i-j+p]%p;
            }
        }
        forup(j,0,p-1){
            (res[j]+=1ll*val*f[j]%p)%=p;
        }
        fordown(j,p,0){
            f[j]=1ll*(p-i)*f[j]%p;
            if(j) (f[j]+=f[j-1])%=p;
        }
    }
    forup(i,0,p-1){
        printf("%d ",res[i]);
    }
    puts("");
}

P5319 [BJOI2019] 奥术神杖

传送门

题意

• 有一个长度为 \(n\) 的字符串 \(s\)，其中有部分位置已经确定，部分没有确定。
• 有 \(m\) 个关键字符串 \(t_i\)，每个字符串有一个权值 \(v_i\)。
• 设 \(s\) 的子串中有 \(c\) 个关键字符串，那么 \(s\) 的权值为关键字符串权值之积开 \(c\) 次方（出现多次算多次），求出权值最大的 \(s\)。
• \(1\le n,m,\sum |t|\le 1501\)。

题解

很厉害的一道题，简单来说是对指数的 \(01\) 分数规划。

具体来说，考虑二分，那么考虑如何判断答案能否大于等于 \(mid\)，即 \(\sqrt[c]{\prod v_i}\ge mid\)。

两边同时取对数，得到 \(\frac{\sum \log v_i}{c}\ge \log mid\)，底数可以随便取，我代码里取的 \(2\)。

移项可得 \(\sum(\log v_i-\log mid)\ge 0\)，然后在 AC 自动机上 DP 即可。

复杂度 \(O(n^2\log v)\)，其中 \(v=\frac{1}{eps}\)，相当于值域吧。

参考代码

#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 db=double;
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=1505,inf=0x3f3f3f3f;
const db eps=1e-7;
int n,m;
int a[N],nd[N];
db val[N];
char str[N];
struct Trie{
    int tr[N][10],cntn,fail[N];
    db val[N];
    vector<int> e[N];
    int Insert(int len){
        int p=0;
        forup(i,1,len){
            int c=str[i]-'0';
            if(!tr[p][c]) tr[p][c]=++cntn;
            p=tr[p][c];
        }
        return p;
    }
    void Build(){
        queue<int> q;
        forup(i,0,9){
            if(tr[0][i]){
                q.push(tr[0][i]);
            }
        }
        while(q.size()){
            int u=q.front();q.pop();
            e[fail[u]].push_back(u);
            forup(i,0,9){
                if(tr[u][i]){
                    fail[tr[u][i]]=tr[fail[u]][i];
                    q.push(tr[u][i]);
                }else{
                    tr[u][i]=tr[fail[u]][i];
                }
            }
        }
    }
    void dfs(int x){
        for(auto i:e[x]){
            val[i]=val[i]+val[x];
            dfs(i);
        }
    }
}mt;
db dp[N][N];
pii pre[N][N];
bool chk(db mm){
    forup(i,0,mt.cntn){
        mt.val[i]=0;
    }
    forup(i,1,m){
        mt.val[nd[i]]=val[i]-mm;
    }
    mt.dfs(0);
    forup(i,0,n){
        forup(j,0,mt.cntn){
            dp[i][j]=-inf;
        }
    }
    dp[0][0]=0;
    forup(i,0,n-1){
        forup(j,0,mt.cntn){
            auto work=[&](int v){
                int p=mt.tr[j][v];
                db val=dp[i][j]+mt.val[p];
                if(val>dp[i+1][p]){
                    dp[i+1][p]=val;
                    pre[i+1][p]=mkp(j,v);
                }
            };
            if(~a[i+1]){
                work(a[i+1]);
            }else{
                forup(v,0,9){
                    work(v);
                }
            }
        }
    }
    int mx=0;
    forup(i,1,mt.cntn){
        if(dp[n][i]>dp[n][mx]){
            mx=i;
        }
    }
    return dp[n][mx]>0;
}
int ans[N];
void print(){
    int p=0;
    forup(i,1,mt.cntn){
        if(dp[n][i]>dp[n][p]){
            p=i;
        }
    }
    fordown(i,n,1){
        ans[i]=pre[i][p].se;
        p=pre[i][p].fi;
    }
    forup(i,1,n){
        printf("%d",ans[i]);
    }
}
signed main(){
    n=read();m=read();
    scanf(" %s",str+1);
    forup(i,1,n){
        if(str[i]=='.'){
            a[i]=-1;
        }else{
            a[i]=str[i]-'0';
        }
    }
    db mx=0,mn=inf;
    forup(i,1,m){
        scanf(" %s",str+1);val[i]=read();
        mx=max(mx,val[i]);mn=min(mn,val[i]);
        val[i]=log2(val[i]);
        nd[i]=mt.Insert(strlen(str+1));
    }
    mt.Build();
    db ll=mn,rr=mx;
    forup(i,1,40){
        db mm=(ll+rr)/2; 
        msg("%lf %lf[%lf]\n",ll,rr,mm);
        if(chk(log2(mm))) ll=mm;
        else rr=mm;
    }
    chk(log2(ll));
    print();
}

[AGC009C] Division into Two

传送门

题意

• 给定一个大小为 \(n\) 的集合，你要把它分成两个集合，其中 \(A\) 集合中任意两个数之差必须大于等于 \(x\)，\(B\) 集合中任意两个数之差必须大于等于 \(y\)，问集合划分方案数。
• \(1\le n\le 10^5\)。

题解

先钦定 \(x\ge y\)，容易想到对 \(A\) 的位置进行 DP，即设 \(f_i\) 表示考虑 \(i\) 之前的数，钦定 \(i\in A\) 的方案数，转移要考虑上一个数和 \(a_i\) 的差大于等于 \(x\)，并且中间的两两之差大于等于 \(y\)。

容易发现合法转移点是一段区间，于是双指针加前缀和维护即可，复杂度 \(O(n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--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,mod=1e9+7;
i64 n,x,y,a[N];
i64 f[N],sum[N];
signed main(){
    n=read();x=read();y=read();
    if(x<y) swap(x,y);
    forup(i,1,n){
        a[i]=read();
    }
    f[0]=1;sum[0]=1;
    i64 pl=0,pr=0;
    forup(i,1,n){
        while(a[i]-a[pr+1]>=x) ++pr;
        if(pl<=pr){
            f[i]=(sum[pr]-sum[pl]+f[pl]+mod)%mod;
        }
        sum[i]=(sum[i-1]+f[i])%mod;
        if(i>1&&a[i]-a[i-1]<y) pl=i-1;
        if(i>2&&a[i]-a[i-2]<y) pl=i;
    }
    printf("%lld\n",(sum[n]-sum[pl]+f[pl]+mod)%mod);
}

CF1635F Closest Pair

传送门

题意

• 给定 \(n\) 条与纵轴垂直的线段，下端点为 \(0\)，上端点为 \(h_i\)，横坐标为 \(w_i\)，且横坐标单调递增。
• 每次区间询问两条线段能组成的最小梯形的面积 \(\times 2\)（即 \(|w_i-w_j|\times(h_i+h_j)\) 的最小值）。
• \(1\le n\le 10^6\)

题解

考虑任意一个点对必定一大一小。

那么从大的那个考虑，容易发现它左右可能和它产生贡献的 \(h_i\) 必定随着远离它单调递减。

然后容易发现这些点对中横跨其它点的必定不优。所以每个点只需要和它左右第一个小于它的点产生贡献就行了。

然后扫描线 \(+\) 树状数组即可，复杂度 \(O(n\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--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=3e5+5,inf=5e18;
i64 n,m,ans[N];
struct Node{
    i64 w,h;
}l[N];
vector<i64> p[N];
vector<pii> q[N];
struct BIT{
    i64 c[N];
    void init(){forup(i,1,n) c[i]=inf;}
    void upd(i64 x,i64 k){for(;x<=n;x+=x&-x)c[x]=min(c[x],k);}
    i64 sum(i64 x){i64 res=inf;for(;x>0;x-=x&-x)res=min(res,c[x]);return res;}
}mt;
signed main(){
    n=read();m=read();
    forup(i,1,n){
        l[i].w=read();l[i].h=read();
    }
    forup(i,1,m){
        i64 ql=read(),qr=read();
        q[ql].push_back(mkp(qr,i));
    }
    stack<i64> stk;
    mt.init();
    l[0].h=l[n+1].h=0;stk.push(0);
    forup(i,1,n){
        while(stk.size()&&l[stk.top()].h>l[i].h) stk.pop();
        if(stk.top()!=0) p[stk.top()].push_back(i);
        stk.push(i);
    }
    while(stk.size()) stk.pop();
    stk.push(n+1);
    fordown(i,n,1){
        while(stk.size()&&l[stk.top()].h>l[i].h) stk.pop();
        if(stk.top()!=n+1) p[i].push_back(stk.top());
        stk.push(i);
    }
    fordown(i,n,1){
        for(auto j:p[i]){
            mt.upd(j,(l[j].w-l[i].w)*(l[j].h+l[i].h));
        }
        for(auto j:q[i]){
            int r=j.fi,pos=j.se;
            ans[pos]=mt.sum(r);
        }
    }
    forup(i,1,m){
        printf("%lld\n",ans[i]);
    }
}

CF1785F Minimums or Medians

传送门

题意

• 有一个长度为 \(2n\) 的序列，初始为 \(1\) 到 \(2n\)，每次可以删掉正中间的两个或者开头的两个。
• 求操作 \(m\) 次后可能的序列个数。
• \(1\le k\le n\le 10^6\)

题解

很厉害的一道题。

考虑整个过程长什么样，相当于有两个指针指示中间的两个点，删中间就是左指针 \(-1\) 右指针 \(+1\)，删开头就是两个指针都 \(+1\)。

也就是说，我们能确定右指针最终位置必定是 \(n+m\)。

考虑最终形态必定是一个前缀和若干长度为偶数的区间被删掉，并且除去前缀以外所有区间必定右端点在 \(n\) 之后，且 \(r-n\ge n-l+1\)。一个结论是这个命题是充要的，因为你一定可以构造出来。

然后对这种形状计数即可。

先考虑一个简单的问题：将一个长度为 \(p\) 序列中 \(2q\) 个点涂黑，要求每个连续的黑色区间长度都是偶数，求方案数。容易发现方案数就是 \(\binom{p-q}{q}\)，考虑组合意义是显然的。

首先若 \(2k < n\)，则不会出现前缀包含 \(n\) 的情况，于是枚举横跨 \(n\) 的这一段长度，因为它 \(r-n\ge n-l+1\)，所以我们先枚举 \(n-l\) 这一段有多长，右侧除去长度相同的一段后容易发现变成了刚才“简单的问题”，再枚举右侧有多少点即可。

这部分答案是 \(\sum_{i=0}^{\min(n,m)}\sum_{p=0}^{\frac{m-i}{2}}\binom{m-i-p}{p}\)。

然后化一下式子：

\[ \begin{aligned} &\sum_{i=0}^{m}\sum_{p=0}^{\frac{m-i}{2}}\binom{m-i-p}{p}\\ =&\sum_{p=0}^{\frac{m}{2}}\sum_{i=0}^{m-2p}\binom{m-i-p}{p}\\ =&\sum_{p=0}^{\frac{m}{2}}\sum_{t=p}^{m-p}\binom{m-t}{p} \end{aligned} \]

相当于每次求组合数一列的前缀和，根据经典结论，\(\sum_{i=0}^n\binom{i}{j}=\binom{n+1}{j+1}\)。

然后若 \(2k\ge n\)，就要考虑前缀包含 \(n\) 的情况了，一个想法是先把这种情况去掉（自己考虑一下上下界），然后再单独算跨过 \(n\) 的最小前缀加上一个上述问题的答案就行了。

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

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)){if(c=='-')f=-1;}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f,mod=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;
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;
}
signed main(){
    n=read();m=read();
    if(m==n){
        puts("1");
        return 0;
    }
    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 ans=0;
    forup(p,0,m/2){
        int r=m-max(2*m-p-n+1,p),l=m-(m-p);
        if(l>r) continue;
        (ans+=(binom(r+1,p+1)-binom(l,p+1)+mod)%mod)%=mod;
    }
    if(n/2+1<=m){
        int p=(n+1)/2;
        (ans+=binom(n+m-p*2-(m-p),m-p))%=mod;
    }
    printf("%d\n",ans);
}

模拟赛神秘题目 【0923 B组】C 屠龙游戏

题意

这个题面写的也太狗屎了，大概可以看作一个神秘自定义 Nim-K 游戏。

• 具体来说，有一个系统，每次会给 Alice 一堆石子，总共会给 \(n\) 次，这一堆石子有 \(x_i\) 个，并且有一个权值 \(y_i\)。
• 在每次给了石子后，Alice 会选择现有石子堆的一个子集 \(S\)，并且将其复制一份得到 \(2|S|\) 堆石子，不妨设得到的集合为 \(T\)。
• 然后 Bob 需要选择一个 \(T\) 的真子集（可以为空）全部删掉，显然会剩下若干堆石子，在剩下的石子中，Alice 和 Bob 会进行一个 Nim-2 游戏。
• 具体来说，由 Alice 先手，操作者每次可以选择一堆或两堆石子，并在自己选择的所有石子堆中各拿走至少一枚石子，不能操作者败。
• 若 Alice 获胜，则获得先前所选集合 \(S\) 对应的所有石子堆的 \(y_i\) 之和个金币，若 Bob 获胜，则 Alice 只能获得 \(0\) 个金币。
• 现在 Alice 想知道每次系统给完石子后，假如直接开始游戏那么 Alice 最多能获得多少个金币，询问间独立。
• \(1\le n\le 5\times 10^5,1\le x_i\le 10^{18},1\le y_i\le 10^9\)，强制在线。

我发现我简化了一下还是很狗屎，算了将就看吧。

题解

首先我们需要学会 Nim-K 游戏怎么玩。

结论是：将每堆石子的个数化为二进制（相当于 SG 函数），然后把每一位当成向量的一个维度求出模 \(K+1\) 意义下的向量和，先手必胜当且仅当向量和不为 \(0\) 向量。

证明和一般的 Nim 游戏类似，首先终态是 \(0\)，然后任何一个 \(0\) 态只能到达非 \(0\) 态，任何一个非 \(0\) 态均能到达 \(0\) 态（构造就贪心地找 \(K\) 次，每次给尽可能多非 \(0\) 位 \(-1\)，显然能减到 \(0\)）。

然后假如 Alice 选好了，Bob 应该怎么办。

显然 Bob 肯定希望剩下的向量和为 \(0\)，注意到在模 \(3\) 意义下，一个向量只可能选 \(0,1,2\) 次，选 \(3\) 次就等于 \(0\) 次了。也就是说假如 Alice 选的集合 \(S\) 有一个非空子集进行线性变换能得到 \(0\) Bob 就赢了。因为必须剩下一个非空集合，所以容易发现 Alice 胜当且仅当 \(S\) 中的向量线性无关。

那么可以用线性基维护，每次插入新的石子堆尝试消元，从高到低枚举 \(x_i\) 的每一个 \(1\)，如果这一位没有代表元就直接插入，否则在原先的代表元和 \(x\) 中选一个更小的继续尝试消元即可。

复杂度 \(O(n\log^2 x)\)，因为每次消元需要暴力扫三进制位，不太能过。

怎么优化呢？考虑位运算优化，用两个 \(64\) 位整数存每个向量中哪些位置为 \(1\) 哪些位置为 \(2\) 即可，复杂度 \(O(\frac{n\log^2 x}{\omega})\)（但是我感觉是 \(O(n\log x)\) 的）。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=5e5+5;
i64 t,n,lans;
struct Vector{
    i64 p1,p2;
    bool empty(){
        return !p1&&!p2;
    }
    i64 gval(const i64 &i){
        if((p1>>i)&1) return 1;
        if((p2>>i)&1) return 2;
        return 0;
    }
    void Get(const i64 &n){
        p1=p2=0;
        forup(i,0,59){
            if((n>>i)&1) p1|=(1ll<<i);
        }
    }
    void Xor(const Vector &r){
        i64 p0=((1ll<<60)-1)^p1^p2,rp0=((1ll<<60)-1)^r.p1^r.p2;
        i64 pp1=p1,pp2=p2;
        p1=(p0&r.p1)|(pp2&r.p2)|(pp1&rp0);
        p2=(pp1&r.p1)|(p0&r.p2)|(pp2&rp0);
    }
};
struct linear_basis{
    Vector vec[60];
    i64 val[60],sum;
    void insert(Vector x,i64 atk){
        fordown(i,59,0){
            if(x.gval(i)){
                if(vec[i].empty()){
                    vec[i]=x;
                    val[i]=atk;
                    sum+=atk;
                    return;
                }else{
                    if(atk>val[i]){
                        sum+=atk-val[i];
                        swap(x,vec[i]);
                        swap(atk,val[i]);
                    }
                    while(x.gval(i)){
                        x.Xor(vec[i]);
                    }
                    if(x.empty()) return;
                }
            }
        }
    }
}mt;
signed main(){
    n=read();
    forup(i,1,n){
        i64 x=read(),y=read();
        x^=lans;
        Vector v1;v1.Get(x);
        mt.insert(v1,y);
        lans=mt.sum;
        printf("%lld\n",lans);
    }
}

CF1868C Travel Plan

传送门

题意

• 给定 \(n,m\)，表示有一个 \(n\) 个点的完全二叉树，每个点有点权，值域为 \([1,m]\)。
• 设 \(s(u,v)\) 表示 \(u,v\) 间简单路径上点权最大值，对于所有 \(m^n\) 种赋点权的方式，求 \(\sum_{i=1}^n\sum_{j=1}^ns(i,j)\)。
• \(1\le n\le 10^{18},1\le m\le 10^5\)，带多测 \(\sum m\le 10^5\)。

题解

今天也是写了一坨大屎的一天。

考虑假如我们能知道每一种长度（指路径上结点数目）的路径有多少条，那么事情就简单了。

具体来说，假如长度为 \(i\) 的路径有 \(cnt_i\) 条，那么答案就是 \(\sum_{i=1}^{2\log_2 n-1}\sum_{j=1}^mm^{n-i}\times (j^i-(j-1)^i)\times cnt_i\times j\)，注意边界情况时 \(i\) 的上界。

那么怎么求呢？我非常逆天的想法是把完全二叉树看作一棵 zkw 线段树（即点有标号的满二叉树）加不完整的一层，然后从 \(n\) 开始一层一层往上跳，显然整个过程中当前结点的兄弟是一棵满二叉树（可以在程序开头预处理），再加上和过程中经过的结点有关的路径即可，简单搞一搞这一部分复杂度能做到 \(O(\log^3 n)\)。

于是总复杂度 \(O(m\log n+log^3 n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(args...) 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,mod=998244353;
i64 ksm(i64 a,i64 b){
    i64 c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
i64 n,m,p,cnt[140];
i64 dp[70][140];
void solve(){
    n=read();m=read();
    p=(63^__builtin_clzll(n))+1;
    forup(i,0,p*2-1) cnt[i]=0;
    i64 nn=n;
    i64 d=1;
    cnt[1]=1;
    while(nn>1){
        if(nn&1){
            forup(k,1,d*2-1){
                (cnt[k]+=dp[d][k])%=mod;
            }
            forup(i,0,d-1){
                forup(j,0,d){
                    (cnt[i+j+1]+=(1ll<<max(i-1,0ll))%mod*((1ll<<max(j-1,0ll))%mod)%mod)%=mod;
                }
            }
            i64 t=(n-(nn<<(d-1))+1)%mod;;
            forup(j,0,d){
                (cnt[d+j+1]+=(1ll<<max(j-1,0ll))%mod*t%mod)%=mod;
            }
        }else{
            forup(k,1,(d-1)*2-1){
                (cnt[k]+=dp[d-1][k])%=mod;
            }
            forup(i,0,d-1){
                forup(j,0,d-1){
                    (cnt[i+j+1]+=(1ll<<max(i-1,0ll))%mod*((1ll<<max(j-1,0ll))%mod)%mod)%=mod;
                }
            }
            i64 t=(n-(nn<<(d-1))+1)%mod;
            forup(j,0,d-1){
                (cnt[d+j+1]+=(1ll<<max(j-1,0ll))%mod*t%mod)%=mod;
            }
        }
//      msg("%lld|",d);
//      forup(i,0,7){
//          msg("%lld ",cnt[i]);
//      }msg("|\n");
        ++d;
        nn>>=1;
    }
    i64 ans=0;
    forup(i,1,p*2-1){
//      msg("%lld %lld|\n",i,cnt[i]);
        if(cnt[i]==0) break;
        i64 p=(n-i)%(mod-1);
        forup(j,1,m){
            (ans+=1ll*cnt[i]*ksm(m,p)%mod*(ksm(j,i)+mod-ksm(j-1,i))%mod*j%mod)%=mod;
        }
    }
    printf("%lld\n",ans);
}
signed main(){
    forup(i,1,60){
        forup(j,1,i*2-1){
            dp[i][j]=2ll*dp[i-1][j]%mod;
            if(j<=i){
                (dp[i][j]+=(1ll<<(j-1))%mod)%=mod;
            }
            forup(k,max(j-i,1ll),min(j-2,i-1)){
                (dp[i][j]+=(1ll<<(k-1))%mod*((1ll<<(j-k-2))%mod)%mod)%=mod;
            }
        }
    }
    i64 t=read();
    while(t--){
        solve();
    }
}

CF599E Sandy and Nuts

传送门

题意

• 逆有一棵 \(n\) 个点的树，但是你忘了这棵树长什么样了，只记得这棵树以 \(1\) 为根，并且你还记得树上的 \(m\) 条边 \((u_i,v_i)\)，和 \(q\) 组 \(\mathrm{lca}(a,b)=c\) 的关系。
• \(1\le n\le 13,0\le m < n,0\le q\le 100\)。

题解

看到 \(n=13\)，显然要状压，考虑能不能让每个状态从自己的子集转移过来。

容易想到设 \(f_{i,msk}\) 表示以 \(i\) 为根的子树为 \(msk\) 的方案数，转移就枚举 \(msk\) 的子集 \(nxt\)，然后 \(f_{i,msk}\gets f_{i,msk\oplus nxt}\times f_{v,nxt}\) 即可（其中 \(\oplus\) 表示按位异或，下同）。

但是有两个问题：这样可能不符合题目中边和 \(\mathrm{lca}\) 的条件，同时因为子树互不区分可能算重。

先解决第二个问题，一个简单想法是钦定 \(msk\) 中除去 \(i\) 之外的 \(\mathrm{lowbit}\) 必须被 \(nxt\) 包含，这样 \(msk\) 的每种子树划分方式就只有一个合法的转移。

然后是第一个问题，两种情况分开考虑。

• 如何保证 \(m\) 条边全都存在

  首先，\(u\) 的所有连边至多只有一条不在子树内，所以若 \(msk\) 中缺了超过两条边那么 \(f_{u,msk}\) 这个状态就不能转移到其它的 \(v\)，只能转移到 \(u\)。

  然后，假如 \(u\) 有且仅有一条边不在子树内，那么它只能转移到这条边指向的点。

• 如何保证 \(\mathrm{lca}\) 的性质

  这个其实比较简单，\(\mathrm{lca}(a,b)=c\) 当且仅当 \(a,b\) 均为 \(c\) 的后代但不在 \(c\) 的同一儿子内。那么若 \(msk\) 没有包含 \(c\) 的全部后代 \(c\) 就不能转移到其它点，同时，若 \(nxt\) 同时包含了 \(a,b\) 那么 \(nxt\) 也不能转移到 \(c\)。

于是我们可以预处理每个状态能转移到的状态以及不能转移到它的状态，搞一搞可以做到 \(O(3^nn^2)\)。

注意数据里面有 \(\mathrm{lca}(a,a)=b\) 的情况，特判即可。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(i64 i=(e),E123123=(e);i>=E123123;--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=20,inf=0x3f3f3f3f;
i64 n,m,q,al;
i64 dp[N][1<<13],ava[N][1<<13],leg[N][1<<13],anc[N];
vector<i64> son[N];
i64 grp[N];
i64 get(i64 i,i64 msk){
    for(auto j:son[i]){
        if((msk&j)!=j) return -1;
    }
    i64 p=al^msk,ss=p&grp[i];
    if(__builtin_popcount(ss)>1) return -1;
    if(ss) return (63^__builtin_clzll(ss))+1;
    return 0;
}
signed main(){
    n=read();m=read();q=read();
    al=(1<<n)-1;
    forup(i,1,m){
        i64 u=read()-1,v=read()-1;
        grp[u]|=(1<<v);
        grp[v]|=(1<<u);
    }
    forup(i,1,q){
        i64 a=read()-1,b=read()-1,c=read()-1;
        if(a==b&&a!=c){
            puts("0");
            return 0;
        }
        son[c].push_back((1<<a)|(1<<b));
        if(a!=c) anc[a]|=(1<<c);
        if(b!=c) anc[b]|=(1<<c);
    }
    forup(i,0,n-1){
        forup(msk,0,al){
            if(!((msk>>i)&1)){
                for(auto j:son[i]){
                    if(__builtin_popcount(msk&j)==2){
                        leg[i][msk]=1;
                        break;
                    }
                }
            }else{
                ava[i][msk]=get(i,msk);
            }
        }
    }
    forup(msk,0,al){
        forup(i,0,n-1){
            if(!((msk>>i)&1)) continue;
            if(msk==(1<<i)){
                dp[i][msk]=1;
                msg("%lld %lld[%lld %lld]\n",i,msk,dp[i][msk],ava[i][msk]);
                continue;
            }
            for(i64 nxt=(msk-1)&msk;nxt;nxt=(nxt-1)&msk){
                if((nxt&(1<<i))||leg[i][nxt]||(!(nxt&((msk^(1<<i))&-(msk^(1<<i)))))) continue;
                forup(v,0,n-1){
                    if(!((nxt>>v)&1)||(ava[v][nxt]&&ava[v][nxt]!=i+1)) continue;
                    (dp[i][msk]+=dp[i][msk^nxt]*dp[v][nxt]);
                }
            }
            msg("%lld %lld[%lld %lld]\n",i,msk,dp[i][msk],ava[i][msk]);
        }
    }
    printf("%lld\n",dp[0][al]);
}

模拟赛神秘题目 【0927 B组】C 列序号括

题意

• 有一个括号序列 \(s\)（不一定是合法的括号序列），我们钦定空字符（字符串末尾）小于左括号小于右括号，现在你可以进行任意次以下操作： - 选择 \(i,j\) 满足 \(i < j\) 且 \(s_i\) 是左括号 \(s_j\) 是右括号，并将它们删掉，然后左右合并补齐空缺。
• 求最终你能得到的字典序最小的括号序列是什么。
• \(1\le |s|\le 10^6\)。

题解

首先容易想到假如要删肯定会删连续的一段合法括号序列，不可能删一对独立的左右括号，否则要么必定不优，要么可以等价于前者。

容易想到一个非常暴力的 DP，设 \(f_i\) 表示子问题 \([i,n]\)，且钦定包含 \(i\) 的答案序列，转移要么直接接在 \(f_{i+1}\) 前面，要么找到以 \(i+1\) 为左端点的最短合法括号序列（显然任意一个更长的都能通过这个最短的和后面一段拼出来）\([i+1,j]\)，接在 \(f_j\) 的第二项前面。

首先这个 \([i+1,j]\) 怎么求出来，考虑括号序列的前缀和（即左括号 \(+1\)，右括号 \(-1\)），容易发现只要 \(s_{i+1}\) 为左括号，那么下一个前缀和和 \(i\) 相等的位置必定就是 \(j\)。

最后考虑怎么维护这个东西才能比较两个转移点的字典序。容易发现可以倍增维护，在维护对应下标的同时再维护对应哈希值即可做到字典序比较。复杂度 \(O(n\log n)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--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 ui64=unsigned 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;
const int P=37;
int n,a[N],val[N],nxt[N],pw2[N];
char str[N];
int f[N][20];
ui64 g[N][20];
bool cmp(int x,int y){
    fordown(i,19,0){
        if(g[x][i]==g[y][i]){
            x=f[x][i];y=f[y][i];
        }
    }
    return y>n||a[y];
}
signed main(){
    scanf(" %s",str+1);
    n=strlen(str+1);
    pw2[0]=P;
    forup(i,1,19){
        pw2[i]=pw2[i-1]*pw2[i-1];
    }
    forup(i,1,n){
        a[i]=(str[i]=='('?1:0);
        val[i]=val[i-1]+(a[i]?1:-1);
    }
    fordown(i,n,0){
        f[i][0]=i+1;
        g[i][0]=a[i]+1;
        if(a[i+1]&&nxt[val[i]]){
            if(cmp(i+1,f[nxt[val[i]]][0])){
                f[i][0]=f[nxt[val[i]]][0];
            }
        }
        nxt[val[i]]=i;
        forup(j,1,19){
            f[i][j]=f[f[i][j-1]][j-1];
            g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1]*pw2[j-1];
        }
    }
    int p=f[0][0];
    while(p<=n){
        putchar(a[p]?'(':')');
        p=f[p][0];
    }
}

CF407D Largest Submatrix 3

传送门

题意

• 给定一个 \(n\times m\) 的数字矩阵 \(a_{i,j}\)，求面积最大的子矩阵满足任意一个数至多在这个矩阵中出现了一次。
• \(1\le n,m\le 400,1\le a_{i,j}\le nm\)。

题解

模拟赛考到了，赛时写的 \(O(\frac{n^4}{\omega})\)，日过去了，结果 CF 没过。

考虑设 \(f_{l,r,y}\) 表示左右边界为 \(l,r\)，下边界为 \(y\) 的矩形上边界最远能到哪里。

容易发现 \(f_{l,r,y}\) 必然不小于 \(\max\begin{Bmatrix}f_{l+1,r,y},f_{l,r-1,y},f_{l,r,y-1}\end{Bmatrix}\)。考虑什么时候这个答案会比这个数大。

仔细想一想可以得到只有 \(a_{y,l}\) 和第 \(r\) 列之前的数重复或者 \(a_{y,r}\) 和第 \(l\) 列之前的数重复才行。这个是可以简单维护的。

注意 \(l,r\) 的枚举顺序，复杂度 \(O(n^3)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)){if(c=='-')f=-1;}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=405,inf=0x3f3f3f3f;
int n,m,a[N][N],ans,f[N][N][N];
int prel[N*N],prer[N*N];
signed main(){
    n=read();m=read();
    forup(i,1,n){
        forup(j,1,m){
            a[i][j]=read();
        }
    }
    forup(len,1,m){
        forup(l,1,m-len+1){
            int r=l+len-1;
            forup(y,1,n){
                f[l][r][y]=max({f[l+1][r][y],f[l][r-1][y],f[l][r][y-1]});
                f[l][r][y]=max(f[l][r][y],prel[a[y][r]]);
                f[l][r][y]=max(f[l][r][y],prer[a[y][l]]);
                if(l!=r&&a[y][l]==a[y][r]){
                    f[l][r][y]=y;
                }
                prel[a[y][l]]=prer[a[y][r]]=y;
                ans=max(ans,(r-l+1)*(y-f[l][r][y]));
            }
            forup(y,1,n){
                prel[a[y][l]]=prer[a[y][r]]=0;
            }
        }
    }
    printf("%d\n",ans);
}

P9192 [USACO23OPEN] Pareidolia P

传送门

题意

• 设 \(f(s)\) 表示从字符串 \(s\) 中删除一些字符后最多能找出多少个 bessie。
• \(g(s)\) 表示 \(s\) 的所有子串的 \(f\) 之和。
• 给定一长度为 \(n\) 的字符串 \(s\)，以及 \(m\) 次单点修改，求最开始以及每次修改后的 \(g(s)\)。
• \(1\le n,m\le 2\times 10^5\)

题解

先考虑静态问题，直接 DP（考虑一些依赖于矩阵乘法分配律的做法）显然是不太可行的，空间会炸掉，于是不妨考虑一些贪心。

容易想到一个贪心，先枚举左端点，然后暴力向右匹配，每完整地匹配一次就统计这个匹配会影响多少右端点，计入答案，复杂度 \(O(n^2)\)。

考虑对这个贪心进行 DP，设 \(f_{i,j}\) 表示右端点为 \(i\)，并且恰好匹配到 bessie 的第 \(j\) 位子串有多少个，每次转移进行对应字符的转移之前还有 \(f_{i,0}\gets f_{i,0}+1\)，就能统计到所有左端点了。在恰好能匹配完时计入答案，即再记一个 \(ans\)，每次遇到 e 就 \(ans\gets f_{i,5}\) 表示这次匹配的贡献。为了统计到所有右端点，再记一个 \(sum\) 表示 \(ans\) 的前缀和即可。因为转移有加一个常数，所以还需要记一维常数 \(1\)。

于是用线段树维护矩阵乘法即可做到动态，复杂度 \(O(q\log n9^3)\)。

参考代码

#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1<<18,inf=0x3f3f3f3f;
i64 n,m,a[N];
char str[N];
struct Matrix{
    i64 c[9][9];
    Matrix(){
        mem(c,0);
    }
    void init(){
        forup(i,0,8) c[i][i]=1;
    }
    Matrix operator*(const Matrix &r){
        Matrix res;
        forup(i,0,8){
            forup(k,0,8){
                i64 p=c[i][k];
                forup(j,0,8){
                    res.c[i][j]+=p*r.c[k][j];
                }
            }
        }
        return res;
    }
    void print(){
        forup(j,0,8){
            forup(k,0,8){
                msg("%lld ",c[j][k]);
            }
            msg("|\n");
        }
    }
}tr[5];
void init(){
    forup(i,0,4){
        tr[i].init();
        tr[i].c[6][7]=1;
        tr[i].c[8][0]=1;
    }
    tr[1].c[0][1]=1;tr[1].c[0][0]=0;
    tr[1].c[8][1]=1;tr[1].c[8][0]=0;
    tr[2].c[1][2]=1;tr[2].c[1][1]=0;
    tr[2].c[5][0]=1;tr[2].c[5][5]=0;
    tr[2].c[5][6]=1;tr[2].c[5][7]=1;
    tr[3].c[2][3]=1;tr[3].c[2][2]=0;
    tr[3].c[3][4]=1;tr[3].c[3][3]=0;
    tr[4].c[4][5]=1;tr[4].c[4][4]=0;
    // forup(i,0,4){
    //     msg("%d=====\n",i);
    //     tr[i].print();
    // }
}
struct SegTree{
    Matrix mat[N<<1];
    void Build(){
        forup(i,0,N-1){
            mat[i+N].init();
        }
        forup(i,1,n){
            mat[i+N]=tr[a[i]];
        }
        fordown(i,N-1,1){
            mat[i]=mat[i<<1]*mat[i<<1|1];
        }
    }
    void Update(i64 P,i64 X){
        mat[P+N]=tr[X];
        for(i64 i=(P+N)>>1;i;i>>=1){
            mat[i]=mat[i<<1]*mat[i<<1|1];
        }
    }
    i64 Query(){
        // msg("=====\n");
        // mat[1].print();
        return mat[1].c[8][7];
    }
}mt;
signed main(){
    init();
    scanf(" %s",str+1);
    n=strlen(str+1);
    forup(i,1,n){
        if(str[i]=='b'){
            a[i]=1;
        }else if(str[i]=='e'){
            a[i]=2;
        }else if(str[i]=='s'){
            a[i]=3;
        }else if(str[i]=='i'){
            a[i]=4;
        }else{
            a[i]=0;
        }
    }
    mt.Build();
    printf("%lld\n",mt.Query());
    m=read();
    forup(i,1,m){
        i64 u=read(),v=0;char c;
        scanf(" %1c",&c);
        if(c=='b'){
            v=1;
        }else if(c=='e'){
            v=2;
        }else if(c=='s'){
            v=3;
        }else if(c=='i'){
            v=4;
        }
        mt.Update(u,v);
        printf("%lld\n",mt.Query());
    }
}

模拟赛神秘题目 【0930 B组】D 最小生成树

题意

• 有一张 \(n+1\) 个点的图，编号从 \(0\) 到 \(n\)。
• 点 \(0\) 和编号非 \(0\) 的点均有连边，其中和 \(i\) 的连边边权是 \(a_i\)。
• 此外还有 \(m\) 条端点非 \(0\) 的边。
• 有 \(q\) 次 \(a_i\) 的单点修改，每次修改后求出这张图最小生成树的边权和。
• \(1\le n,m,q\le 3\times 10^5\)，所有边权在 \(10^9\) 以内。

题解

感觉很厉害。

容易联想到一些线段树分治的做法，但是容易发现对点操作的话复杂度是假的。

考虑若 \(m\) 条边形成一条链怎么做。容易（？）想到按链建立线段树，每个结点维护 \(t_{0/1,0/1}\) 表示左端点所在连通块是否和 \(0\) 相连，右端点连通块是否和 \(0\) 相连，\(a_i\) 在叶子处处理，合并时只考虑非 \(0\) 边即可。

然后怎么办呢？有一个逆天思路：Kruskal 合并连通块时我们假装两个连通块均为链，将链的端点连起来，转化成上一个问题。

容易发现这样有错当且仅当原本 \((u,v)\) 边被当成 \((x,y)\) 了，并且合并时 \(u,x\) 不在一个连通块，\(v,y\) 不在一个连通块。考虑 Kruskal 的过程，容易发现这样显然不优。

于是复杂度 \(O(m\log m+n\alpha(n)+q\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=3e5+5,inf=1e18;
i64 n,m,q,a[N];
struct edge{
    i64 u,v,w;
}e[N];
i64 fa[N],st[N],ed[N];
i64 son[N],sv[N];
i64 getfa(i64 x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void merge(i64 u,i64 v,i64 w){
    u=getfa(u),v=getfa(v);
    if(u==v) return;
    fa[v]=u;
    son[ed[u]]=st[v];
    sv[ed[u]]=w;
    ed[u]=ed[v];
}
i64 pos[N],mp[N],cntn;
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 t[N<<2][2][2];
    void PushUp(i64 id,i64 l,i64 r){
        forup(i,0,1){
            forup(j,0,1){
                t[id][i][j]=min(t[id<<1][i][1]+t[id<<1|1][1][j],
                                min(t[id<<1][i][0]+t[id<<1|1][1][j],t[id<<1][i][1]+t[id<<1|1][0][j])+sv[pos[mid]]);
            }
        }
    }
    void Build(i64 l=1,i64 r=n,i64 id=1){  
        if(l==r){
            t[id][0][0]=0;
            t[id][1][1]=a[pos[l]];
            return;
        }
        Build(lson);Build(rson);
        PushUp(id,l,r);
    }
    void Update(i64 P,i64 l=1,i64 r=n,i64 id=1){
        if(l==r){
            t[id][0][0]=0;
            t[id][1][1]=a[pos[l]];
            return;
        }
        if(P<=mid) Update(P,lson);
        else       Update(P,rson);
        PushUp(id,l,r);
    }
}mt;
signed main(){
    n=read();m=read();
    forup(i,1,n){
        a[i]=read();
        fa[i]=st[i]=ed[i]=i;
    }
    forup(i,1,m){
        e[i].u=read();e[i].v=read();e[i].w=read();
    }
    sort(e+1,e+m+1,[&](edge a,edge b){return a.w<b.w;});
    forup(i,1,m){
        merge(e[i].u,e[i].v,e[i].w);
    }
    forup(i,1,n){
        if(fa[i]==i){
            for(i64 j=st[i];j;j=son[j]){
                pos[++cntn]=j;
                mp[j]=cntn;
            }
        }
        if(!son[i]) sv[i]=inf;
    }
    mt.Build();
    q=read();
    forup(i,1,q){
        i64 u=read(),val=read();
        a[u]=val;
        mt.Update(mp[u]);
        printf("%lld\n",mt.t[1][1][1]);
    }
}

评论