01背包能不能输出哪些物品被选中了

题目要求区间 $[x,y]$ 和 $[m,n]$ 一模一样，我就考虑到了并查集。

$\forall\ i\in [x,y]$ 以及 $i$ 在 $[m,n]$ 中对应的格子，我们把这两个格子连边，这样经过若干次连便之后，凡是处在同一个联通块中的格子，取的数字必须是相等的。

如果目前得到了 $k$ 个连通块，则答案就等于 $9\times 10^{k-1}$。有 $1$ 在的那个连通块只能取 $1 \sim 9$ 这九个数字，而其他的 $k-1$ 个连通块可以取 $0\sim 10$ 这十个数字，根据乘法原理便可证明上式的正确性。

但是看一看数据范围，我们发现如果一条边一条边的连，早就 $TLE$ 了。

利用倍增的思想，我们考虑区间并查集。$f[i][j]$ 表示的含义是：以 $i$ 为左端点，长度为 $2^j$ 的一个区间。为了方便描述，我们令 $x=1,y=13,m=20,n=32$。这样两个区间，可以按照下图进行分割：

$merge$ 是并查集中的连边操作函数，那么我们在分割完区间之后需要进行的操作是：

merge{f[1][3],f[20][3]};
merge{f[9][2],f[28][2]};
merge{f[13][0],f[32][0]};

然后利用并查集统计答案。

记得要开 $long\ long$ 哦！

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

const int mod=1e9+7;
const int maxn=100005;

long long ans=1;
int n,m;
int f[maxn][20]; //f[i][j]：[i,j] --> id，他表示的含义是 [i,j] 区间所对应的编号 
int id;          //用于给区间编号 
int fa[maxn*20];
int s[maxn*20]; //s[i]：编号为 i 的区间的左端点 

void build(){
    for(int j=0;j<=log2(n);j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=++id;
            fa[id]=id;
            s[id]=i;
        }
    }
}

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void merge(int l1,int l2,int k){
    int p=find(f[l1][k]),q=find(f[l2][k]);
    if(p>q){
        swap(p,q);
    }
    fa[q]=p;
}

int main(){
    cin>>n>>m;
    build();
    for(int i=1;i<=m;i++){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        for(int k=log2(r1-l1+1);k>=0;k--){
            if(l1+(1<<k)-1<=r1){
                merge(l1,l2,k);  //合并区间 [l1,k] & [l2,k]
                l1+=(1<<k);
                l2+=(1<<k);
            }
        }
    }
    for(int k=log2(n);k>0;k--){
        for(int i=1;i+(1<<k)-1<=n;i++){
            int pa=find(f[i][k]);
            int spa=s[pa];      //pa 区间的左端点 
            merge(spa,i,k-1);
            merge(spa+(1<<k-1),i+(1<<k-1),k-1);
        }
    }
    for(int i=2;i<=n;i++){          //注意 i 从 2 开始，因为 f[1][0] 代表的是 1 所在的那个连通块，而这个连通块是需要乘以 9 的，并不需要乘以 10，所以会放在输出的时候特殊处理 
        if(f[i][0]==find(f[i][0])){ //这个判断结果如果为真，那么就是找到了一个连通块，ans需要乘以 10 
            ans=ans*10ll%mod;
        }
    }
    cout<<ans*9%mod<<endl;
    return 0;
}

想问一下，treap 的旋转是如何进行的，最好是能够用动图直观展示，谢谢大佬！

为了方便分析问题，我们假设 $n=3$。数字 $1\sim 3$ 总共有 $n!=6$ 种排列。则：
$$
k=1时，有这几种排列情况\begin{cases}
1,2,3
\end{cases}
$$
$$
k=1时，有这几种排列情况\begin{cases}
1,3,2\
2,1,3
\end{cases}
$$
$$
k=2时，有这几种排列情况\begin{cases}
2,3,1\
3,1,2
\end{cases}
$$
$$
k=3时，有这几种排列情况\begin{cases}
3,2,1
\end{cases}
$$
以 $k=2，k-1=1$ 两个例子来举例，画出如下的图：

