[题目链接]
https://www.luogu.org/problemnew/show/P4899
[算法]
建出原图的最小/最大生成树的kruskal重构树然后二维数点
时间复杂度 : O((N+Q)logN)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define M 400010
#define MAXLOG 20
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} struct info
{
int x , y;
} a[M];
struct edge
{
int to , nxt;
} ea[N << ] , eb[N << ]; int n , m , q , tot , timera , timerb , cnta , cntb;
int la[N << ] , ra[N << ] , fathera[N << ][MAXLOG] , fatherb[N << ][MAXLOG] ,
deptha[N << ] , depthb[N << ] , rt[N << ] , heada[N << ] , headb[N << ] ,
lb[N << ] , rb[N << ] , fa[N << ] , valuea[N << ] , valueb[N << ] , w[N << ]; struct Presitent_Segment_Tree
{
int sz;
Presitent_Segment_Tree()
{
sz = ;
}
struct node
{
int lc , rc;
int cnt;
} a[N * ];
inline void modify(int &now , int old , int l , int r , int x , int value)
{
now = ++sz;
a[now].lc = a[old].lc , a[now].rc = a[old].rc;
a[now].cnt = a[old].cnt + value;
if (l == r) return;
int mid = (l + r) >> ;
if (mid >= x) modify(a[now].lc , a[old].lc , l , mid , x , value);
else modify(a[now].rc , a[old].rc , mid + , r , x , value);
}
inline int query(int rt1 , int rt2 , int l , int r , int ql , int qr)
{
if (l == ql && r == qr)
return a[rt1].cnt - a[rt2].cnt;
int mid = (l + r) >> ;
if (mid >= qr) return query(a[rt1].lc , a[rt2].lc , l , mid , ql , qr);
else if (mid + <= ql) return query(a[rt1].rc , a[rt2].rc , mid + , r , ql , qr);
else return query(a[rt1].lc , a[rt2].lc , l , mid , ql , mid) + query(a[rt1].rc , a[rt2].rc , mid + , r , mid + , qr);
}
} PST;
inline void addedgea(int u , int v)
{
++tot;
ea[tot] = (edge){v , heada[u]};
heada[u] = tot;
}
inline void addedgeb(int u , int v)
{
++tot;
eb[tot] = (edge){v , headb[u]};
headb[u] = tot;
}
inline void dfsa(int u , int par)
{
fathera[u][] = par;
deptha[u] = deptha[par] + ;
for (int i = ; i < MAXLOG; i++)
fathera[u][i] = fathera[fathera[u][i - ]][i - ];
la[u] = ++timera;
for (int i = heada[u]; i; i = ea[i].nxt)
{
int v = ea[i].to;
if (v == par) continue;
dfsa(v , u);
}
ra[u] = timera;
}
inline void dfsb(int u , int par)
{
fatherb[u][] = par;
depthb[u] = depthb[par] + ;
for (int i = ; i < MAXLOG; i++)
fatherb[u][i] = fatherb[fatherb[u][i - ]][i - ];
lb[u] = ++timerb;
for (int i = headb[u]; i; i = eb[i].nxt)
{
int v = eb[i].to;
if (v == par) continue;
dfsb(v , u);
}
rb[u] = timerb;
}
inline bool cmpa(info a , info b)
{
return min(a.x , a.y) > min(b.x , b.y);
}
inline bool cmpb(info a , info b)
{
return max(a.x , a.y) < max(b.x , b.y);
}
inline int getroot(int x)
{
if (fa[x] == x) return x;
else return fa[x] = getroot(fa[x]);
}
inline void kruskalA()
{
int tot = ;
cnta = n;
timera = ;
sort(a + , a + m + , cmpa);
for (int i = ; i <= * n; i++) fa[i] = i;
for (int i = ; i <= m; i++)
{
int fu = getroot(a[i].x) , fv = getroot(a[i].y);
if (fu != fv)
{
++cnta;
addedgea(cnta , fu);
addedgea(cnta , fv);
valuea[cnta] = min(a[i].x , a[i].y);
fa[fu] = fa[fv] = fa[cnta] = cnta;
++tot;
}
if (tot == n - ) break;
}
dfsa(cnta , );
}
inline void kruskalB()
{
int tot = ;
cntb = n;
timerb = ;
sort(a + , a + m + , cmpb);
for (int i = ; i <= * n; i++) fa[i] = i;
for (int i = ; i <= m; i++)
{
int fu = getroot(a[i].x) , fv = getroot(a[i].y);
if (fu != fv)
{
++cntb;
addedgeb(cntb , fu);
addedgeb(cntb , fv);
valueb[cntb] = max(a[i].x , a[i].y);
fa[fu] = fa[fv] = fa[cntb] = cntb;
++tot;
}
if (tot == n - ) break;
}
dfsb(cntb , );
}
inline bool query(int l1 , int r1 , int l2 , int r2)
{
return PST.query(rt[r1] , rt[l1 - ] , , * n , l2 , r2);
} int main()
{ read(n); read(m); read(q);
for (int i = ; i <= m; i++)
{
read(a[i].x);
read(a[i].y);
++a[i].x; ++a[i].y;
}
kruskalA();
kruskalB();
for (int i = ; i <= n; i++) w[la[i]] = lb[i];
for (int i = ; i <= * n; i++) PST.modify(rt[i] , rt[i - ] , , * n , w[i] , );
for (int i = ; i <= q; i++)
{
int s , e , l , r;
read(s); read(e); read(l); read(r);
++s; ++e; ++l; ++r;
if (s < l || e > r)
{
puts("");
continue;
}
for (int i = MAXLOG - ; i >= ; i--)
if (fathera[s][i] && valuea[fathera[s][i]] >= l)
s = fathera[s][i];
for (int i = MAXLOG - ; i >= ; i--)
if (fatherb[e][i] && valueb[fatherb[e][i]] <= r)
e = fatherb[e][i];
if (query(la[s] , ra[s] , lb[e] , rb[e])) puts("");
else puts("");
} return ;
}