Luogu P3381 最小费用最大流

费用流

最大流 && Dinic 算法 一文中,我们简述了网络流的概念及最大流的求法

但如果每条边不单单有流的限制,还有使用的费用,我们现在不光只求最大流,还要求费用最小

这就是最小费用最大流问题

继续阅读“Luogu P3381 最小费用最大流”

最大流 && Dinic 算法

最大流问题

给定一个有向图,有两个特别的点$S$和$T$,每条边都有一个容量限制 ,现询问,从 $ S $ 到 $ T $ 最大可以流多少过去

第一眼看过去,跟水厂子往水管里灌水一样简单

问题在于这个东西并不好计算

有没有办法计算它呢

如果我们每次都枚举我们怎么走的话,时间复杂度是不可估计的

我们有没有办法让我们走过去的流反悔呢?

有,这里就要引入两个概念: 残余网络 && 反向边

继续阅读“最大流 && Dinic 算法”

二分图最大匹配及其各种各样奇怪的概念与算法

二分图

对于一张图中的点,可以分成两组,其中,同一组内的点互不相连,则我们成这张图为二分图

由此可得一些东西

  • 我们可以通过交叉染色判定二分图,如果图$G$是二分图,则只需要两种颜色来染色
  • 不含奇数边环的图」就是二分图

匹配

匹配是一张图中一部分边的集合,这个集合内的边没有相交点

完美匹配

如果一个匹配中包含了这张图内所有的点,我们就称这个匹配为完美匹配

最大匹配问题

给你一张图,询问这张图的匹配最多包含多少个点,这个匹配被成为最大匹配,这个问题被称为最大匹配问题

匈牙利算法

交替路

从未匹配点出发依次经过匹配边与未匹配边的路我们称作交替路

增广路

从为匹配点出发走交替路走到一个未匹配点的交替路我们称其为增广路

增广路的非匹配边定会比匹配边多一条,故此我们可以通过查找增广路来改进现有匹配,如果一个匹配已走不出增广路那他就是最大匹配了

与最大匹配相关的定理

最小路径覆盖

点数 – 最大匹配数 = 最小路径覆盖

可谓是相当好理解了,如果有一个最小路径覆盖比当前少,则最大匹配一定会比当前多,那这还是最大匹配?

最小点覆盖

最小点覆盖 = 最大匹配数

详见 : [ König定理 ]

代码

// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
using namespace std;
//edge start
struct edge{
    int to,next;
}e[1100000];
int ehead[2100],ecnt;
inline void add(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
int u,v;
int n,m,ee;
int ans;
bool vis[2100];
int cx[1100],cy[1100];
int dfs(int now){
    for(int i=ehead[now];i;i=e[i].next){
        if(!vis[e[i].to]){
            vis[e[i].to]=true;
            if(cy[e[i].to]==false||dfs(cy[e[i].to])){
                cx[now]=e[i].to;
                cy[e[i].to]=now;
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&ee);
    for(int i=1;i<=ee;i++){
        scanf("%d%d",&u,&v);
        if(u<=n&&v<=m){
            add(u,v);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        ans+=dfs(i);
    }
    printf("%d",ans);
}

最大流方法

最大流也可以求解二分图最大匹配

设二分图中两组互不相连接的点集中任意一个集合为$U$,另一个为$V$,然后

  1. 将$ S $超级源点依次向 $ U $的每一个点连一条流量为 1 的边
  2. 将$ U $中的每一个点依次想$T$超级汇点连一条流量为 1 的边
  3. 将原二分图中每一条边的容量设为 1
  4. 跑最大流

别忘了反向边

]]>

内网穿透 (1) — ssh 反向代理

0 说在前面

因为各种各样奇怪的问题,各大公司学校,甚至一个家庭,都会有一个局域网,在学校和公司内部,甚至还会出现局域网套局域网的情况(毕竟一个路由器就可以组网了) ,形成一个树状结构,底层级的可以访问高层级,高层级却无法直接访问低层级

这个时候有两种解决方式

  • 端口转发
  • 内网穿透

端口转发需要硬件支持,而且一个端口最多只能整一台机子……(除非你的交换机支持多个IP你还会配置)

今天我们就来讲讲内网穿透最基础的实现方法 —— ssh 反向嗲里

1 关于ssh

说起ssh 并不是一个陌生的话题,在大多数时候,我们都会通过ssh远程控制服务器,以使用命令行,即使是内部的服务器也一样

ssh是一种加密的网络传输协议,在一定程度上避免了明文传输会带来的一系列分限

Warning: ssh 加密算法已经有能力被刺探及干扰,甚至有概率被破解,读取原文

2 故事背景

先让我们假设一个背景

现在有 3 台机子,网络访问情况如下:

  • A 位于 a 局域网内
  • B 位于 a b 两个局域网内
  • C 位于 b 局域网内

我们现在想让C能够访问A

我们将以B机作为代理机器,使C通过B访问A

3 ssh 的反向代理

ssh -R port:host:hostport

将远程主机(服务器)的某个端口转发到本地端指定机器的指定端口

我们可以这样理解:

  • port 为 B 机上用于反代的端口
  • host 为被代理的IP地址(A 机器 IP 地址 )
  • hostport 为 A 机器将要被代理的端口

反向代理需要 A 机器主动连接 B 机器,并需要以 root 身份登陆 B 机器

4 访问

如果是 A 网页需要在 C 上面可以访问,我们可以通过 Apache2 Nginx 等将上文的port 在转发到 80 / 443等端口上,不需要 C 可以通过 ssh 直接连接 B 来 访问 A

可以通过 ssh 密钥简化过程

如果出现因超时而自动断开的问题,可以在/etc/ssh/sshd_config 尾部加入以下命令

ClientAliveInterval 30 # B 每隔30秒发送一次请求给 A,然后 A 响应,从而保持连接
ClientAliveCountMax 3 #B 发出请求后,A 没有响应得次数达到3,就自动断开连接,正常情况下,A 不会不响应

5 附加

这里有一些可能有用的参数

-v 调试链接,会显示出详细问题
-f 后台运行 ssh
-N 不运行命令,仅转发端口
-C 允许压缩数据

]]>

通过 Certbot 申请 Let's Encrypt ECC 泛域名加密证书

0 ECC

参照维基百科: [椭圆曲线加密学]

ECC(椭圆曲线加密学)是一种公开密钥算法,相比较常见的RSA算法,在大多数情况下有着更加优秀的性能

1 生成

我们首先需要通过openssl生成通过ecc加密的 csr

先申请 key

openssl ecparam -genkey -name secp384r1 | openssl ec -out domain.key

然后通过 key 生成 csr

openssl req -new -sha256 -key domain-ecc.key -nodes -out domain.csr -outform pem

这一步中将会询问你一些关于你的信息,请务必注意Common Name这一行应填写你将要申请的域名,其他你随意就可以了

2 申请

有了csr文件,我们就可以欢乐申请证书

./certbot-auto certonly --csr elsenow-ecc.csr --manual --preferred-challenges dns --server https://acme-v02.api.letsencrypt.org/directory

3 部署

经过上面的命令,你的命令执行目录下应当有这几个文件

0000_cert.pem  - crt.pem
0000_chain.pem - chain.pem
0001_chain.pem - fullchain.pem
domain.key     - privatekey

请根据服务器按与部署普通证书一样的方法部署

]]>

Luogu P3231 [HNOI2013]消毒 — 二分图匹配

题目

