怎么什么套路也不会？怎么什么套路也不会？怎么什么套路也不会？

一类DP

总结转移里带最值的一类 DP。

对于转移为 $f_i=\max_{0\le j < i} f_j+\max_{k=j+1}^i a_k$ ，如果用 ST 表预处理，然后暴力转移的话，复杂度是 $O(n^2)$ 的。

然后有一个套路，出自 Pudding Monsters。

设 $b_j=\max_{k=j}^i$，可以发现，序列 $b$ 一定是形如下图的一些连续段：

根据 $\max$ 的单调性，连续段的权值一定单调递减。

所以我们可以维护一个单调递减的单调栈，在加入元素 $a_i$ 时，维护单调栈并更新一些段的 $b$ 值。

然后可以用线段树维护这个东西。

具体的，我们枚举 $i$，然后用单调栈维护 $b_j$，对应的修改在线段树上完成。

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

把 $\max$ 换成 $\min$ 同理，不再赘述。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=1e5+10,inf=1e18;
int n,top,rt,segcnt;
int a[maxn],stk[maxn],f[maxn];
struct tree{
    int ls,rs,mx,tag;
}tr[maxn<<1];
inline void up(int p){tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);}
inline void add(int p,int val){tr[p].mx+=val,tr[p].tag+=val;}
inline void down(int p){if(tr[p].tag) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=0;}
inline void build(int l,int r,int &p){
    p=++segcnt;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p));
}
inline void update(int l,int r,int L,int R,int val,int p){
    if(l>=L&&r<=R){add(p,val);return;}
    int mid=(l+r)>>1;down(p);
    if(L<=mid) update(l,mid,L,R,val,ls(p));
    if(R>mid) update(mid+1,r,L,R,val,rs(p));
    up(p);
}
inline int query(int l,int r,int L,int R,int p){
    if(l>=L&&r<=R) return tr[p].mx;
    int mid=(l+r)>>1,res=-inf;down(p);
    if(L<=mid) res=max(res,query(l,mid,L,R,ls(p)));
    if(R>mid) res=max(res,query(mid+1,r,L,R,rs(p)));
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;build(0,n,rt);
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=n;++i){
        while(top&&a[stk[top]]<=a[i]) update(0,n,stk[top-1],stk[top]-1,-a[stk[top]],rt),--top;
        update(0,n,stk[top],i-1,a[i],rt),stk[++top]=i;
        f[i]=query(0,n,0,i-1,rt);
        update(0,n,i,i,f[i],rt); 
    }
    cout<<f[n];
    return 0;
}

然后来看下面这道题。

刚才已经维护好 $\max$ 和 $\min$ 了，考虑怎么维护 $\operatorname{mex}$。

可以发现，$\operatorname{mex}$ 也是有单调性的，也会形成一些 $\operatorname{mex}$ 连续段。

考虑加入元素 $a_i$ 带来的影响。

可以发现，只有 $\operatorname{mex}=a_i$ 的那一段会受到影响，且这一段会分裂成若干不同段。

举个例子：

图中的 $\operatorname{mex}$ 表示 $\operatorname{mex}_{k=j}^i a_k$，且还没有考虑到 $a_i$ 的影响。

下面我们就来考虑 $a_i$ 会对前面的 $\operatorname{mex}$ 连续段有什么影响。

可以发现，加入 $a_i$ 后，连续段会变成这样：

我们可以维护 $l_x,r_x$ 表示 $\operatorname{mex}$ 值为 $x$ 的连续段的左右端点。

我们从右端点开始向前推：先找到右端点新的 $\operatorname{mex}$，然后向前找到这个值在的位置，把这个值所在位置的后一个到右端点这一部分的 $\operatorname{mex}$ 修改（因为这一段的 $\operatorname{mex}$ 都是这个值），然后更新右端点。

以上图为例，我们先找到 $3$ 的新 $\operatorname{mex}$，发现是 $5$，然后找到 $5$ 的位置，把这一段的 $\operatorname{mex}$ 都更新成 $5$，然后更新右端点，继续操作。

关于找到新的 $\operatorname{mex}$ 是几以及它的位置，可以维护一颗权值线段树，然后在权值线段树上二分。

修改次数均摊是 $O(n)$ 的，只能感性理解了。

具体可以看这道题：Rmq Problem / mex。

