差别

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

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

CVBB ACM Team

用户工具

站点工具

差别

页面工具