差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/08/19 12:13]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/10/03 11:38] (当前版本)
jxm2001 [习题四]
@@ 行 17: / 行 17: @@
 考虑对时间序列建线段树，然后将每条边插入线段树。
-遍历线段树，同时使用拓展域并查集动态维护此时是否为二分图。如果当前区间已经不是二分图或者遍历到叶子节点即可得到答案并回溯。
+遍历线段树，同时使用拓展域并查集动态维护此时是否为二分图。
+如果当前区间已经不是二分图或者遍历到叶子节点即可得到答案并回溯。
 由于修改操作需要支持回溯，所有考虑使用按秩合并的可撤销并查集。
@@ 行 239: / 行 241: @@
 对于修改即进货操作，考虑先对其根据商店编号进行排序，这样就可以使用可持久化字典树加离散化处理询问。
-然后遍历线段树时处理完当前节点询问后可以根据修改的时间分配到左右子树处理，每次处理询问重建清空字典树即可。
+然后遍历线段树时处理完当前节点询问后可以根据修改的时间分配到左右子树处理，每次处理询问重建字典树即可。
 时间复杂度 $O((n+m)\log v\log m)$。
@@ 行 350: / 行 352: @@
 	solve(1,1,cnt1);
 	_rep(i,1,cnt2)enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/P3733|洛谷p3733]]