#include"bits/stdc++.h"
#define re register
#define int long long
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define pii pair<int,int> 
#define fi first
#define se second
using namespace std;
const int maxn=2e5+10,inf=1e18;
int n,A,B,C,D;
int a[maxn],f[maxn];
int L[maxn],R[maxn];
struct Stack{
    int top;
    int stk[maxn];
}mn,mx;
namespace tree1{
    int rt,segcnt;
    struct tree{
        int ls,rs,mx,tag;
    }tr[maxn<<1];
    inline void up(int p){tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);}
    inline void add(int p,int val){tr[p].mx+=val,tr[p].tag+=val;}
    inline void down(int p){if(tr[p].tag) add(ls(p),tr[p].tag),add(rs(p),tr[p].tag),tr[p].tag=0;}
    inline void build(int l,int r,int &p){
        p=++segcnt;tr[p].mx=tr[p].tag=0;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p));
    }
    inline void update(int l,int r,int L,int R,int val,int p){
        if(l>=L&&r<=R){add(p,val);return;}
        int mid=(l+r)>>1;down(p);
        if(L<=mid) update(l,mid,L,R,val,ls(p));
        if(R>mid) update(mid+1,r,L,R,val,rs(p));
        up(p);
    }
    inline int query(int l,int r,int L,int R,int p){
        if(l>=L&&r<=R) return tr[p].mx;
        int mid=(l+r)>>1,res=-inf;down(p);
        if(L<=mid) res=max(res,query(l,mid,L,R,ls(p)));
        if(R>mid) res=max(res,query(mid+1,r,L,R,rs(p)));
        return res;
    }
    inline void clear(){rt=segcnt=0;}
}
namespace tree2{
    int rt,segcnt;
    struct tree{
        int ls,rs;
        pii s;
    }tr[maxn<<1];
    inline void up(int p){tr[p].s=min(tr[ls(p)].s,tr[rs(p)].s);}
    inline void build(int l,int r,int &p){
        p=++segcnt;
        if(l==r){tr[p].s={0,l};return;}
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p));
        up(p);
    }
    inline void update(int l,int r,int pos,int val,int p){
        if(l==r){tr[p].s={val,pos};return;}
        int mid=(l+r)>>1;
        if(pos<=mid) update(l,mid,pos,val,ls(p));
        else update(mid+1,r,pos,val,rs(p));
        up(p);
    }
    inline pii query(int l,int r,int pos,int p){
        if(tr[p].s.fi>=pos) return {-1,-1};
        if(l==r) return tr[p].s;
        int mid=(l+r)>>1;
        if(tr[ls(p)].s.fi>=pos) return query(mid+1,r,pos,rs(p));
        else return query(l,mid,pos,ls(p));
    }
    inline void clear(){rt=segcnt=0;}
}
inline void clear(){
    for(re int i=0;i<=n;++i) L[i]=R[i]=-1;L[0]=1,R[0]=n;
    for(re int i=1;i<=n;++i) f[i]=0;
    mn.top=mx.top=0;
    tree1::clear();tree2::clear();
}
inline void solve(){
    cin>>n>>A>>B>>C>>D;clear();tree1::build(0,n,tree1::rt);tree2::build(0,n,tree2::rt);
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,x;i<=n;++i){
        while(mx.top&&a[mx.stk[mx.top]]<=a[i]) tree1::update(0,n,mx.stk[mx.top-1],mx.stk[mx.top]-1,-A*a[mx.stk[mx.top]],tree1::rt),--mx.top;
        tree1::update(0,n,mx.stk[mx.top],i-1,A*a[i],tree1::rt),mx.stk[++mx.top]=i;
        while(mn.top&&a[mn.stk[mn.top]]>=a[i]) tree1::update(0,n,mn.stk[mn.top-1],mn.stk[mn.top]-1,-B*a[mn.stk[mn.top]],tree1::rt),--mn.top;
        tree1::update(0,n,mn.stk[mn.top],i-1,B*a[i],tree1::rt),mn.stk[++mn.top]=i;
        x=a[i];
        tree2::update(0,n,x,i,tree2::rt);
        if(L[x]!=-1){
            int l=L[x],r=min(R[x],i);
            if(x!=0) L[x]=R[x]=-1;
            else L[x]=i+1;
            tree1::update(0,n,l-1,r-1,-C*x,tree1::rt);
            while(l<=r){
                pii res=tree2::query(0,n,r,tree2::rt);
                int pos=res.fi,val=res.se;++pos;
                if(l<=pos){
                    L[val]=pos,R[val]=r;
                    tree1::update(0,n,pos-1,r-1,C*val,tree1::rt);
                }
                else{
                    R[val]=r;
                    tree1::update(0,n,l-1,r-1,C*val,tree1::rt);
                }
                r=pos-1;
            }
        }
        f[i]=tree1::query(0,n,0,i-1,tree1::rt)+D;
        tree1::update(0,n,i,i,f[i],tree1::rt);
    }
    cout<<f[n]<<'\n';
}
signed main(){
    freopen("mix.in","r",stdin);
    freopen("mix.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;cin>>T;while(T--) solve();
    return 0;
}

一类二分

Minimax Problem

看到一堆 $\min,\max$ 套在一起，想到用二分去掉一个限制。

设当前二分到 $mid$，然后把 $\ge mid$ 的位置设为 $1$，其他位置设为 $0$。

然后把一行状压成一个数，那么当前答案合法当且仅当存在两个数或起来是全集。

判断就暴力 $\operatorname{dfs}$ 即可。

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

感觉类似套路的题有一车，就是二分答案，然后把大于答案的看成 $1$，小于的看成 $0$ 或者 $-1$。

最短路树/最短路 DAG

没咋做过这种题，但是最近见到了一些。

感觉这个概念好像也不太重要？

[COCI2008-2009#3] NAJKRACI

见到这道题后，想到的第一个暴力做法可能是：枚举边和点对，然后看这条边是否在两点的最短路上。

但两点间的最短路可能有多条，暴力判断也不太好判断。

我们考虑从点 $s$ 跑最短路，得到一张最短路 DAG。

对于一条在该 DAG 上的边 $(u,v)$ 来说，它的贡献为 $cnt_u\times sum_v$。

其中 $cnt_u$ 表示 $s$ 到 $u$ 的最短路数量，$sum_v$ 表示 $v$ 后面的点的数量。

具体实现可以先跑最短路，然后拓扑排序求 $sum_u$，不过我写了 $\operatorname{dfs}$，本质相同。

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1510,maxm=5e3+10,mod=1e9+7,inf=1e18;
int n,m,tot;
int head[maxn],dis[maxn],cnt[maxn],sum[maxn];
int ans[maxm];
bitset<maxn> vis;
struct edge{
    int to,nxt,w,id;
}e[maxm];
inline void add(int u,int v,int w){
    ++tot,e[tot]={v,head[u],w,tot};
    head[u]=tot;
}
inline void dij(int s){
    for(re int i=1;i<=n;++i) dis[i]=inf,vis[i]=0,cnt[i]=0;
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({0,s});dis[s]=0,cnt[s]=1;
    while(!q.empty()){
        int u=q.top().se;q.pop();
        if(vis[u]) continue;vis[u]=1;
        for(re int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                cnt[v]=cnt[u];
                q.push({dis[v],v});
            }
            else if(dis[v]==dis[u]+e[i].w) cnt[v]+=cnt[u];
        }
    }
}
inline void clear(){for(re int i=1;i<=n;++i) sum[i]=0;}
inline void dfs(int u){
    if(sum[u]) return;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(dis[v]==dis[u]+e[i].w){
            dfs(v);
            ans[e[i].id]=(ans[e[i].id]+cnt[u]*sum[v])%mod;
            sum[u]+=sum[v];
        }
    }
    ++sum[u];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v,w;i<=m;++i) cin>>u>>v>>w,add(u,v,w);
    for(re int i=1;i<=n;++i) dij(i),clear(),dfs(i);
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

