题解：P14532 [RMI 2018] 颜色 / Colors

· · 题解

先考虑一个正确的操作方式，由于点权是不能变大的，所以把目标点权最大的挑出来，设为 v，点权比 v 大的点都是无意义的，需要找一个小于等于 v 的最大点权进行覆盖，且只能操作这些点，然后把目标点权为 v 的点删掉，直到全部点都删光为止。发现这样会进行很多无意义赋值，考虑直接跳到 v 等于这个点目标点权的时刻，发现此时 b_i>v 的点已经被删光了，a_i<v 的点不能操作，所以能操作的点必须满足 b_i\leq v\leq a_i，能操作的边必须两个端点都满足这个限制，只要在当前点的连通块内有一个点满足 a_i=v 即合法，充要性是显然的。

因此考虑线段树分治，按秩合并并查集，启发式合并 unordered_multiset，注意 erase 函数会将整个 multiset 中所有值为 value 的元素全部删掉，所以要使用 find 找出一个后再 erase。时间复杂度应该是 O(n\log^2n) 的。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=4e5+5;
int flag,a[N],b[N],f[N],h[N],tp=0;
struct node2{int x,y,z;}st[M];
struct node{int x,y;}s[M];
vector<int> e[N<<2],pt[N];
unordered_multiset<int> ex[N];
void add(int u,int l,int r,int x,int y,int z){
    if(x<=l && r<=y){
        e[u].emplace_back(z);
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) add(u<<1,l,mid,x,y,z);
    if(mid<y) add(u<<1|1,mid+1,r,x,y,z);
    return;
}
int find(int x){
    if(x==f[x]) return x;
    return find(f[x]);
}
void merge(int x,int y,int u){
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    tp++;
    st[tp].x=u;
    if(h[fx]>h[fy]){
        f[fy]=fx;
        st[tp].y=fy;
        if(ex[fx].size()<ex[fy].size()){
            swap(ex[fx],ex[fy]);
            st[tp].z=1;
        }
        else st[tp].z=0;
        for(auto it:ex[fy]) ex[fx].insert(it);
    }
    else if(h[fx]<h[fy]){
        f[fx]=fy;
        st[tp].y=fx;
        if(ex[fy].size()<ex[fx].size()){
            swap(ex[fx],ex[fy]);
            st[tp].z=1;
        }
        else st[tp].z=0;
        for(auto it:ex[fx]) ex[fy].insert(it);
    }
    else {
        f[fy]=fx;h[fx]++;h[fy]++;
        st[tp].y=fy;
        if(ex[fx].size()<ex[fy].size()){
            swap(ex[fx],ex[fy]);
            st[tp].z=1;
        }
        else st[tp].z=0;
        for(auto it:ex[fy]) ex[fx].insert(it);
    }
    return;
}
void dg(int u,int l,int r){
    for(auto it:e[u]) merge(s[it].x,s[it].y,u);
    if(l==r){
        for(auto it:pt[l]){
            int x=find(it);
            if(ex[x].find(l)==ex[x].end()){
                flag=1;
                break;
            }
        }
    }
    else {
        int mid=l+r>>1;
        dg(u<<1,l,mid);
        dg(u<<1|1,mid+1,r);
    }
    while(tp>0 && st[tp].x==u){
        int x=st[tp].y,z=st[tp].z;
        if(h[x]==h[f[x]]) h[x]--,h[f[x]]--;
        for(auto it:ex[x]) ex[f[x]].erase(ex[f[x]].find(it));
        if(z) swap(ex[x],ex[f[x]]);
        f[x]=x;tp--;
    }
    e[u].clear();
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n,m;flag=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>b[i];
            if(a[i]<b[i]) flag=1;
            pt[b[i]].emplace_back(i);
            f[i]=i,h[i]=1;
            ex[i].insert(a[i]);
        }
        for(int i=1,x,y,l,r;i<=m;i++){
            cin>>x>>y;
            s[i].x=x,s[i].y=y;
            l=max(b[x],b[y]);
            r=min(a[x],a[y]);
            if(l<=r) add(1,1,n,l,r,i);
        }
        dg(1,1,n);
        if(flag==1) cout<<"0\n";
        else cout<<"1\n";
        for(int i=1;i<=n;i++){
            ex[i].clear();
            pt[i].clear();
        }
    }
    return 0;
}