题目链接: [https://www.luogu.org/problemnew/show/P3231]

先考虑一下,如果这张图是一个二维的情况?

对于每一个需要消毒的点的 $x,y$ 相互链接,然后直接跑最小点覆盖就对了

三维的情况?

三分图匹配?

不会,但是显然我们可以知道,如果我们设$ x $为三边中最小值则
$$ x \leq \sqrt[3]{5000} $$
也就约等于$$ x \leq 17$$

直接$ 2^{17} $ 枚举每一层选或者不选即可….

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
inline int Min(int a, int b) { return a < b ? a : b; }
const int N = 5e3 + 1e2;
const int INF = 0x4fffffff;
int T, u, v, w, op, res, ans;
int len[3], vis[30], match[30], vcnt, pos;
bool chose[30];
// edge start
struct edge {
    int to, next, val;
} e[N << 1];
int ehead[N], ecnt;
inline void add_edge(int now, int to, int val) {
    ecnt++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// edge end
inline void init() {
    memset(vis, 0, sizeof(vis));
    memset(ehead, 0, sizeof(ehead));
    ecnt = vcnt = 0;
    ans = INF;
}
inline void readin() {
    scanf("%d%d%d", &len[0], &len[1], &len[2]);
    if (len[0] <= len[1] && len[0] <= len[2])
        pos = 0;
    else if (len[1] <= len[2] && len[1] <= len[0])
        pos = 1;
    else
        pos = 2;
    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            for (int k = 1; k <= len[2]; k++) {
                scanf("%d", &op);
                if (!op)
                    continue;
                if (pos == 0)
                    add_edge(j, k, i);
                else if (pos == 1)
                    add_edge(k, i, j);
                else if (pos == 2)
                    add_edge(i, j, k);
            }
        }
    }
}
bool eft(int now) {
    for (int i = ehead[now]; i; i = e[i].next) {
        if (!chose[e[i].val] && vis[e[i].to] < vcnt) {
            vis[e[i].to] = vcnt;
            if (!match[e[i].to] || eft(match[e[i].to])) {
                match[e[i].to] = now;
                return true;
            }
        }
    }
    return false;
}
inline int get_ans(int now) {
    res = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= len[(pos + 1) % 3]; i++) {
        vcnt++;
        if (eft(i))
            res++;
        if (res + now >= ans)//最优化剪枝
      return ans;
    }
    return res + now;
}
void dfs(int now, int sum) {
    if (now > len[pos]) {
        ans = Min(get_ans(sum), ans);
        return;
    }
    chose[now] = 1;
    dfs(now + 1, sum + 1);
    chose[now] = 0;
    dfs(now + 1, sum);
}
inline void work() {
    dfs(1, 0);
    printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("bzoj.3140.in", "r", stdin);
    freopen("bzoj.3140.out", "w", stdout);
#endif
    scanf("%d", &T);
    while (T--) {
        init();
        readin();
        work();
    }
}
]]>

Codeforces Round #530 (Div. 2) 解题报告

A

题目大意: 有一个高h重w的雪球从山上滚下来,每下降一米,重量+=高度,中间会碰到两个石头,碰到后雪球减去石头的重量,问到达高度为 0 是重量为多少

小于0则看做0

模拟题……

#include <cstdio>
int w,h;
int u1,u2,d1,d2;
int main(){
    scanf("%d%d%d%d%d%d",&w,&h,&u1,&d1,&u2,&d2);
    while(h){
        w+=h;
        if(h==d1) w-=u1;
        if(h==d2) w-=u2;
        if(w<0) w=0;
        h--;
    }
    printf("%d",w);
}

B

现在需要画$n$个正方形,问最少需要几个单位线段可以保证画出来的$n$个正方形的每条边都可以通过已有线段平行得到

贪心就对了

#include <cstdio>
#include <cmath>
int n,tmp,ans;
int main(){
    scanf("%d",&n);
    tmp=std::sqrt(n);
    if(n%tmp==0){
        printf("%d",tmp+(n/tmp));
        return 0;
    }
    else {
        ans=tmp+(n/tmp);
        printf("%d",ans+1);
    }
}

