可持久化数据结构

nich666 / 2023-06-30 / 原文

配套题单

Day1

谈笑风生

给一颗有根树$T$,$Q$次询问，每次给定两个数$a$和$k$，求有多少个有序三元组$(a,b,c)$满足、

$a,b,c$互不相同
$a,b$都是$c$的祖先
$a,b$在树上的距离不超过$k$

对于$b$是$a$祖先的情况，贡献明显是$\min(dep_a-1,k)\times (sz_a-1)$

对于$a$是$b$祖先的情况，贡献为

\[\sum_{dfn_a<dfn_b<df n_a+sz_z\and dep_a< dep_b \le dep_a+k} sz_b-1 \]

对$dfn$序建主席树，二维数点即可

Peaks加强版

给你一张边带权点带权无向图（点权范围不超过$n$），多次询问$(u,x)$，代表从$u$出发，只经过边权不大于$x$的边，所能到达的点中点权的 $K$ 小值是多少。强制在线。

先建出 $Kruskal$ 重构树，同理对$dfn$序建主席树

BZOJ3514 Codechef MARCH14 GERALD07加强版

$N$个点$M$条边的无向图，多次询问保留图中编号在$[l,r]$的边的时候图中的联通块个数，强制在线。

这个题就很有趣了

首先有一个结论：联通块数量为点数$-$边数

对下标建主席树，$T[r]$的$[L,R]$表示$[L,R]$区间中有哪些有用的的边，所以我们用$LCT$维护联通块最小编号

BZOJ3744 Gty的妹子序列

强制在线，多次询问区间逆序对数

咕了

BZOJ3166 [HEOI 2013]ALO

现有一个序列，一段长度>1区间的权值为区间内的次大值与区间内除次大值外的数的异或最大值

保证序列内元素两两不同。N<=50000，每个元素都不超过10^9.
问你这个序列所有长度>1的子区间的权值的最大值是多少。

建出可持久化$Tries$

用链表找到每个数往左往右第二个比他大的数，然后区间查询与一个数异或最大值

BZOJ4103

给定长度为$n$的数列$X={x_1,x_2,...,x_n}$和长度为$m$的数列$Y={y_1,y_2,...,y_m}，$令矩阵$A$中第$i$行第$j$列的值$A_{i,j}=x_i\ xor y_j$，每次询问给定矩形区域$i\in [u,d],j\in [l,r]$，找出第$k$大的$A_{i,j}$。

对于100%的数据，$0\le X_i,Y_j<2^{31}$,$1\le u\le d\le n\le 10^3$,
$1\le l\le r\le m\le 3\times 10^5,1\le k\le (d-u+1)\times (r-l+1),1\le p\le 500$

看这个范围，我们可以猜测这是一个$O(np\log V+m\log V)$的做法

对$Y$建可持久化$Tries$，枚举每个$x_i$在这一位为$1$的总数和，跟$k$比较一下即可

~~算了，还是看代码吧~~

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,V=30;
struct Node{int ch[2],v;}t[N<<6];
int n,m,Q,a[N],rt[N],tot;
inline void add(int k,int p,int v){
	t[k]=t[p],t[k].v++;
	for(int i=V;~i;--i){
		int c=(v>>i)&1;
		t[t[k].ch[c]=++tot]=t[t[p].ch[c]];
		++t[k=t[k].ch[c]].v,p=t[p].ch[c];
	}
}
int b[N],cnt;
int p[N],q[N];
inline int ask(int k){
	int res=0;
	for(int i=V;~i;--i){
		int tmp=0;
		for(int j=1;j<=cnt;++j){
			int c=((b[j]>>i)&1)^1;
			tmp+=t[t[q[j]].ch[c]].v-t[t[p[j]].ch[c]].v;
		}
		if(k<=tmp){
			res+=1<<i;
			for(int j=1;j<=cnt;++j){
				int c=((b[j]>>i)&1)^1;
				q[j]=t[q[j]].ch[c],p[j]=t[p[j]].ch[c];
			}
		}
		else{
			k-=tmp;
			for(int j=1;j<=cnt;++j){
				int c=((b[j]>>i)&1);
				q[j]=t[q[j]].ch[c],p[j]=t[p[j]].ch[c];
			}
		}
	}
	return res;
}
signed main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1,x;i<=m;++i) cin>>x,add(rt[i]=++tot,rt[i-1],x);
	cin>>Q;
	int l1,l2,r1,r2,k;
	while(Q--){
		cin>>l1>>r1>>l2>>r2>>k;
		cnt=0;
		for(int i=l1;i<=r1;++i) b[++cnt]=a[i],p[cnt]=rt[l2-1],q[cnt]=rt[r2];
		cout<<ask(k)<<endl;
	}
}

BZOJ2653 middle

一个长度为$n$的序列$a$，设其排过序之后为$b$，其中位数定义为$b[n/2]$，其中$a,b$从$0$开始标号,除法取下整。给你一个长度为$n$的序列$s$。回答$Q$个这样的询问：$s$的左端点在$[a,b]$之间,右端点在$[c,d]$之间的子序列中，最大的中位数。
其中$a<b<c<d$。位置也从$0$开始标号。强制在线

先离散化

