bzoj3718 [PA2014]Parking

Description

你的老板命令你将停车场里的车移动成他想要的样子。
停车场是一个长条矩形，宽度为w。我们以其左下角顶点为原点，坐标轴平行于矩形的边，建立直角坐标系。停车场很长，我们可以认为它一直向右边伸展到无穷远处。
车都是边平行于坐标轴的矩形，大小可能不同。你可以将车任意地平移（但不能旋转），只要他们不超出停车场的边界，且不能互相碰撞，但紧挨着是允许的（即任意时刻任两辆车的重叠面积为0）。
你知道目前各辆车的摆放位置，以及老板心中所想的位置。你需要判断是否可以办到老板的任务。

Input

第一行为一个整数t(1<=t<=20)，表示测试数据数量。
对于每组测试数据，第一行两个整数n,w(1<=n<=50000,1<=w<=10^9)，分别表示车的数量和停车场的宽度。
接下来n行，第i行有四个整数x1,y1,x2,y2(0<=x1,x2<=10^9,0<=y1,y2<=w)，表示编号为i的车的当前位置是由x1,y1,x2,y2确定的矩形。（注意：数据有可能出现x1>x2或y1>y2）
再接下来n行，格式和意义同上，表示车的目标位置。

Output

输出t行，第i行为TAK（是）或NIE（否），表示第i组测试数据中能否按照要求进行移动。

Sample Input

2
3 3
0 0 2 2
2 1 4 3
4 0 6 1
0 0 2 2
2 1 4 3
0 2 2 3
3 3
0 0 2 2
2 1 4 3
4 0 6 1
2 1 4 3
0 0 2 2
4 0 6 1

Sample Output

TAK
NIE

正解：树状数组。

首先我们可以知道一个结论，就是两个木块如果宽度之和$>w$且前后相对位置不同那么就不合法。

我们把每个车的横坐标$x0$记为$x1+x2$的和，$x1$为移动后的和，然后我们可以发现只要$ax0<bx0$，且$ax1>bx1$，且$ay+by>w$就不合法。

然后我们可以把所有车按照$x0$从大到小排序，并用树状数组记录$bx1$对应位置的$y$的前缀最大值，然后我们只要查询一下前缀最大值，并判断与$y$相加是否大于$w$就行了。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 #define lb(x) (x & -x)
 6 #define N (100010)
 7 
 8 using namespace std;
 9 
10 struct data{ int x1,x2,y; }q[N];
11 
12 int c[N],hsh[N],n,w,tot;
13 
14 il int gi(){
15   RG int x=0,q=1; RG char ch=getchar();
16   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
17   if (ch=='-') q=-1,ch=getchar();
18   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
19   return q*x;
20 }
21 
22 il int cmp(const data &a,const data &b){ return a.x1>b.x1; }
23 
24 il void add(RG int x,RG int v){
25   for (;x<=tot;x+=lb(x)) c[x]=max(c[x],v); return;
26 }
27 
28 il int query(RG int x){
29   RG int res=0;
30   for (;x;x^=lb(x)) res=max(res,c[x]); return res;
31 }
32 
33 il void work(){
34   n=gi(),w=gi(),tot=0;
35   for (RG int i=1,X1,Y1,X2,Y2;i<=n;++i){
36     X1=gi(),Y1=gi(),X2=gi(),Y2=gi();
37     q[i].x1=X1+X2,q[i].y=abs(Y1-Y2);
38   }
39   for (RG int i=1,X1,Y1,X2,Y2;i<=n;++i){
40     X1=gi(),Y1=gi(),X2=gi(),Y2=gi();
41     q[i].x2=X1+X2,hsh[++tot]=q[i].x2;
42   }
43   sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;
44   for (RG int i=1;i<=n;++i)
45     q[i].x2=lower_bound(hsh+1,hsh+tot+1,q[i].x2)-hsh,c[i]=0;
46   sort(q+1,q+n+1,cmp);
47   for (RG int i=1,res;i<=n;++i){
48     res=query(q[i].x2-1);
49     if (q[i].y+res>w){ puts("NIE"); return;  }
50     add(q[i].x2,q[i].y);
51   }
52   puts("TAK"); return;
53 }
54 
55 int main(){
56 #ifndef ONLINE_JUDGE
57   freopen("Parking.in","r",stdin);
58   freopen("Parking.out","w",stdout);
59 #endif
60   RG int T=gi();
61   while (T--) work();
62   return 0;
63 }