P14532 [RMI 2018] 颜色 / Colors

考虑从编号大的数开始完成任务，\(u\) 能将祂的颜色传递到 \(v\)，必须满足祂们之间的某条路径上的点的编号小于等于 \(u\)。
假设目前在完成所有 \(b_i=x\) 的任务，那么可以经过的点 \(u\) 必须满足 \(b_u\le x\le a_u\)，可以看作一个点在 \([b_u,a_u]\) 这个区间出现，则一条边 \((u,v)\) 会在 \([max(b_u,b_v),min(a_u,a_v)]\) 这个区间出现。而查询是联通性的问题，考虑使用线段树分治+可撤销并查集。
实现好一点可以做到 \(\mathcal{O}(n\log^2n)\)，我比较懒，写了一个 \(unordred\_map\),常数可能大一些。

代码

/*
Luogu P14532 [RMI 2018] 颜色 / Colors
2026-03-09
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
struct Hash{
    static unsigned long long splitmix64(unsigned long long x){
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator()(unsigned long long x)const{return splitmix64(x+1999999973);}
};
const int maxn=200010;
int n,m,a[maxn],b[maxn],ans;
struct EDGE{int u,v;};
vector<int>hv[maxn];
unordered_map<int,int,Hash>mp[maxn];
class Segment_Tree{
private:
    int fa[maxn];
    int find_root(int u){return fa[u]==0?u:find_root(fa[u]);}
    bool merge(int u,int v){
        u=find_root(u),v=find_root(v);
        if(u==v) return 0;
        if(mp[u].size()<mp[v].size()) swap(u,v);
        fa[v]=u;
        for(auto[x,y]:mp[v]) mp[u][x]+=y;
        return 1;
    }
    vector<EDGE>e[maxn*8];
    void update(int u,int l,int r,int ll,int rr,EDGE b){
        if(l>rr||r<ll) return ;
        if(ll<=l&&r<=rr){e[u].push_back(b);return ;}
        int mid=l+r>>1;
        update(u<<1,l,mid,ll,rr,b),update(u<<1|1,mid+1,r,ll,rr,b);
    }
    void query(int u,int l,int r){
        if(!ans) return ;
        vector<EDGE>ad;
        for(auto[x,y]:e[u]){
            x=find_root(x),y=find_root(y);
            if(merge(x,y)) ad.push_back({x,y});
        }
        if(l==r){
            for(int v:hv[l]){
                int rt=find_root(v);
                if(mp[rt][l]==0){ans=0;return ;}
            }
        }
        else{
            int mid=l+r>>1;
            query(u<<1,l,mid),query(u<<1|1,mid+1,r);
        }
        if(!ans) return ;
        for(int i=ad.size()-1;~i;i--){
            int x=ad[i].u,y=ad[i].v;
            if(fa[x]!=y) swap(x,y);
            fa[x]=0;
            for(auto[a,b]:mp[x]){
                mp[y][a]-=b;
                if(mp[y][a]==0) mp[y].erase(a);
            }
        }
    }
    void clear(int u,int l,int r){
        e[u].clear();
        if(l>=r) return ;
        int mid=l+r>>1;
        clear(u<<1,l,mid),clear(u<<1|1,mid+1,r);
    }
public:
    void update(int l,int r,EDGE b){update(1,1,n,l,r,b);}
    void clear(){
        for(int i=1;i<=n;i++) fa[i]=0;
        clear(1,1,n);
    }
    void query(){query(1,1,n);}
    void build(){for(int i=1;i<=n;i++) mp[i].clear(),mp[i][a[i]]=1;}
}t;
void solve(){
    t.clear(),ans=1;
    for(int i=1;i<=n;i++) hv[i].clear();
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]),hv[b[i]].push_back(i);
    for(int i=1;i<=n;i++) if(a[i]<b[i]) ans=0;
    t.build();
    for(int i=1;i<=m;i++){
        int u,v;read(u,v);
        int appear_l=max(b[u],b[v]),appear_r=min(a[u],a[v]);
        t.update(appear_l,appear_r,{u,v});
    }
    t.query();
    write(ans),write("\n");
}
signed main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}