Problem Lights (HDU 5820)
题目大意
在一个大小为50000*50000的矩形中，有n个路灯。（n<=500000）
询问是否每一对路灯之间存在一条道路，使得长度为|x1 – x2| + |y1 – y2|且每个拐弯点都是路灯。
解题分析
官方题解：
除了从左往右扫描一遍外，个人认为还需从右往左扫描一遍，记录右上方的点的信息。 实际实现时，只需将整个图左右对称翻转一下即可。
学习了一下可持久化线段树的正确姿势。
可持久化线段树的空间一定要开大，开大，开大。
下图为模拟的小数据可持久化线段树的构造。
参考程序
1 #include <map>
2 #include <set>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <ctime>
7 #include <string>
8 #include <vector>
9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17
18 #define N 1000008
19 #define M 50008
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m,r+1,rt<<1|1
23 #define clr(x,v) memset(x,v,sizeof(x));
24
25 const int mo = 1000000007;
26 const int inf = 0x3f3f3f3f;
27 const int INF = 2000000000;
28 /**************************************************************************/
29 struct node{
30 int x,y;
31 bool operator < (const node &b) const {
32 return x<b.x || x==b.x && y<b.y;
33 }
34 node(int x=0,int y=0):x(x),y(y){}
35 }a[N];
36 int n,flag;
37 map<pair<int,int>,int> Mpp;
38
39 int mx[M],my[M];
40
41 int cnt;
42 int sum[N<<3],ls[N<<3],rs[N<<3];
43 int root[M];
44
45 void dfs(int rt,int l,int r){
46 if (rt==0) return;
47 printf("%d %d %d %d\n",rt,l,r,sum[rt]);
48 if (l==r) return;
49 int m=(l+r)/2;
50 dfs(ls[rt],l,m);
51 dfs(rs[rt],m+1,r);
52 }
53 void debug(){
54 printf("====================\n");
55 dfs(root[0],1,3);
56 printf("\n");
57 dfs(root[1],1,3);
58 printf("\n");
59 dfs(root[2],1,3);
60 printf("\n");
61 dfs(root[3],1,3);
62 printf("====================\n");
63 }
64 void pushup(int rt){
65 int l=ls[rt],r=rs[rt];
66 sum[rt]=sum[l]+sum[r];
67 }
68 void build(int &rt,int l,int r){
69 rt=++cnt;
70 sum[rt]=0;
71 if (l==r) return;
72 int m=(l+r)/2;
73 build(ls[rt],l,m);
74 build(rs[rt],m+1,r);
75 pushup(rt);
76 }
77 void update(int pos,int val,int x,int &y,int l,int r){
78 y=++cnt;
79 if (l==r){
80 sum[y]=sum[x]+val;
81 return;
82 }
83 ls[y]=ls[x]; rs[y]=rs[x];
84 int m=(l+r)/2;
85 if (pos <= m) update(pos,val,ls[x],ls[y],l,m);
86 if (m < pos) update(pos,val,rs[x],rs[y],m+1,r);
87 pushup(y);
88 }
89
90 int query(int L,int R,int rt,int l,int r){
91 if (L<=l && r<=R){
92 return sum[rt];
93 }
94 int m=(l+r)/2;
95 int res=0;
96 if (L <= m) res+=query(L,R,ls[rt],l,m);
97 if (m < R) res+=query(L,R,rs[rt],m+1,r);
98 return res;
99 }
100
101 void work1(){
102 clr(mx,0); clr(my,0);
103 cnt=0;
104 build(root[0],1,50000);
105 int last=root[0];
106 for (int i=1;i<=n;i++){
107 int x1=a[i].x , y1=a[i].y;
108 int x2=a[my[y1]].x , y2=a[mx[x1]].y;
109 update(y1,1,last,root[x1],1,50000);
110 int k1=query(y2+1,y1,root[x1],1,50000);
111 int k2=query(y2+1,y1,root[x2],1,50000);
112 if (k1!=k2+1) { flag=0; return; }
113 mx[a[i].x]=i; my[a[i].y]=i; last=root[x1];
114 }
115 }
116
117 int main(){
118 int T;
119 while (~scanf("%d",&n)){
120 if (n==0) break;
121 Mpp.clear();
122 int num=0;
123 for (int i=1;i<=n;i++){
124 int x,y;
125 scanf("%d %d",&x,&y);
126 if (Mpp[make_pair(x,y)]==1){
127 num++;
128 }
129 else
130 {
131 Mpp[make_pair(x,y)]=1;
132 a[i-num].x=x;
133 a[i-num].y=y;
134 }
135 }
136 n=n-num;
137 sort(a+1,a+n+1);
138 flag=1;
139 work1();
140 for (int i=1;i<=n;i++) a[i].x=50001-a[i].x;
141 sort(a+1,a+n+1);
142 work1();
143 printf("%s\n",flag ? "YES" : "NO" );
144 }
145 }
146 /*
147 5
148 1 1
149 1 2
150 1 3
151 2 1
152 3 3
153 */