Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这是四分树,查矩形的复杂度感人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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator