BZOJ 4537 LCM

发表于 | 更新于

Link

有一种智障叫做看到了简单路径的定义就觉得需要求简单路径 有一种被欺骗叫做写挂复杂度而心甘情愿地卡了一晚上常数

Solution

所以说，暴力并查集+线段树+O(n)O(n)扫可以得到45分。。 正解是非常鬼畜的 把边按照aa排序，分成m\sqrt m块

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "lucida"

const int MAXM=100000+11,MAXN=50000+11;
using std::max;
using std::min;
using std::swap;
using std::sort;
template <class T> inline T max(const T &a,const T &b,const T &c) {return max(a,max(b,c));}
namespace dju {
	const int PERM_OPT=0,TEMP_OPT=1;
	struct Node {
		int fa,sz,mxa,mxb;
		void Reset() {
			fa=0;
			sz=1;
			mxa=mxb=-1;
		}
	};
	struct Backup {
		int *var,val;
		Backup(){}Backup(int *var,int val):var(var),val(val){}
	}stack[MAXM];int top;
	void Assign(int &a,int b) {
		stack[++top]=Backup(&a,a);
		a=b;
	}
	void Fallback() {
		while(top) {
			*stack[top].var=stack[top].val;
			top--;
		}
	}
	struct DJU {
		int n;
		Node node[MAXN];
		typedef Node *Iter;
		void Reset() {
			for(int i=1;i<=n;++i)
				node[i].Reset();
		}
		int Root(int x) const {
			return !node[x].fa?x:Root(node[x].fa);	
		}
		Node *Get(int x) {
			return node+Root(x);
		}
		void Union(int x,int y,int a,int b,int type) {//临时操作必须在永久操作后面
			int pret=top,rx=Root(x),ry=Root(y);
			if(rx!=ry) {//return;//小的合到大的里面
				if(node[rx].sz<node[ry].sz) swap(rx,ry);
				Assign(node[ry].fa,rx);
				Assign(node[rx].sz,node[rx].sz+node[ry].sz);
			}
			Assign(node[rx].mxa,max(a,node[rx].mxa,node[ry].mxa));
			Assign(node[rx].mxb,max(b,node[rx].mxb,node[ry].mxb));
			top=type==PERM_OPT?pret:top;
		}
	};
}
using dju::DJU;
using dju::PERM_OPT;
using dju::TEMP_OPT;
using dju::Fallback;
DJU S;

struct Edges {
	int f,t,a,b,id;
}e[MAXM],q[MAXN],t[MAXN];
bool cmp_a(const Edges &e1,const Edges &e2) {
	return e1.a<e2.a;
}
bool cmp_b(const Edges &e1,const Edges &e2) {
	return e1.b<e2.b;
}
int main() {
//	freopen("input","r",stdin);	
	//注意：路径可以不是简单路径 :) :] :}
	static bool Ans[MAXN];
	int n,m;is>>n>>m;S.n=n;
	for(int i=1;i<=m;++i)
		is>>e[i].f>>e[i].t>>e[i].a>>e[i].b;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		is>>q[i].f>>q[i].t>>q[i].a>>q[i].b;
		q[i].id=i;
	}	
	sort(e+1,e+1+m,cmp_a);
	int bsz=(int)sqrt(m+0.5);
	e[m+1].a=INT_MAX;
	for(int l=1,r=bsz;l<=m;l+=bsz,r=min(l+bsz-1,m)) {//每次循环 处理完所有a\in [p,p+bsz) 的询问
		int tc=0;
		for(int i=1;i<=Q;++i)
			if(q[i].a>=e[l].a && q[i].a<e[r+1].a)
				t[++tc]=q[i];
		sort(e+1,e+l,cmp_b);
		sort(t+1,t+1+tc,cmp_b);
		S.Reset();
		for(int i=1,pe=1;i<=tc;++i) {
			while(pe<=l && e[pe].b<=t[i].b) {
				S.Union(e[pe].f,e[pe].t,e[pe].a,e[pe].b,PERM_OPT);
				pe++;
			}
			for(int j=l;j<=r;++j)
				if(e[j].a<=t[i].a && e[j].b<=t[i].b)
					S.Union(e[j].f,e[j].t,e[j].a,e[j].b,TEMP_OPT);
			DJU::Iter pf=S.Get(t[i].f),pt=S.Get(t[i].t);
			Ans[t[i].id]=pf==pt && pf->mxa==t[i].a && pt->mxb==t[i].b;
			Fallback();
		}
	}
	for(int i=1;i<=Q;++i)
		os<<(Ans[i]?"Yes":"No")<<'\n';
	return 0;
}