最小生成树

母题$Prim$ 母题$Kruskal$

最大边权最小的生成树

严格次小生成树

限定根最大度数的最小生成树

最短路径生成树

最优比率生成树

序列问题

1. 把一个序列A变成非严格单调递增的，至少需要修改 序列总长度-A的最长不下降子序列长度 个数。
2. 把一个序列A变成严格单调递增的，至少需要修改 构造序列B[i]=A[i]-i，序列总长度-B的最长不下降子序列长度 个数。
3. 把一个序列A变成严格单调的，至少需要花费多少偏移量？
4. 给定一个序列A，可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一，至少要修改 差分后的序列$\max(\sum|所有正数|,\sum|所有负数|)$ 次，且可以得到不同的序列 $|\sum|所有正数|-\sum|所有负数||+1$ 种。
5. 求序列A的最大连续子段和：$O(N)$扫描该数列，不断把新的数加入子段，当子段和变成负数时，把当前的整个子段清空。扫描过程中出现过的最大子段和即为所求。

K问题

• 第k小数

• 整体第k小数（静态）

  • 方法一：快速排序求第k小数

int n,k;
int a[N];

void quick_sort(int l,int r,int k)
{
    if(l>=r) return ;//不要忘记这里！！！
    int i=l,j=r,mid=a[(l+r)>>1];
    while(i<=j)
    {
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(j-l+1>=k) quick_sort(l,j,k);//！！！
    else quick_sort(i,r,k-(j-l+1));//！！！
    return ;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    quick_sort(1,n,k);
    printf("%d\n",a[k]);
    return 0;
}

  - 方法二：二分答案（铺垫整体二分）

    设当前二分的值是mid，统计序列里cnt个数≤mid。

    若k≤cnt，则答案一定在左半区间，继续二分；否则在一定在右半区间，令k-=cnt，继续二分。

1. 整体第k小数（动态修改）

   值域线段树
   1. 区间求不大于S的数的个数（动态修改）（铺垫整体二分）

   • 树状数组

     初始对于任意A[i]≤S，在树状数组中执行add(i,1);，表示在第i个位置上有一个不大于S的数（即第i个位置对答案的贡献+1）。

     询问时答案就是ans=ask(r)-ask(l-1);。

     修改A[i]=x时，若A[i]≤S，则执行add(i,-1);，表示删除第i个位置对答案的贡献；若x≤S，则再执行add(i,1);。然后别忘了维护原数组A[i]=x;。
     1. 区间第k小数（静态）

   • 方法一：整体二分

     把所有的操作（包括将数组的原值看作一开始就赋值的操作）先按时间排好序（本来就自然地排好序），然后只要进行1次值域上的二分：

     1. merge(lval,rval,st,ed)：值域为[L,R]的整数序列a，对操作序列q（含删除、赋值、询问）进行实现。
     2. 利用树状数组，在当前的序列a中，对于q的每个询问，统计不大于mid的数有c个。
     3. 若k≤c则将该询问加入操作序列lq中，否则令k-=c加入rq。
     4. 令整数序列a中≤mid的数构成整数序列la，>mid的数构成整数序列ra，操作序列q中涉及≤mid的数的操作构成操作序列lq，涉及≤mid的数的操作构成操作序列rq。注意保持操作的时间顺序。
     5. 还原树状数组，分治求解merge(lval,mid):la,lq和merge(mid+1,rval):ra,rq。边界：当操作序列为空时直接返回；当整数序列只剩1个数时得到答案。

int n,m;
int ans[N];
int tr[N];

int idx;
struct Data
{
    int op,x,y,z;
}q[N],lq[N],rq[N];

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)
{
    while(x<=n)
    {
        tr[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

void merge(int lval,int rval,int st,int ed)
{
    if(st>ed) return ;
    if(lval==rval)
    {
        for(int i=st;i<=ed;i++) if(q[i].op>0) ans[q[i].op]=lval;
        return ;
    }

    int mid=(lval+rval)>>1;
    int lqidx=0,rqidx=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op==0)
        {
            if(q[i].y<=mid)
            {
                add(q[i].x,1);
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z) lq[++lqidx]=q[i];
            else
            {
                q[i].z-=cnt;
                rq[++rqidx]=q[i];
            }
        }
    }

    for(int i=ed;i>=st;i--)
    {
        if(q[i].op==-1 && q[i].y<=mid) add(q[i].x,1);
        else if(q[i].op==0 && q[i].y<=mid) add(q[i].x,-1);
    }
    for(int i=1;i<=lqidx;i++) q[st+i-1]=lq[i];
    for(int i=1;i<=rqidx;i++) q[st+lqidx+i-1]=rq[i];
    merge(lval,mid,st,st+lqidx-1);
    merge(mid+1,rval,st+lqidx,ed);

    return ;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int val;
        scanf("%d",&val);
        q[++idx]={0,i,val};
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        q[++idx]={i,l,r,k};
    }
    merge(-INF,INF,1,idx);
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

  - 方法二：主席树

    p：前一个线段树，q：当前新建的线段树。

类似于动态开点新建一个节点q，节点q复制节点p的信息，随着p往下走在节点q新建新的信息。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,M=1e4+5;
int n,m;
int a[N];
vector<int> nums;
struct Tree //区间左右端点由函数中l和r决定
{
    int lson,rson;    ////lson：左儿子的编号（注意不是区间左端点）；rson：右儿子的编号；
    int cnt;    //当前区间所包含数的个数
}tr[N*4+N*17];
int root[N],idx;

int build(int l,int r)
{
    int p=++idx;    //类似于动态开点
    if(l==r) return p;
    int mid=(l+r)>>1;
    tr[p].lson=build(l,mid);
    tr[p].rson=build(mid+1,r);
    return p;
}

void pushup(int p)
{
    tr[p].cnt=tr[tr[p].lson].cnt+tr[tr[p].rson].cnt;
    return ;
}

//区间左右端点由函数中l和r决定
int insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];    //复制
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }

    //新建
    int mid=(l+r)>>1;
    if(x<=mid) tr[q].lson=insert(tr[p].lson,l,mid,x);
    else tr[q].rson=insert(tr[p].rson,mid+1,r,x);
    pushup(q);
    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1,cnt=tr[tr[q].lson].cnt-tr[tr[p].lson].cnt; //区间具有前缀和的性质，这样区间里的数就一定大于L
    if(k<=cnt) return query(tr[q].lson,tr[p].lson,l,mid,k);
    else return query(tr[q].rson,tr[p].rson,mid+1,r,k-cnt);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        nums.push_back(a[i]);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin();

    root[0]=build(0,nums.size()-1);

    for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,a[i]);

    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",nums[query(root[r],root[l-1],0,nums.size()-1,k)]);
    }

    return 0;
}

