class=”markdown_views prism-atom-one-light”>
Title
【Title Description】
Suppose T a m p e r e Tampere Tamper e The fourth-generation mobile phone base station in the area operates as follows. The area is divided into some squares (phalanx). These squares form a S S S╳ S S S matrix, matrix row and columns are numbered from 0 0 0 to S − 1 S-1 S−1. Each square contains a base station. Since a cell phone may move from one square to another, or the cell phone may be switched on or off, the number of cell phones in use within a square may vary from time to time. Sometimes, each base station needs to report changes in the number of handsets in use to the main base station using the rows and columns of the matrix.
Write a program that receives these reports and answers queries about the total number of cell phones currently in use within any rectangular area.
【Input】
Input is to read an integer from standard input, and the answer to a query is to write an integer to standard output. The input format is as follows. Each input occupies one line, and each line consists of a flag number and some parameters. The format of the flag number and these parameters is shown in the table below.
| Number of flags | parameter | meaning |
|---|---|---|
| 0 | S | Initialize the matrix with all zeros, of size S´S. This marker is given only once and will be the first marker. |
| 1 | X Y A | Add the value of A to the number of mobile phones currently in use in the square matrix (X, Y) of the matrix table. A can be positive or negative. |
| 2 | L B R T | Query the sum of the number of mobile phones currently in use in the square matrix (X,Y), where L ≤ X ≤ R ， B ≤ Y ≤ T L \leq X \leq R， B \leq Y \leq T L≤X≤R,B ≤Y≤ T |
| 3 | End program | This marker number is given only once and will be the last marker number. |
All values will always be within range, so no checking is required. In particular, when A A A When negative, it can be assumed that it will not reduce the number inside the square to 0 0 0 below. Ranges are numbered from 0 0 0Get started. For example, for a 4 4 4* 4 4 4 table, X X X and Y Y Y ranges from 0 ≤ X ≤ 3 , 0 ≤ Y ≤ 3 0\leq X\leq 3, 0\leq Y\leq 3 0≤X≤3,0 ≤Y≤ 3.
For a sign number not (not) 2 2 2 your program should not answer anything. If number of signs is 2 2 2, your program should answer the query by writing the answer to standard output as an integer.
【Output】
For each sign the number is 2 2 2, output the result.
【Sample input】
0 4
1 1 2 3
2 0 0 2 2
3
【Sample output】
3
【Data Range】
| Matrix table size | S S S S S S | 1 1 ≤ S S ≤ 1024 1024 11 \leq SS \leq 10241024 11≤SS≤10241024 |
|---|---|---|
| Cell value at any time | V V V | 0 ≤ V ≤ 2 15 – 1 0 \leq V \leq 2^{15 } –1 0≤V≤215– 1 ( = 32767 =32767 =3 +=lowbit(j); } i+=lowbit(i); } if(m==1) { scanf(“%d%d%lld”,&x,&y,&k) ; update(x+1,y+1 ,k); } if(m==2) { scanf(“%d%d%d%d”,&x,&y,&x1,&x1,&y1); x++;y++;x1++;y1 ++; ans=sum(x1,y1)–sum(x–1,y1)–sum(x1,y–1)+sum(x–1,y–1); //two-dimensional prefix and printf(“%lld\n”,ans); } if(m==3) break; } return 0; }
This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/problem-solution-ioi-2001-mobile-phones-two-dimensional-tree-array_ioi2001__boss_s-blog/
给这篇文章的作者打赏
微信扫一扫打赏
支付宝扫一扫打赏
Contact Us
Contact us181-3619-1160Online consultation: E-mail: [email protected] Working hours: Monday to Friday, 9:00-17:30, holidays off
Follow wechat
Scan wechat and follow us |
