Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这是四分树,查矩形的复杂度感人

Posted by liuyuhong at 2015-12-03 12:35:49 on Problem 1656
In Reply To:二维线段树 Posted by:wwwaaannngggrs at 2011-04-08 09:40:03
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> int num[2000001], cover[2000001];
> void push(int idx, int lx, int rx, int ly, int ry)
> {
> 	if (cover[idx] == -1) return;
> 	cover[idx * 4 + 1] = cover[idx * 4 + 2] = cover[idx * 4 + 3] = cover[idx * 4 + 4] = cover[idx];
> 	int mx = (lx + rx) >> 1, my = (ly + ry) >> 1;
> 	num[idx * 4 + 1] = cover[idx] * (mx - lx + 1) * (my - ly + 1);
> 	num[idx * 4 + 2] = cover[idx] * (mx - lx + 1) * (ry - my);
> 	num[idx * 4 + 3] = cover[idx] * (rx - mx) * (my - ly + 1);
> 	num[idx * 4 + 4] = cover[idx] * (rx - mx) * (ry - my);
> 	cover[idx] = -1;
> }
> void update(int idx)
> {
> 	num[idx] = num[idx * 4 + 1] + num[idx * 4 + 2] + num[idx * 4 + 3] + num[idx * 4 + 4];
> }
> void insert(int idx, int lx, int rx, int ly, int ry, int Lx, int Rx, int Ly, int Ry, int w)
> {
> 	if (Lx <= lx && Rx >= rx && Ly <= ly && Ry >= ry){
> 		cover[idx] = w;
> 		num[idx] = (rx - lx + 1) * (ry - ly + 1) * w;
> 		return;
> 		}
> 	push(idx, lx, rx, ly, ry);
> 	int mx = (lx + rx) >> 1, my = (ly + ry) >> 1;
> 	if (Lx <= mx && Ly <= my) insert(idx * 4 + 1, lx, mx, ly, my, Lx, Rx, Ly, Ry, w);
> 	if (Lx <= mx && Ry > my) insert(idx * 4 + 2, lx, mx, my + 1, ry, Lx, Rx, Ly, Ry, w);
> 	if (Rx > mx && Ly <= my) insert(idx * 4 + 3, mx + 1, rx, ly, my, Lx, Rx, Ly, Ry, w);
> 	if (Rx > mx && Ry > my) insert(idx * 4 + 4, mx + 1, rx, my + 1, ry, Lx, Rx, Ly, Ry, w);
> 	update(idx);
> }
> int query(int idx, int lx, int rx, int ly, int ry, int Lx, int Rx, int Ly, int Ry)
> {
> 	if (Lx <= lx && Rx >= rx && Ly <= ly && Ry >= ry) return num[idx];
> 	push(idx, lx, rx, ly, ry);
> 	int mx = (lx + rx) >> 1, my = (ly + ry) >> 1, t = 0;
> 	if (Lx <= mx && Ly <= my) t += query(idx * 4 + 1, lx, mx, ly, my, Lx, Rx, Ly, Ry);
> 	if (Lx <= mx && Ry > my) t += query(idx * 4 + 2, lx, mx, my + 1, ry, Lx, Rx, Ly, Ry);
> 	if (Rx > mx && Ly <= my) t += query(idx * 4 + 3, mx + 1, rx, ly, my, Lx, Rx, Ly, Ry);
> 	if (Rx > mx && Ry > my) t += query(idx * 4 + 4, mx + 1, rx, my + 1, ry, Lx, Rx, Ly, Ry);
> 	return t;
> }
>  
> int main()
> {
> 	int Q, x, y, L;
> 	char op[100];
> 	memset(cover, 0xff, sizeof(cover));
> 	scanf("%d", &Q);
> 	while(Q--){
> 		scanf("%s%d%d%d", &op, &x, &y, &L);
> 		switch(op[0]){
> 			case 'B':insert(0, 1, 101, 1, 101, x, x + L - 1, y, y + L - 1, 1); break;
> 			case 'W':insert(0, 1, 101, 1, 101, x, x + L - 1, y, y + L - 1, 0); break;
> 			case 'T':printf("%d\n", query(0, 1, 101, 1, 101, x ,x + L - 1, y, y + L - 1)); break;
> 			}
> 		}
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator