HDU 4419 Colourful Rectangle(세그먼트 트리 + 스캔 라인)
22155 단어 HDU
주로pushup 코드이며, 기타와 구간 업데이트 + 스캐닝 라인의 차이가 많지 않습니다.
그 구간에 x를 한 층 더 칠하려면sum[x][rt]=que[r+1]-que[l];그러나 원래 색깔이 i라면 색깔은 i|x,sum[x][rt]가 되어 이전의 i색을 빼야 합니다.sum[i|x][rt]는 그 부분을 더해야 합니다.
이 문제는 용척도 사용할 수 있다. 용척은 여러 번 면적을 구하고 합치면 된다. 코드는 바로 모델이고 스캐닝 라인에 대해 아직 익숙하지 않다.
1 #include <cstdio>
2 #include <cstring>
3 #include <string>
4 #include <algorithm>
5 using namespace std;
6 #define LL __int64
7 #define maxn 20100
8 #define lson l , m, rt<<1
9 #define rson m+1, r,rt<<1|1
10 int que[4*maxn];
11 int sum[8][4*maxn];
12 int cnt[4*maxn][4];
13 LL ans[8];
14 struct node
15 {
16 int lx,rx,y;
17 int s;
18 node() {}
19 node (int a,int b,int c,int d):lx(a),rx(b),y(c),s(d) {}
20 bool operator < (const node &S)const
21 {
22 return y < S.y;
23 }
24 } mat[2*maxn];
25 int bin(int x,int n)
26 {
27 int str,end,mid;
28 str = 0;
29 end = n;
30 while(str <= end)
31 {
32 mid = (str + end)/2;
33 if(que[mid] == x)
34 return mid;
35 else if(que[mid] > x)
36 end = mid - 1;
37 else
38 str = mid + 1;
39 }
40 return mid;
41 }
42 void pushup(int rt,int l,int r)
43 {
44 int i,x,t;
45 x = 0;
46 for(i = 1;i <= 3;i ++)
47 {
48 if(cnt[rt][i] > 0)
49 x |= (1<<(i-1));
50 }
51 if(x)
52 {
53 for(i = 1;i < 8;i ++)
54 sum[i][rt] = 0;
55 sum[x][rt] = que[r+1] - que[l];
56 for(i = 1; i < 8; i ++)//
57 {
58 if(x != (i|x))
59 {
60 t = sum[i][rt<<1] + sum[i][rt<<1|1];
61 sum[x|i][rt] += t;
62 sum[x][rt] -= t;//
63 }
64 }
65 }
66 else if(l == r)
67 {
68 for(i = 1; i < 8; i ++)
69 sum[i][rt] = 0;
70 }
71 else
72 {
73 for(i = 1; i < 8; i ++)
74 sum[i][rt] = sum[i][rt<<1] + sum[i][rt<<1|1];
75 }
76 }
77 void update(int L,int R,int c,int l,int r,int rt)
78 {
79 int m;
80 if(l >= L&&r <= R)
81 {
82 c > 0 ? cnt[rt][c] ++:cnt[rt][-c] --;
83 pushup(rt,l,r);
84 return ;
85 }
86 m = (l+r)>>1;
87 if(L <= m)
88 update(L,R,c,lson);
89 if(R > m)
90 update(L,R,c,rson);
91 pushup(rt,l,r);
92 }
93 int main()
94 {
95 int n,cas = 1,i,j,l,r,t,num;
96 char ch[10];
97 int a,b,c,d,col;
98 scanf("%d",&t);
99 while(t --)
100 {
101 scanf("%d",&n);
102 num = 0;
103 for(i = 1; i <= n; i ++)
104 {
105 scanf("%s%d%d%d%d",ch,&a,&b,&c,&d);
106 if(ch[0] == 'R')
107 col = 1;
108 else if(ch[0] == 'G')
109 col = 2;
110 else
111 col = 3;
112 mat[num] = node(a,c,b,col);
113 que[num++] = a;
114 mat[num] = node(a,c,d,-col);
115 que[num++] = c;
116 }
117 sort(que,que+num);
118 sort(mat,mat+num);
119 int k = 1;
120 for(i = 1; i < num; i ++)
121 {
122 if(que[i] != que[i-1])
123 que[k++] = que[i];
124 }
125 memset(cnt,0,sizeof(cnt));
126 memset(sum,0,sizeof(sum));
127 memset(ans,0,sizeof(ans));
128 for(i = 0; i < num-1; i ++)
129 {
130 l = bin(mat[i].lx,k-1);
131 r = bin(mat[i].rx,k-1) - 1;
132 if(l <= r)
133 update(l,r,mat[i].s,0,k-1,1);
134 for(j = 1; j < 8; j ++)
135 ans[j] += ((LL)mat[i+1].y - (LL)mat[i].y)*(LL)sum[j][1];
136 }
137 printf("Case %d:
",cas++);
138 printf("%I64d
",ans[1]);
139 printf("%I64d
",ans[2]);
140 printf("%I64d
",ans[4]);
141 printf("%I64d
",ans[3]);
142 printf("%I64d
",ans[5]);
143 printf("%I64d
",ans[6]);
144 printf("%I64d
",ans[7]);
145 }
146 return 0;
147 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu4671(다교리그 7--수 시뮬레이션)클릭하여 링크 열기 제목: n과 서버, m개의 데이터베이스가 있고 모든 데이터베이스는 서버를 연결해야 하지만 모든 데이터베이스는 서버를 연결하는 우선순위가 있습니다.모든 데이터베이스의 서버 우선순위를 구하다.또한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.