[bzoj1935][shoi2007]Tree 園丁的煩惱(樹狀數組+離線) - Pumbit-Legion－IT工程師數位筆記本

文章出處

1935: [Shoi2007]Tree 園丁的煩惱

Time Limit: 15 Sec Memory Limit: 357 MB
Submit: 980 Solved: 450
[Submit][Status][Discuss]

Description

很久很久以前，在遙遠的大陸上有一個美麗的國家。統治著這個美麗國家的國王是一個園藝愛好者，在他的皇家花園里種植著各種奇花異草。有一天國王漫步在花園里，若有所思，他問一個園丁道： “最近我在思索一個問題，如果我們把花壇擺成六個六角形，那么……” “那么本質上它是一個深度優先搜索，陛下”，園丁深深地向國王鞠了一躬。 “嗯……我聽說有一種怪物叫九頭蛇，它非常貪吃蘋果樹……” “是的，顯然這是一道經典的動態規劃題，早在N元4002年我們就已經發現了其中的奧秘了，陛下”。 “該死的，你究竟是什么來頭？” “陛下息怒，干我們的這行經常莫名其妙地被問到和OI有關的題目，我也是為了預防萬一啊！” 王者的尊嚴受到了傷害，這是不可容忍的。看來一般的難題是難不倒這位園丁的，國王最后打算用車輪戰來消耗他的實力： “年輕人，在我的花園里的每一棵樹可以用一個整數坐標來表示，一會兒，我的騎士們會來輪番詢問你某一個矩陣內有多少樹，如果你不能立即答對，你就準備走人吧！”說完，國王氣呼呼地先走了。這下輪到園丁傻眼了，他沒有準備過這樣的問題。所幸的是，作為“全國園丁保護聯盟”的會長——你，可以成為他的最后一根救命稻草。

Input

第一行有兩個整數n，m（0≤n≤500000，1≤m≤500000）。n代表皇家花園的樹木的總數，m代表騎士們詢問的次數。文件接下來的n行，每行都有兩個整數xi，yi，代表第i棵樹的坐標（0≤xi，yi≤10000000）。文件的最后m行，每行都有四個整數aj，bj，cj，dj，表示第j次詢問，其中所問的矩形以（aj，bj）為左下坐標，以（cj，dj）為右上坐標。

Output

共輸出m行，每行一個整數，即回答國王以（aj，bj）和（cj，dj）為界的矩形里有多少棵樹。

Sample Input

3 1
0 0
0 1
1 0
0 0 1 1

Sample Output

HINT

Source

二維樹狀數組?快去試試！

好吧，數組已炸。但可以試試別的方法，比如只用一維樹狀數組

一維怎么做?忽略另一維就好了

當然，數據不會弱到這都能A的

但是我們看看什么情況這種做法就是對的

畫一個圖，觀察到例如忽略y軸時，對于詢問(1,1)(x,y)，如果在1到x間，只添加了從1到y間的點，那么這么做就是正確的

所以對于所有坐標和詢問都按一個坐標軸排序，按另一軸建樹狀數組(注意是混起來)

這樣就能保證處理詢問時，上面的情況時刻成立

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef struct{
 7     int x,y,id,f;
 8 }tr;
 9 int cmp(const tr a,const tr b){
10     if(a.x!=b.x)return a.x<b.x;
11     else if(a.y!=b.y)return a.y<b.y;
12     else return a.id<b.id;//??? 
13 }
14 tr qr[2500010];
15 int cnt=0;
16 int bit[10000010];
17 int ans[500010];
18 int mx=0,m,n;
19 int lb(int x){
20     return x&(-x);
21 }
22 int q(int x){
23     int ans=0;
24     while(x){
25         ans+=bit[x];
26         x-=lb(x);
27     }
28     return ans;
29 }
30 int c1(int x){
31     while(x<=mx+1){
32         bit[x]++;
33         x+=lb(x);
34     }
35     return 0;
36 }
37 int main(){
38     scanf("%d %d",&n,&m);
39     for(int i=1;i<=n;i++){
40         scanf("%d %d",&qr[i].x,&qr[i].y);
41         qr[i].x++;
42         qr[i].y++;
43         mx=max(qr[i].y,mx);
44     }
45     cnt=n;
46     for(int i=1;i<=m;i++){
47         int a,b,c,d;
48         scanf("%d %d %d %d",&a,&b,&c,&d);
49         c++;
50         d++;
51         qr[++cnt].x=a,qr[cnt].y=b,qr[cnt].f=1,qr[cnt].id=i;
52         qr[++cnt].x=a,qr[cnt].y=d,qr[cnt].f=-1,qr[cnt].id=i;
53         qr[++cnt].x=c,qr[cnt].y=b,qr[cnt].f=-1,qr[cnt].id=i;
54         qr[++cnt].x=c,qr[cnt].y=d,qr[cnt].f=1,qr[cnt].id=i;
55     }
56     sort(qr+1,qr+cnt+1,cmp);
57     for(int i=1;i<=cnt;i++){
58         
59         if(!qr[i].id)c1(qr[i].y);
60         else ans[qr[i].id]+=(qr[i].f)*(q(qr[i].y));
61     }
62     for(int i=1;i<=m;i++){
63         printf("%d\n",ans[i]);
64     }
65     return 0;
66 }