题目

分析

考虑将询问和边权按 \(a\) 分别从小到大排序，考虑最暴力的做法就是将不超过 \(a'\) 且 不超过 \(b'\) 的边抽取出来

放进并查集判断 \(a,b\) 的最大值都能达到 \(a',b'\)，并查集可以撤销，这样就做到 \(O(qm\log n)\)

考虑让边尽量减小抽取的次数，将边每 \(B\) 个分一段，那么询问实际上也会分段，

之前段的所有边可以用归并排序按照 \(b\) 排序，用双指针加入并查集。

当前段的边只有 \(B\) 条，每次完成一个询问后撤销操作，

\(O(qB\log n+\frac{m^2}{B}\log n)\)，理论上取 \(B=\sqrt{\frac{m^2}{q}}\) 时最优，

实际上取 \(B=\sqrt{m\log{n}}\) 就可以跑得飞快了

代码

#include 
#include 
#include  
#include 
#define rr register
using namespace std;
const int N=50011,M=100011;
struct four{int x,y,a,b;}e[M],E[M],q[N];
int b[N],f[N],dep[N],mxa[N],mxb[N],yea[M],yeb[M],yed[M],yex[M],yey[M],Top,n,m,Q,block,rk[N],ans[N];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
bool cmp1(four x,four y){return x.ab?a:b;}
inline signed getf(int u){return f[u]==u?u:getf(f[u]);}
inline void uni(four t){
	rr int fa=getf(t.x),fb=getf(t.y);
	if (dep[fa]m)?(m+1):(i+block);
		for (rr int j=1;j<=Q;++j)
		if (e[i].a<=q[rk[j]].a&&(i+block>m||q[rk[j]].a