模拟赛

数据范围：$1\le n \le 600$。

核心思路还是拆贡献。

设加进来的边为 $(u,v)$，考虑这条边带来的影响。

我们固定一个源点 $s$，设边 $(u,v)$ 会对 $(s,t)$ 产生影响，则 $dis_{s,u}+1+dis_{v,t}< dis_{s,t}$。

移项，得到 $dis_{s,u}< dis_{s,t}-dis_{v,t}-1$。

可以发现，这条边会使花费减少 $(dis_{s,t}-dis_{v,t}-1)-dis_{s,u}$。

考虑如何求出每条边带来的贡献。

可以发现，对于一对 $(u,v)$，合法的 $dis_{s,t}-dis_{v,t}-1$ 是一段后缀。

所以可以枚举 $v,t$，然后对每个点 $v$ 维护后缀和，同时还要维护个数。

然后枚举 $u,v$ 算贡献即可。

那么最后的答案就是选使花费减少的最多的那些边。

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

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=610;
int n,m,ans;
int dis[maxn][maxn];
bool vis[maxn][maxn];
int sum[maxn][maxn],cnt[maxn][maxn];
int c[maxn][maxn];
inline void Floyd(){
    for(re int i=1;i<=n;++i) dis[i][i]=0;
    for(re int k=1;k<=n;++k){
        for(re int i=1;i<=n;++i){
            for(re int j=1;j<=n;++j){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;memset(dis,0x3f,sizeof dis);
    for(re int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        dis[u][v]=dis[v][u]=1;
        vis[u][v]=vis[v][u]=1;
    }
    Floyd();
    for(re int i=1;i<=n;++i) for(re int j=i+1;j<=n;++j) ans+=dis[i][j];
    for(re int s=1;s<=n;++s){
        for(re int v=1;v<=n;++v){
            for(re int j=0;j<=n;++j) sum[v][j]=cnt[v][j]=0;
            for(re int t=1;t<=n;++t){
                int val=dis[s][t]-dis[v][t]-1;
                if(val<0) continue;
                sum[v][val]+=val;
                ++cnt[v][val];
            }
            for(re int j=n-1;j;--j){
                sum[v][j]+=sum[v][j+1];
                cnt[v][j]+=cnt[v][j+1];
            }
        }
        for(re int u=1;u<=n;++u){
            for(re int v=u+1;v<=n;++v){
                if(vis[u][v]) continue;
                int D=dis[s][u]+1;
                c[u][v]+=sum[v][D]-cnt[v][D]*dis[s][u];
            }
        }
    }
    int res=0;
    for(re int u=1;u<=n;++u){
        for(re int v=u+1;v<=n;++v){
            if(vis[u][v]) continue;
            res=max(res,c[u][v]);
        }
    }
    int num=0;
    for(re int u=1;u<=n;++u){
        for(re int v=u+1;v<=n;++v){
            if(vis[u][v]) continue;
            if(c[u][v]==res) ++num;
        }
    }
    cout<<ans-res<<' '<<num;
    return 0;
}