线段树 poj 1436

时间:2022-11-13 22:51:27
题目大意:给出n条垂直于x轴的线段的数据y1,y2,x,求出有几个三条线段一组的三元组并且他们兩兩能相见的。
思路:对y轴建树,将x排序,然后按顺序边询问边擦入,用mark[i][j]表示j往左可以看到i。最后用一个三重循环计算答案。
但是注意:0,4,1 和 0,2,2 和 3,4,2这三条线段覆盖的结果是区间0~4通过线段树查找可见线段是两条,其实是3条(2~3可见另一条)
这里可以将y轴×2表示。这样就能解决这样的问题
0 1 2 3 4 2~3被覆盖 所以乘2解决
#include<stdio.h>
#include<string.h>
#include<algorithm> using namespace std; #define MAXN 16005
struct node
{
int l,r,w;
}x[MAXN<<];
struct abc
{
int y1,y2,x;
}z[MAXN];
bool m1[MAXN/][MAXN/];
bool cmp(abc a,abc b)
{
return a.x<b.x;
}
void push_down(int a)
{
x[a<<].w=x[a<<|].w=x[a].w;
x[a].w=-;
} void Build(int l,int r,int a)
{
x[a].l=l;
x[a].r=r;
x[a].w=-;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,a<<);
Build(mid+,r,a<<|);
}
void Insert(int l,int r,int i,int a)
{
if(z[i].y1<=l&&r<=z[i].y2)
{
x[a].w=i;
return ;
}
if(l==r)
return ;
if(x[a].w!=-)
push_down(a);
int mid=(l+r)>>;
if(z[i].y1<=mid)
Insert(l,mid,i,a<<);
if(z[i].y2>mid)
Insert(mid+,r,i,a<<|);
}
void Ques(int l,int r,int i,int a)
{
if(x[a].w!=-)
{
m1[x[a].w][i]=;
return ;
}
if(l==r)
return ;
if(x[a].w!=-)
push_down(a);
int mid=(l+r)>>;
if(z[i].y1<=mid)
Ques(l,mid,i,a<<);
if(z[i].y2>mid)
Ques(mid+,r,i,a<<|);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
memset(m1,,sizeof(m1)); for(int i=;i<=n;i++)
{
scanf("%d%d%d",&z[i].y1,&z[i].y2,&z[i].x);
z[i].y1<<=;
z[i].y2<<=;
}
Build(,MAXN,);
sort(z+,z+n+,cmp);
for(int i=;i<=n;i++)
{
Ques(,MAXN,i,);
Insert(,MAXN,i,);
}
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(m1[i][j])
for(int k=;k<=n;k++)
if(m1[i][k]&&m1[j][k])
ans++;
printf("%d\n",ans);
}
return ;
}