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 <algorithm>
#include <cstdio>
#include <cstring>
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;
}