blog's People
Watchers
blog's Issues
友链
nalemy
link: //nalemy.top/
cover: //nalemy.top/img/logo.jpg
avatar: //nalemy.top/img/logo.jpg
RJlalala
link: //www.cnblogs.com/RJlalala
cover: //cdn.luogu.com.cn/upload/usericon/503670.png
avatar: //cdn.luogu.com.cn/upload/usericon/503670.png
小修小补 #2
LeanCloud 如修。
要挂数据删除才能正常用。
Blog 索引
君のこころは輝いてるかい？
基本都是我乱写的。
为了便于挑选文章，下面有几种标记 ：
-
$\color{blue}\large\circledcirc$ 意为 内容完善 -
$\color{red}\large\circledcirc$ 意为 内容简略/尚不完整 -
$\color{purple}\large\circleddash$ 意为 施工中/内容不严谨 -
$\checkmark$ 意为 推荐 -
$\dag$ 意为 过时/可能存在错误
- 数据结构
-
可持久化线段树
$\color{red}\large\circledcirc$ -
整体二分
$\color{red}\large\circledcirc$ $\dag$ -
dsu on tree
$\color{red}\large\circledcirc$ -
平衡树合并
$\color{blue}\large\circledcirc$ $\checkmark$
-
可持久化线段树
- 数学
- 图论
- 动态规划
- 杂
-
高维前缀和/sosdp
$\color{blue}\large\circledcirc$ -
切比雪夫距离与曼哈顿距离
$\color{blue}\large\circledcirc$ $\checkmark$
-
高维前缀和/sosdp
等我写了 200 道就发出来。
也许是文化课相关内容，或者是我感兴趣的一些研究，再者就是杂谈。
AT_abc290_g 题解
“空高く舞う鳥へ かさねたハート”—— 《Jump up HIGH!!》
题意简述
有一颗深度为
分析
考虑选择 所有 大小大于等于
感性理解一下，考虑为什么是对的。在原树上的任意一棵子树都可以看成一棵树，树的根节点往上有一条链。先不考虑链，原问题变成了有一颗满
复杂度
代码
const int N = 70;
int a[N];
int D,K,X;
signed main(){
int t;
cin >> t;
while(t--){
cin >> D >> K >> X;
a[0] = 1;
for(int k=1;k<=D;k++)
a[k] = a[k-1]*K+1;
int ans = 1e18;
for(int k=0;k<=D;k++){
if(a[k]>=X){
int tmpans = k!=D;
int x = a[k]-X,j = k-1;
while(x&&~j){
tmpans += x/a[j];
x %= a[j];
j--;
}
ans = min(ans,tmpans);
}
}
cout << ans << endl;
}
return 0;
}闲话
考场写了个只选择最小的大小大于等于
圆方树
模拟赛考到了，正好写一下。
简介
圆方树是一种将图变成树的方法，解决一些路径连通性相关的东西或者是仙人掌。
描述
前置知识：点双连通分量。以下不考虑孤立点。
在圆方树中，原来的点为圆点，点双为方点。每个点双内部是一个菊花图 1，多个菊花图通过原图中的割点连接在一起。
圆方树有
性质
圆方树有优美的性质。
- 无论如何换根，圆方树形态不变
- 圆方树的子树 = 原仙人掌的子仙人掌
- 相同种类的点不会相连
算法
在找点双的时候，新找到一个点双就新建一个方点，与点双内部所有点连边即可。
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
stk[++top] = u;
for(auto v:g[u]){
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v]>=dfn[u]){
nod++;
do{
Tree::g[stk[top]].push_back(nod);
Tree::g[nod].push_back(stk[top--]);
}while(stk[top+1]!=v);
Tree::g[u].push_back(nod);
Tree::g[nod].push_back(u);
}
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}题目
无向图相关
[APIO2018] 铁人两项
建出圆方树，枚举中转点
-
$c$ 为圆点，$c$ 的每一个儿子$v$ 子树内的点都能和其他子树内的点组成合法的$(s,f)$ ，贡献为$size_v \times (size_c-size_v-1)$ （$size$ 是原本的树的大小）。 -
$c$ 为方点，计算的是以这个点双中的某个点作为$c$ ，$(s,f)$ 中至少有一个点在点双内，且没有被圆点统计到的答案。$(s,f)$ 中有一个点在点双内，共有$deg_c-1$ 种，但是在割点出被圆点统计到了一次，所以有$deg_c-2$ 种。
用换根 DP 也统计父亲的答案就行了。
typedef long long ll;
const int N = 200005;
ll ans;
int n,m;
namespace Tree{
vector<int> g[N];
int siz[N],fa[N],siz2[N],deg[N];
void dfs1(int u){
siz[u] = u<=n;
for(auto v:g[u]){
if(v==fa[u])
continue;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
}
}
void dfs2(int u){
if(fa[u])
siz2[u] = siz2[fa[u]]+siz[fa[u]]-siz[u];
for(auto v:g[u])
if(v!=fa[u])
dfs2(v);
int sum = siz[u]+siz2[u];
if(u<=n){
for(auto v:g[u])
if(v!=fa[u])
ans += (ll)(sum-siz[v]-1)*siz[v];
ans += (ll)(sum-siz2[u]-1)*siz2[u];
}
else{
for(auto v:g[u])
if(v!=fa[u])
ans += (ll)(sum-siz[v])*siz[v]*(deg[u]-2);
ans += (ll)(sum-siz2[u])*siz2[u]*(deg[u]-2);
}
}
}
namespace Graph{
vector<int> g[N];
int dfn[N],low[N],idx;
int stk[N],top;
int nod;
void dfs(int u,int father){
auto add = [](int a,int b){
Tree::g[a].push_back(b);
Tree::g[b].push_back(a);
Tree::deg[a]++;
Tree::deg[b]++;
};
dfn[u] = low[u] = ++idx;
stk[++top] = u;
for(auto v:g[u]){
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v]>=dfn[u]){
nod++;
do{
add(nod,stk[top--]);
}while(stk[top+1]!=v);
add(nod,u);
}
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
inline void build(int u){
if(!nod)
nod = n;
dfs(u,0);
}
}
int main(){
n = in(),m = in();
for(int k=1;k<=m;k++){
int a = in(),b = in();
Graph::g[a].push_back(b);
Graph::g[b].push_back(a);
}
for(int k=1;k<=n;k++)
if(!Graph::dfn[k]){
Graph::build(k);
Tree::dfs1(k);
Tree::dfs2(k);
}
out(ans);
return 0;
}CF487E Tourists
经过的点双的并就是所有可能路径的并，也就是问经过的所有点双中边权的最小值。
建圆方树，查询可以用树剖解决，问题在修改。
修改时计算更新所有相连的方点是不行的，菊花图就可以卡掉。
一个圆点的贡献挂到父亲上，父亲一定是方点。但是这样点双会缺一个点，缺的是深度最小的圆点，这个点被计算到了上方的点双里。
查询
对每个方点维护一个 multiset，查询用树剖 + 线段树求最小值。
const int N = 200005;
int w[N];
int n,m;
namespace Tree{
vector<int> g[N];
int fa[N],dep[N],siz[N],son[N],top[N],dfn[N],idx;
multiset<int> s[N];
int m;
class segtree{
private:
int tr[N<<2];
inline void pushup(int x){
tr[x] = min(tr[x<<1],tr[x<<1|1]);
}
public:
segtree(){memset(tr,0x3f,sizeof(tr));}
void update(int u,int l,int r,int x,int c){
if(l==r){
tr[u] = c;
return;
}
int mid = (l+r)>>1;
if(x<=mid)
update(u<<1,l,mid,x,c);
else
update(u<<1|1,mid+1,r,x,c);
pushup(u);
}
int query(int u,int l,int r,int L,int R){
if(l>=L&&r<=R)
return tr[u];
int mid = (l+r)>>1,ans = 1e9;
if(L<=mid)
ans = min(ans,query(u<<1,l,mid,L,R));
if(R>mid)
ans = min(ans,query(u<<1|1,mid+1,r,L,R));
return ans;
}
}tr;
void dfs1(int u){
siz[u] = 1;
for(auto v:g[u]){
if(v==fa[u])
continue;
fa[v] = u;
dep[v] = dep[u]+1;
dfs1(v);
siz[u] += siz[v];
if(siz[v]>siz[son[u]])
son[u] = v;
}
}
void dfs2(int u,int tp){
dfn[u] = ++idx;
top[u] = tp;
if(son[u])
dfs2(son[u],tp);
for(auto v:g[u]){
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
inline void add(int x,int c,bool flag=true){
if(flag&&fa[x])
s[fa[x]].erase(s[fa[x]].find(w[x]));
w[x] = c;
if(!fa[x])
return;
s[fa[x]].insert(c);
tr.update(1,1,m,dfn[fa[x]],*s[fa[x]].begin());
}
inline int query(int x,int y){
int ans = 1e9;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
ans = min(ans,tr.query(1,1,m,dfn[top[x]],dfn[x]));
x = fa[top[x]];
}
if(dep[x]<dep[y])
swap(x,y);
ans = min(ans,tr.query(1,1,m,dfn[y],dfn[x]));
if(y<=n)
ans = min(ans,w[y]);
else
ans = min(ans,w[fa[y]]);
return ans;
}
}
namespace Graph{
vector<int> g[N];
int dfn[N],low[N],idx;
int stk[N],top;
int nod;
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
stk[++top] = u;
for(auto v:g[u]){
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v]>=dfn[u]){
nod++;
do{
Tree::g[stk[top]].push_back(nod);
Tree::g[nod].push_back(stk[top--]);
}while(stk[top+1]!=v);
Tree::g[u].push_back(nod);
Tree::g[nod].push_back(u);
}
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
inline void build(){
nod = n;
dfs(1,0);
Tree::m = nod;
}
}
int main(){
n = in(),m = in();
int q = in();
for(int k=1;k<=n;k++)
w[k] = in();
for(int k=1;k<=m;k++){
int a = in(),b = in();
Graph::g[a].push_back(b);
Graph::g[b].push_back(a);
}
Graph::build();
Tree::dfs1(1);
Tree::dfs2(1,1);
for(int k=1;k<=n;k++)
Tree::add(k,w[k],false);
while(q--){
char ops = getchar();
while(ops!='C'&&ops!='A')
ops = getchar();
int x = in(),y = in();
if(ops=='C')
Tree::add(x,y);
else{
out(Tree::query(x,y));
putchar('\n');
}
}
return 0;
}Footnotes
-
存在一个点为支配点，其余点之间没有边相连，则这个图为菊花图（简单来说就是存在一个点与所有点相连，其余的点之间没有边）。 ↩
小修小补 #3
更换英文字体为等宽字体。
更换网站图标，现为津岛善子头上的丸子（よしこ玉）。
网络流常见建模
本文主要讲建图方法，定义和证明内容较少。
正好网络流二十四题做完了整理下。
目录
- 网络流模型
- 最大流最小割
- 最小割树
- 平面图最小割
- 费用流
- SSP 算法
- 有负圈的费用流
- 上下界建模
- 无源汇上下界可行流
- 有源汇上下界可行流
- 有源汇上下界最大/小流
- 最大流最小割
- 经典问题
- 二分图
- 二分图最大匹配
- 二分图最小点覆盖
- 二分图最大独立集
- 路径覆盖与链覆盖
- DAG 最小路径覆盖
- DAG 最小链覆盖
- DAG 最长反链
- 最大权闭合子图
- 最大密度子图
- 二分图
- 各种建模
- 分层图/拆点
- 最大流相关
- 最小割相关
- 最小割离散变量模型（切糕）
- 费用流相关
- 杂
- 区间问题常见建模
网络流模型
最大流最小割
最大流 = 最小割是网络流中的重要结论，运用最大流和最小割可以解决一些复杂度划分问题。
最小割树
主要解决 多次询问 无向图两点之间的最小割的问题。
一个
Gomory-Hu 算法
考虑分治，在所有点中任取两个作为源汇点求出最小割，划分成两个互不连通的割集。对这两个点连边，边权为求出来的最小割。然后对与两个割集递归下去做。同时每次的最小割都是对于全局跑的，
询问两个点之间的最小割，就是求这两个点在最小割树上的路径中最小的边。可以用倍增实现。
参考&例题
平面图最小割
平面图最小割 = 对偶图最短路。
平面图
如果图
对偶图
设
- 在
$G$ 的每个面放$R_i$ 置 $G^$ 的一个顶点 $v^$。 - 设
$e$ 为$G$ 的一条边，若$e$ 在$G$ 的面$R_i$ 和$R_j$ 的公共边上，做 $G^$ 的边 $e^$ 与$e$ 相交，且 $e^$ 连接 $G^$ 的顶点 $v_i^,v_j^$，即 $e^=(v_i^,v_j^)$，$e^$ 不与其他边相交。若$e$ 为$G$ 中的桥且在$R_i$ 的边界上，则 $e^$ 是以 $R_i$ 中顶点 $v_i^$ 为端点的环，即 $e^=(v_i^,v_j^*)$。
形象化的说，对偶图就是把平面图的每条边 旋转了
对偶图的性质
-
$G^*$ 为平面图，且为平面嵌入。 -
$G$ 中自环对应 $G^$ 桥，$G$ 中桥对应 $G^$ 自环。 -
$G^*$ 是连通的。 - 若
$G$ 的面$R_i,R_j$ 的边界上至少有两条公共边，则关联
$v_i^,v_j^$ 的边有平行边，$G^*$ 多半是多重图。 - 同构的图的对偶图不一定是同构的。
-
$G^{**}$ 与$G$ 同构当且仅当$G$ 是连通图。 - 平面图最小割 = 对偶图最短路
参考&例题
费用流
可以解决一些需要最优化的问题。
SSP 算法
每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。
如果图上存在单位费用为负的圈，SSP 算法正确无法求出该网络的最小费用最大流。
设该网络的最大流为
实现
只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。
参考&例题
有负圈的费用流
由于存在最短路，所以费用流算法不能直接做费用有负圈的图。
消圈算法本身就有消除负圈的过程，但是效率低下。
对于网络中的负费用边
跑有源汇上下界最小费用最大流即可。
例题
上下界建模
上下界网络流本质是给流量网络的每一条边设置了流量上界
无源汇上下界可行流
先假设每条边已经流了
最大流需要满足初始流量平衡条件，但是构造出来的初始流很有可能不满足初始流量平衡。
假设一个点初始流入流量减初始流出流量为
-
$M=0$ 流量平衡 -
$M>0$ 入流量大，$S$ 向其连流量为$M$ 的边 -
$M<0$ 出流量大，其向$T$ 连流量为$-M$ 的边
如果附加边满流，说明这一个点的流量平衡条件可以满足，否则这个点的流量平衡条件不满足。
在建图完毕之后跑
有源汇上下界可行流
设源点为
注意这里的源汇点已被视为普通点，与超级源汇点不同的。
有源汇上下界最大/小流
最大流
先找到可行流，然后删去附加边
将可行流流量和最大流流量相加即为答案。
最小流
先在没加附加边的网络上跑最大流，再对残量网络加入附加边
例题
经典问题
二分图
二分图最大匹配
将源点连上左边所有点，右边所有点连上汇点，容量dou为
如果用 Dinic 算法求最大流，时间复杂度为
二分图最小点覆盖
最小点覆盖：选最少的点，满足每条边至少有一个端点被选。
König 定理：最小点覆盖
二分图最大独立集
最大独立集：选最多的点，满足两两之间没有边相连。
二分图中，最大独立集
因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大。
参考
路径覆盖与链覆盖
DAG 最小路径覆盖
DAG 最小路径覆盖：尽可能少的不相交的路径（链）覆盖掉所有节点。
考虑把单个结点也看成一条路径，相邻结点合并路径条数就会减少，所以要最大化可以合并的个数。
因为是最大化合并，考虑 二分图最大匹配 ，把每个点拆成
DAG 最小链覆盖
DAG 最小链覆盖：尽可能少的的路径（链）覆盖掉所有节点，可以相交。
最小链覆盖与最小路径覆盖非常相近，考虑将最小链覆盖转化为最小路径覆盖。
用 Floyd 求出原图的传递闭包，直接在传递闭包上跑最小路径覆盖即可。
传递闭包：这里简单理解为对于所有联通的点对连边的新图
DAG 最长反链
反链：点的集合满足任意
$x,y$ ，$x,y$ 互不连通
Dilworth 定理：最小链覆盖大小
最大权闭合子图
闭合子图：对于点集
$S$ ，任意$u\in S$ ，$u$ 的出边的另一个点也属于$S$ 。
最大权闭合子图：点权和最大的闭合子图。
最大权闭合子图
例题
最大密度子图
最大密度子图：闭合子图使得
$\frac{|E|}{|V|}$ 最大。
一般情况下，我们使用 01 分数规划 解决最大密度子图问题。
AT_abc279_f 并查集题解
“我仍然在无人问津的阴雨霉湿之地” —— 《世末歌者》
题目分析
由于要支持类似合并集合的操作，首先想到并查集。但是题目中的把
所以我们对于题目中的每个把
每个合并操作新建一个节点，至多有
代码
const int N = 1000005;
int c[N],w[N];
//c是每个箱子对应的是哪个并查集节点
//w是每个球对应的是哪个并查集节点
int ans[N];//每个并查集节点对应的是哪个箱子
int fa[N];
int n,q;
int find(int x){
if(fa[x]==x)
return fa[x];
return fa[x]=find(fa[x]);
}
int main(){
cin >> n >> q;
for(int k=1;k<=n;k++)
fa[k] = ans[k] = c[k] = w[k] = k;
int siz = n,idx = n;
while(q--){
int ops;
cin >> ops;
if(ops==1){
int x,y;
cin >> x >> y;
fa[c[y]] = c[x];
c[y] = ++idx;
fa[idx] = idx;//对于 y 新建一个并查集节点
ans[idx] = y;
}
else if(ops==2){
int x;
cin >> x;
w[++siz] = c[x];
}
else{
int x;
cin >> x;
cout << ans[find(w[x])] << endl;
}
}
return 0;
}闲话
这可比写个合并平衡树之类的代码短多啦，代码量低于 1kb。
小修小补
换了个背景，修了下字体。
更加舒服啦～
office 365 E5 开发者订阅弄好啦～
希望能自动续期。
5T 的 onedrive 真舒服。
风格改变 #1
从今天开始我求
预告 #1
过几天发篇网络流总结。
可持久化线段树 basic!
都是典中典，我之前还不是很会。
简介
对于一颗正常的线段树，如果要支持所有版本都既可以访问又可以修改（完全可持久化），对于每个版本保存一颗线段树是不可接受的。
发现每次修改操作修改的点的个数只有
区间问题
大概就是两个区间范围限制，一个用值域搞掉，一个用根节点搞掉。
静态区间第 k 大
考虑全局第 k 大怎么用线段树做，对值域建线段树，然后在线段树上二分。如果问题为求
回到原问题，发现我们统计的信息是前缀和，在二分时将
int a[N];
int n,q;
class persistent_segtree{
private:
class tree{
public:
int l,r,c;
}tr[N<<5];
int idx;
public:
int rt[N];
void build(int &u,int l,int r){
u = ++idx;
if(l==r)
return;
int mid = (l+r)>>1;
build(tr[u].l,l,mid);
build(tr[u].r,mid+1,r);
}
void modify(int u,int &v,int l,int r,int x,int c){
v = ++idx,tr[v] = tr[u];
tr[v].c += c;
if(l==r)
return;
int mid = (l+r)>>1;
if(x<=mid)
modify(tr[u].l,tr[v].l,l,mid,x,c);
else
modify(tr[u].r,tr[v].r,mid+1,r,x,c);
}
int query_Kth(int u,int v,int l,int r,int K){
if(l==r)
return l;
int mid = (l+r)>>1,c = tr[tr[v].l].c-tr[tr[u].l].c;
if(c>=K)
return query_Kth(tr[u].l,tr[v].l,l,mid,K);
return query_Kth(tr[u].r,tr[v].r,mid+1,r,K-c);
}
}tr;
vector<int> ha;
inline int h(int x){
return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;
}
int main(){
n = in(),q = in();
for(int k=1;k<=n;k++)
ha.push_back(a[k]=in());
sort(ha.begin(),ha.end());
ha.erase(unique(ha.begin(),ha.end()),ha.end());
int m = ha.size();
tr.build(tr.rt[0],1,m);
for(int k=1;k<=n;k++){
int x = h(a[k]);
tr.modify(tr.rt[k-1],tr.rt[k],1,m,x,1);
}
while(q--){
int l = in(),r = in(),K = in();
out(ha[tr.query_Kth(tr.rt[l-1],tr.rt[r],1,m,K)-1]);
putchar('\n');
}
return 0;
}带修区间第 k 大
和静态一样，利用前缀和的性质。暴力修改前缀和是不可接受的，考虑用树状数组维护主席树的根节点，每次取出树状数组的
时间复杂度
class persistent_segtree{
private:
class tree{
public:
int l,r,c;
}tr[N<<6];
int idx;
inline void pushup(int x){tr[x].c = tr[tr[x].l].c+tr[tr[x].r].c;}
public:
int rt[N];
void modife(int u,int &v,int l,int r,int x,int c){
if(!v)v = ++idx;
tr[v] = tr[u];
if(l==r){
tr[v].c += c;
return;
}
int mid = (l+r)>>1;
if(x<=mid)
modife(tr[u].l,tr[v].l,l,mid,x,c);
else
modife(tr[u].r,tr[v].r,mid+1,r,x,c);
pushup(v);
}
int query(vector<int> lp,vector<int> rp,int l,int r,int c){
if(l==r)
return l;
int mid = (l+r)>>1,sum = 0;
for(auto x:rp)
sum += tr[tr[x].l].c;
for(auto x:lp)
sum -= tr[tr[x].l].c;
if(c<=sum){
for(auto &x:lp)
x = tr[x].l;
for(auto &x:rp)
x = tr[x].l;
return query(lp,rp,l,mid,c);
}
for(auto &x:lp)
x = tr[x].r;
for(auto &x:rp)
x = tr[x].r;
return query(lp,rp,mid+1,r,c-sum);
}
}tr;
class inquiry{
public:
int l,r,k;
};
vector<inquiry> qus;
int a[N];
int n,m,q;
vector<int> ha;
inline int h(int x){return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;}
inline void modife(int y,int c,bool del=true){
if(del){
for(int x=y;x<=n;x+=x&-x)
tr.modife(tr.rt[x],tr.rt[x],1,m,a[y],-1);
}
a[y] = c;
for(int x=y;x<=n;x+=x&-x)
tr.modife(tr.rt[x],tr.rt[x],1,m,a[y],1);
}
inline int query(int l,int r,int c){
vector<int> lp,rp;
if(l>1)
for(int x=l-1;x;x&=x-1)
lp.push_back(tr.rt[x]);
for(int x=r;x;x&=x-1)
rp.push_back(tr.rt[x]);
return tr.query(lp,rp,1,m,c);
}
int main(){
n = in(),q = in();
for(int k=1;k<=n;k++)
ha.push_back(a[k]=in());
for(int k=1;k<=q;k++){
char ops = getchar();
while(ops!='Q'&&ops!='C')
ops = getchar();
if(ops=='Q'){
int l = in(),r = in(),c = in();
qus.push_back({l,r,c});
ha.push_back(c);
}
else{
int x = in(),c = in();
qus.push_back({x,0,c});
ha.push_back(c);
}
}
sort(ha.begin(),ha.end());
ha.erase(unique(ha.begin(),ha.end()),ha.end());
m = ha.size();
for(int k=1;k<=n;k++)
modife(k,a[k]=h(a[k]),false);
for(auto [l,r,c]:qus){
if(r){
out(ha[query(l,r,c)-1]);
putchar('\n');
}
else
modife(l,h(c));
}
return 0;
}树上主席树
板子
在树上用主席树做一个前缀和的东西，和区间类似，拿着
int fa[N],siz[N],dep[N],son[N],top[N],idx;
vector<int> g[N];
int w[N];
int n,m,q;
class persistent_segtree{
private:
class starwish{
public:
int l,r,c;
}tr[N<<8];
int idx;
public:
int rt[N];
void build(int &u,int l,int r){
u = ++idx;
if(l==r)
return;
int mid = (l+r)>>1;
build(tr[u].l,l,mid);
build(tr[u].r,mid+1,r);
}
void modify(int u,int &v,int l,int r,int x,int c){
v = ++idx,tr[v] = tr[u];
tr[v].c += c;
if(l==r)
return;
int mid = (l+r)>>1;
if(x<=mid)
modify(tr[u].l,tr[v].l,l,mid,x,c);
else
modify(tr[u].r,tr[v].r,mid+1,r,x,c);
}
int Kth(int a,int b,int c,int d,int l,int r,int K){
if(l==r)
return l;
int mid = (l+r)>>1,w = tr[tr[a].l].c+tr[tr[b].l].c-tr[tr[c].l].c-tr[tr[d].l].c;
if(w>=K)
return Kth(tr[a].l,tr[b].l,tr[c].l,tr[d].l,l,mid,K);
return Kth(tr[a].r,tr[b].r,tr[c].r,tr[d].r,mid+1,r,K-w);
}
}tr;
void dfs1(int u){
siz[u]++;
for(auto v:g[u]){
if(v==fa[u])
continue;
fa[v] = u;
dep[v] = dep[u]+1;
dfs1(v);
siz[u] += siz[v];
if(siz[v]>siz[son[u]])
son[u] = v;
}
}
void dfs2(int u,int tp){
top[u] = tp;
if(son[u])
dfs2(son[u],tp);
for(auto v:g[u]){
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x = fa[top[x]];
}
if(dep[x]<dep[y])
swap(x,y);
return y;
}
vector<int> ha;
inline int h(int x){
return lower_bound(ha.begin(),ha.end(),x)-ha.begin()+1;
}
void dfs3(int u){
tr.modify(tr.rt[fa[u]],tr.rt[u],1,m,h(w[u]),1);
for(auto v:g[u]){
if(v==fa[u])
continue;
dfs3(v);
}
}
int main(){
n = in(),q = in();
for(int k=1;k<=n;k++)
ha.push_back(w[k]=in());
sort(ha.begin(),ha.end());
ha.erase(unique(ha.begin(),ha.end()),ha.end());
m = ha.size();
for(int k=1;k<n;k++){
int a = in(),b = in();
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1);
dfs2(1,1);
tr.build(tr.rt[0],1,m);
dfs3(1);
int lastans = 0;
while(q--){
int x = in()^lastans,y = in(),K = in();
int d = lca(x,y);
out(lastans=ha[tr.Kth(tr.rt[x],tr.rt[y],tr.rt[d],tr.rt[fa[d]],1,m,K)-1]);
putchar('\n');
}
return 0;
}异或/可持久化trie 相关
平移后的异或问题
其实就是区间操作的典题，不过用了可持久化 trie 的**。
从高到底枚举
可持久化 trie 是个和可持久化线段树差不多的东西。
class persistent_segtree{
private:
class tree{
public:
int l,r,c;
}tr[N<<5];
int rt[N],idx;
inline void pushup(int x){tr[x].c = tr[tr[x].l].c+tr[tr[x].r].c;}
public:
inline int& operator [] (const int &x){return rt[x];}
void build(int &u,int l,int r){
u = ++idx;
if(l==r)
return;
int mid = (l+r)>>1;
build(tr[u].l,l,mid);
build(tr[u].r,mid+1,r);
}
void modife(int u,int &v,int l,int r,int x,int c){
v=++idx;
tr[v] = tr[u];
if(l==r){
tr[v].c += c;
return;
}
int mid = (l+r)>>1;
if(x<=mid)
modife(tr[u].l,tr[v].l,l,mid,x,c);
else
modife(tr[u].r,tr[v].r,mid+1,r,x,c);
pushup(v);
}
int query(int u,int v,int l,int r,int L,int R){
if(l>=L&&r<=R)
return tr[v].c-tr[u].c;
int mid = (l+r)>>1,ans = 0;
if(L<=mid)
ans += query(tr[u].l,tr[v].l,l,mid,L,R);
if(R>mid)
ans += query(tr[u].r,tr[v].r,mid+1,r,L,R);
return ans;
}
}tr;
int a[N];
int n,m;
inline bool query(int u,int v,int l,int r,int L,int R){
L = max(l,L),R = min(r,R);
if(L>R)
return false;
return tr.query(u,v,l,r,L,R);
}
int main(){
n = in(),m = in();
int v = 0;
for(int k=1;k<=n;k++)
v = max(v,a[k]=in());
tr.build(tr[0],0,v);
for(int k=1;k<=n;k++)
tr.modife(tr[k-1],tr[k],0,v,a[k],1);
while(m--){
int b = in(),x = in(),l = in(),r = in(),ans = 0;
for(int k=C;~k;k--){
int tmp = ans+((((b>>k)&1)^1)<<k);
if(query(tr[l-1],tr[r],0,v,tmp-x,tmp-x+(1<<k)-1))
ans = tmp;
else
ans += ((b>>k)&1)<<k;
}
out(ans^b);
putchar('\n');
}
return 0;
}願います！！！
希望 WC 能拿 Au 吧，这样我也好过点。
最近在看缪斯，感觉，真好啊，いいね。
AT_abc241_g 题解
“而雨下不停” —— 《一秒的梦》
分析
枚举第一名，假设以后的比赛该名玩家都获胜，然后判定是否合法。
数据范围很网络流，考虑最大流，流量代表得分，然后是建图：
- 源点和每场比赛连容量为
$1$ 的边 - 比赛如果有胜负就向胜者连边，否则就向参与比赛的两个人连边
- 设第一名的得分为
$w$ ，第一名向汇点连容量为$w$ 的边，其余的人得分不能超过第一名，所以其余的人向汇点连容量为$w-1$ 的边
由于总场次为
代码
const int N = 3000,M = 10000;
int h[N],ne[M],e[M],w[M],idx;
int win[N][N];
int n,m,S,T;
void add(int a,int b,int c){
w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx++;
w[idx] = 0,e[idx] = a,ne[idx] = h[b],h[b] = idx++;
}
namespace Dinic{
int q[N],d[N],cur[N];
bool bfs(){
int hh = 0,tt = -1;
memset(d,-1,sizeof(d));
d[S] = 0,cur[S] = h[S];
q[++tt] = S;
while(hh<=tt){
int u = q[hh++];
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(d[v]==-1&&w[k]){
d[v] = d[u]+1;
cur[v] = h[v];
if(v==T)
return true;
q[++tt] = v;
}
}
}
return false;
}
int find(int u,int lim){
if(u==T)
return lim;
int flow = 0;
for(int k=cur[u];~k&&flow<lim;k=ne[k]){
cur[u] = k;
int v = e[k];
if(d[v]==d[u]+1&&w[k]){
int t = find(v,min(w[k],lim-flow));
if(!t)
d[v] = -1;
w[k] -= t;
w[k^1] += t;
flow += t;
}
}
return flow;
}
int dinic(){
int r = 0,flow;
while(bfs())
if((flow=find(S,1e9)))
r += flow;
return r;
}
}
signed main(){
n = in(),m = in();
for(int k=1;k<=m;k++){
int a = in(),b = in();
win[a][b] = 1;
win[b][a] = 2;
}
S = 0,T = n+n*(n-1)/2+1;
for(int k=1;k<=n;k++){
memset(h,-1,sizeof(h));
idx = 0;
int cnt = n,wnt = 0;
for(int j=1;j<=n;j++)
for(int i=j+1;i<=n;i++){
add(S,++cnt,1);
if(win[i][j]){
if(win[j][i]==1){
if(j==k)
wnt++;
add(S,j,1);
}
else{
if(i==k)
wnt++;
add(S,i,1);
}
}
else{
if(j==k||i==k){
add(cnt,k,1);
wnt++;
}
else{
add(cnt,j,1);
add(cnt,i,1);
}
}
}
for(int j=1;j<=n;j++)
if(j==k)
add(j,T,wnt);
else
add(j,T,wnt-1);
if(Dinic::dinic()==n*(n-1)/2)
out(k,' ');
}
return 0;
}整体二分浅谈
浅浅的总结一下简单情况。
适用范围
可以使用整体二分解决的题目需要满足以下性质：
- 询问的答案具有可二分性
- 修改对判定答案的贡献互相独立，修改之间互不影响效果
- 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
- 贡献满足交换律，结合律，具有可加性
- 题目允许使用离线算法
许昊然《浅谈数据结构题几个非经典解法》
一般来说适用于二分时每次 check 都要预处理，同时预处理代价较大的情况。
把所有询问一起二分，对于一个 check 就只需要预处理一次。
特殊情况的处理
查询
比如区间第
修改
把修改和询问都视为操作（修改要满足上面的性质）。
比如带修改区间第 k 大，修改为把
二维化
把初始的的都视作修改就能轻松处理。
优化
相比每次都撤销
然后有些预处理操作不用撤销可以换成区间操作，就能少一个
About
常用名字是 DaydreamWarrior 和 raininifty。
目前初三，就读于 CQ 的弱校。
ACG 浓度较高，OI 水平入门-，还算是有梦想。
luogu id: 407214，atcoder 和 codeforces 太烂了不想放。
博客来源于 蝉時雨 。
以下是我的博客：
rainlycoris.github.io [firefox 推荐][背景是津岛善子]
tianyiv.github.io [不保证此网站正常运行][背景是星尘]
luogu.com.cn/blog/ldl[里面只有题解]
博客文章存放于 github 的 issues 里，找文章和复制代码会方便一些。
有一个 blog 索引，里面另外标注了一些东西。
AT_abc294_f 题解
“「あるべき人間の姿へ」 「正しい人間の姿へ」 そう思えばなんだか 人間全てが汚く思えてくるな”—— 《不可解》
题意
高橋君有
高橋君的第
青木君的第
将两人的糖水各选一瓶混合有
有
分析
二分浓度
有
令
那么两瓶糖水
因为
二分浓度，将青木君糖水的
复杂度
代码
const int N = 50005;
const double eps = 1e-12;
vector<pair<int,int>> a,b;
int n,m,K;
inline int check(double c){
vector<double> w1,w2;
for(auto [x,y]:a)
w1.push_back(x-(x+y)*c);
for(auto [x,y]:b)
w2.push_back(x-(x+y)*c);
sort(w2.begin(),w2.end());
int ans = 0;
for(auto c:w1)
ans += lower_bound(w2.begin(),w2.end(),-c+eps)-w2.begin();
return ans;
}
signed main(){
cin >> n >> m >> K;
a.resize(n);
b.resize(m);
for(auto &[x,y]:a)
cin >> x >> y;
for(auto &[x,y]:b)
cin >> x >> y;
double l = 0,r = 1;
K = n*m-K+1;
while(abs(r-l)>eps){
double mid = (l+r)/2;
if(check(mid)>=K)
r = mid;
else
l = mid;
}
printf("%.10lf",r*100);
return 0;
}APIO2023 赛博乐园
“并没有 不一样 为何感到悲伤” —— 《尘降》
分析
首先把图反着跑，这样总通行时间除以
然后把一个点拆开成
注意一下
发现除以二操作做
代码
const int N = 100005,C = 72,L = 70;
typedef pair<double,pair<int,int>> LDII;
vector<pair<int,int>> g[N];
double dis[N][C];//清零和超过 L 次除以 2 视为一致
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
for(int k=0;k<N;k++){
g[k].clear();
for(int j=0;j<=L;j++)
dis[k][j] = 2e18;
}
for(int k=0;k<M;k++){
g[x[k]].emplace_back(y[k],c[k]);
g[y[k]].emplace_back(x[k],c[k]);
}
priority_queue<LDII,vector<LDII>,greater<LDII>> q;
q.push({0,{H,0}});
dis[H][0] = 0;
while(!q.empty()){
auto [u,k] = q.top().second;
q.pop();
for(auto[v,w]:g[u]){
if(v==H)
continue;
if(k>=L){//视作清零操作
if(dis[v][L]>dis[u][k]){
dis[v][L] = dis[u][k];
q.push({dis[v][L],{v,L}});
}
continue;
}
if(arr[v]==0){
if(dis[v][L]>dis[u][k]+w*1.0/(1ll<<k)){
dis[v][L] = dis[u][k]+w*1.0/(1ll<<k);
q.push({dis[v][L],{v,L}});
}
continue;
}
if(arr[v]==2&&k<K){
if(dis[v][k+1]>dis[u][k]+w*1.0/(1ll<<k)){
dis[v][k+1] = dis[u][k]+w*1.0/(1ll<<k);
q.push({dis[v][k+1],{v,k+1}});
}
}
if(dis[v][k]>dis[u][k]+w*1.0/(1ll<<k)){
dis[v][k] = dis[u][k]+w*1.0/(1ll<<k);
q.push({dis[v][k],{v,k}});
}
}
}
double ans = 2e18;
for(int k=0;k<=L;k++)
ans = min(ans,dis[0][k]);
if(ans>1e18)
return -1;
return ans;
}闲话
考试的时候用的是
P5494 题解
这是一篇平衡树合并题解，平衡树合并的复杂度 并不是假的，带有分裂的可以证明到
https://codeforces.com/blog/entry/108601
和上面的分析相同，但受个人水平所限可能有误，还希望多多包涵。
平衡树比线段树适用性更广，常数也不大（未卡常 fhqtreap 用时 615ms，这也是我认为是单
平衡树合并
先不考虑分裂，单说合并。
现在要合并
int Merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri<tr[y].pri)
swap(x,y);
int l,r;
split(y,tr[x].v,l,r);
tr[x].l = Merge(tr[x].l,l);
tr[x].r = Merge(tr[x].r,r);
pushup(x);
return x;
}明显是把小的树裂开更优，但是堆值大大概率就是树大的，下文也默认此情况（主要是带有随机的不会分析）。
其实这里存在一个合不合并相同结点的问题，其实是 要合并 的，因为 treap 的复杂度依赖于树和堆的唯一性，如果存在相同结点那么可能会失去性质（比如全部都一样，可以在不违反树和堆的情况下出来一条链），对于一般的 treap 也存在此问题。
现在分析平衡树合并的复杂度，设第一棵树大小为
为什么说是上界，因为在两颗树值域重合少的时候复杂度和最少不相交的值域段数
更通用的复杂度分析
定义势能为
合并
形如 $ _ {[-----]}$ 的是一段值域，形如 $ _ {<--d_i-->}$ 的是值域之间的距离且距离为
合并后
$$
\Delta\varphi=\log(d_1+b_1+d_2)+\log(d_2+a_2+d_3)+\dots+\log(d_{k-1}+a_{\frac{k}{2}}+d_k)-(\log d_1+\dots+d_k)
$$
前面的把
显然有
$$
\Delta\varphi\geq\log(d_1+d_2)+\log(d_2+d_3)+\dots+\log(d_{k-1}+d_k)-(\log d_1+\dots+d_k)
$$
因为
$$
\log(a+b)\geq 1+\frac{\log a+\log b}{2}
$$
那么把
$$
\Delta\varphi\geq k-1-\frac{d_1+d_k}{2}
$$
忽略常数可得
$$
\Delta\varphi\geq k-O(\log V)
$$
也就是说最多做
带有分裂的复杂度分析
一次分裂会减少
一次合并如果增加就至多增加
那么最多就只有
完整代码
const int N = 200005;
int n,m;
mt19937 myrand(713);
class fhqtreap{
private:
struct{int l,r,v,s,siz;unsigned pri;} tr[2*N];
int rt[N];
int idx;
int create(int v,int s){tr[++idx] = {0,0,v,s,s,myrand()};return idx;}
void pushup(int u){tr[u].siz = tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].s;}
public:
int& operator [] (const int &x){return rt[x];}
void split(int u,int c,int &x,int &y){
if(!u){
x = y = 0;
return;
}
if(tr[u].v<=c){
x = u;
split(tr[u].r,c,tr[x].r,y);
}
else{
y = u;
split(tr[u].l,c,x,tr[y].l);
}
pushup(u);
}
void split_rk(int u,int c,int &x,int &y){
if(!u){
x = y = 0;
return;
}
if(tr[tr[u].l].siz+tr[u].s<=c){
x = u;
split_rk(tr[u].r,c-tr[tr[u].l].siz-tr[u].s,tr[x].r,y);
}
else{
y = u;
split_rk(tr[u].l,c,x,tr[y].l);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri>tr[y].pri){
tr[x].r = merge(tr[x].r,y);
pushup(x);
return x;
}
tr[y].l = merge(x,tr[y].l);
pushup(y);
return y;
}
int Merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri<tr[y].pri)
swap(x,y);
int l,r;
split(y,tr[x].v,l,r);
tr[x].l = Merge(tr[x].l,l);
tr[x].r = Merge(tr[x].r,r);
pushup(x);
return x;
}
void insert(int &u,int c,int s){
int x,y;
split(u,c,x,y);
u = merge(merge(x,create(c,s)),y);
}
int kth(int &u,int K){
int x,y;
split_rk(u,K-1,x,y);
int p = y;
while(tr[p].l)
p = tr[p].l;
u = merge(x,y);
return p?tr[p].v:-1;
}
int count(int &u,int l,int r){
int x,y,z;
split(u,l-1,x,y);
split(y,r,y,z);
int ans = tr[y].siz;
u = merge(merge(x,y),z);
return ans;
}
void move(int &x,int &y,int l,int r){
int a,b,c;
split(x,l-1,a,b);
split(b,r,b,c);
y = b;
x = merge(a,c);
}
}tr;
signed main(){
n = in,m = in;
for(int k=1;k<=n;k++)
tr.insert(tr[1],k,in);
int idx = 1;
while(m--){
int op = in,p = in;
if(!op){
int x = in,y = in;
tr.move(tr[p],tr[++idx],x,y);
}
else if(op==1){
int t = in;
tr[p] = tr.Merge(tr[p],tr[t]);
}
else if(op==2){
int x = in,q = in;
tr.insert(tr[p],q,x);
}
else if(op==3){
int x = in,y = in;
out(tr.count(tr[p],x,y),'\n');
}
else
out(tr.kth(tr[p],in),'\n');
}
return 0;
}闲话
确实这东西很能拓展，只要不咋影响势能都可以把合并当作基本操作。
跑的比我写的线段树合并还快，所以我觉得这像是
或许可以就考虑值域上的段数，毕竟分裂就只会把一整段变成两段，其他操作除了合并都不影响段树。
但是这个合并对段数的影响真不会算啊。
真·浅谈线性基
或许是该努努力了呢，快要来不及了。
异或线性基
简单来说，线性基是一个数的集合，每个序列都拥有一个线性基，线性基中的若干个数异或起来原序列中的任意一个数。
重要性质：
- 原序列中的任意一个数都能通过线性基中的若干个数异或得到。
- 线性基内任意数异或和不为
$0$ 。 - 一个序列的所有线性基大小相同。
别的性质：
- 由
$n$ 个数组成的大小为$s$ 的线性基，能构成$2^s$ 种不同的数，每个数出现$2^{n-s}$ 次。
基本操作
插入
void insert(int x){
for(int k=62;~k;k--)
if((x>>k)&1){
if(!d[k]){
d[k] = x;
break;
}
x ^= d[k];
}
}求异或最大值
int query(int x=0){
for(int k=62;~k;k--)
if((x^d[k])>x)
x ^= d[k];
return x;
}求异或最小值
如果是序列内部最小的异或值，那么如果有元素不能被插入线性基，最小值为
如果是丢一个数进去的话，类似于求异或最大值做就行了。
查询存在性
能插入进去就是不存在，否则就是存在。
求 $k$ 小值
先预处理，对于线性基
void init(){
for(int k=0;k<62;k++)
for(int j=0;j<k;j++)
if((d[k]>>j)&1)
d[k] ^= d[j];
}
int kth(int K){
if(s<n)
K--;
//n 表示序列长度，s 表示线性基元素个数
int ans = 0;
for(int k=0;k<62;k++)
if((K>>k)&1)
ans ^= d[k];
return ans;
}线性基求并
把一个线性基的全部元素插入另一个就行。
例题
P3857 [TJOI2008] 彩灯
一个序列若干数异或得到的集合和这个序列的线性基异或得到的集合是一样的。
由于线性基性质 2，一个大小为
那么算出这个序列的线性基，答案就为
P4570 [BJWC2011] 元素
因为线性基性质 2，线性基内任意数异或和不为
因为线性基性质 3，无论顺序能放进去的总个数是不变的，贪心的先放贡献大的就行。
P5556 圣剑护符
距离
那么对于
P4151 [WC2011] 最大XOR和路径
走的路径一定是一条链然后走到了一些别的地方又回来。
一个路径走两遍就没了贡献，那么有贡献的一定是走到了环，并且贡献为环本身，因为走去环回来这条路径被走了两遍。
这样的话所有的环都能自由选择，把所有的小环的异或值加入线性基（大环相当于小环的异或值），就相当于自由选择所有的环。
考虑选择走的
把选择的链的异或值去线性基里跑最大异或值就行了。CF845G 就是跑最小值。
P5607 [Ynoi2013] 无力回天 NOI2017
首先这是个数据结构套线性基础，考虑线段树，但是修改是区间修改线性基不太好做。
差分，$b_i=a_i\ \text{xor}\ a_i$，把区间修改变为单点修改。
用线段树维护
询问就求出
线性基合并的复杂度为
P3292 [SCOI2016] 幸运数字
因为是算异或最大值，求的是树上路径线性基，倍增直接做是
发现 线性基重复部分没有贡献，类似于
具体的，先倍增预处理线性基。对于询问找到 lca 之后拆成
复杂度为
P4869 albus就是要第一个出场
由
查询排名就是从低位到高位看，如果第
因为是第
不会证明，之后再补吧。
根号数据结构
很久之前写的烂尾笔记
根号数据结构
简介
顾名思义，复杂度含
分块
简介
分块的基本**是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度，或和其他算法搭配平衡出更优的时间复杂度。
使用分块进行维护对数据的特征要求较少 可以维护很多线段树无法维护的东西。
设块长为
缺点是
分类
序列分块
对于一个序列按每
通常修改块内元素为暴力修改之后更新整块信息，修改整块元素则是以区间标记的形式修改。
值域分块
在值域上按每
因为在值域本就存在一维偏序关系，即数据是有序的，所以可以依据序列分块的**去解决问题。
通常用来平衡复杂度，例如
询问分块
对于每
通常用于需要较大时间维护全局，但是可以以较小时间进行单次查询的问题，也是平衡复杂度的**。
其他
例如块状链表等等。
莫队
简介
一种通过暴力移动端点去离线解决区间问题的方法。发明者为国集队长莫涛，所以被称为莫队。
算法发现过程 (大概?)
查询一个区间可以暴力的从左端点扫到右端点。当我们有两个区间
考虑分块的**，限制端点移动范围。设块长为
可证在最优的情况下
一些细节
- 莫队可以维护的数据需要支持在区间头或者尾加上或者删除,(也有不需要支持删除的莫队，详见回滚莫队)，比线段树之类的数据结构适用性更加更加广泛。
- 一般的莫队不支持修改 (也有支持修改的莫队，详见带修莫队)。
- 莫队是一种离线算法，对于强制在线的题目和信息学竞赛之外的方面应该没有啥用途。
板子题
分类
带修莫队
简介
一般的莫队是无法支持修改的，因为一般无法做到在区间内修改快速更新 (要是可以就不需要莫队了)。及解决方法和 dp 类似，我们可以加一个维度。落实到带修莫队就是加一个时间维度，区间变为$[l,r,time]$。
转移和普通莫队一样转移，但是我们的排序多了一个关键字，以
板子题
回滚莫队
简介
莫队配合分块 / bitse
板子题
烦恼 #1
距离中考还有 40 多天了，但是感觉我，没啥干劲呢。
有点寂寞有点累，话说回来，明天我要努力了吧。
毕竟考不上高中，学不好英语这些的影响很大呢。
P3730 莫队+值域分块题解
“生きる熱さを感じたいだけさ”—— 《スリリング・ワンウェイ》
题意简述
查询区间内出现次数第k小的值的出现次数。
题目分析
这种
考虑平衡复杂度，莫队有
一些细节
- 题目值域是
$[1,10^9]$ ，需要离散化。 - 莫队的最优块长其实是
$\dfrac{n}{\sqrt m}$ 。因为$n$ 和$m$ 同价的时候和$\sqrt n$ 是一样的，一般也没理这个事。证明详见 普通莫队算法 - Oi Wiki。
代码
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005,M = 320;
class inquiry{
public:
int l,r,x,block,id;
inline bool operator < (const inquiry &tmp)const{
if(block!=tmp.block)//奇偶性优化，个人感觉不是对时间优化，而是防出题人卡莫队
return l<tmp.l;
return block&1?r<tmp.r:r>tmp.r;
}
};
vector<inquiry> qus;
int ans[N],cnt[N];
vector<int> has;
int block,len;
int a[N];
int n,m;
namespace sqrtrange{//值域分块
int cnt[N],sum[M];
inline void update(int x,int c){
cnt[x] += c;
sum[x/len] += c;//更新所在块的贡献
}
inline int query(int x){
int top = ceil(n*1.0/len);
for(int k=0;k<top;k++){
if(x>sum[k])//答案不在块内
x -= sum[k];
else{//答案在块内，遍历整个块寻找答案
int l = k*len,r = min((k+1)*len,n);
for(int j=l;j<=r;j++){
if(x>cnt[j])
x -= cnt[j];
else
return j;
}
}
}
return -1;
}
}
inline int h(int x){
return lower_bound(has.begin(),has.end(),x)-has.begin();
}
inline void add(int x){
if(cnt[a[x]])
sqrtrange::update(cnt[a[x]],-1);//减去修改前出现次数的贡献
cnt[a[x]]++;
sqrtrange::update(cnt[a[x]],1);//更新贡献
}
inline void del(int x){
sqrtrange::update(cnt[a[x]],-1);
cnt[a[x]]--;
if(cnt[a[x]])
sqrtrange::update(cnt[a[x]],1);
}
int main(){
n = in(),m = in();
block = ceil(n/sqrt(m));
for(int k=1;k<=n;k++)
has.emplace_back(a[k]=in());
sort(has.begin(),has.end());
has.erase(unique(has.begin(),has.end()),has.end());
for(int k=1;k<=n;k++)
a[k] = h(a[k]);
len = ceil(sqrt(n));
for(int k=1;k<=m;k++){
int l = in(),r = in(),x = in();
qus.push_back({l,r,x,l/block,k});
}
sort(qus.begin(),qus.end());
int L = 1,R = 0;
for(auto[l,r,x,tmp,id]:qus){
while(l<L)
add(--L);
while(l>L)
del(L++);
while(r<R)
del(R--);
while(r>R)
add(++R);
ans[id] = sqrtrange::query(x);
}
for(int k=1;k<=m;k++){
out(ans[k]);
putchar('\n');
}
return 0;
}后话
- 这种莫队套分块去平衡复杂度还挺常见的，有时候也搭配
bitset。 - 第一次写题解，水平有限还请见谅。
AT_arc158_c 题解
“かけがえのない日々を ここで 積みかさねて ひとつひとつ いまさらわかった”—— 《想いよひとつになれ》
题意简述
设
给定一个长度为
分析
设
考虑如何计算
代码
const int N = 200005,M = 17;
int a[M][N];
int n;
signed main(){
cin >> n;
int ans = 0;
for(int k=1;k<=n;k++){
int c;
cin >> c;
int d = 10;
for(int j=1;j<M;j++){
a[j][k] = c%d;
d *= 10;
}
while(c){
ans += c%10;
c /= 10;
}
}
ans *= 2*n;
for(int k=1;k<M;k++)
sort(a[k]+1,a[k]+1+n);
int d = 10;
int sum = 0;
for(int k=1;k<M;k++){
for(int j=1;j<=n;j++){
int w = a[k]+n+1-lower_bound(a[k]+1,a[k]+1+n,d-a[k][j]);
sum += w;
}
d *= 10;
}
cout << ans-sum*9;
return 0;
}P4698 题解
“请告诉我为何心不停的跳动 这颗心究竟装着什么” —— 《人偶之梦》
分析
注意到
一个贪心的想法是，按照订单的
但是如果房间已经被占用，就住进大于
考虑这样为什么是对的，设占用房间的为
- 如果
$i,j$ 都要入住，答案无影响。 - 如果
$i,j$ 只有一个要入住，因为$v_i>v_j$ ，所以$i$ 肯定比$j$ 更优，$j$ 必定不会被选到（就选选的不是最优的房间也不影响）。
现在问题变成了，找到大于 multiset 可以解决（注意房间可重，set 不可重）。
代码
multiset<pair<int,int>> house;
vector<pair<int,int>> order;
int n,m,o;
int main(){
n = in(),m = in(),o = in();
for(int k=1;k<=n;k++){
int c = in(),p = in();
house.insert({p,c});
}
order.resize(m);
for(auto &[v,d]:order)
v = in(),d = in();
sort(order.begin(),order.end(),[](auto a,auto b){return a.first!=b.first?a.first>b.first:a.second<b.second;});
vector<int> res;
for(auto [v,d]:order){
auto it = house.lower_bound({d,0});
if(it!=house.end()){
if(v<=(*it).second)
continue;
res.push_back(v-(*it).second);
house.erase(it);
}
}
sort(res.begin(),res.end(),greater<>());
long long ans = 0;
for(int k=0;k<min(o,(int)res.size());k++)
ans += res[k];
out(ans);
return 0;
}环境配置 #1
用了 GCC13.1，并且给本地添加了 <atcoder> 库！
prufer 序列
发现标题字打错了，然后改不了标题就重新发了一遍。
简介
prufer 序列可以把一个结点带标号的树用
一棵树对应唯一的 prufer 序列，一个 prufer 序列对应唯一的树，二者为双射关系。
对树建立 prufer 序列
每次找到编号最小的 叶子结点，把这个结点的父亲放入 prufer 序列的末尾，然后删掉这个叶子。重复
算法实现
显然可以用堆实现，也可以线性构造。
维护一个
- 删除
$p$ 。 - 如果父亲成为了叶子，且父亲的编号
$<p$ ，删除父亲。不断重复 2 操作。 -
$p$ 自增直到找到新的叶子结点。
分析正确性，删除一个点新成为叶子的只会是父亲，如果父亲的编号
代码
for(int k=1;k<n;k++)
d[fa[k]]++;
for(int k=1,j=1;k<=n-2;k++,j++){
while(d[j])
j++;
p[k] = fa[j];
while(k<=n-2&&!(--d[p[k]])&&p[k]<j){
p[k+1] = fa[p[k]];
k++;
}
}对 prufer 序列建立树
prufer 序列里的点的出现次数
每次找到编号最小的 度数为
最后剩下两个度数为
算法实现
同理可以用堆实现，当然也可以线性构造。
现在 prufer 序列末尾添加结点
- 删除
$p$ 。 - 如果父亲度数变为
$1$ ，且父亲的编号$<p$ ，删除父亲。不断重复 2 操作。 -
$p$ 自增直到找到新的度数为$1$ 的点。
代码
for(int k=1;k<=n;k++)
d[p[k]]++;
p[n-1] = n;
for(int k=1,j=1;k<n;k++,j++){
while(d[j])
j++;
fa[j] = p[k];
while(k<n&&!(--d[p[k]])&&p[k]<j){
fa[p[k]] = p[k+1];
k++;
}
}Cayley 公式
完全图
证明可以使用 prufer 序列，prufer 序列有
一一对应，所以有
类似的：
-
$n$ 个点的无根树有$n^{n-2}$ 种 -
$n$ 个点的有根树有$n \times n^{n-2}$ 种 -
$n$ 个点的无根树，每个点的度数为$d_i$ ，有 $\frac{(n-2)!}{\prod^{n}{i-1}(d_i-1)!}$ 种，也为 $\prod^{n}{i-1}C_{d_i-1}^{sum}$（sum 为还剩下的位置）
图连通方案数
一个
感性理解一下，如果把每个连通块看成点，总方案数为
然后每个连通块还要和上一个连边，联通块内的每一个点都可能拿出来连，所以总方案数是
详细证明之后再说吧。
相关题目
建 prufer 和建树：【模板】Prüfer 序列
Cayley 公式相关：[HNOI2004] 树的计数
图连通方案数：CF156D Clues
P2120 题解
“生きてく意味があると感じるよ…確かに！”——《Nameless Love Song》
分析
首先写个
然后
一些细节
要特判末尾连续的
代码
const int N = 1000005,INF = (1ull<<63)-1;
int x[N],p[N],c[N],f[N];
int n;
class lctree{
private:
struct{int l,r;pair<int,int> f;} tr[N];
int val(pair<int,int> f,int x){return f.first*x+f.second;};
int idx;
public:
int root;
void insert(int &u,int l,int r,pair<int,int> f){
if(!u)
tr[u=++idx].f = f;
else{
int mid = (l+r)>>1;
if(val(f,mid)<val(tr[u].f,mid))
swap(f,tr[u].f);
if(f.first>tr[u].f.first)
insert(tr[u].l,l,mid,f);
else
insert(tr[u].r,mid+1,r,f);
}
}
int query(int u,int l,int r,int p){
if(!u)
return INF;
int mid = (l+r)>>1;
return min(val(tr[u].f,p),p<=mid?query(tr[u].l,l,mid,p):query(tr[u].r,mid+1,r,p));
}
}tr;
signed main(){
n = in;
int V = 0;
for(int k=1;k<=n;k++){
x[k] = in,p[k] = in,c[k] = in;
V = max(V,x[k]);
}
tr.insert(tr.root,0,V,{0,0});
int sp = 0,sxp = 0;
for(int k=1;k<=n;k++){
sp += p[k];
sxp += x[k]*p[k];
f[k] = tr.query(tr.root,0,V,x[k])+x[k]*sp-sxp+c[k];
tr.insert(tr.root,0,V,{-sp,f[k]+sxp});
}
int ans = f[n];
for(int k=n;k&&!p[k];k--)
ans = min(ans,f[k-1]);
out(ans);
return 0;
}完工~
博客终于弄好了，加个 ketax 渲染支持和解决字体问题弄半天。
切比雪夫距离与曼哈顿距离
内含高维曼哈顿-切比雪夫转换。
定义
曼哈顿距离：$|x_1-x_2|+|y_1-y_2|$
切比雪夫距离：$\max(|x_1-x_2|,|y_1-y_2|)$
更多距离
欧几里得距离：$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
转换
曼哈顿转切比雪夫：$(x,y)\rightarrow(x+y,x-y)$
切比雪夫转曼哈顿：$(x,y)\rightarrow(\frac{x+y}{2},\frac{x-y}{2})$
证明
证明可以用几何，因为曼哈顿坐标系是通过切比雪夫坐标系旋转
或者纯代数，$x\leq y$ 时
其实是转换成
切比雪夫转曼哈顿其实就是解 $\begin{cases}x+y=a\cr x-y=b\end{cases}$ 的方程。
高维切比雪夫和曼哈顿
通过上面的证明可以得到，$k$ 维曼哈顿可以转换为
也就是指定每一位取正还是取负，在去掉重复的
但是高维切比雪夫却不一定都能转换为曼哈顿，因为本质这个转换是解方程，拿四维切比雪夫
这个方程需要满足
而切比雪夫不是
比如求
$$
\sum_{i=1}^n\sum_{j=1}^{i-1}\max(a_i-a_j,b_i-b_j,c_i-c_j)-\min(a_i-a_j,b_i-b_j,c_i-c_j)
$$
可以直接 min-max 容斥，但是跑的慢
推式子
这明显是一个三维切比雪夫，给他升成四维，令
这个直接排序就能求了。
joi2015ho_d 舞踏会
“你眼中倒映的世界 一瞬永远” —— 《梦语》
分析
首先答案有单调性，考虑二分。
然后每次留下来的构成一颗三叉树，父亲是儿子的中位数，考虑树形 dp。
上很经典的中位数套路，设二分的值为
如果儿子的值之和
考虑设
转移为
如果
代码
const int N = 200005;
int d[N],p[N],f[N];
vector<int> g[N];
int root;
int n,m;
void dfs(int u){
int maxx = 0;
for(int v:g[u]){
dfs(v);
f[u] += f[v];
maxx = max(maxx,f[v]);
}
f[u] -= maxx;
}
bool check(int v){
for(int k=1;k<=root;k++)
f[k] = 0;
for(int k=1;k<=n;k++){
if(p[k])
f[k] = d[p[k]]>=v?0:N+1;
else
f[k] = 1;
}
int cnt = 0;
for(int k=m+1;k<=n;k++)
cnt += d[k]>=v;
dfs(root);
return f[root]<=cnt;
}
int main(){
n = in,m = in;
queue<int> q;
for(int k=1;k<=n;k++)
q.push(k);
root = n;
while(q.size()>1){
int a = q.front();
q.pop();
int b = q.front();
q.pop();
int c = q.front();
q.pop();
root++;
g[root].push_back(a);
g[root].push_back(b);
g[root].push_back(c);
q.push(root);
}
for(int k=1;k<=m;k++)
d[k] = in,p[(int)in] = k;
for(int k=m+1;k<=n;k++)
d[k] = in;
int L = 1,R = 1000000000,ans;
while(L<=R){
int mid = (L+R)>>1;
if(check(mid)){
ans = mid;
L = mid+1;
}
else
R = mid-1;
}
out(ans,'\n');
return 0;
}真·浅谈高维前缀和/sosdp
夜空是否全然知晓？
高维前缀和/sosdp
计算高维前缀和可以不用容斥，而是对每一维分别做前缀和，复杂度为
对于子集求和问题，相当于二进制下的
那么就可以在
题目
ARC100E Or Plus Max
先算出
然后就是求子集最大值和次大值，高维前缀和解决。
CF1208F Bits And Pieces
考虑枚举一个
要使得
假设当前选择的为
相当于求一个超集的最大值和次大值，这种类似子集和的问题可以用高维前缀和解决。
P6442 [COCI2011-2012#6] KOŠARE
设选择的集合为
也可以再跑一遍差分。
CF449D Jzzhu and Numbers
和上一道类似，不过不是跑子集是跑超集。
然后跑容斥或者差分。
兼容性问题
cross-fade 一直在 Firefox 上有问题，一查是 Firefox 根本不支持。
看着蝉时雨更新了 zero 我也跟着改了改，但是多背景不想改了，睡觉。
下周六就春测了，有点紧张。
APIO 线上游记
人生第一次参加 APIO。
day-?
报名被报成线上了，寄寄寄。
day-?
P 和我的年龄给了我可能今年唯一能看的成绩。
day 0 5.18
麦会炸，是那种嘶吼声的回音的感觉。
字符串，感觉自己没学过了。
直播能很好看到旷课人数，很震撼，签到更震撼。
同时知道了 线上没监考。
线下看起来好好玩，你们发在 LA 群里的自拍是在同情我吗，你们玩音游的真多，我也想玩，你们发在 LA 里的 kfc 是在同情我吗，华山饭店好厉害，你们带带我行不。
然后一遍听中v曲一边改之前 apio 的题（为了体现我的合群一定要提个关键词），自信啊，那不得保底 Ag。
day 1
T1 板到不行，半小时就写好了。
这是什么，cms，刷新一下。
这是什么，OJ，交一下。
啥情况就不说了，结束前半小时才知道我 T1 过了（一个小时 debug 一次），我 K 和 50 取 min 还能过很厉害啊，想不通。
T2 不会，32 分不说了，$a_i\leq 3$ 的随便搞几下就过了（当然也是在考试后知道的）。$7$ 分的暴力写挂了（同上）。
T3 电路，可是我去的 P 没有优势，加法器没写出来。
能不能下次复刻光追，求求你了。
结束了。
day 2
听到了 200 一车，早就知道了，我考的相当烂，我无法改变。
晚上在阳台吹了一晚上风。
以为自己打铁打的，结果线上 Ag 了（那
一看线下 Cu 130，别的不评价了，没资格评价。
上半年这就是最后一场比赛，本来说能买个 D 的，结果感觉我穿越到平行世界了。
结束了，感觉最近精神状态一直不太好，空落落的。
聊聊 dsu on tree
契约签订完毕，接下来要认真起来了。
简介
对于子树查询类问题，大多可以 dfs 序然后上数据结构，不行就树上莫队。
一个方法是 dsu on tree，是一个好写的复杂度
过程
考虑启发式，对于每个节点找出重子树，然后
- 递归询问所有轻子树（询问后删除贡献）
- 递归询问重子树（保留贡献）
- 加入所有轻子树内节点的贡献
证明
对于复杂度，总操作次数为
性质
加入重儿子之前的全局所有贡献都是被删掉了的。
这意味着 dsu on tree 和
题目
CF600E Lomsat gelral
直接 dsu on tree，求众数和可以正常做，撤销的时候不仅要把计数的数组撤销，还要把最多出现次数和众数和撤销，后者也好办，操作前记录一个撤销的时候直接赋值就好了。
CF741D Arpa’s letter-marked tr...
排序后能是回文串要么每个字符都是偶数，或者只有一个为奇数。
字符只有
把这个过程按照 dsu on tree 做就好了。
CF1767F Two Subtrees
如果只询问一个子树，那么就是 dsu on tree 板子。
考虑把 dsu on tree 序列化，先加入轻子树，再加入重子树，再加入根。
当扫描这个序列的所有子树时，轻子树的移动后会直接被删掉，重子树移动后再查询根，重子树会被保留同时加入所有轻子树，扫描的复杂度为
直接在这个序列上莫队，区间的左右端点为询问的两颗子树。
子树询问的区间移动就如果目标区间当前区间无交就当前区间删除然后暴力加入目标区间，否则就就正常移动左右端点。
AT_abc295_g 题解
“いつか君に届く言叶に乗せて 远く远く远く远く 仆らを连れさってみて”——《アイラ》
题意简述
给定一张点数为
-
1 u v：$u$ 向$v$ 连一条有向边，保证最开始时$v$ 能到达$u$ ，$u \ne v$。 -
2 x：询问$x$ 能到达的点中编号最小的点。
分析
最开始时，$u$ 能到达的所有点都比
一个点
代码
const int N = 200005;
int fa[N],p[N];
int n;
int find(int x){
if(fa[x]==x)
return fa[x];
return fa[x]=find(fa[x]);
}
int main(){
cin >> n;
for(int k=2;k<=n;k++)
cin >> p[k];
for(int k=1;k<=n;k++)
fa[k] = k;
int q;
cin >> q;
while(q--){
int t;
cin >> t;
if(t==1){
int u,v;
cin >> u >> v;
u = find(u),v = find(v);
while(find(u)!=v){
fa[find(u)] = find(p[u]);
u = p[u];
}
fa[find(u)] = v;
}
else{
int x;
cin >> x;
cout << find(x) << endl;
}
}
return 0;
}闲话
警惕 abc 打普及 G 牌。
AT_abc299_g 题解
“言葉にならない心の全部を 燃やしてゆけ” —— 《Surges》
分析
维护一个栈，每次加入一个值。
如果栈顶在之后也会出现并且比加入的值大就弹出。
这样使得每个值尽可能放在前面。
错略的证明一下。假设有两个序列
那么找到的序列是字典序最小的。
不过一个排列的置换字典序最小不一定代表这个排列的字典序最小。
代码
const int N = 200005;
int a[N],pos[N];
int stk[N],top;
bool b[N];
int n,m;
int main(){
cin >> n >> m;
for(int k=1;k<=n;k++){
cin >> a[k];
pos[a[k]] = k;
}
for(int k=1;k<=n;k++){
if(b[a[k]])
continue;
while(top&&stk[top]>a[k]&&pos[stk[top]]>k){
b[stk[top]] = false;
top--;
}
stk[++top] = a[k];
b[a[k]] = true;
}
for(int k=1;k<=m;k++)
cout << stk[k] << " ";
return 0;
}风格改变 #2
去除函数 inline，啥用没有
联通性相关
发现这部分学的最烂，稍微整理下。
强连通分量
定义
强连通的定义：有向图
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
Tarjan 算法
DFS 生成树
有向图的 DFS 生成树主要有
-
树边：是搜索时找到一个未访问的结点形成的边。
-
返祖边：是搜索时找到自己的祖先形成的边。
-
横叉边：是搜索时找到已遍历过的结点形成的边，并且这个节点不是自己的祖先和子树中的结点。
-
前向边：是搜索时找到子树中的结点形成的边。
DFS 生成树与强连通分量之前的关系
如果
证明：假设强连通分量其它的结点不都在
Tarjan 算法求强连通分量
维护对于每个结点
-
$dfn_u$ 表示结点$u$ 是第几个被搜到的。 -
$low_u$ 表示在$u$ 的子树中能够回溯到的最早出现在栈中的结点。具体的，$low_u$ 为以$u$ 为根的子树的和子树中通过一条不在搜索树上的边能到达的结点的$dfn$ 的最小值。
按照深度优先搜索依次搜索每个值，对于每个值维护
-
$v$ 未被访问过：继续对$v$ 进行搜索，用$low_v$ 更新$low_u$ ，因为$v$ 能够回溯到的点$u$ 一定也能回溯到。 -
$v$ 被访问过且在栈中：根据定义，用$dfn_v$ 更新$low_u$ 。 -
$v$ 被访问过且不在栈中：说明$v$ 已经被处理，不做更新。
代码实现
int dfn[N],low[N],idx;
int sta[N],top;
bool vis[N];
void tarjan(int u){
dfn[u] = low[u] = ++idx;
sta[++top] = u;
vis[u] = true;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
do{
vis[sta[top]] = false;
}while(sta[top--]!=u);
}
}割点和桥
定义
对于一张无向图，如果删去一个点后这张图的联通分量增加了，那么这个点是这张图的割点。
对于一张无向图，如果删去一条边后这张图的联通分量增加了，那么这条边是这张图的桥。
Tarjan 算法求割点
dfs 记录时间戳
判断一个点
这个判定唯一不适用于
代码实现
int dfn[N],low[N],idx;
vector<int> g[N];
bool vis[N];
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
int cnt = 0;
for(int v:g[u]){
if(!dfn[v]){
cnt++;
dfs(v,u);
low[u] = min(low[u],low[v]);
if(father&&dfn[u]<=low[v])
vis[u] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
if(!father&&cnt>1)
vis[u] = true;
}Tarjan 算法求割边
和求割点差不多，不需要特殊处理根节点。
因为
代码实现
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],cnt;
bool vis[N];
void dfs(int u,int father){
dfn[u] = low[u] = ++cnt;
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<low[v])
vis[k] = vis[k^1] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}双连通分量
定义
在一张无向图中，对于两个点
在一张无向图中，对于两个点
边双连通具有传递性，点双连通没有。
Tarjan 算法求点双连通
与边双连通不同，一个点可能属于多个点双连通分量。
除了独立点，所有点双连通都有两个以上的点构成。我们用栈维护点，当遇到割点或根节点时，将子树内目前不属于其它点双的非割点或在子树中的割点归到一个新的点双。注意这个点可能还是与其它点双的公共点，所以不能将其出栈。
代码实现
vector<vector<int>> ans;
int dfn[N],low[N],idx;
vector<int> g[N];
int stk[N],tp;
void dfs(int u,int father){
dfn[u] = low[u] = ++idx;
if(g[u].empty()){
ans.push_back({u});
return;
}
stk[++tp] = u;
for(int v:g[u]){
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<=low[v]){
ans.push_back({});
do{
ans.back().push_back(stk[tp--]);
}while(stk[tp+1]!=v);
ans.back().push_back(u);
}
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}Tarjan 算法求边双连通
删掉割边所剩下的就是边双连通分量。割边用 Tarjan 求即可。
代码实现
int h[N],ne[M],e[M],idx;
vector<vector<int>> ans;
int dfn[N],low[N],cnt;
bool b[M],vis[N];
int n,m;
void dfs(int u,int father){
dfn[u] = low[u] = ++cnt;
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(dfn[u]<low[v])
vis[k] = vis[k^1] = true;
}
else if(v!=father)
low[u] = min(low[u],dfn[v]);
}
}
void dfs(int u){
vis[u] = true;
ans.back().push_back(u);
for(int k=h[u];~k;k=ne[k]){
int v = e[k];
if(vis[v]||b[k])
continue;
dfs(v);
}
}
int main(){
for(int k=1;k<=n;k++)
if(!dfn[k])
dfs(k,0);
for(int k=1;k<=n;k++)
if(!vis[k]){
ans.push_back(vector<int>());
dfs(k);
}
}P4200 题解
“遥か月を目指した 今日の空は 彼方西に流れた もう届かないや 届かないや”——《回る空うさぎ》
分析
首先对于每个坐标开一颗平衡树，要维护的东西需要全局取 max，但是自己不能取。
士气值和团结值在一个点没加进去之前是好算的，直接是坐标内部的点威武值的最大值和点的个数。
然后就是要更新坐标上的所有点，先给平衡树的根节点打上标记，打完之后再把点加进去。
现在这个点的标记就不会打在自己身上了。
代码
const int N = 30005,M = 330005;
__gnu_pbds::gp_hash_table<ull,int> ha;
int anss[N],anst[N];
multiset<int> st[M];
int w[N],p[N];
int n;
namespace FHQtreap{
mt19937 myrand(233);
class fhqtreap{
private:
class tree{
public:
int val,l,r;
unsigned int pri;
int tags,tagt;
}tr[N];
vector<int> pool;
int idx;
int create(int val_){
int u = -1;
if(pool.empty())
u = ++idx;
else{
u = pool.back();
pool.pop_back();
}
tr[u] = {val_,0,0,(unsigned int)myrand(),0,0};
return u;
}
void recycle(const int &u){pool.push_back(u);}
void pushdown(int u){
anss[tr[tr[u].l].val] = max(anss[tr[tr[u].l].val],tr[u].tags);
anst[tr[tr[u].l].val] = max(anst[tr[tr[u].l].val],tr[u].tagt);
anss[tr[tr[u].r].val] = max(anss[tr[tr[u].r].val],tr[u].tags);
anst[tr[tr[u].r].val] = max(anst[tr[tr[u].r].val],tr[u].tagt);
tr[tr[u].l].tags = max(tr[tr[u].l].tags,tr[u].tags);
tr[tr[u].l].tagt = max(tr[tr[u].l].tagt,tr[u].tagt);
tr[tr[u].r].tags = max(tr[tr[u].r].tags,tr[u].tags);
tr[tr[u].r].tagt = max(tr[tr[u].r].tagt,tr[u].tagt);
tr[u].tags = tr[u].tagt = 0;
}
int root[M];
public:
int& operator [] (const int &x){return root[x];}
void split(int u,int c,int &x,int &y){
if(!u){
x = y = 0;
return;
}
pushdown(u);
if(tr[u].val<=c){
x = u;
split(tr[u].r,c,tr[u].r,y);
}
else{
y = u;
split(tr[u].l,c,x,tr[u].l);
}
}
int merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri>tr[y].pri){
pushdown(x);
tr[x].r = merge(tr[x].r,y);
return x;
}
pushdown(y);
tr[y].l = merge(x,tr[y].l);
return y;
}
void insert(int r,int c){
int x,y;
split(root[r],c,x,y);
root[r] = merge(merge(x,create(c)),y);
}
void erase(int r,int c){
int x,y,z;
split(root[r],c-1,x,y);
split(y,c,y,z);
if(y){
recycle(y);
y = merge(tr[y].l,tr[y].r);
}
root[r] = merge(merge(x,y),z);
}
void tag(int x,int s,int t){
if(!x)
return;
pushdown(x);
anss[tr[x].val] = max(anss[tr[x].val],s);
anst[tr[x].val] = max(anst[tr[x].val],t);
tr[x].tags = max(tr[x].tags,s);
tr[x].tagt = max(tr[x].tagt,t);
}
void down(int x){
if(!x)
return;
pushdown(x);
down(tr[x].l);
down(tr[x].r);
}
};
}
FHQtreap::fhqtreap tr;
int h(int x,int y){
ull w = (((1ull<<31)+x)<<32)+((1ull<<31)+y);
if(!ha[w])
ha[w] = ha.size();
return ha[w];
}
void insert(int x){
if(!st[p[x]].empty())
anss[x] = max(anss[x],*prev(st[p[x]].end()));
anst[x] = max({anst[x],(int)st[p[x]].size()});
tr.tag(tr[p[x]],w[x],(int)st[p[x]].size());
tr.insert(p[x],x);
st[p[x]].insert(w[x]);
}
void move(int x,int np){
tr.erase(p[x],x);
st[p[x]].erase(st[p[x]].find(w[x]));
p[x] = np;
insert(x);
}
signed main(){
n = in();
for(int k=1;k<=n;k++){
w[k] = in();
int x = in(),y = in();
p[k] = h(x,y);
insert(k);
}
int t = in();
while(t--){
int v = in(),x = in(),y = in();
move(v,h(x,y));
}
for(int k=ha.size();k;k--)
tr.down(tr[k]);
for(int k=1;k<=n;k++)
out(1ll*anss[k]*anst[k],'\n');
return 0;
}后话
至少 2023.04.17 我还是最优解。
风格改变 #3
快读快输添加功能，精简代码
风格改变 #4
快读快输添加泛型，预计三个月内不再修改。
P9989 题解
“笑って走っていく日も 泣きながら帰る日も この街と共に生きてる”——《街》
分析
操作过后的数一定至少变为原来的
可以维护
但是
于是限制一个
最多会被修改
代码
const int N = 200005,V = 1e18;
int a[N];
int n,m;
class segtree{
private:
int tr[N*4];
unsigned s[N*4];
void pushup(int u){
if(tr[u<<1]>V||tr[u<<1|1]>V)
tr[u] = V+1;
else
tr[u] = tr[u<<1]/gcd(tr[u<<1],tr[u<<1|1])*tr[u<<1|1];
s[u] = s[u<<1]+s[u<<1|1];
}
public:
void modify(int u,int l,int r,int L,int R,int v){
if(tr[u]<=V&&v%tr[u]==0)
return;
if(l==r){
s[u] = tr[u] = gcd(tr[u],v);
return;
}
int mid = (l+r)>>1;
if(L<=mid)
modify(u<<1,l,mid,L,R,v);
if(R>mid)
modify(u<<1|1,mid+1,r,L,R,v);
pushup(u);
}
unsigned query(int u,int l,int r,int L,int R){
if(l>=L&&r<=R)
return s[u];
int mid = (l+r)>>1;
if(L<=mid&&R>mid)
return query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
if(L<=mid)
return query(u<<1,l,mid,L,R);
return query(u<<1|1,mid+1,r,L,R);
}
void build(int u,int l,int r){
if(l==r){
s[u] = tr[u] = a[l];
return;
}
int mid = (l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}tr;
signed main(){
n = in,m = in;
for(int k=1;k<=n;k++)
a[k] = in;
tr.build(1,1,n);
while(m--){
int op = in,l = in,r = in;
if(op==1)
tr.modify(1,1,n,l,r,in);
else
out(tr.query(1,1,n,l,r),'\n');
}
return 0;
}P4732 题解
“这样的我会被谁拯救吗 你发现了吧” —— 《月光掌》
分析
设第
考虑可持久化线段树，维护操作的优先级，撤销操作
代码
const int N = 300005;
class segtree{
private:
struct{int l,r,v;} tr[N*30];
int root[N],idx;
void pushup(int u){tr[u].v = min(tr[tr[u].l].v,tr[tr[u].r].v);}
public:
segtree(){tr[0].v=1e9;}
int& operator [](const int &x){return root[x];}
void modify(int &u,int l,int r,int p,int v){
tr[++idx] = tr[u];
u = idx;
if(l==r){
tr[u].v = v;
return;
}
int mid = (l+r)>>1;
if(p<=mid)
modify(tr[u].l,l,mid,p,v);
else
modify(tr[u].r,mid+1,r,p,v);
pushup(u);
}
int query(int u,int l,int r,int p){
if(l==r)
return l;
int mid = (l+r)>>1;
if(!tr[u].r||tr[tr[u].r].v>=p)
return query(tr[u].l,l,mid,p);
return query(tr[u].r,mid+1,r,p);
}
}tr;
int ans[N];
int n;
int main(){
n = in;
for(int k=1;k<=n;k++){
int x = in;
if(x>0){
tr[k] = tr[k-1];
ans[k] = x;
tr.modify(tr[k],1,n,k,0);
}
else{
int p = tr.query(tr[k-1],1,n,-x);
tr[k] = tr[p-1];
ans[k] = ans[p-1];
tr.modify(tr[k],1,n,k,-x);
}
out(ans[k],'\n');
}
return 0;
}Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.