离散化操作

acwing 103电影

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1000000007;
const ll N = 2e5 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            w = -1;
    for (; isdigit(ch); ch = getchar())
        s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

ll  n , m , a[N], b[N] , c[N] , ans[N] , lang[3*N] , ui[3*N];
int cnt;
ll get(ll x){
    return lower_bound(ui + 1, ui + 1 + cnt , x) - ui;
} 
int main()
{
    n = read();
    int tot = 0;
    for(int i = 1; i <= n ; i++) {
        a[i] = read();
        lang[++tot] = a[i];
    }
    m = read();
    for(int i = 1; i <= m ; i++){
        b[i] = read();
        lang[++tot] = b[i];
    }
    for(int i = 1; i <= m ; i++){
        c[i] = read();
        lang[++tot] = c[i];
    }
    sort(lang + 1 , lang  + 1 + tot);
    cnt = 0;
    for(int i = 1; i < tot ; i++){
        if(i == 1 || lang[i] != lang[i - 1])
        ui[++cnt] = lang[i];
    }
    for(int i = 1; i <= n ; i++) ans[get(a[i])]++;
    int ans0 = 0 , ans1 = 0 , ans2 = 0;
    for(int i = 1; i <= m ; i++){
        int ansb = ans[get(b[i])] ,ansc = ans[get(c[i])];
        if(ansb > ans1 || ansb == ans1 && ansc > ans2){
            ans0 = i , ans1 = ansb , ans2 = ansc;
        }
    }
    cout<<ans0<<endl;
    return 0;
}

acwing237 (程序自动化分析（离散加并查集）)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1000000007;
const ll N = 1e6 + 7;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            w = -1;
    for (; isdigit(ch); ch = getchar())
        s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

int n , ui[2*N], a[N] , b[N] , c[N] , lang[2*N], tot, cnt , fa[2*N];
ll get(ll x){
    return lower_bound(ui + 1, ui + 1 + cnt , x) - ui;
} 
void init(){
    for(int i = 1; i <= cnt ; i++)
    fa[i] = i;
}
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)] = find(y);
}
int main()
{
    int t = read();
    while(t--){
        n = read();
        for(int i = 1; i <= n ; i++){
            a[i] = read() , b[i] = read(), c[i] = read(); 
        }
        tot = 0;
        for(int i = 1; i <= n ; i++){
            lang[++tot] = a[i];
            lang[++tot] = b[i];
        }
        cnt = 0;
        sort(lang + 1, lang + 1 + tot);
        for(int i = 1 ; i <= tot ; i++){
            if(i == 1 || lang[i] != lang[i - 1]){
                ui[++cnt] = lang[i];
            }
        }
        init();
        int flag = 1;
        for(int i = 1 ; i <= n ; i++){
            int x = get(a[i]) , y = get(b[i]);
            if(c[i] == 1) merge(x,y);  
        }
        for(int i = 1 ; i <= n ; i++){
            int x = get(a[i]) , y = get(b[i]);
            if(c[i] == 0){
                if(find(x) == find(y)){
                    flag = 0;
                    break;
                }
            }
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}