题意:
给出一系列竖直的线段, 给出上下两端点坐标和横坐标, 定义"水平可见"为两线段之间可以连一条水平线段, 使得该线段不与其他线段接触.
又定义"三条线段可组成三角形"为三条线段两两"水平可见".
问一组线段中一共可以组成多少三角形.
思路:
首先这个"可见"可以想到涂色覆盖问题, 纵向建立线段树. 可知横坐标只起到排序的作用, 并无影响.
因为是一层层添加, 所以就像求逆序数一样, 插入一条之前先询问, 再插入.
难点在于query.(之前理解不深之故...用着生疏)
离散化记得线段树是一个数代表一条线段, 因此要想表达分立的点, 需要扩大二倍留出点之间的空隙 !
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//1024K 157MS
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int MAXN = 8888;
struct v_seg
{
int s, t, x;
bool operator<(const v_seg& b) const
{
return x < b.x;
}
}ss[MAXN];
int col[MAXN<<2], hash[MAXN];
vector<int> v[MAXN];
void PushDown(int rt)
{
if(col[rt]!=-1)
{
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
}
void update(int L, int R, int id, int l, int r, int rt)
{
if(L<=l && r<=R)
{
col[rt] = id;
return;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L<=m) update(L, R, id, lson);
if(m<R) update(L, R, id, rson);
}
void query(int L, int R, int id, int l, int r, int rt)
{
if(col[rt]!=-1)
{
if(hash[col[rt]]!=id)
{//query其实就是一个找纯色的过程, 找到了纯色, 其下的一段便确定;
//没找到纯色, 就继续往下分.
v[col[rt]].push_back(id);//统计该条线段都能够被那些线段看到
hash[col[rt]] = id;//索引是否不是第一次被同一条线段看到
}
return;
}
if(l==r) return;//等于-1但又长度为1, 说明这里没有线段
PushDown(rt);
int m = (l + r) >> 1;
if(L<=m) query(L, R, id, lson);
if(m<R) query(L, R, id, rson);
}
int main()
{
int i, j, k, t, n, T;
scanf("%d",&T);
while(T--)
{
memset(col, -1, sizeof(col));
memset(hash, -1, sizeof(hash));
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d%d",&ss[i].s,&ss[i].t,&ss[i].x);
ss[i].s<<=1; ss[i].t<<=1; v[i].clear();
}
sort(ss,ss+n);
for(i=0;i<n;i++)
{
query(ss[i].s,ss[i].t,i,0,16000,1);
update(ss[i].s,ss[i].t,i,0,16000,1);
}
int ans = 0;
for(i=0;i<n;i++)
for(j=0;j<v[i].size();j++)
{
k = v[i][j];
for(t=0;t<v[i].size();t++)
for(int w=0;w<v[k].size();w++)
if(v[k][w] == v[i][t]) ans++;
}
printf("%d\n",ans);
}
}
存储边用前向星好些~
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//648K 110MS
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int MAXN = 8888;
//但是不知道为什么这里写8005就不对...大概是需要的冗余比较多...
struct v_seg
{
int s, t, x;
bool operator<(const v_seg& b) const
{
return x < b.x;
}
}ss[MAXN];
int col[MAXN<<2],hash[MAXN];
struct pool
{
int to,pre;
}p[MAXN<<2];//适当开
int head[MAXN],num;
void add(int u, int v)
{
p[++num].to = v;
p[num].pre = head[u];
head[u] = num;
}
void PushDown(int rt)
{
if(col[rt]!=-1)
{
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
}
void update(int L, int R, int id, int l, int r, int rt)
{
if(L<=l && r<=R)
{
col[rt] = id;
return;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L<=m) update(L, R, id, lson);
if(m<R) update(L, R, id, rson);
}
void query(int L, int R, int id, int l, int r, int rt)
{
if(col[rt]!=-1)
{
if(hash[col[rt]]!=id)
{
add(col[rt],id);
hash[col[rt]] = id;
}
return;
}
if(l==r) return;//等于-1但又长度为1, 说明这里没有线段
PushDown(rt);
int m = (l + r) >> 1;
if(L<=m) query(L, R, id, lson);
if(m<R) query(L, R, id, rson);
}
int main()
{
int i, n, T;
scanf("%d",&T);
while(T--)
{
memset(col, -1, sizeof(col));
memset(head, 0, sizeof(head));
memset(hash,-1,sizeof(hash));
num = 0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d%d",&ss[i].s,&ss[i].t,&ss[i].x);
ss[i].s<<=1; ss[i].t<<=1;
}
sort(ss,ss+n);
for(i=0;i<n;i++)
{
query(ss[i].s,ss[i].t,i,0,16000,1);
update(ss[i].s,ss[i].t,i,0,16000,1);
}
int ans = 0;
for(int n1=0;n1<n;n1++)
for(int i2=head[n1],n2;n2=p[i2].to,i2;i2=p[i2].pre)
for(int i3=head[n1],n3;n3=p[i3].to,i3;i3=p[i3].pre)
for(int i4=head[n2],n4;n4=p[i4].to,i4;i4=p[i4].pre)
if(n3==n4) ans++;
printf("%d\n",ans);
}
}