同行比较的话，可以发现，欲使逆序对的数量减少 $1$，只需要把 $n$ 这个数与它后一个数交换位置即可。反过来也一样，欲使逆序对的数量增加 $1$，只需要把 $n$ 这个数与它前一个数交换位置即可。也就是说红色集合圈与绿色集合圈实现了一个相互映射：

这又引出了另一个问题：如果 $n$ 在第一位，或者最后一位，那它就无法与它后一个数或者前一个数交换位置。

因此，$n$ 在第一位，或者最后一位的情况时无法参与到映射中的。根据数学知识，$n$ 在第一位是包含于红色集合圈的，$n$ 在最后一位也是包含于绿色集合圈的，这两种情况需要排除，也就是下图中紫色蓝色集合圈不参与映射：

现在有了这些分析，我们开始推到递推方程。假设 $f[n][k]$ 代表的含义是 $1,2,\ldots n$ 的所有排列中，逆序对数量等于 $k$ 的方案数。

在左图中，真正参与的是红色集合圈减去紫色集合圈，也就是 $f[n][k]-f[n-1][k]$。因为 $n$ 是最大数，放在最后一位对逆序对的贡献是 $0$，也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k$，所以紫色集合圈就是 $f[n-1][k]$。

同理，右图中真正参与的是绿色集合圈减去蓝色集合圈，也就是 $f[n][k-1]-f[n-1][k-n]$。当 $n$ 在第一位时，它大于后面所有的 $n-1$ 个数，所以对逆序对数量的贡献是 $n-1$，也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k-1-(n-1)=k-n$即可，所以蓝色集合圈就是 $f[n-1][k-n]$。

既然两者数量上相等，所以等式 $f[n][k]-f[n-1][k]=f[n][k-1]-f[n-1][k-n]$ 就成立，通过移项，就是：
$$
f[n][k]=f[n][k-1]+f[n-1][k]-f[n-1][k-n]
$$
这就是最后的递推方程。

$AC$ 代码如下：

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

const int mod=1000000007;
const int maxn=1005;
const int maxk=10005;

int n,k;
bool mem_flag[maxn][maxk];
int mem[maxn][maxk];

long long f(int n,int k){
    if(k<0) return 0;
    if(n==0 && k==0) return 1;
    if(n==0 && k>0) return 0;
    if(mem_flag[n][k]) return mem[n][k];

    long long ret=f(n-1,k)+f(n,k-1)-f(n-1,k-n);
    ret%=mod;
    mem_flag[n][k]=true;
    return mem[n][k]=ret;
}

int main(){
    scanf("%d%d",&n,&k);
    printf("%d\n",(f(n,k)+mod)%mod);
    return 0;
}

学习笔记目录
有任何问题，欢迎私信/评论。
码字不易，求点赞啦~

网络流的基本概念

网络

网络指的是一张有向图。图中每一条边都有一个权值 $c(u,v)$ ，叫做边的容量。

图中还有两个特殊的点：源点 $s$ 与汇点 $t$。

流量

定义 $f(u,v)$ 是一条边 $(u,v)$ 的流量，那么 $f(u,v)$ 满足如下性质：

• 一条边的流量不得大于它的容量，$f(u,v)\leq c(u,v)$。
• 每条边的流量与其相反边的流量之和为 $0$，$f(u,v)+f(v,u)=0$。
• 从源点流出的流量等于汇点流入的流量。$\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$。

可以把流量理解为城市排水系统中的水流。

本题 我的主要思路如下：

假设完成第 $i$ 个运输任务耗时 $t_i$ ，然后二分答案，假设当前二分得到的答案是 $x$，如果 $t_i<=x$ 则无需考虑，对于 $t_i>x$ 的运输计划 $i$，虫洞必须要在这条路径上，才有可能使得最后的耗时小于等于 $x$。也就是对于所有 $t_i > x$ 的路径，标记每条边经过的次数。

最后，从交集里面选最长的边 $l$，如果能满足所有 $t_i-l<=x$，说明 $x$ 可行，否则 $x$ 不可行。

现在蒟蒻已经打出了大部分代码，但唯独不太会标记边经过的次数。想请教一下大佬，这标记该怎么实现呢？（暴力除外）