C

给你一个字符串,如果一个字母后跟的是*表示这个字母可以被删除,保留或重复多次,如果跟的是?表示这个字母可以被删除或者保留,如果都不是,则表明其必须留在原位置

贪心题目,比较原字符串长度与要求的长度,然后分段讨论

#include <cstdio>
#include <cstring>
int k,len,zlen,sfcnt,tmp;
bool sf,cd;
char s[1000];
int main(){
    scanf("%s",s+1);
    scanf("%d",&k);
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(s[i]>='a'&&s[i]<='z')
            zlen++;
        if(s[i]=='?') sfcnt++;
        if(s[i]=='*') {cd=true;sfcnt++;}
    }
    if(zlen>k){
        if(sfcnt<zlen-k){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            if(s[i+1]=='?'||s[i+1]=='*'){
                if(zlen>k) {zlen--;sfcnt--;}
                else printf("%c",s[i]);
            }
            else printf("%c",s[i]);
        }
    }
    else if(zlen==k){
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else printf("%c",s[i]);
        }
    }
    else if(zlen<k){
        if(!cd){
            printf("Impossible");
            return 0;
        }
        for(int i=1;i<=len;i++){
            if(s[i]=='*'||s[i]=='?') continue;
            else if(s[i+1]=='*'){
                printf("%c",s[i]);
                while(1){
                   if(zlen>=k) break;
                   printf("%c",s[i]);
                   zlen++;
                }
            }
            else printf("%c",s[i]);
        }
    }
}

D

现在已知树的形态与奇数深度点到根的长度(最短路径所经过的边的边权和)

因为交叉未知……所以直接贪心!!!

#include <cstdio>
#include <cstdlib>
inline int Min(int a,int b){return a<b?a:b;}
const int N=1e5+2e4;
const int INF=2147483640;
int n,v;
long long sum=0;
int s[N],a[N],son[N];
// edge start
struct edge{
    int to,next;
}e[N<<1];
int ehead[N],ecnt;
inline void add_edge(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
void dfs(int now,int val){
    if(s[now]<=-1){
        int tmp=INF;
        for(int i=ehead[now];i;i=e[i].next){
            tmp=Min(s[e[i].to],tmp);
        }
        if(tmp==INF) return ;
        tmp-=val;a[now]=tmp;
        for(int i=ehead[now];i;i=e[i].next){
            s[e[i].to]-=val+a[now];
        }
        for(int i=ehead[now];i;i=e[i].next){
            dfs(e[i].to,val+a[now]);
        }
        return ;
    }
    a[now]=s[now];
    for(int i=ehead[now];i;i=e[i].next){
        dfs(e[i].to,val+a[now]);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&v);
        add_edge(v,i);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        if(s[i]!=-1&&s[i]<s[1]){
            printf("-1");
            return 0;
        }
    }
    dfs(1,0);
    sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]<0){
            printf("-1");
            return 0;
        }
        sum+=a[i];
    }
    printf("%lld",sum);
}
]]>

使用 dnsforwarder 建立本地 DNS 服务器避免 DNS 问题

0 事出有因

我们学校的网络似乎被污染了,目前看来dns污染是主要问题

dns 是使用udp明文传输的,监听和被污染的难度是相当的低的

然后就被污染了……

主要是 IP 解析出来会连接到一些比较奇怪的地方

正常的DNS延迟高到怀疑人生

看起来搭建一个自己的DNS服务器是非常有必要的了…

1 坑

如果想要直接看教程的话,建议从 2 部分看

一开始找到的解决方案是 dnsmasq 其并不支持 tcp 链接,而我们的 udp 访问方式已经被全端口污染了 ……

网上建议的方法是 pdnsd然而 Debian 官方库里并没有这个东西,而这个东西的源码感觉已经在互联网上销声匿迹了,而且它的已知的最后更新时间已经远在2012 年了……

然后我找到了 dnsforwarder

