/*
lazy思想
染色模型
适合颜色数目较少(64以内)的区间染色问题。
具体操作：
1、对某个连续区间进行染色。
2、询问某个连续区间的颜色情况（种类、数目等等）。
适用题型：
poj 2777 Count Color
hdu 5023 A Corrupt Mayor's Performance Art
结点存储
颜色值的位或colorBit：每个颜色用2的幂来表示，颜色值表示分别为1、2、4、8
，该区间有哪些颜色就可以用他们的或来表示
延迟标记lazy：该段区间完全被染色成了lazy这种颜色，这里的lazy要么是2的幂，要么是0
接口说明
giveLazyToSon 传递延迟标记给两个子结点（调用子结点的updateByValue，并且lazy重置）
updateByValue 通过某个颜色值更新当前结点信息（更新colorBit、lazy）
updateFromSon 通过两个子结点更新当前结点信息（更新colorBit）
mergeQuery 询问时用于对分割后的子结点进行合并用，不同情况实现不同
调用说明
建树： 调用静态函数 treeNode::segtree_build(1, 1, n);
插入([x, y], val)： 调用静态函数 treeNode::segtree_insert(1, 1, n, x, y, val);
询问([x, y]): 调用静态函数 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();
// 询问的时候将结点合并后计入答案
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);
// 区间询问[x, y]上的信息
static void segtree_query(
int p,
int l,
int r,
int x,
int y,
int id);
};
/* 全局变量
nodes[MAXN*2] 存储所有静态线段树结点(动态开内存太费时间)
totalNodes 存储结点数目
*/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) {
// 创建线段树结点的时候只需要知道该线段树结点管辖区间的长度，区间端点不用存，可以在递归的时候作为函数传参
nodes[p].reset(p, r-l+1);
if (l < r) {
int mid = (l + r) >> 1;
// 递归创建左右儿子结点
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;
}