poj 1436(线段树区间覆盖

题意：
给出 n 条垂线，问有多少个三元组 中，任意两条可以看得到对方

思路：
线段间能不能看得见，又是一道线段树区间覆盖，但是稍微改一下我就懵逼了，x从左到右排序，以y轴为区间建线段树，每加入一条就看先前有多少条是可以看得见的，打个vis标记，再update,其实这里我想到了，但是n^3枚举我觉得绝壁T，但是居然真的可以，这垃圾数据，和poj2528一样的是，这里覆盖的是线段而不是端点，长度为1的线段如果两边都被覆盖，就错判了，所以区间要乘2，注意，区间覆盖问题要看清楚覆盖的是点还是线段，相应处理，这题我还学到了一个新的n ^3枚举的方法，就是先枚举起点终点，再枚举中间的点，似乎比我直接顺序枚举快了600ms，如果有大佬知道为啥请在博客下告诉我一下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn=8005;
struct Node{
int y1,y2,x;
bool operator<(const Node&a)const
{
return x<a.x;
}
}node[maxn];
bool vis[maxn][maxn];
int lazy[maxn<<3],t,n;
void pushDown(int p)
{
if(lazy[p])
{
lazy[ls]=lazy[rs]=lazy[p];
lazy[p]=0;
}
}
void query(int p,int l,int r,int L,int R,int x)
{
if(lazy[p])
{
vis[lazy[p]][x]=vis[x][lazy[p]]=1;
return;
}
if(l==r)return;
pushDown(p);
int mid=l+r>>1;
if(L<=mid)query(lson,L,R,x);
if(R>mid)query(rson,L,R,x);
}
void update(int p,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R){
lazy[p]=x;
return;
}
pushDown(p);
int mid=l+r>>1;
if(L<=mid)update(lson,L,R,x);
if(R>mid)update(rson,L,R,x);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
vis[i][j]=0;
int mx=-1;
for(int i=1;i<=n;++i)
scanf("%d%d%d",&node[i].y1,&node[i].y2,&node[i].x),mx=max(mx,node[i].y2);
mx<<=1;
for(int i=0;i<=4*mx;++i)
lazy[i]=0;
sort(node+1,node+1+n);
for(int i=1;i<=n;++i)
{
query(1,0,mx,2*node[i].y1,2*node[i].y2,i);
update(1,0,mx,2*node[i].y1,2*node[i].y2,i);
}
ll ans=0;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{
if(!vis[i][j])continue;
for(int k=i+1;k<j;++k)
if(vis[i][k]&&vis[j][k])
ans++;
}
printf("%lldn",ans);
}
return 0;
}

最后

以上就是笑点低芹菜最近收集整理的关于poj 1436(线段树区间覆盖的全部内容，更多相关poj内容请搜索靠谱客的其他文章。