2 编译 && 安装

项目链接: [https://github.com/holmium/dnsforwarder]

将项目克隆到本地

git clone https://github.com/holmium/dnsforwarder.git
cd ./dnsforwarder

编译

make

安装

sudo make install

然后 dnsforwarder 便位于你的 /usr/bin/ 目录下,你就可以使用了

然而你直接运行本质上与和用 8.8.8.8是除了多了内存缓存是没有区别的…

3 配置

实际上如果你要看官方的 config 的话

它介绍的是挺清楚的

问题就是太清楚了,你要没有基础感觉就跟没学过英语的人读英翻英词典一样……

这里有一份推荐设置

LogOn true
LogFileThresholdLength 102400
LogFileFolder
UDPLocal 127.0.0.1:53
TCPGroup 208.67.220.220:5353 * no
GroupFile
BlockIP 243.185.187.39,46.82.174.68,37.61.54.158,93.46.8.89,59.24.3.173,203.98.7.65,8.7.198.45,78.16.49.15,159.106.121.75,69.63.187.12,31.13.76.8,31.13.64.49
IPSubstituting
BlockNegativeResponse false
Hosts
HostsUpdateInterval 18000
HostsDownloadPath
HostsScript
HostsRetryInterval 30
AppendHosts
BlockIpv6WhenIpv4Exists false
UseCache true
CacheSize 1048576
MemoryCache true
CacheFile
IgnoreTTL false
OverrideTTL -1
MultipleTTL 1
ReloadCache false
OverwriteCache false
DisabledType
DisabledDomain
DisabledList
DomainStatistic false
DomainStatisticTempletFile
StatisticUpdateInterval 29

这份配置使用了 TCP 链接,你可以设置端口或使用多个DNS

  • 开启了硬盘缓存 && 内存缓存
  • 避免了不存在IP
  • 监听本地53端口,非本机无法使用

然后更改 /etc/resolv.conf (dns配置文件) 的内容为

nameserver 127.0.0.1

执行以下命令防止被自动配置(DHCP) 覆盖

sudo chattr +i /etc/resolv.conf

Enjoy it!

04 日常使用

你可以把dnsforwarder设置为开机启动…..

不愿意的话,你可以每次开机执行这个东西qwq

]]>

私たち、 輝きたい! — Woshiluo 的 2018 总结

00 写在开头

私たち、 輝きたい!

我们,想要闪闪发光!

“2018年真的是有趣的一年呢”,Woshiluo 如是说道

说真的,别说在年初,就是在今年9月,我也想不到我现在会这样,作为一名省队选手在努力,在弱省中,书写着属于自己的篇章……

01 风平浪静的年初

一月初的时候逐渐找到了写作业的感觉,再也不用每天晚上写作业写到老晚了

期末成绩出来,英语满分?进步约100名?

寒假欢乐培训,在3&4班听金哥讲bfs,第一次发现常数问题是如此重要

在2班金哥讲了许多种类的DP,当时第一次接触邻接表,头还是晕的

暑假作业成功全部推到最后一天

期初考试,除去语文,我好像可以年级前十?

这一切听起来都是那么的有希望,仿佛只要今后一直努力下去,身上的兵二校服将会再穿五年

02 抛向湖面上的一颗石头

一次OI上课的机会,杨老师[我的Oi教练]表明了她想将我送去126中的思想,这个话题被在兵二的同班同学听到,回去报告给了班主任?

然后从此在我平静如水的生活中抛进了一块石头,至今它所引起的水波,仍未平静

兵二似乎对这个事情的反应有点大……

正当我企图一步步平静下来这些水波时,在五月份时,杨老师却也发出了最后通碟

兵二代表着稳健的前途,126中代表这遥不可及的梦想

那一阵子,我正在补Lovelive,在某一瞬间内,我也想到了自己,如果自己敢像千歌,像穗乃果一样,向着梦想奔跑,是否,也能够书写出属于自己的奇迹,属于自己的希望 ……

