NOI 2015 Day1 T1啊… 学(nao'bu)了一下离散化，跟哈希的写法差不多咯… 大概的想法就是搞一个struct，两个域，分别储存原值和排序后的编号（也就是离散化之后的值）。然后利用这个二分查找一下即可。举个例子，原序列排序后为$ 1, 2, 5, 1000, 25000 $，然后我们分别重新赋予编号\(1, 2, 3, 4, 5\)。当我们要查找其中一个元素时，如\(1000\)，我们就在原值的域中二分一下，即可查找到它对应的离散化后的编号\(4\)。这样，我们的空间复杂度就由\(O(max\{a_i\})\)变成了\(O(n)\)。剩下的就是基础的并查集了：由于本题是离线的，所以先把所有的等于的约束处理一遍，然后判断每一个不等于号是否满足即可。代码如下:

// BZOJ 4195#include 
    
     #include 
     
      #include 
      
       using namespace std; #define rep(i,a,b) for (int i=a; i<=b; i++) #define read(x) scanf("%d", &x)  const int N = 1000000+5; int T, n, a[N], b[N], e[N], fa[N*2], map[N*2]; // 本题map的代码实现是不需要开两个域的，——排序后的下标就是离散后的值 int search(int x) {    int l = 0, r = 2*n+1;    while (l+1 < r) {        int mid = (l+r)>>1;        if (map[mid] <= x) l = mid; else r = mid;    }    while (map[l-1]==map[l]) l--;    return l; } int find(int x) { return fa[x]==x ? x : fa[x] = find(fa[x]); }int main(){    read(T);    while (T--) {        read(n);        rep(i,1,2*n) fa[i] = i;        map[0] = -1;        rep(i,1,n) {            read(a[i]); read(b[i]); read(e[i]);            map[2*i-1] = a[i];            map[2*i] = b[i];        }        sort(map+1, map+n*2+1);        rep(i,1,n) {            if (e[i]==0) continue;            int x = search(a[i]), y = search(b[i]);            int fx = find(x), fy = find(y);            if (fx!=fy) fa[fx] = fy;        }        bool ans = true;        rep(i,1,n) {            if (e[i]==1) continue;            int x = search(a[i]), y = search(b[i]);            int fx = find(x), fy = find(y);            if (fx==fy) { ans = false; break; }        }        printf(ans ? "YES" : "NO");         puts("");    }    return 0;}
      
     
    

​