题目链接： 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 <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque>#define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using 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<b.x; }void init(int l,int r,int i) {a[i].l = l;a[i].r = r;a[i].n = -1;if(l==r)return;int mid = (l+r)>>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 <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque>#define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using 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 flaga[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的， 他们一定是做了很多题， 也知道了线段树只维护了连续的点组成的区间， 至于线段连续不连续并不关心， 所以这里成了一个二让这种情况变成点也不是连续的了， 好巧的啊......线段树还得搞啊......细心再细心点儿.,.....