/*
lazy思想
染色模型
適合顏色數(shù)目較少(64以內(nèi))的區(qū)間染色問題。
具體操作：
1、對某個連續(xù)區(qū)間進行染色。
2、詢問某個連續(xù)區(qū)間的顏色情況（種類、數(shù)目等等）。
適用題型：
poj 2777 Count Color
hdu 5023 A Corrupt Mayor's Performance Art
結(jié)點存儲
顏色值的位或colorBit：每個顏色用2的冪來表示，顏色值表示分別為1、2、4、8
，該區(qū)間有哪些顏色就可以用他們的或來表示
延遲標記lazy：該段區(qū)間完全被染色成了lazy這種顏色，這里的lazy要么是2的冪，要么是0
接口說明
giveLazyToSon 傳遞延遲標記給兩個子結(jié)點（調(diào)用子結(jié)點的updateByValue，并且lazy重置）
updateByValue 通過某個顏色值更新當前結(jié)點信息（更新colorBit、lazy）
updateFromSon 通過兩個子結(jié)點更新當前結(jié)點信息（更新colorBit）
mergeQuery 詢問時用于對分割后的子結(jié)點進行合并用，不同情況實現(xiàn)不同
調(diào)用說明
建樹： 調(diào)用靜態(tài)函數(shù) treeNode::segtree_build(1, 1, n);
插入([x, y], val)： 調(diào)用靜態(tài)函數(shù) treeNode::segtree_insert(1, 1, n, x, y, val);
詢問([x, y]): 調(diào)用靜態(tài)函數(shù) treeNode::segtree_query(1, 1, n, x, y, ans);
*/ #include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 131072
typedef
int ValueType;
// 返回[l, r]和[x, y]兩條線段是否相交
bool is_intersect(
int l,
int r,
int x,
int y) {
return !(r < x || l > y);
}
// 返回[x, y]是否完全包含[l, r]
bool is_contain(
int l,
int r,
int x,
int y) {
return x <= l && r <= y;
}
struct treeNode {
ValueType lazy;
ValueType colorBit;
int pid;
int len;
treeNode() {
reset(-1, 0);
}
void reset(
int p,
int _len) {
pid = p;
colorBit = 0;
lazy = 0;
len = _len;
}
int lson() {
return pid << 1; }
int rson() {
return pid<<1|1; }
void updateByValue(ValueType _val);
void giveLazyToSon();
void updateFromSon();
// 詢問的時候?qū)⒔Y(jié)點合并后計入答案
void mergeQuery(
int p);
// 建樹
static void segtree_build(
int p,
int l,
int r);
// 插入線段[x, y]到[l, r]
static void segtree_insert(
int p,
int l,
int r,
int x,
int y, ValueType val);
// 區(qū)間詢問[x, y]上的信息
static void segtree_query(
int p,
int l,
int r,
int x,
int y,
int id);
};
/* 全局變量
nodes[MAXN*2] 存儲所有靜態(tài)線段樹結(jié)點(動態(tài)開內(nèi)存太費時間)
totalNodes 存儲結(jié)點數(shù)目
*/treeNode nodes[MAXN*2];
vector <
int> adj[MAXN];
int adjHash[MAXN], adjHashCount = 0;
void treeNode::updateByValue(ValueType _val) {
lazy = _val;
colorBit = _val;
}
void treeNode::giveLazyToSon() {
if(lazy) {
nodes[ lson() ].updateByValue(lazy);
nodes[ rson() ].updateByValue(lazy);
lazy = 0;
}
}
void treeNode::updateFromSon() {
int lc = nodes[ lson() ].colorBit;
int rc = nodes[ rson() ].colorBit;
if(lc == -1 || rc == -1) {
colorBit = -1;
}
else {
colorBit = (lc == rc) ? lc : -1;
}
}
void treeNode::mergeQuery(
int p) {
colorBit |= nodes[p].colorBit;
}
void treeNode::segtree_build(
int p,
int l,
int r) {
// 創(chuàng)建線段樹結(jié)點的時候只需要知道該線段樹結(jié)點管轄區(qū)間的長度，區(qū)間端點不用存，可以在遞歸的時候作為函數(shù)傳參
nodes[p].reset(p, r-l+1);
if (l < r) {
int mid = (l + r) >> 1;
// 遞歸創(chuàng)建左右兒子結(jié)點
treeNode::segtree_build(p<<1, l, mid);
treeNode::segtree_build(p<<1|1, mid+1, r);
nodes[p].updateFromSon();
}
}
void treeNode::segtree_insert(
int p,
int l,
int r,
int x,
int y, ValueType val) {
if( !is_intersect(l, r, x, y) ) {
return ;
}
if( is_contain(l, r, x, y) ) {
nodes[p].updateByValue(val);
return ;
}
nodes[p].giveLazyToSon();
int mid = (l + r) >> 1;
treeNode::segtree_insert(p<<1, l, mid, x, y, val);
treeNode::segtree_insert(p<<1|1, mid+1, r, x, y, val);
nodes[p].updateFromSon();
}
void treeNode::segtree_query(
int p,
int l,
int r,
int x,
int y,
int id) {
if( !is_intersect(l, r, x, y) ) {
return ;
}
if( is_contain(l, r, x, y) ) {
int preid = nodes[p].colorBit;
if( preid != -1 ) {
if( adjHash[ preid ] < adjHashCount ) {
adj[ preid ].push_back( id );
adjHash[ preid ] = adjHashCount;
}
return ;
}
}
nodes[p].giveLazyToSon();
int mid = (l + r) >> 1;
treeNode::segtree_query(p<<1, l, mid, x, y, id);
treeNode::segtree_query(p<<1|1, mid+1, r, x, y, id);
nodes[p].updateFromSon();
}
struct line {
int y1, y2, x;
}L[MAXN];
int cmp(line a, line b) {
return a.x < b.x;
}
int n = 16001, m;
int segHash[MAXN], segHashCount;
int main() {
int i, j, k, t;
scanf("%d", &t);
while( t-- ) {
scanf("%d", &m);
for(i = 0; i < m; i++) {
scanf("%d %d %d", &L[i].y1, &L[i].y2, &L[i].x);
L[i].y1 = L[i].y1 * 2 + 1;
L[i].y2 = L[i].y2 * 2 + 1;
adj[i+1].clear();
}
sort(L, L + m, cmp);
treeNode::segtree_build(1, 1, n);
for(i = 0; i < m; i++) {
adjHashCount ++;
int color = i + 1;
treeNode::segtree_query(1, 1, n, L[i].y1, L[i].y2, color);
treeNode::segtree_insert(1, 1, n, L[i].y1, L[i].y2, color);
}
int ans = 0;
for(i = 1; i <= m; i++) {
int u = i;
for(j = 0; j < adj[u].size(); j++) {
int v = adj[u][j];
segHashCount ++;
for(k = 0; k < adj[v].size(); k++) {
segHash[ adj[v][k] ] = segHashCount;
}
for(k = 0; k < adj[u].size(); k++) {
if( segHash[ adj[u][k] ] == segHashCount ) {
ans ++;
}
}
}
}
printf("%d\n", ans);
}
return 0;
}