1. 区间第k小数（动态修改）

   • 方法一：整体二分（必须离线）

     结合第3小问，在第4小问增加修改操作：分成删除和增添操作。

int n,m;
int a[N];   //原数组
int ans[N];
int tr[N];  //树状数组维护单个区间静态第k小数

//操作序列（按时间排好序）
//当op=-1：删除某个位置上的数的贡献；0：在某个位置增添一个数的贡献；1：询问
int idx;
struct Data
{
    int op,x,y,z;
}q[N],lq[N],rq[N];  //q：当前操作序列；lq（rq）：分配到左（右）儿子的操作序列

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)
{
    while(x<=n)
    {
        tr[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

void merge(int lval,int rval,int st,int ed) //lval、rval：值域；st、ed：操作序列
{
    if(st>ed) return ;  //空操作序列，返回
    if(lval==rval)  //找到答案
    {
        for(int i=st;i<=ed;i++) if(q[i].op>0) ans[q[i].op]=lval;
        return ;
    }

    //分配到左儿子或右儿子
    int mid=(lval+rval)>>1;
    int lqidx=0,rqidx=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op==-1)
        {
            if(q[i].y<=mid) //按值域划分：对答案有贡献的数的值小于mid分到左儿子
            {
                add(q[i].x,-1); //删除某个位置上的数的贡献，而不是减这个数的值，因此修改操作分成的两个操作就算分道扬镳也不会影响正确性
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else if(q[i].op==0) //类似上面
        {
            if(q[i].y<=mid)
            {
                add(q[i].x,1);
                lq[++lqidx]=q[i];
            }
            else rq[++rqidx]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z) lq[++lqidx]=q[i];   //这个区间小于mid的数的个数大于k，因此答案应该在左儿子
            else
            {
                q[i].z-=cnt;    //注意分到右儿子前应减去左儿子的影响
                rq[++rqidx]=q[i];
            }
        }
    }

    for(int i=ed;i>=st;i--) //清空树状数组
    {
        if(q[i].op==-1 && q[i].y<=mid) add(q[i].x,1);
        else if(q[i].op==0 && q[i].y<=mid) add(q[i].x,-1);
    }
    for(int i=1;i<=lqidx;i++) q[st+i-1]=lq[i];  //节省空间
    for(int i=1;i<=rqidx;i++) q[st+lqidx+i-1]=rq[i];    //节省空间
    merge(lval,mid,st,st+lqidx-1);  //往下分治
    merge(mid+1,rval,st+lqidx,ed);  //往下分治

    return ;
}

int main()
{
    memset(ans,-1,sizeof ans);  //输出时方便判断是否为查询操作
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        q[++idx]={0,i,a[i]};
    }
    for(int i=1;i<=m;i++)
    {
        char op[2];
        scanf("%s",op);
        if(op[0]=='Q')
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            q[++idx]={i,l,r,k};
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);

            //修改操作可以分成2个操作。并且因此数组要开3*10^5！
            q[++idx]={-1,x,a[x]};
            q[++idx]={0,x,y};

            a[x]=y; //别忘记修改原数组
        }
    }
    merge(0,INF,1,idx);
    for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%d\n",ans[i]);
    return 0;
}

  - 方法二：主席树（可以在线）

