本文共 4285 字，大约阅读时间需要 14 分钟。
题目链接： http://poj.org/problem?id=1436
题目描述： 在一个平面直角坐标系中有若干条竖线， 如果两条竖线能够用一条横线相连那么就说这两条竖线是可见的， 定义三条竖线成三角形如果两两可见， 问在n条竖线中有多少个三角形？ n <= 8000
解题思路： 首先我们要预处理出来map(i, j)表示编号i, j可见， 再O(n^3)暴力。 如果处理map呢， 我们先用一个x数组记录线段信息， 再用 a 数组记录线段i 可见的线段号， a数组也就是线段树。 先将a 数组初始化成表示所有区间的线段树， 就是节点1表示 1 ~ n， 节点2表示 1 ~ n/2, 节点3表示n/2+1 ~ n， 节点4······这样我后来插入的x数组一定会落在a的某个或某几个线段上，再加上一开始我们对x进行了排序， 所以我们保证了如果是此时a[rt].n != -1 那么此时插入的m号线段一定和n 互相可见， 如果说a[rt].n == -1 那就将m赋值给n。 这样就能够创建map·······话说我的懒惰标记理解的还不是很好， 这道题手写一下
代码： 这个是大神的代码， 我先背写， 再自己debug， 实在不行再看
#include #include #include #include #include #include #include #include #include #include #include #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1using namespace std;const int L = 8000+10;int color[L<<3];bool map1[L][L];//一开始我存的int型，但是int型会超内存，用bool型能节省大量空间int n;struct node{ int l,r,n;} a[L<<3];struct kode{ int x,y1,y2;} s[L];int cmp(kode a,kode b){ return a.x >1; init(l,mid,2*i); init(mid+1,r,2*i+1);}void insert(int l,int r,int i,int m){ if(l<=a[i].l && a[i].r<=r) { a[i].n = m; return ; } if(a[i].n!=-1)//将父亲节点的状态更新到孩子节点中 { a[2*i].n = a[2*i+1].n = a[i].n; a[i].n = -1; } if(l<=a[2*i].r) insert(l,r,2*i,m); if(r>=a[2*i+1].l) insert(l,r,2*i+1,m);}void query(int l,int r,int i,int m){ if(a[i].n!=-1) { map1[a[i].n][m] = true; return ; } if(a[i].l == a[i].r) return; if(a[i].n!=-1) { a[2*i].n = a[2*i+1].n = a[i].n; a[i].n = -1; } if(l<=a[2*i].r) query(l,r,2*i,m); if(r>=a[2*i+1].l) query(l,r,2*i+1,m); }int main(){ int t,ans,i,j,k; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i = 1; i<=n; i++) { scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x); s[i].y1*=2; s[i].y2*=2;; } sort(s+1,s+1+n,cmp); memset(map1,false,sizeof(map1)); init(0,16000,1); for(i = 1; i<=n; i++) { query(s[i].y1,s[i].y2,1,i); insert(s[i].y1,s[i].y2,1,i); } ans = 0; for(i = 1; i<=n; i++)//暴力求解 for(j = 1; j<=n; j++) if(map1[i][j]) { for(k = 1; k<=n; k++) if(map1[i][k] && map1[j][k]) ans++; } printf("%d\n",ans); } return 0;}
转自： http://blog.csdn.net/libin56842/article/details/14466011
这个是我的代码， 出现了一些bug， 自己以后要仔细分析
#include #include #include #include #include #include #include #include #include #include #include #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1using namespace std;const int L = 8000+100;struct node { int l, r, n; node() {} void init(int _l, int _r, int _n) {l = _l, r = _r, n = _n;} };struct kode { int y1, y2, x; kode() {} void init(int _1, int _2, int _x) {y1 = _1, y2 = _2, x = _x;}};node a[L<<3];kode x[L];bool map1[L][L];void build(int l, int r, int rt) { a[rt].init(l, r, -1); if( l == r ) return; int m = (l + r) >> 1; build(lson); build(rson);}void update(int l, int r, int i, int m) { if( l <= a[i].l && a[i].r <= r) { a[i].n = m; return; }// if( l == r ) return; if( a[i].n != -1 ) { // lazy flag a[i<<1].n = a[i<<1|1].n = a[i].n; a[i].n = -1; } if( l <= a[i<<1].r ) update(l, r, i<<1, m); if( r >= a[i<<1|1].l ) update(l, r, i<<1|1, m);}void query(int l, int r, int i, int m) { if( a[i].n != -1 ) { map1[a[i].n][m] = true; return; } if( a[i].l == a[i].r ) return; if( a[i].n != -1 ) { a[i<<1].n = a[i<<1|1].n = a[i].n; a[i].n = -1; } if( l <= a[i<<1].r ) query(l, r, i<<1, m); if( r >= a[i<<1|1].l ) query(l, r, i<<1|1, m);}int cmp(kode k1, kode k2) { return k1.x < k2.x;}int main() { int t; scanf( "%d", &t ); while( t-- ) { int n; scanf( "%d", &n ); build(0, 16000, 1); memset(map1, false, sizeof(map1)); for( int i = 1; i <= n; i++ ) { int y1, y2, t; scanf( "%d%d%d", &y1, &y2, &t ); x[i].init(y1<<1, y2<<1, t); } sort(x+1, x+n+1, cmp); // 对x数组排序， 保证第一个一定是可见的 for( int i = 1; i <= n; i++ ) { query(x[i].y1, x[i].y2, 1, i); update(x[i].y1, x[i].y2, 1, i); } int ans = 0; for( int i = 1; i <= n; i++ ) { for( int j = 1; j <= n; j++ ) { if( map1[i][j] ) { for( int k = 1; k <= n; k++ ) { if( map1[i][k] && map1[j][k] ) ans++; } } } } printf( "%d\n", ans ); } return 0;}
思考： 这道题其实有好多trick比如说乘二的问题， 好多博客都有提到， 要是我是绝对想不到这个trick的， 他们一定是做了很多题， 也知道了线段树只维护了连续的点组成的区间， 至于线段连续不连续并不关心， 所以这里成了一个二让这种情况变成点也不是连续的了， 好巧的啊......线段树还得搞啊......细心再细心点儿.,.....
转载于:https://www.cnblogs.com/FriskyPuppy/p/7337520.html