+=== 题意 ===
+给定一个带边权连通图，接下来三种操作：
+  - 新增一条边，新增边从 $1$ 开始编号
+  - 删除某条新增边，保证新增边一定存在
+  - 修改某条新增边的权值，保证新增边一定存在
+要求输出初始时所有经过点 $1$ 的回路的边权异或和最大值和每次操作后的最大值。其中边权为二进制数，且长度 $L\le 1000$。
+=== 题解 1 ===
+首先建立 $\text{dfs}$ 树，于是题目转化为求所有非树边代表环的边权的集合的子集的异或和最大值。
+不难想到线性基加 $\text{bitset}$ 维护。考虑对时间序列建立线段树，操作 $1,2,3$ 不难转化为修改操作加入线段树。
+同时考虑保存线段树分治时当前遍历的链上的所有线性基即可完成回溯操作。时间复杂度 $O\left(\cfrac {(m+q)L^2\log q}w\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1005,MAXD=15;
+typedef bitset<MAXN> bt;
+struct LB{
+	bt p[MAXN];
+	void insert(bt x){
+		for(int i=MAXN-1;i>=0;i--){
+			if(x[i]){
+				if(p[i].any())
+				x^=p[i];
+				else
+				return p[i]=x,void();
+			}
+		}
+	}
+	bt query(){
+		bt ans(0);
+		for(int i=MAXN-1;i>=0;i--){
+			if(!ans[i]&&p[i][i])
+			ans^=p[i];
+		}
+		return ans;
+	}
+}lb[MAXD];
+void Enter_bitset(const bt& x){
+	bool flag=false;
+	for(int i=MAXN-1;i>=0;i--){
+		if(x[i])flag=true;
+		if(flag)putchar('0'+x[i]);
+	}
+	if(!flag)putchar('\0');
+	putchar('\n');
+}
+char buf[MAXN];
+bt Read_bitset(){
+	bt ans(0);
+	scanf("%s",buf);
+	int len=strlen(buf);
+	reverse(buf,buf+len);
+	_for(i,0,len)
+	ans[i]=buf[i]-'0';
+	return ans;
+}
+vector<bt> s[MAXN<<2];
+int lef[MAXN<<2],rig[MAXN<<2];
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	if(L==R)return;
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+}
+void update(int k,int L,int R,const bt& v){
+	if(L<=lef[k]&&rig[k]<=R){
+		s[k].push_back(v);
+		return;
+	}
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)
+	update(k<<1,L,R,v);
+	if(mid<R)
+	update(k<<1|1,L,R,v);
+}
+void solve(int k,int d){
+	_for(i,0,s[k].size())
+	lb[d].insert(s[k][i]);
+	if(lef[k]==rig[k]){
+		Enter_bitset(lb[d].query());
+		return;
+	}
+	lb[d+1]=lb[d];
+	solve(k<<1,d+1);
+	lb[d+1]=lb[d];
+	solve(k<<1|1,d+1);
+}
+struct Edge{
+	int to,next;
+	bt w;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void AddEdge(int u,int v,const bt& w){
+	edge[++edge_cnt]=Edge{v,head[u],w};
+	head[u]=edge_cnt;
+}
+bt dis[MAXN];
+int dfn[MAXN],dfs_t;
+void dfs(int u){
+	dfn[u]=++dfs_t;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(!dfn[v]){
+			dis[v]=dis[u]^edge[i].w;
+			dfs(v);
+		}
+		else if(dfn[v]<=dfn[u])
+		lb[1].insert(dis[u]^dis[v]^edge[i].w);
+	}
+}
+struct Edge2{
+	int u,v,last;
+	bt w;
+}edge2[MAXN];
+int main()
+{
+	int n=read_int(),m=read_int(),q=read_int();
+	build(1,0,q);
+	while(m--){
+		int u=read_int(),v=read_int();
+		bt w=Read_bitset();
+		AddEdge(u,v,w);
+		AddEdge(v,u,w);
+	}
+	dis[1]=bt(0);
+	dfs(1);
+	int k=0;
+	_rep(i,1,q){
+		scanf("%s",buf);
+		if(buf[0]=='A'){
+			k++;
+			edge2[k].u=read_int(),edge2[k].v=read_int();
+			edge2[k].w=Read_bitset(),edge2[k].last=i;
+		}
+		else if(buf[1]=='a'){
+			int t=read_int();
+			update(1,edge2[t].last,i-1,dis[edge2[t].u]^dis[edge2[t].v]^edge2[t].w);
+			edge2[t].last=0;
+		}
+		else{
+			int t=read_int();
+			update(1,edge2[t].last,i-1,dis[edge2[t].u]^dis[edge2[t].v]^edge2[t].w);
+			edge2[t].w=Read_bitset();
+			edge2[t].last=i;
+		}
+	}
+	_rep(i,1,k){
+		if(edge2[i].last)
+		update(1,edge2[i].last,q,dis[edge2[i].u]^dis[edge2[i].v]^edge2[i].w);
+	}
+	solve(1,1);
+	return 0;
+}
+</code>
+</hidden>
+=== 题解 2 ===
+同样考虑线性基维护，将所有修改操作按左端点排序，然后按右端点贪心处理。时间复杂度 $O\left(\cfrac {(m+q)L^2}w\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1005,MAXD=15;
+typedef bitset<MAXN> bt;
+namespace LB{
+	bt p[MAXN];
+	int pos[MAXN];
+	void insert(bt x,int y){
+		for(int i=MAXN-1;i>=0;i--){
+			if(x[i]){
+				if(!p[i].any()){
+					p[i]=x;
+					pos[i]=y;
+					break;
+				}
+				else if(pos[i]<y){
+					swap(p[i],x);
+					swap(pos[i],y);
+				}
+				x^=p[i];
+			}
+		}
+	}
+	bt query(int l){
+		bt ans(0);
+		for(int i=MAXN-1;i>=0;i--){
+			if(!ans[i]&&p[i][i]&&pos[i]>=l)
+			ans^=p[i];
+		}
+		return ans;
+	}
+};
+void Enter_bitset(const bt& x){
+	bool flag=false;
+	for(int i=MAXN-1;i>=0;i--){
+		if(x[i])flag=true;
+		if(flag)putchar('0'+x[i]);
+	}
+	if(!flag)putchar('\0');
+	putchar('\n');
+}
+char buf[MAXN];
+bt Read_bitset(){
+	bt ans(0);
+	scanf("%s",buf);
+	int len=strlen(buf);
+	reverse(buf,buf+len);
+	_for(i,0,len)
+	ans[i]=buf[i]-'0';
+	return ans;
+}
+struct Edge{
+	int to,next;
+	bt w;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void AddEdge(int u,int v,const bt& w){
+	edge[++edge_cnt]=Edge{v,head[u],w};
+	head[u]=edge_cnt;
+}
+bt dis[MAXN];
+int dfn[MAXN],dfs_t;
+void dfs(int u){
+	dfn[u]=++dfs_t;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(!dfn[v]){
+			dis[v]=dis[u]^edge[i].w;
+			dfs(v);
+		}
+		else if(dfn[v]<=dfn[u])
+		LB::insert(dis[u]^dis[v]^edge[i].w,MAXN);
+	}
+}
+struct Edge2{
+	int u,v,last;
+	bt w;
+}edge2[MAXN];
+struct Node{
+	bt x;
+	int l,r;
+}node[MAXN];
+int idx[MAXN];
+struct cmp{
+	bool operator () (const int a,const int b)const{
+		return node[a].l<node[b].l;
+	}
+};
+int main()
+{
+	int n=read_int(),m=read_int(),q=read_int();
+	while(m--){
+		int u=read_int(),v=read_int();
+		bt w=Read_bitset();
+		AddEdge(u,v,w);
+		AddEdge(v,u,w);
+	}
+	dis[1]=bt(0);
+	dfs(1);
+	int k=0,q2=0;
+	_rep(i,1,q){
+		scanf("%s",buf);
+		if(buf[0]=='A'){
+			k++;
+			edge2[k].u=read_int(),edge2[k].v=read_int();
+			edge2[k].w=Read_bitset(),edge2[k].last=i;
+		}
+		else if(buf[1]=='a'){
+			int t=read_int();
+			node[q2].x=dis[edge2[t].u]^dis[edge2[t].v]^edge2[t].w;
+			node[q2].l=edge2[t].last,node[q2].r=i-1;
+			q2++;
+			edge2[t].last=0;
+		}
+		else{
+			int t=read_int();
+			node[q2].x=dis[edge2[t].u]^dis[edge2[t].v]^edge2[t].w;
+			node[q2].l=edge2[t].last,node[q2].r=i-1;
+			q2++;
+			edge2[t].w=Read_bitset();
+			edge2[t].last=i;
+		}
+	}
+	_rep(i,1,k){
+		if(edge2[i].last){
+			node[q2].x=dis[edge2[i].u]^dis[edge2[i].v]^edge2[i].w;
+			node[q2].l=edge2[i].last,node[q2].r=q;
+			q2++;
+		}
+	}
+	_for(i,0,q2)
+	idx[i]=i;
+	sort(idx,idx+q2,cmp());
+	int pos=0;
+	_rep(i,0,q){
+		while(pos<q2&&node[idx[pos]].l<=i){
+			LB::insert(node[idx[pos]].x,node[idx[pos]].r);
+			pos++;
+		}
+		Enter_bitset(LB::query(i));
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题四 ====
+[[https://loj.ac/problem/6515|LOJ6515]]
+=== 题意 ===
+给定一个双端队列，队列的每个元素有属性 $(w,v)$，队列初始为空。接下来有以下操作：
+  - 在队首添加一个元素
+  - 在队尾添加一个元素
+  - 在队首删除一个元素
+  - 在队尾删除一个元素
+  - 从队列取出若干元素，使得 $(\sum w\bmod p)\in [l,r]$，且 $\sum v$ 取最大值，输出此时的 $\sum v$
+=== 题解 1 ===
+考虑线段树分治处理，由于 $p$ 较小，于是可以 $\text{dp}$ 暴力转移和回溯。时间复杂度 $O(pq\log q)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5,MAXP=505,MAXD=18;
+LL dp[MAXD][MAXP],temp[MAXP];
+int p,ql[MAXN],qr[MAXN];
+int lef[MAXN<<2],rig[MAXN<<2];
+vector<pair<int,int> >s[MAXN<<2];
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	if(L==R)return;
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+}
+void update(int k,int L,int R,pair<int,int> v){
+	if(L<=lef[k]&&rig[k]<=R){
+		s[k].push_back(v);
+		return;
+	}
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)
+	update(k<<1,L,R,v);
+	if(mid<R)
+	update(k<<1|1,L,R,v);
+}
+LL get_max(LL a,LL b,int v){
+	if(a!=-1&&b!=-1)
+	return max(a,b+v);
+	else if(a!=-1)
+	return a;
+	else if(b!=-1)
+	return b+v;
+	else
+	return -1;
+}
+void cal(LL *dp,int w,int v){
+	_for(i,0,p)
+	temp[i]=get_max(dp[i],dp[(i+p-w)%p],v);
+	_for(i,0,p)
+	dp[i]=temp[i];
+}
+void solve(int k,int d){
+	_for(i,0,p)
+	dp[d][i]=dp[d-1][i];
+	_for(i,0,s[k].size())
+	cal(dp[d],s[k][i].first,s[k][i].second);
+	if(lef[k]==rig[k]){
+		if(ql[lef[k]]!=-1){
+			LL ans=-1;
+			_rep(i,ql[lef[k]],qr[lef[k]])
+			ans=max(ans,dp[d][i]);
+			enter(ans);
+		}
+		return;
+	}
+	solve(k<<1,d+1);
+	solve(k<<1|1,d+1);
+}
+struct node{
+	int last,w,v;
+};
+deque<node>q;
+char buf[MAXN];
+int main()
+{
+	int n=read_int();
+	p=read_int();
+	build(1,1,n);
+	mem(ql,-1);mem(qr,-1);
+	_rep(i,1,n){
+		scanf("%s",buf);
+		if(buf[0]=='I'){
+			int w=read_int()%p,v=read_int();
+			if(buf[1]=='F')
+			q.push_front(node{i,w,v});
+			else
+			q.push_back(node{i,w,v});
+		}
+		else if(buf[0]=='D'){
+			if(buf[1]=='F'){
+				update(1,q.front().last,i-1,make_pair(q.front().w,q.front().v));
+				q.pop_front();
+			}
+			else{
+				update(1,q.back().last,i-1,make_pair(q.back().w,q.back().v));
+				q.pop_back();
+			}
+		}
+		else
+		ql[i]=read_int(),qr[i]=read_int();
+	}
+	while(!q.empty()){
+		update(1,q.front().last,n,make_pair(q.front().w,q.front().v));
+		q.pop_front();
+	}
+	mem(dp[0],-1);
+	dp[0][0]=0;
+	solve(1,1);
+	return 0;
+}
+</code>
+</hidden>
+=== 题解 2 ===
+考虑建立两个栈维护队首修改操作和队尾修改操作。当加入元素时直接暴力背包转移，当删除元素时如果栈为空则均分重构栈。
+根据势能分析法，易知重构的均摊时间复杂度为 $O(p)$。
+对于查询操作，考虑先假定第一个栈提供特征值为 $0$，单调队列维护第二个栈 $[l,r]$ 范围最大值。
+然后第一个栈遍历 $0\sim p-1$，同时单调队列维护第二个栈的区间最大值，单次询问时间复杂度 $O(p)$。
+于是总时间复杂度 $O(pq)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5,MAXP=505;
+LL dp1[MAXN][MAXP],dp2[MAXN][MAXP];
+int p,lpos=MAXN+1,rpos=MAXN,mpos=MAXN,ltop,rtop;
+pair<int,int> a[MAXN<<2];
+pair<int,LL> que[MAXN<<1];
+LL get_max(LL a,LL b,int v){
+	if(a!=-1&&b!=-1)
+	return max(a,b+v);
+	else if(a!=-1)
+	return a;
+	else if(b!=-1)
+	return b+v;
+	else
+	return -1;
+}
+void cal(LL *dp1,LL *dp2,int w,int v){
+	_for(i,0,p)
+	dp1[i]=get_max(dp2[i],dp2[(i+p-w)%p],v);
+}
+LL cal2(LL a,LL b){
+	if(a!=-1&&b!=-1)
+	return a+b;
+	else
+	return -1;
+}
+void rebuild(){
+	mpos=lpos+rpos>>1;
+	ltop=rtop=0;
+	for(int i=mpos;i>=lpos;i--){
+		cal(dp1[ltop+1],dp1[ltop],a[i].first,a[i].second);
+		ltop++;
+	}
+	for(int i=mpos+1;i<=rpos;i++){
+		cal(dp2[rtop+1],dp2[rtop],a[i].first,a[i].second);
+		rtop++;
+	}
+}
+LL query(int ql,int qr){
+	if(qr<ql)qr+=p;
+	int front=0,tail=1,ml=qr-ql;
+	_for(i,ql,qr){
+		while(front>=tail&&que[front].second<=dp2[rtop][i%p])front--;
+		que[++front]=make_pair(i,dp2[rtop][i%p]);
+	}
+	LL ans=-1;
+	_for(i,qr,qr+p){
+		while(front>=tail&&i-que[tail].first>ml)tail++;
+		while(front>=tail&&que[front].second<=dp2[rtop][i%p])front--;
+		que[++front]=make_pair(i,dp2[rtop][i%p]);
+		ans=max(ans,cal2(dp1[ltop][(p-i+qr)%p],que[tail].second));
+	}
+	return ans;
+}
+char buf[MAXN];
+int main()
+{
+	int n=read_int();
+	p=read_int();
+	mem(dp1[0],-1);dp1[0][0]=0;
+	mem(dp2[0],-1);dp2[0][0]=0;
+	_rep(i,1,n){
+		scanf("%s",buf);
+		if(buf[0]=='I'){
+			int w=read_int()%p,v=read_int();
+			if(buf[1]=='F'){
+				a[--lpos]=make_pair(w,v);
+				cal(dp1[ltop+1],dp1[ltop],a[lpos].first,a[lpos].second);
+				ltop++;
+			}
+			else{
+				a[++rpos]=make_pair(w,v);
+				cal(dp2[rtop+1],dp2[rtop],a[rpos].first,a[rpos].second);
+				rtop++;
+			}
+		}
+		else if(buf[0]=='D'){
+			if(ltop+rtop==1){
+				ltop=rtop=0;
+				mpos=lpos+rpos>>1;
+				lpos=mpos+1,rpos=mpos;
+			}
+			else if(buf[1]=='F'){
+				if(!ltop)rebuild();
+				lpos++,ltop--;
+			}
+			else{
+				if(!rtop)rebuild();
+				rpos--,rtop--;
+			}
+		}
+		else{
+			int ql=read_int(),qr=read_int();
+			enter(query(ql,qr));
+		}
+	}
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具