社区讨论

关于移动一行的 1e5 A性质

wwrkwrkwrk
P11364[NOIP2024] 树上查询参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m46hgmqb
此快照首次捕获于
2024/12/02 11:41
去年
此快照最后确认于
2025/11/04 13:28
4 个月前
查看原帖
本人试图复现赛时代码，期望 52，交上去发现 36。
CPP
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
vector<int>g[500005]; 
set<pair<int,int>>gg[500005];
int dep[500005];
vector<pair<pair<int,int>,int>>fz[500005];
//min(r,r')-max(l,l')>=k
//r-l+1>=k
//r-l'+1>=k r>=k+l'-1
//r'-l+1>=k l<=r'+1-k
vector<pair<pair<int,int>,int>>ques[500005];
void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	gg[now].insert({now,now});
		fz[1].push_back({{now,now},dep[now]});//notice~
	for(auto x:g[now])if(x!=fa){
//		cnt++;
		dfs(x,now);
		if(gg[x].size()>gg[now].size())swap(gg[x],gg[now]);
		for(auto p:gg[x]){
			auto w=p,ww=p;
			auto c=gg[now].upper_bound(w);
			while(c!=gg[now].end()&&(*c).first==w.second+1){
				w.second=(*c).second;
				c=gg[now].erase(c);
			}
			while(c!=gg[now].begin()&&(*prev(c)).second==w.first-1){
				w.first=(*prev(c)).first;
				gg[now].erase(prev(c));
			}
			if(w!=ww){
				int l=w.first,r=w.second;
//				cerr<<now<<' '<<l<<' '<<r<<','<<dep[now]<<'\n';
				fz[r-l+1].push_back({{l,r},dep[now]});
			}
			gg[now].insert(w);
		}
	}
//	if(gg[now].find({now,now})!=gg[now].end()){
//	}
}
inline int lowbit(int x){
	return x&(-x);
}
struct bit1{
	gp_hash_table<int,int>ww;
	void fz(int a,int b){
		a=500000-a+1;
		while(a<=500000){
			ww[a]=max(ww[a],b);
			a+=lowbit(a); 
		}
	}
	int ge(int a){
		a=500000-a+1;
		if(a<0)return 0;
		int ans=0;
		while(a){
			if(ww.find(a)!=ww.end()){
				ans=max(ans,ww[a]);
			}
			a-=lowbit(a);
		}
		return ans;
	}
};
struct bit2{
	bit1 w[500005];
	void fz(int a,int b,int c){
		while(a<=500000){
			w[a].fz(b,c);
			a+=lowbit(a);
		}
	}
	int ge(int a,int b){
		if(a<0)return 0;
		int ans=0;
		while(a){
			ans=max(ans,w[a].ge(b));
			a-=lowbit(a);
		}
		return ans;
	}
}bb;
int ans[500005];
signed main(){
//	freopen("a.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	} 
	dfs(1,0);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int l,r,k;
		cin>>l>>r>>k;
		ques[k].push_back({{l,r},i});
	}
