T4701 【卜卜】树状数组模板

2018-06-17 22:02:48来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

令 夜 色 的 钟 声 响 起

令 黄 昏 (起 始) 的 钟 声 响 起

我 爱 (渴 望) 的 就 只 有 你

我 爱 ( 渴 望 ) 你

正因如此 独自安静地哭泣吧

正因如此 无论你在何处哭泣 我都会率先去迎接你

不存在何处 直至深夜(小小的你)

你存在此处 至美者(心显崇高之人)

在这个夜晚(场所) 你(我)是孤独的(一个人)

许 下 约 定 送 上 我 的 歌

那阵旋律是 心灵的奏鸣(撼动) 泪珠的音色(舞动)

那阵旋律是 心灵的刻划(震动) 泪珠的赞歌(庆典)

因为那是令世界湿濡 冰冷(心爱)之夜的一滴(歌曲)

那 是 令 世 界 湿 濡 亲 爱 的 夜 之 拥 抱 ( 歌 曲 )

让夜色的吟唱(誓言)来到你身边

让夜色的祝福(誓言)来到你身边 绵延(长久)地、永久(长久)地、直到永远

被 遗 忘 的 孩 子 啊

就算全世界(每个人)都遗忘了你 我也绝对不会遗忘你

来吧 呱呱坠地的孩子啊

回到似睡非睡(摇篮)之中吧

似睡非睡(摇篮)的时间 因为约定的钟声而宣告终止

接着 我会──

接 着 你 会

黄昏的创始之女(夏娃) 你 在 黎 明 时 微 笑

题目描述

在二维平面内给定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号操作输出一个答案

 

输入输出样例

输入样例#1:
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
输出样例#1:
-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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Luogu P2888 [USACO07NOV]牛栏Cow Hurdles

下一篇:P3387 【模板】缩点