• $\text{A*}$求第k短路

第一次出队是最短路，第k次出队是第k短路。

int h[N],rh[N],e[M],w[M],ne[M],idx;
int d[N],cnt[N];
int n,m,s,t,k;
bool vis[N];

void add(int hh[],int a,int b,int c){
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=hh[a];
    hh[a]=idx;
    return ;
}

//反向边求估价函数
void dij(){
    priority_queue<PII,vector<PII>,greater<PII> > q;
    memset(d,0x3f,sizeof d);
    d[t]=0;
    q.push({0,t});
    while(q.size()){
        auto t=q.top();
        q.pop();
        int u=t.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=rh[u];i!=0;i=ne[i]){
            int j=e[i];
            if(d[j]>d[u]+w[i]){
                d[j]=d[u]+w[i];
                q.push({d[j],j});
            }
        }
    }
    return ;
}

int A_star(){
    priority_queue<PIII,vector<PIII>,greater<PIII> > q;
    q.push({d[s],{0,s}});
    while(q.size()){
        auto tt=q.top();
        q.pop();
        int u=tt.second.second,dis=tt.second.first;
        cnt[u]++;
        if(cnt[t]==k) return dis;   //第一次出队是最短路，第k次出队是第k短路
        for(int i=h[u];i!=0;i=ne[i]){
            int j=e[i];
            if(cnt[j]<k) q.push({dis+w[i]+d[j],{dis+w[i],j}});
        }
    }
    return -1;
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b,l;
        cin>>a>>b>>l;
        add(h,a,b,l);
        add(rh,b,a,l);  //反向边求估价函数
    }
    cin>>s>>t>>k;
    if(s==t) k++;   //注意特判
    dij();  //预处理估价函数
    cout<<A_star()<<endl;
    return 0;
}

• Bellman-Ford求边数不超过k的最短路

int bellford(){
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int i=1;i<=k;i++){//用上一次的边权扩展，扩展k次，保证经过不超过k条边
        memcpy(last,d,sizeof d);
        for(int j=1;j<=m;j++){
            int w=q[j].first,u=q[j].second.first,v=q[j].second.second;
            d[v]=min(d[v],last[u]+w);
        }
    }
    return d[n];
}

• 求在从 1 到 N 的路径中，路径上第 k 大的值最小是多少

形如“最大值最小” / “最小值最大”之类的字眼：用二分求解。

自变量：x。

因变量：y，表示对于给定的 x ，从 1 到 N 的路径中最少要经过边权大于 x 的边有多少条。

判定：y≤k-1

我们设原边权大于 x 的边的新边权为 1 ，小于等于 x 的边新边权为 0，求出从 1 到 N 的最短路即为 y 的值。01边权双端队列BFS求解。

int n,m,k;

int h[N],e[M],w[M],ne[M],idx;

int dis[N]; //dis[u]：从1到u至少有多少条线路费用大于limit
bool vis[N];
deque<int> q;

void add(int a,int b,int c){
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    return ;
}

//双向队列BFS
bool check(int limit){
    memset(dis,0x3f,sizeof dis);
    memset(vis,false ,sizeof vis);
    dis[1]=0;
    q.push_front(1);

    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        if(vis[u]) continue;    //双段队列BFS是判断u而不是v
        vis[u]=1;
        for(int i=h[u];i!=0;i=ne[i]){
            int j=e[i],d=0;

            if(w[i]>limit) d=1;

            if(dis[j]>dis[u]+d){
                dis[j]=dis[u]+d;

                if(d==0) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    return dis[n]<=k-1;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    //二分答案转化为判定
    int l=0,r=INF;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }

    if(l==INF) puts("-1");
    else printf("%d\n",l);

    return 0;
}