POJ 1436 Horizontally Visible Segments（线段树区间修改）
最后更新于：2022-04-01 15:53:34
题目链接：[点击打开链接](http://poj.org/problem?id=1436)
题意：n条竖直线段，如果两条线段之间可见（即可以用一条水平线段连接而不触碰其他线段），则称它们可见。 如果三条线段任意两条都可见， 则称它们为a triangle of segments， 求a triangle of segments的个数
思路： 一开始真没想到n^3的复杂度可以过。。。 如果这样的话， 问题的关键就是怎样判断任意两个线段是否可见。
那么如果对y坐标建立区间， 这就成了线段树的区间覆盖问题。
另外， 由于是用点代替线段， 所以对于”可见“这个问题， 就会出现问题， 比如 有三条线段[1,4]、[1,2]、[3,4]， 则在[1,4]区间中可以看见3条线段， 即可以通过[2,3]的空隙看见第一条线段。 解决方法很简单， 把坐标扩大2倍就行了，这样[1,2]变成[2,4]，[3,4]变成[6,8]，空出了一个5。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 8000 + 10;
int T,n,t,q,l,r,c,col[maxn<<3],y[maxn<<1];
bool vis[maxn][maxn];
struct node {
int ly, ry, x;
node(int l=0, int r=0, int xx=0):ly(l),ry(r),x(xx) {}
bool operator < (const node& rhs) const {
return x < rhs.x || (x == rhs.x && ly < rhs.ly);
}
}a[maxn];
void pushdown(int o) {
if(col[o] >= 0) {
col[o<<1] = col[o<<1|1] = col[o];
col[o] = -1;
}
}
void update(int L, int R, int c, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
col[o] = c;
return ;
}
pushdown(o);
if(L <= m) update(L, R, c, l, m, o<<1);
if(m < R) update(L, R, c, m+1, r, o<<1|1);
}
void query(int L, int R, int id, int l, int r, int o) {
int m = (l + r) >> 1;
if(col[o] >= 0) {
vis[id][col[o]] = true; return ;
}
if(l == r) return ;
if(L <= m) query(L, R, id, l, m, o<<1);
if(m < R) query(L, R, id, m+1, r, o<<1|1);
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int m = 0;
for(int i=0;i<n;i++) {
scanf("%d%d%d",&a[i].ly, &a[i].ry, &a[i].x);
m = max(m, max(a[i].ly, a[i].ry));
}
sort(a, a+n);
memset(col, -1, sizeof(col));
memset(vis, false, sizeof(vis));
for(int i=0;i<n;i++) {
int l = a[i].ly;
int r = a[i].ry;
query(2*l, 2*r, i, 0, 2*m, 1);
update(2*l, 2*r, i, 0, 2*m, 1);
}
int ans = 0;
for(int i=n-1;i>=0;i--) {
for(int j=i-1;j>=0;j--) {
if(vis[i][j]) {
for(int k=j-1;k>=0;k--) {
if(vis[i][k] && vis[j][k]) ++ans;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
~~~