英雄哪里出来

/*
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;
}