调了太久...

Solution

比 树 难调多了，一堆细节，而且难想...

超暴力的分块。按 $a$ 排序后分块，然后把询问塞到对应 $a$ 值域范围的 最后面 的块。

然后就可以怎么暴力怎么来了，其中有一些玄妙的操作...

注意最大值初始化为负数...

https://oi.men.ci/hnoi2016-multiple/

Code

// Code by ajcxsu
// Problem: lcm

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10, M=1e5+10;
struct Edge { int u, v, a, b, id; } e[M];
bool cmp(const Edge &a, const Edge &b) { return a.a<b.a; }
bool cmp2(const Edge &a, const Edge &b) { return a.b<b.b; }
int bel[M], al[M], ar[M];
vector<Edge> q[700];
bool ans[N];

#define CLR(x, y) memset(x, y, sizeof(x))
int fa[M], ma1[M], ma2[M], rk[M];
int r1[M], r2[M], r3[M], r4[M], ri[M], top;
int Find(int x) { return fa[x]?Find(fa[x]):x; }
void ins(int x) { ++top, r1[top]=fa[x], r2[top]=ma1[x], r3[top]=ma2[x], r4[top]=rk[x], ri[top]=x; }
void Union(Edge x, bool rec=0) {
    int af=Find(x.u), bf=Find(x.v);
    if(rec) ins(af);
    if(af==bf) { ma1[bf]=max(ma1[bf], x.a), ma2[bf]=max(ma2[bf], x.b); return; }
    if(rec) ins(bf);
    if(rk[af]>rk[bf]) swap(af, bf);
    fa[af]=bf, rk[bf]=max(rk[af]+1, rk[bf]), ma1[bf]=max({ma1[bf], ma1[af], x.a}), ma2[bf]=max({ma2[bf], ma2[af], x.b});
}
void res() { top=0; CLR(fa, 0), CLR(ma1, -1), CLR(ma2, -1), CLR(rk, 0); }
void pop() {
    while(top) {
        int id=ri[top]; fa[id]=r1[top], ma1[id]=r2[top], ma2[id]=r3[top], rk[id]=r4[top];
        top--;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].a>>e[i].b;
    sort(e+1, e+1+m, cmp);
    int unit=sqrt(m), cm=(m-1)/unit+1;
    memset(al, 0x3f, sizeof(al));
    for(int i=1;i<=m;i++) bel[i]=(i-1)/unit+1, ar[bel[i]]=e[i].a, al[bel[i]]=min(al[bel[i]], e[i].a);
    int c; cin>>c;
    Edge na;
    for(int i=1;i<=c;i++) {
        cin>>na.u>>na.v>>na.a>>na.b, na.id=i;
        int x=upper_bound(ar+1, ar+1+cm, na.a)-ar;
        if(na.a<al[x]) x--;
        q[x].push_back(na);
    }
    int nl, nr;
    for(int i=1;i<=cm+1;i++) {
        nl=min((i-1)*unit+1, m+1), nr=min(i*unit, m);
        sort(q[i].begin(), q[i].end(), cmp2);
        sort(e+1, e+nl, cmp2); res();
        int np=1;
        for(Edge x:q[i]) {
            while(np<nl && e[np].b<=x.b) Union(e[np]), np++;
            for(int j=nl;j<=nr;j++) if(e[j].a<=x.a && e[j].b<=x.b) Union(e[j], 1);
            int af=Find(x.u), bf=Find(x.v);
            ans[x.id]=(af==bf && ma1[af]==x.a && ma2[af]==x.b);
            pop();
        }
    }
    for(int i=1;i<=c;i++) cout<<(ans[i]?"Yes\n":"No\n");
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-hnoi-2016-multiple.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