poj 3695 Rectangles 线段树扫描线 or 容斥原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
struct REC{
int x1,y1,x2,y2;
}rec[22];
struct seg{
int x1,x2,y,h,flag,id;
seg(){}
seg(int x1,int x2,int h,int flag,int id) : x1(x1), x2(x2), h(h), flag(flag), id(id) {}
bool operator < (const seg &a) const {
return h<a.h;
}
}ss[55];
struct PP{
int x,id;
bool operator < (const PP &a) const
{
return x<a.x;
}
}ax[55];
int sum[11111],cnt[11111],xx[111],vis[22];
void push_up(int rt,int l,int r)
{
if(cnt[rt])
sum[rt] = xx[r+1]-xx[l];
else if(l==r)
sum[rt] = 0;
else
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void update(int rt,int l,int r,int L,int R,int flag)
{
if( L<=l && R>=r)
{
cnt[rt]+=flag;
push_up(rt,l,r);
return ;
}
int mid = (l+r)>>1;
if(L<=mid)
update(lson,L,R,flag);
if(R>mid)
update(rson,L,R,flag);
push_up(rt,l,r);
}
int bin(int x,int l,int r)
{
while(l<=r)
{
int mid = (l+r)>>1;
if(xx[mid] == x)
return mid;
if(xx[mid] > x)
r = mid-1;
else
l = mid+1;
}
}
void init()
{
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
}
int main()
{
int n,m,i,x,r,j;
int cas = 1;
while(scanf("%d%d", &n, &m)!=-1 && n)
{
printf("Case %d:n", cas++);
int d = 0;
for(i = 1;i <= n ; i++)
{
scanf("%d%d%d%d", &rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
ax[d].x = rec[i].x1;
ax[d].id = i;
ss[d++] = seg(rec[i].x1,rec[i].x2,rec[i].y1,1,i);
ax[d].x = rec[i].x2;
ax[d].id = i;
ss[d++] = seg(rec[i].x1,rec[i].x2,rec[i].y2,-1,i);
}
sort(ss,ss+d);
sort(ax,ax+d);
int dd = 1;
for(i = 1;i < d; i++)
if(ax[i].x!=ax[i-1].x)
ax[dd++] = ax[i];
for(i = 1;i <= m ;i++)
{
for(j = 1;j <= n; j++)
vis[j] = 0;
scanf("%d", &r);
int mm = 0;
while(r--)
{
scanf("%d", &x);
vis[x]++;
}
int k = 0;
for(j = 0;j < dd; j++)
{
if(!vis[ax[j].id])
continue;
xx[k++] = ax[j].x;
}
int ans = 0;
int pre = 0;
int preh = -1;
for(j = 0;j < d; j++)
{
if(!vis[ss[j].id])
continue;
int l = bin(ss[j].x1,0,k-1);
int r = bin(ss[j].x2,0,k-1)-1;
update(1,0,k-1,l,r,ss[j].flag);
//	printf("sum[1] = %dn",sum[1]);
if(preh>=0)
ans += pre*(ss[j].h-preh);
preh = ss[j].h;
pre = sum[1];
}
printf("Query %d: %dn",i,ans);
}
puts("");
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
using namespace std;
struct REC{
int x1,x2,y1,y2;
}rec[22],cur[22],d[22];
int change[22] , top;
void find(int now,int num,int tot)
{
int i;
if(num == tot)
{
if(tot==1)
{
change[tot] += (d[0].x2-d[0].x1)*(d[0].y2-d[0].y1);
find(now,num,tot+1);
return ;
}
int mx1 = max(d[tot-1].x1,d[tot-2].x1);
int mx2 = min(d[tot-1].x2,d[tot-2].x2);
int my1 = max(d[tot-1].y1,d[tot-2].y1);
int my2 = min(d[tot-1].y2,d[tot-2].y2);
if(mx1 < mx2 && my1 < my2)
{
d[tot-1].x1 = mx1;
d[tot-1].x2 = mx2;
d[tot-1].y1 = my1;
d[tot-1].y2 = my2;
change[tot] += (mx2-mx1)*(my2-my1);
//	printf("tot = %dn", tot);
//	printf("%d %d %d %dn",mx1,my1,mx2,my2);
find(now,num,tot+1);
}
}
else
for(i = now;i < top; i++)
{
d[num] = cur[i];
find(i+1,num+1,tot);
}
}
int main()
{
int n,m,i,j,r,x;
int cas = 1;
while(scanf("%d%d", &n , &m )!=-1 && n)
{
printf("Case %d:n", cas++);
for(i = 1;i <= n; i ++)
scanf("%d%d%d%d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
for(i = 1;i <= m; i++)
{
scanf("%d", &r);
for(j = 0;j < r; j++)
{
scanf("%d", &x);
cur[j] = rec[x];
}
top = r;
for(j = 1;j <= r; j++)
change[j] = 0;
find(0,0,1);
int ans = 0;
for(j = 1;j <= r; j++)
{
//	printf("change[%d] = %dn",j , change[j]);
if(j&1)
ans += change[j];
else
ans -= change[j];
}
printf("Query %d: %dn",i, ans);
}
puts("");
}
return 0;
}