首页 > 代码库 > Poj1436Horizontally Visible Segments线段树
Poj1436Horizontally Visible Segments线段树
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 8000 + 10;bool Hash[maxn][maxn];struct Node{ int a; int b; int c;}node[maxn];int color[maxn * 10];int cmp(const Node &a, const Node &b){ return a.c < b.c;}void down(int rt){ if (~color[rt]){ color[rt << 1] = color[rt << 1 | 1] = color[rt]; color[rt] = -1; }}void build(int l, int r, int rt){ color[rt] = -1; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson);}void update(int L, int R, int add, int l, int r, int rt){ if (L <= l&&r <= R){ color[rt] = add; return; } down(rt); int mid = (l + r) >> 1; if (L <= mid) update(L, R, add, lson); if (R > mid) update(L, R, add, rson);}void ask(int L, int R, int add, int l, int r, int rt){ if (~color[rt]){ Hash[add][color[rt]] = Hash[color[rt]][add] = add; return; } if (l == r) return; int mid = (l + r) >> 1; if (L <= mid) ask(L, R, add, lson); if (R > mid) ask(L, R, add, rson);}int main(){ int Icase, n; cin >> Icase; while (Icase--){ cin >> n; int ans = 0; int Max = 0; memset(Hash, 0, sizeof(Hash)); for (int i = 0; i < n; i++){ int a; int b; int c; scanf("%d%d%d", &a, &b, &c); node[i].a = a * 2; node[i].b = b * 2; node[i].c = c; if (node[i].b>Max) Max = node[i].b; } sort(node, node + n, cmp); build(0, Max, 1); for (int i = 0; i < n; i++){ ask(node[i].a, node[i].b, i, 0, Max, 1); update(node[i].a, node[i].b, i, 0, Max, 1); } for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ if (!Hash[i][j]) continue; for (int k = j + 1; k < n; k++){ if (Hash[i][k] && Hash[j][k])ans++; } } } cout << ans << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。