03 追寻着遥不可及的梦想

我最终还是选择来到了126中,每天下午过去学一下听起来很厉害的数据结构与神仙算法,实际上大家都没记住几个,但却对算法水平有了一个不易观察却很重要的提升

每天同时进行着文化课和OI的学习肯定是要付出代价的,过度的熬夜终究使自己在之后相当长一阵时间内的思维迟钝和身体不适,本来就处于亚健康的身体终究还是会隔三差五出现问题

但是那阵时间真的是相当欢乐的……

有着各种各样还算可以看清的目标,可以实现(?)的目标

那时我希望自己能够普及一等,明年参加提高,争取省队

04 宛若繁花般灿烂的暑假

暑假初每天在天百待着基本上就是语文数学OI(数学),当时`15owzLy1`大佬给我们讲数学,听说了好多自己根本没听说过的东西

杨老师告诉我7月底有个网安赛,没人去,我要不要过去凑个数,一问,吃住行参赛费用全免?去去去,西安三日游能不去吗

去了一趟西安,莫名奇妙随便写写就三等奖了?然后原来这比赛还是有奖金的?

感觉莫名奇妙减了不少rp,以及获得一个奥妙重重的称号网安选手

八月初杨老师告诉我们可以去常州集训?仔细想了想,去吧,看看内地的选手

后来被证实被虐成傻逼,不过也获得不少奇怪的加成……

不过也有负buff,养成了Oi考试睡觉的奇怪习惯……

值得一起的是我的手机成功在常州用上了内地的主板

05 接近又远离梦想的NOIP

开学以后,每天依然文化课Oi一同训练,然后 ,但是因为NOIP的原因每天培训时间加长了,身体终于还是打出了GG,要么停课要么放弃Oi,仔细想了想,我是因Oi而来,遂停课

Wahacerdalao向杨老师表明了觉得我可以参加提高组的思想,杨老师同意了这个看法

停课开始还好,过了一个月左右吧,成绩开始出现波动,然后开始疯狂爆炸,基本上每次垫底吧

连杨老师都说了,你这次还是参加普及组吧

那时感觉,自己好像选错了路,为什么不好好学文化课啊 ……

Wahacer Dalao告诉我,按照你自己的想法走就对了

仔细想了一想,还是去提高组一下,算是当经验吧,大体也不会太拉平均分

然后事情的结果就非常有意思了,详见[NOIP2018游记]

06 属于自己的未来

私たち、 輝きたい!

我们,想要闪闪发光

NOIP 成绩出来了,全省第四,XJ没有省选,直接A队

后面上了几天的课,又申请了停课,当我再坐到熟悉的电脑面前的时候,回忆起NOIP时,五味杂陈

开始几天将NOIP前埋的坑都填了(比如某个从NOIP前看到NOIP后的小说)

后来继续向前学,依然觉得什么东西不太对经,约是在12月底的时候我发现,我把Oi,学死了

开始好好认真的举一反三,锻炼思维的时候,已经是停课后两周

果然NOIP前的集训还是对我造成一定的负面心里阴影的

07 尾声

依稀记得Wahacer大佬坚持我应该参加提高组
依稀记得兵二同学们一起努力的次次活动
依稀记得常州淳朴的商店阿姨
依稀记得调到通宵图论
依稀记得调到半夜的Web
依稀记得写到深夜的作业
依稀记得看到半夜的动漫

我超额达成了自己的目标,于今年进入省队

我又有了新的目标,我想在接下来的舞台上闪闪放光

只要朝着梦想奔跑,总有一天会实现的吧?

尽自己努力,做自己最好

]]>

线段树?前缀和?主席树! — 主席树初步 — Luogu P3834 【模板】可持久化线段树 1(主席树)

值得一提的是,静态主席树比单纯的线段树求区间和要短……

