a513:
[模板] 二維前綴和
內容
每次下課排球場都好多人，場地很難搶，唐狗針與他的朋友只能在旁邊等，但唐狗針是社恐，而且唐狗針想跟他的朋友說他們的共同朋友--二薇的八卦:總而言之就是上次他們一起出門，但二薇居然不小心把他的錢包掉到河裡的，由於快輪到他們了，時間不夠，所以唐狗針只能先說二薇錢墜河，因為他們不想讓二薇知道他們在說她的八卦所以他們不想站在人太多的地方，唐狗針很笨的會用平均人數來估算擁擠度。
整個排球場可以切割成$N \times M$個格子，第$(i,j)$個格子有$a_{ij}$個人，唐狗針希望你告訴他$(x_1,y_1)$到$(x_2,y_2)$這個長方形區間的擁擠度，他也很煩的會問很多次，來確定是不是有二薇的眼線，不然不給你AC。
擁擠度：長方形區間的總人數 / 長方形區間的格子數
輸入說明
第一行有兩個數字$N,M(1 \leq N,M \leq 1500)$代表有$NM$個格子，接下來$N$行每行有$M$個數字$a_{ij}(1 \leq a_{ij} \leq 3000000)$代表第$i,j$個格子的人數，第$N+2$行有一個數字$Q(Q \leq 100000)$代表唐狗針會問幾次，接下來$Q$行有四個數字$x_1,y_1,x_2,y_2(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M)$代表詢問的長方形區間
輸出說明
對於每次唐狗針的發問，輸出該長方形區間的擁擠度，無條件捨去到整數位
範例輸入
#1
3 3 1 2 3 4 5 6 7 8 9 3 1 1 3 3 1 2 2 3 2 2 3 3
範例輸出
#1
5 4 7
範例輸入
#2
2 4 2 1 6 5 3 4 7 9 3 1 1 1 1 1 1 2 4 2 3 2 4
範例輸出
#2
2 4 8
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 5.0s , <50M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 5.0s , <50M
提示 ：
一個一個慢慢加會TLE哦
C++程式最前面要加上
ios_base::sync_with_stdio(0);
cin.time(0);
不然會TLE
標籤:
出處:
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||