CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/09/09 22:33]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数据结构练习_1 [2020/10/08 15:00] (当前版本)
jxm2001
@@ 行 24: / 行 24: @@
 但由于区间 $[l,b]$ 可能已经属于某个区间 $[a,b]$，所以需要线段树分裂将其分裂为 $[a,l-1],[l,b]$。
-同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。
+同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。
+最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。
 初始化时间复杂度 $O(n\log n)$，产生点数 $O(n\log n)$。每次分裂时间复杂度 $O(\log n)$，且增加 $O(\log n)$ 个点。
@@ 行 461: / 行 463: @@
 考虑答案 $x$ 和 $x+1$ 的线段树大部分相同，考虑可持久化线段树维护所有可能答案，答案 $x+1$ 的线段树只需要在答案 $x$ 的线段树上修改即可。
-将数据值域离散化即可，时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n\log n)$。
+将数据值域离散化即可，时间复杂度 $O(n\log n+q\log^2 n)$，空间复杂度 $O(n\log n)$。
 <hidden 查看代码>
@@ 行 571: / 行 573: @@
 		}
 		enter(last=b[ans]);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/P4094|洛谷p4094]]
+=== 题意 ===
+给定一个长度为 $n$ 的字符串 $S$ 和 $m$ 个询问。每次询问所有 $S[a,b]$ 的子串和 $S[c,d]$ 的 $\text{LCP}$ 的最大值。
+=== 题解 ===
+发现所有 $S[a,b]$ 的子串和 $S[c,d]$ 的 $\text{LCP}$ 的最大值等价于所有 $S[a,b]$ 的后缀和 $S[c,d]$ 的 $\text{LCP}$ 的最大值。
+考虑二分答案，对每个答案 $x$，只需要存在 $p$ 满足 $\text{LCP}(S[p,b],S[c,d])\ge x$ 即可。
+而要满足上式必有 $\min(b-p+1,d-c+1)\ge x$，于是上式等价于 $\text{LCP}(S[p,n],S[c,n])\ge x,p\le b-x+1$。
+考虑建立后缀数组，于是满足 $\text{LCP}(S[p,n],S[c,n])\ge x$ 的 $p$ 必然是 $sa$ 数组中的一段连续区间，可以通过二分得到该连续区间。
+然后对 $sa$ 数组建立主席树查询该连续区间是否存在点属于 $[a,b-x+1]$ 即可。
+时间复杂度 $O(n\log n+q\log^2 n)$，空间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=30;
+namespace SA{
+	int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN];
+	int d[MAXN][MAXM],lg2[MAXN];
+	void get_sa(char *s,int n,int m){
+		int *x=X,*y=Y;
+		_rep(i,0,m)c[i]=0;
+		_rep(i,1,n)c[x[i]=s[i]]++;
+		_rep(i,1,m)c[i]+=c[i-1];
+		for(int i=n;i;i--)sa[c[x[i]]--]=i;
+		for(int k=1;k<n;k<<=1){
+			int pos=0;
+			_rep(i,n-k+1,n)y[++pos]=i;
+			_rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k;
+			_rep(i,0,m)c[i]=0;
+			_rep(i,1,n)c[x[i]]++;
+			_rep(i,1,m)c[i]+=c[i-1];
+			for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
+			swap(x,y);
+			pos=0,y[n+1]=0;
+			_rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos;
+			if(pos==n)break;
+			m=pos;
+		}
+		_rep(i,1,n)rk[sa[i]]=i;
+	}
+	void get_height(char *s,int n){
+		for(int i=1,k=0;i<=n;i++){
+			if(k)k--;
+			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
+			height[rk[i]]=k;
+		}
+	}
+	void build_st(int n){
+		lg2[1]=0;
+		_rep(i,2,n)
+		lg2[i]=lg2[i>>1]+1;
+		_rep(i,1,n)
+		d[i][0]=height[i];
+		for(int j=1;(1<<j)<=n;j++){
+			_rep(i,1,n+1-(1<<j))
+			d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
+		}
+	}
+	int lcp(int lef,int rig){
+		lef++;
+		int len=rig-lef+1;
+		return min(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
+	}
+}
+struct Node{
+	int ch[2],cnt;
+}node[MAXN*MAXM];
+int root[MAXN],node_cnt;
+void update(int &k,int p,int lef,int rig,int pos){
+	k=++node_cnt;
+	node[k]=node[p];
+	node[k].cnt++;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update(node[k].ch[0],node[p].ch[0],lef,mid,pos);
+	else
+	update(node[k].ch[1],node[p].ch[1],mid+1,rig,pos);
+}
+int query(int k1,int k2,int L,int R,int ql,int qr){
+	if(ql<=L&&R<=qr)return node[k2].cnt-node[k1].cnt;
+	int M=L+R>>1;
+	if(M>=qr)return query(node[k1].ch[0],node[k2].ch[0],L,M,ql,qr);
+	else if(M<ql)return query(node[k1].ch[1],node[k2].ch[1],M+1,R,ql,qr);
+	else return query(node[k1].ch[0],node[k2].ch[0],L,M,ql,qr)+query(node[k1].ch[1],node[k2].ch[1],M+1,R,ql,qr);
+}
+bool check(int x,int l,int r,int pos,int n){
+	int ql=SA::rk[pos],qr=SA::rk[pos],lef,rig,mid;
+	lef=1,rig=SA::rk[pos]-1;
+	while(lef<=rig){
+		mid=lef+rig>>1;
+		if(SA::lcp(mid,SA::rk[pos])>=x){
+			rig=mid-1;
+			ql=mid;
+		}
+		else
+		lef=mid+1;
+	}
+	lef=SA::rk[pos]+1,rig=n;
+	while(lef<=rig){
+		mid=lef+rig>>1;
+		if(SA::lcp(SA::rk[pos],mid)>=x){
+			lef=mid+1;
+			qr=mid;
+		}
+		else
+		rig=mid-1;
+	}
+	return query(root[ql-1],root[qr],1,n,l,r);
+}
+char buf[MAXN];
+int main()
+{
+	int n=read_int(),q=read_int();
+	scanf("%s",buf+1);
+	SA::get_sa(buf,n,'z');
+	SA::get_height(buf,n);
+	SA::build_st(n);
+	_rep(i,1,n)
+	update(root[i],root[i-1],1,n,SA::sa[i]);
+	while(q--){
+		int l1=read_int(),r1=read_int(),l2=read_int(),r2=read_int();
+		int lef=0,rig=min(r1-l1+1,r2-l2+1),mid,ans;
+		while(lef<=rig){
+			mid=lef+rig>>1;
+			if(check(mid,l1,r1-mid+1,l2,n)){
+				lef=mid+1;
+				ans=mid;
+			}
+			else
+			rig=mid-1;
+		}
+		enter(ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题四 ====
+[[https://www.luogu.com.cn/problem/P3899|洛谷p3899]]
+=== 题意 ===
+给定一棵以 $1$ 为根的树，接下来 $q$ 次询问。每次询问给定 $a,k$，有多少个二元组 $(b,c)$ 满足：
+  - 结点 $a,b,c$ 互异
+  - 结点 $a$ 和结点 $b$ 是结点 $c$ 的祖先
+  - 结点 $a$ 和结点 $b$ 的距离不超过 $k$
+=== 题解 ===
+对每次查询操作，答案分为 $b$ 为 $a$ 祖先和 $a$ 为 $b$ 祖先两种。对于 $b$ 为 $a$ 祖先的情况，易知答案为 $(\text{sz}_a-1)\min(d_a-1,k)$。
+对于 $a$ 为 $b$ 祖先的情况，易知每个 $a$ 的子树中距离 $a$ 不超过 $k$ 的结点的贡献为该结点的子树大小减一。
+于是考虑将每个结点的权值设为该结点的子树大小减一，于是贡献和为所有深度为 $[d_a+1,d_a+k]$ 且 $\text{dfs}$ 序属于 $a$ 的子树的结点的权值和。
+于是问题转化为二维偏序问题，考虑主席树统计答案。时间复杂度 $O((n+q)\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5,MAXM=40;
+struct Node{
+	LL s;
+	int ch[2];
+}node[MAXN*MAXM];
+int root[MAXN],n,node_cnt;
+void update(int &k,int p,int pos,int v,int lef=1,int rig=n){
+	node[k=++node_cnt]=node[p];
+	node[k].s+=v;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(pos<=mid)
+	update(node[k].ch[0],node[p].ch[0],pos,v,lef,mid);
+	else
+	update(node[k].ch[1],node[p].ch[1],pos,v,mid+1,rig);
+}
+LL query(int k1,int k2,int ql,int qr,int lef=1,int rig=n){
+	if(ql<=lef&&rig<=qr)return node[k1].s-node[k2].s;
+	int mid=lef+rig>>1;
+	if(mid>=qr)return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid);
+	else if(mid<ql)return query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+	else return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+}
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int dfs_t,dfn[MAXN],sz[MAXN],d[MAXN],inv_dfn[MAXN];
+void dfs(int u,int fa,int dep){
+	dfn[u]=++dfs_t;
+	sz[dfs_t]=1;d[dfs_t]=dep;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u,dep+1);
+		sz[dfn[u]]+=sz[dfn[v]];
+	}
+}
+int main()
+{
+	n=read_int();
+	int q=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	dfs(1,0,1);
+	_rep(i,1,n)
+	update(root[i],root[i-1],d[i],sz[i]-1);
+	while(q--){
+		int p=read_int(),k=read_int(),u=dfn[p];
+		enter(1LL*(sz[u]-1)*min(d[u]-1,k)+query(root[u+sz[u]-1],root[u],d[u],min(d[u]+k,n)));
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题五 ====
+[[https://www.luogu.com.cn/problem/P3293|洛谷p3293]]
+=== 题意 ===
+给定长度为 $n$ 的序列 $a$ 和 $q$ 个询问。每次询问给定 $b,x,l,r$，输出 $\max_{l\le i\le r}(b\oplus(a_i+x))$。
+=== 题解 ===
+考虑按高位到低位贪心枚举。假设当前枚举到第 $4$ 为，答案 $\text{ans}=c_1c_2c_3???,b=b_1b_2b_3b_4??$。
+优先考虑是否可以使 $\text{ans}=c_1c_2c_31??$，如果 $b_4=1$，则 $\text{ans}\oplus b\in[d_1d_2d_3000,d_1d_2d_3011]$。
+如果 $b_4=0$，则 $\text{ans}\oplus b\in[d_1d_2d_3100,d_1d_2d_3111]$。而 $a=\text{ans}\oplus b-x$，于是主席树查询即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXM=17,MAXV=1e5;
+int root[MAXN],node_cnt;
+struct Node{
+	int ch[2],sz;
+}node[MAXN*40];
+void update(int &k,int p,int pos,int lef=0,int rig=MAXV){
+	node[k=++node_cnt]=node[p];
+	node[k].sz++;
+	if(lef==rig)return;
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update(node[k].ch[0],node[p].ch[0],pos,lef,mid);
+	else
+	update(node[k].ch[1],node[p].ch[1],pos,mid+1,rig);
+}
+int query(int k1,int k2,int ql,int qr,int lef=0,int rig=MAXV){
+	if(lef>qr||rig<ql)return 0;
+	if(ql<=lef&&rig<=qr)return node[k1].sz-node[k2].sz;
+	int mid=lef+rig>>1;
+	return query(node[k1].ch[0],node[k2].ch[0],ql,qr,lef,mid)+query(node[k1].ch[1],node[k2].ch[1],ql,qr,mid+1,rig);
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)
+	update(root[i],root[i-1],read_int());
+	while(q--){
+		int b=read_int(),x=read_int(),l=read_int(),r=read_int();
+		int ans=0;
+		for(int i=MAXM;~i;i--){
+			int ql=((ans^b)>>(i+1))<<(i+1);
+			if(b&(1<<i)){
+				if(query(root[r],root[l-1],ql-x,ql+(1<<i)-1-x))
+				ans|=1<<i;
+			}
+			else{
+				if(query(root[r],root[l-1],ql+(1<<i)-x,ql+(1<<(i+1))-1-x))
+				ans|=1<<i;
+			}
+		}
+		enter(ans);
 	}
 	return 0;

CVBB ACM Team

用户工具

站点工具

页面工具