//	cout<<(*gg[1].begin()).first<<endl;
	int w=0; 
	for(int i=1;i<=n;i++){
		w+=fz[i].size();
	}
	for(int i=n;i>=1;i--){
		for(auto x:fz[i]){
//		cout<<i<<endl;
			bb.fz(x.first.first,x.first.second,x.second);
//			cerr<<x.first.first<<' '<<x.first.second<<' '<<x.second<<endl; 
		}
		for(auto x:ques[i]){
//		cout<<' '<<i<<endl;
			int k=i;
			int l=x.first.first,r=x.first.second,id=x.second;
//			cerr<<i<<' '<<r+1-k<<'.'<<k+l-1<<bb.ge(r+1-k,k+l-1)<<' '<<'\n';
			ans[id]=bb.ge(r+1-k,k+l-1);
		}
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}
其中被 1e5 的链卡了。在试图研究原因的过程中移动了一行代码，变成这样：
CPP
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
vector<int>g[500005]; 
set<pair<int,int>>gg[500005];
int dep[500005];
vector<pair<pair<int,int>,int>>fz[500005];
//min(r,r')-max(l,l')>=k
//r-l+1>=k
//r-l'+1>=k r>=k+l'-1
//r'-l+1>=k l<=r'+1-k
vector<pair<pair<int,int>,int>>ques[500005];
void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	gg[now].insert({now,now});
	for(auto x:g[now])if(x!=fa){
//		cnt++;
		dfs(x,now);
		if(gg[x].size()>gg[now].size())swap(gg[x],gg[now]);
		for(auto p:gg[x]){
			auto w=p,ww=p;
			auto c=gg[now].upper_bound(w);
			while(c!=gg[now].end()&&(*c).first==w.second+1){
				w.second=(*c).second;
				c=gg[now].erase(c);
			}
			while(c!=gg[now].begin()&&(*prev(c)).second==w.first-1){
				w.first=(*prev(c)).first;
				gg[now].erase(prev(c));
			}
			if(w!=ww){
				int l=w.first,r=w.second;
//				cerr<<now<<' '<<l<<' '<<r<<','<<dep[now]<<'\n';
				fz[r-l+1].push_back({{l,r},dep[now]});
			}
			gg[now].insert(w);
		}
	}
//	if(gg[now].find({now,now})!=gg[now].end()){
//	}
		fz[1].push_back({{now,now},dep[now]});//moved~
}
inline int lowbit(int x){
	return x&(-x);
}
struct bit1{
	gp_hash_table<int,int>ww;
	void fz(int a,int b){
		a=500000-a+1;
		while(a<=500000){
			ww[a]=max(ww[a],b);
			a+=lowbit(a); 
		}
	}
	int ge(int a){
		a=500000-a+1;
		if(a<0)return 0;
		int ans=0;
		while(a){
			if(ww.find(a)!=ww.end()){
				ans=max(ans,ww[a]);
			}
			a-=lowbit(a);
		}
		return ans;
	}
};
struct bit2{
	bit1 w[500005];
	void fz(int a,int b,int c){
		while(a<=500000){
			w[a].fz(b,c);
			a+=lowbit(a);
		}
	}
	int ge(int a,int b){
		if(a<0)return 0;
		int ans=0;
		while(a){
			ans=max(ans,w[a].ge(b));
			a-=lowbit(a);
		}
		return ans;
	}
}bb;
int ans[500005];
signed main(){
//	freopen("a.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	} 
	dfs(1,0);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int l,r,k;
		cin>>l>>r>>k;
		ques[k].push_back({{l,r},i});
	}
//	cout<<(*gg[1].begin()).first<<endl;
	int w=0; 
	for(int i=1;i<=n;i++){
		w+=fz[i].size();
	}
	for(int i=n;i>=1;i--){
		for(auto x:fz[i]){
//		cout<<i<<endl;
			bb.fz(x.first.first,x.first.second,x.second);
//			cerr<<x.first.first<<' '<<x.first.second<<' '<<x.second<<endl; 
		}
		for(auto x:ques[i]){
//		cout<<' '<<i<<endl;
			int k=i;
			int l=x.first.first,r=x.first.second,id=x.second;
//			cerr<<i<<' '<<r+1-k<<'.'<<k+l-1<<bb.ge(r+1-k,k+l-1)<<' '<<'\n';
			ans[id]=bb.ge(r+1-k,k+l-1);
		}
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}
（注意到 dfs 中有一行代码被移动位置） 它成功获得了 52 分。想知道原因。
（52 分的RE是因为对 >105> 10^5 进行 assertassert 跳掉）
（思路：lca\text{lca} 能取到 kk 当且仅当所有节点都在子树内。启发式合并之后在线动态二维数点。）
（这份代码常数应该比赛时大，赛时代码大样例4 2.6s，这份代码本机 4.5s）。

回复

共 2 条回复，欢迎继续交流。

正在加载回复...