差别

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

--- 2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/10/02 20:51]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/10/03 11:38] (当前版本)
jxm2001 [习题四]
@@ 行 17: / 行 17: @@
 考虑对时间序列建线段树，然后将每条边插入线段树。
-遍历线段树，同时使用拓展域并查集动态维护此时是否为二分图。如果当前区间已经不是二分图或者遍历到叶子节点即可得到答案并回溯。
+遍历线段树，同时使用拓展域并查集动态维护此时是否为二分图。
+如果当前区间已经不是二分图或者遍历到叶子节点即可得到答案并回溯。
 由于修改操作需要支持回溯，所有考虑使用按秩合并的可撤销并查集。
@@ 行 517: / 行 519: @@
 	}
 	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

用户工具

站点工具

差别

页面工具