AC了但有疑问
查看原帖
AC了但有疑问
856004
Grammar_hbw楼主2024/9/2 16:04

以下代码把s.insert(o)提到调用newnode(o)的地方可以AC(主函数已省略,就是调用询问的),请问在newnode里面和外面insert有什么区别

struct dsu{
	map<int,int> mp;
	set<int> s;
	int p[maxn<<2],num[maxn<<2],cnt;
	int newnode(int o){
		if(!mp[o]){
			s.insert(o);
			mp[o]=(++cnt);
			num[cnt]=o;
			p[cnt]=cnt;
		}
		return mp[o];
	}
	void build(int n){cnt=n;for(int i=1;i<=n;i++) p[i]=newnode(a[i]);}
	int find(int x){return (p[x]==x)?x:(p[x]=find(p[x]));}
	void modify(int x,int v){p[x]=newnode(v);} //byPos
	int query(int x){return num[find(x)];}
	void modify(int l,int r,int v){
		auto ll=s.lower_bound(l),rr=s.upper_bound(r);
		for(auto i=ll;i!=rr;i++) p[mp[*i]]=newnode(v),mp[*i]=0;
		for(auto i=ll;i!=rr;i=s.erase(i)); 
	} //byVal
} tr;
2024/9/2 16:04
加载中...