T4701 【卜卜】樹狀數組模板

題目背景

令 夜 色 的 鐘 聲 響 起

令 黃 昏 （起 始） 的 鐘 聲 響 起

我 愛 （渴 望） 的 就 只 有 你

我 愛 （ 渴 望 ） 你

正因如此 獨自安靜地哭泣吧

正因如此 無論你在何處哭泣 我都會率先去迎接你

不存在何處 直至深夜（小小的你）

你存在此處 至美者（心顯崇高之人）

在這個夜晚（場所） 你（我）是孤獨的（一個人）

許 下 約 定 送 上 我 的 歌

那陣旋律是 心靈的奏鳴（撼動） 淚珠的音色（舞動）

那陣旋律是 心靈的刻劃（震動） 淚珠的贊歌（慶典）

因為那是令世界濕濡 冰冷（心愛）之夜的一滴（歌曲）

那 是 令 世 界 濕 濡 親 愛 的 夜 之 擁 抱 （ 歌 曲 ）

讓夜色的吟唱（誓言）來到你身邊

讓夜色的祝福（誓言）來到你身邊 綿延（長久）地、永久（長久）地、直到永遠

被 遺 忘 的 孩 子 啊

就算全世界（每個人）都遺忘了你 我也絕對不會遺忘你

來吧 呱呱墜地的孩子啊

回到似睡非睡（搖籃）之中吧

似睡非睡（搖籃）的時間 因為約定的鐘聲而宣告終止

接著 我會──

接 著 你 會

黃昏的創始之女（夏娃） 你 在 黎 明 時 微 笑

題目描述

在二維平面內給定n個點:

0 x y v表示給(x,y)的權值減去v

1 x y v表示給(x,y)的權值加上v

然後有m個操作

0 x y v , 1 x y v 意義如上

2 a b c d表示詢問左上角為(a,b) , 右下角為(c,d)的矩陣權值和

輸入輸出格式

輸入格式：

第一行一個數n

後n行 每行三個數 type x y 意義見上

然後一個數m表示操作數

後m行 第一個數為type

若type=2 則接四個數 a,b,c,d 意義見上

否則接三個數 x,y,v 意義見上

輸出格式：

對每一個 2號操作輸出一個答案

輸入輸出樣例

8
0 8 10 1
0 8 6 9
0 10 2 48
0 4 8 21
1 6 6 75
0 4 4 23
1 2 9 12
0 4 10 2
9
2 7 2 10 8
1 4 2 92
2 2 4 6 4
0 6 10 29
0 10 8 42
2 4 4 6 6
2 6 6 10 10
2 1 6 8 8
2 8 1 8 2

-57
-23
52
-6
45
0

說明

n,m<=100000 ; x,y<=1000

還是由於出題人不會造數據 保證數據全是隨機

二維樹狀數組，，

比較有意思，

和一維的差不多，

就是多了層迴圈

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 //#define lowbit(x)  (x)&(-x)
 6 using namespace std;
 7 const int MAXN=1010;
 8 inline void read(int &n)
 9 {
10     char c='+';bool flag=0;n=0;
11     while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
12     while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
13 }
14 int tree[MAXN][MAXN];
15 int maxn=1000;
16 inline int lowbit(int x)    {return x&(-x);}
17 inline void add(int x,int y,int val)
18 {
19     for(int i=x;i<=maxn;i+=lowbit(i))
20         for(int j=y;j<=maxn;j+=lowbit(j))
21             tree[i][j]+=val;
22 }
23 inline int query(int x,int y)
24 {
25     int ans=0;
26     for(int i=x;i;i-=lowbit(i))
27         for(int j=y;j;j-=lowbit(j))
28             ans+=tree[i][j];
29     return ans;
30 }
31 int main()
32 {
33     int n;
34     for(int k=1;k<=2;k++)
35     {
36         read(n);
37         for(int i=1;i<=n;i++)
38         {
39             int how;
40             read(how);
41             if(how==0)// 減 
42             {
43                 int x,y,v;read(x);read(y);read(v);
44                 add(x,y,-v);
45             }
46             else if(how==1)//jia
47             {
48                 int x,y,v;read(x);read(y);read(v);
49                 add(x,y,v);
50             }
51             else//sum 
52             {
53                 int a,b,c,d;
54                 read(a);read(b);read(c);read(d);
55                 printf("%d\n",query(c,d)+query(a-1,b-1)-query(a-1,d)-query(c,b-1));
56             }
57         }    
58     }
59     return 0;
60 }