题目链接：?id=1436
题意：给出一些与y轴平行的在第一象限（也可能在y轴上）的线段，告诉你线段对应x轴的位置xi，线段对应y轴的yi1，yi2。
如果两个线段能用一条平行x轴的线段连接起来，且该线段不与其他垂直的线段相交，则称这两个线段可见。若存在三个垂直线段两两可见，则构成一个线段三角形。
求给出的所有线段中的线段三角形的个数。
思路：对y轴方向构造一棵线段树，用来查询区间[l，，r]被哪个线段覆盖。如果区间[l，r]被多个线段覆盖，并不需要存储所有的线段。可以对x先进行排序，依次进行更新，所以只需存循环到当前的线段时，该区间[l，r]被之前的哪一个线段覆盖。注意对y的值还需倍增。每次更新前可以先查询当前线段与之前线段的是否可见。若区间[l，r]被某个线段覆盖，则现在枚举的线段与覆盖的线段可见（可用一个数组记录线段之间的两两可见的情况，最后暴力求解答案）。
代码如下
;N = 8010;struct Segment {int x;int ys, ye;< (Segment a, Segment b) {if (a.x != b.x)return a.x > b.x;else if (a.ys != b.ys)return a.ys > b.ys;return a.ye > b.ye;}};int n;Segment Se[N];int a[N << 3];int lazy[N << 3];bool visble[N][N];void pushup(int rt) {if (a[rt << 1] == a[rt << 1 | 1])a[rt] = a[rt << 1];elsea[rt] = -1;}void pushdown(int rt) {if (lazy[rt] != -1) {lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];a[rt << 1] = a[rt << 1 | 1] = lazy[rt];lazy[rt] = -1;}}void update(int p, int l, int r, int rt) {if (Se[p].ys <= l && r <= Se[p].ye) {a[rt] = p;lazy[rt] = p;return ;}if (l == r)return ;pushdown(rt);int m = (l + r) >> 1;if (Se[p].ys <= m)update(p, lson);if (Se[p].ye > m)update(p, rson);pushup(rt);}void query(int p, int l, int r, int rt) {if (a[rt] == 0)return ;if (a[rt] != 0 && a[rt] != -1) {visble[a[rt]][p] = true;return ;}if (l == r)return ;pushdown(rt);int m = (l + r) >> 1;if (Se[p].ys <= m)query(p, lson);if (Se[p].ye > m)query(p, rson);pushup(rt);}int main() {int t_case;scanf(“%d”, &t_case);for (int i_case = 1; i_case <= t_case; i_case++) {memset(lazy, -1, sizeof(lazy));memset(visble, false, sizeof(visble));memset(a, 0, sizeof(a));scanf(“%d”, &n);for (int i = 1; i <= n; i++) {scanf(“%d%d%d”, &Se[i].ys, &Se[i].ye, &Se[i].x);Se[i].ys <<= 1;Se[i].ye <<= 1;}sort(Se + 1, Se + n + 1);for (int i = 1; i <= n; i++) {query(i, 1, N << 1, 1);update(i, 1, N << 1, 1);}int co = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (visble[i][j]) {for (int k = 1; k <= n; k++) {if (visble[i][k] && visble[k][j])co++;}}}}printf(“%d\n”, co);}return 0;}
懂得倾听别人的忠告。