0 前置技能点

  • 线段树
  • 前缀和
  • 离散化(权值线段树求第k大前置技能)
  • 正常状况下的大脑 一定的Debug能力

1 主席树

1.1 静态

1.1.1 权值线段树

我们现在看一下这个问题

区间第$k$大

我会排序!

$ N,M \leq 2e5$

我会排序!等下,时间复杂度不对

是的,显然这需要一个数据结构来维护它

我们来想想,如果只求第$k$大的话,有什么做法?

平衡树,权值线段树

加上区间查询?

我会Splay

嗯,Splay是一个比较优秀的解决方案,

但是权值线段树真的没有用武之地吗

1.1.2 可持久化

可持久化

这是一个非常有趣的名词

许多数据结构都可以可持久化

eg: 可持久化数组,可持久化平衡树,可持久化并查集等

什么是可持久化呢

可以访问历史版本的数据结构,我们通常就称其为可持久化数据结构

1.1.3 前缀和与权值线段树

我们先来回顾一下如果我们查询全局第$k$大时的步骤

  1. 离散化
  2. 按排名建立权值线段树
  3. 按照与二叉搜索树中查找第$k$大一样的方法查找并输出

有一种办法,建立 $ n^2 $ 棵线段树(枚举每个区间),但这种做法显然是不且实际的

但是如果我们仔细思考便会发现,我们对与区间$ [1,1] [1,2] [1,3] [1,4] \cdots [1,n] $ 中建立的权值线段树中的每一个节点都满足前缀和性质

也就是说我们只需要建立$n$棵权值线段树了

1.1.4 可持久化与权值线段树

到了这一步,我们的问题在空间与时间上都存在了

很明显,我们的空间有太多重复的叶子节点[区间相同,权值相同]

所以如果两个节点,它们的左节点(或者右节点)重复,我们可以将它们指向一个叶子

经过这么操作我们的时间也得到了大幅度优化,从原来的$O(n^2log(n))$变成了$O(nlog(n))$,空间也优化到$nlog(n)$

这么一来,这些线段树变成一个数据结构,我们可以访问历史版本

是的,这就是可持久化权值线段树,也称主席树

1.1.5 静态主席树

#include <cstdio>
#include <algorithm>
const int N=2e5+1e4;
int n,m,l,r,k,tcnt,idcnt;
int nid[N],rt[N],rk[N];
struct val{
    int now,id;
}a[N];
bool cmp(val a,val b){
    return a.now<b.now;
}
struct Persistable_Segment_Tree{
    int left,rig;
    int sum;
}tree[N*20];
void update(int &root,int left,int rig,int val){
    tree[tcnt++]=tree[root];
    tree[tcnt-1].sum++;
    root=tcnt-1;
    if(left==rig) return ;
    int mid=(left+rig)>>1;
    if(val<=mid) update(tree[root].left,left,mid,val);
    else update(tree[root].rig,mid+1,rig,val);
}
int query(int left_root,int rig_root,int k,int left,int rig){
    int dep=tree[tree[rig_root].left].sum-tree[tree[left_root].left].sum;
    if(left==rig) return left;
    int mid=(left+rig)>>1;
    if(k<=dep) return query(tree[left_root].left,tree[rig_root].left,k,left,mid);
    else return query(tree[left_root].rig,tree[rig_root].rig,k-dep,mid+1,rig);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    scanf("%d",&a[i].now);
    a[i].id=i;
    }
    std::sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    rk[a[i].id]=i;
    tcnt=1;
    for(int i=1;i<=n;i++){
    rt[i]=rt[i-1];
    update(rt[i],1,n,rk[i]);
    }
    for(int i=1;i<=m;i++){
    scanf("%d%d%d",&l,&r,&k);
    printf("%d\n",a[query(rt[l-1],rt[r],k,1,n)].now);
    }
}

1.2 动态(带修)

Waiting For Updating

]]>