给出 n 条垂线,问有多少个三元组 中,任意两条可以看得到对方
样例中 答案为 1 ,横坐标 为 1 的线段+横坐标 为 2 (3,4)的线段+横坐标为 1 的线段
做过 poj 2777 区间染色的问题 就 很容易看出这个 题目 其实就 是 该问题 的小 延伸,我们可以根据x坐标进行从小到大的排序,然后对每条线段query该线段左端,改线段统领的
区间内 有多少种color,vis[][]记录,如果可以看得到的color在两个color之间加一条相当于边的标记,表示可看见,然后Update
全部query完之后,暴力n^3 求解。。
同时要注意如 样例 中 ,0 2 2,3 4 2这两条线段,可以看到 2 3之间是没有被覆盖的,然而我们查询的时候查到的是2被覆盖,3被覆盖,因此我们会认为[2,3]是被覆盖的。解决方法就是把纵坐标都乘以2.
做题过程:
哎,12分钟就敲完了。然后调了18分钟还是没过。发现又是思路有点偏颇。刚开始把更新和查询放在一起做了,这样子做是不对的。因为更新只更新到[L,R],但是查询可以查询到更下一层。结果就。。。orz了。
还有一点是不变的真理。可以用-1表示这个区间有很多种颜色,用0表示这个区间没有颜色。用>= 1来表示颜色。这样形成习惯就好。
刚开始看的时候没想明白为什么要先按坐标排序,敲的时候想明白了。这样才能保证题意所要求的能相连。
/* Pro: 0 Sol: date: */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <set> #include <vector> #define maxn 20000 #define lson l, m , rt << 1 #define rson m + 1, r, rt << 1 |1 #define havem int m = (l + r ) >> 1 using namespace std; int T,n; bool vis[8001][8001]; int color[maxn << 2]; struct Seg{ int x, y1, y2; bool operator <(const Seg & cmp) const{ return x < cmp.x; } }p[maxn]; void build(int l, int r, int rt){ color[rt] = 0; if(l == r) return ; havem; build(lson); build(rson); } void push_dn(int rt){ if(color[rt] != -1) color[rt << 1] = color[rt << 1 | 1] = color[rt], color[rt] = -1; } void query(int L, int R, int val, int l , int r, int rt){ if(color[rt] != -1){// vis[color[rt]][val] = true; return ; }havem; push_dn(rt); if(L <= m) query(L,R,val,lson); if(R > m) query(L,R,val,rson); } void update(int L,int R,int val, int l, int r,int rt){ // if(color[rt] != -1){// 不能偷懒,将更新和询问写着一起。因为可能递归到L,R的更下一层,在这里写的话就不对了。。。 // vis[color[rt]][val] = true; // } if(L <= l && r <= R){ color[rt] = val; return ; }havem; push_dn(rt); if(L <= m) update(L,R,val,lson); if(R > m) update(L,R,val,rson); } int main(){ scanf("%d",&T); while(T --){ scanf("%d",&n); for(int i = 1; i <= n; i ++) memset(vis[i],0,sizeof(vis[i])); for(int i = 1; i <= n; i ++){ scanf("%d%d%d",&p[i].y1,&p[i].y2, &p[i].x); p[i].y1 <<= 1; p[i].y2 <<= 1; } sort(p + 1, p + n + 1); build(0,maxn,1); for(int i = 1; i <= n; i ++){ // query(p[i].y1,p[i].y2,i,0,maxn,1); update(p[i].y1,p[i].y2,i,0,maxn,1); } int cnt = 0; for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ if(i == j) continue; if(vis[i][j]){ for(int k = 1; k <= n; k ++){ if(k == i || k == j) continue; if(vis[i][k] && vis[j][k]) cnt ++; } } } } printf("%d\n",cnt); } return 0; }