对一个$v$来说,将序列中$\ge v$的看做$1$,$<v$的看做$-1$,中位数$\ge v$即区间存在一个连续段使总和$\ge 0$，转化成两个前缀的形式

从小到大枚举$v$,每次对将$v-1$从$1$变为$-1$，也就是后缀$-2$,预处理出对每个$v$的主席树

对于询问二分，在主席树上找到$[a-1,b-1]$的的最小值，$[c,d]$的最大值，判断相减是否$\ge 0$

BZOJ4571 美味

一家餐厅有$ n$ 道菜，编号 $1\ldots n$ ，大家对第 $i$ 道菜的评价值为 $a_i(1≤i≤n)$。有 $m$ 位顾客，第 $i$ 位顾客的期望值为 $b_i$，而他的偏好值为 $x_i$ 。因此，第 $i $位顾客认为第 $j$ 道菜的美味度为 $b_i XOR (a_j+x_i)$，$XOR$ 表示异或运算。第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 $l_i$ 道到第 $r_i $道中选择。请你帮助他们找出最美味的菜。

见到异或考虑$Tries$,~~然后就死掉了~~

对原序列建主席树，然后对每位顾客的每一个二进制位分开处理

找到使此位为$1$的区间，减去$x_i$，得到菜品区间，判断这里面是否有数就行了

BZOJ3784 树上的路径

给定一个$n$个结点的树，结点用正整数$1\ldots n$编号。每条边有一个正整数权值。用$d(a,b)$表示从结点$a$到结点$b$路边上经过边的权值。其中要求$a<b$.将这$\frac{n(n-1)}{2}$个距离从大到小排序，输出前$m$个距离值。

$n\le 5\times 10^4,m\le \min(\frac{n(n-1)}{2},3\times 10^5)$

令$1$为根，处理一颗线段树为$1$到其他节点的距离，记录对应距离与对应的节点

然后我们发现，对于$u$的子节点$v$,距离改变的是$v$子树内节点的距离减少了$v$(边权),而对$v$子树之外的节点增加了$v$

然后主席树修改即可

然后考虑将离每个节点最远距离放在堆里，每次取出时将对应节点主席树上最远距离清零，放入此时最远距离

由于有$a<b$限制，所以要减少一遍

评测记录

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,INF=1e9;
int rt[N],n,m,tot;
struct tree{int lc,rc,v,pos,add;}t[N<<6];
#define k1 t[k].lc
#define k2 t[k].rc
#define mid ((l+r)>>1)
inline void up(int k){
	t[k].v=max(t[k1].v,t[k2].v)+t[k].add;
	if(t[k1].v>=t[k2].v) t[k].pos=t[k1].pos;
	else t[k].pos=t[k2].pos;
}
void change(int &k,int p,int l,int r,int x,int v){
	t[k=++tot]=t[p];
	if(l==r) return t[k].v=v,t[k].pos=x,void();
	if(x<=mid) change(k1,t[p].lc,l,mid,x,v);
	else change(k2,t[p].rc,mid+1,r,x,v);
	up(k);
}
void add(int &k,int p,int l,int r,int L,int R,int v){
	t[k=++tot]=t[p];
	if(L<=l&&R>=r) return t[k].add+=v,t[k].v+=v,void();
	if(L<=mid) add(k1,t[p].lc,l,mid,L,R,v);
	if(R>mid)  add(k2,t[p].rc,mid+1,r,L,R,v);
	up(k);
}
int ask(int k,int l,int r,int x){
	if(!k||l==r) return t[k].v;
	if(x<=mid) return ask(k1,l,mid,x)+t[k].add;
	else ask(k2,mid+1,r,x)+t[k].add;
}
int head[N],to[N],ne[N],e[N],idx,dis[N];
int dfn[N],ed[N],id[N];
inline void add(int x,int y,int z){to[++idx]=y,ne[idx]=head[x],head[x]=idx,e[idx]=z;}
void dfs(int x,int fa){
	dfn[x]=++idx,id[idx]=x;
	for(int i=head[x];i;i=ne[i])
		if(to[i]!=fa) dis[to[i]]=dis[x]+e[i],dfs(to[i],x);
	ed[x]=idx;
}
void dfs2(int x,int fa){
	for(int i=head[x];i;i=ne[i])
		if(to[i]!=fa){
			add(rt[to[i]],rt[x],1,n,1,n,e[i]);
			add(rt[to[i]],rt[to[i]],1,n,dfn[to[i]],ed[to[i]],-2*e[i]);
			dfs2(to[i],x);
		}
}
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
priority_queue<PII >q;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	int a,b,c;
	for(int i=1;i<n;++i)
		cin>>a>>b>>c,add(a,b,c),add(b,a,c);
	idx=0,dfs(1,0);
	for(int i=1;i<=n;++i) change(rt[1],rt[1],1,n,i,dis[id[i]]);
	dfs2(1,0);
	for(int i=1;i<=n;++i) q.push(mp(t[rt[i]].v,i));
	m<<=1;
	while(m--){
		PII a=q.top();q.pop();
		int x=a.second,k=t[rt[x]].pos;
		change(rt[x],rt[x],1,n,t[rt[x]].pos,-INF);
		if(t[rt[x]].v>0) q.push(mp(t[rt[x]].v,x));
		if(m&1) cout<<a.first<<endl;
	}
}