首页 > 代码库 > vijos p1512——SuperBrother打鼹鼠(树状数组)(复习)

vijos p1512——SuperBrother打鼹鼠(树状数组)(复习)

背景

SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊......),于是便无聊地开始玩“打鼹鼠”......

描述

在这个“打鼹鼠”的游戏中,鼹鼠会不时地从洞中钻出来,不过不会从洞口钻进去(鼹鼠真胆大……)。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中,左下角为(0,0),右上角为(n-1,n-1)。洞口所在的位置都是整点,就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。

格式

输入格式

每个输入文件有多行。

第一行,一个数n,表示鼹鼠的范围。

以后每一行开头都有一个数m,表示不同的操作: m=1,那么后面跟着3个数x,y,k(0<=x,y<n),表示在点(x,y)处新出现了k只鼹鼠; m=2,那么后面跟着4个数x1,y1,x2,y2(0<=x1<=x2<n,0<=y1<=y2<n),表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量; m=3,表示老师来了,不能玩了。保证这个数会在输入的最后一行。

询问数不会超过10000,鼹鼠数不会超过maxlongint。

输出格式

对于每个m=2,输出一行数,这行数只有一个数,即所询问的区域内鼹鼠的个数。

样例1

样例输入1

41 2 2 52 0 0 2 33

样例输出1

5

限制

各个测试点1s

一道二维的树状数组题,二维数组存起点到i,j的鼹鼠的和。这里的起点由于可以是0,0所以在输入后横纵坐标都加上1.在查询的时候,也是2层for循环将整个范围找完。

由于此题没有关于树状数组求最大值,所以明天再总结下树状数组求最大值的方法。

祝自己NOIP顺利~

 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1030; 4 int a[maxn][maxn]; 5 int n,m; 6 int lowbit(int x) 7 { 8     return x&(-x); 9 }10 void add(int x,int y,int w)11 {12     for(int i=x;i<=n;i+=lowbit(i))13     for(int j=y;j<=n;j+=lowbit(j))14     a[i][j]+=w;15     return ;16 }17 int sum(int x,int y)18 {19     int ans=0;20     for(int i=x;i>=1;i-=lowbit(i))21     for(int j=y;j>=1;j-=lowbit(j))22     ans+=a[i][j];23     return ans;24 }25 int main()26 {27     scanf("%d",&n);28     while(1)29     {30         int k;31         scanf("%d",&k);32         if(k==3)break;33         if(k==2)34         {35             int x1,x2,x3,x4;36             scanf("%d%d%d%d",&x1,&x2,&x3,&x4);37             x1++;x2++;x3++;x4++;//除去坐标轴上的点38             printf("%d\n",sum(x3,x4)-sum(x1-1,x4)-sum(x3,x2-1)+sum(x1-1,x2-1));//容斥39             continue; 40         }41         if(k==1)42         {43             int x1,x2,w;44             scanf("%d%d%d",&x1,&x2,&w);45             x1++;x2++;46             add(x1,x2,w);47         }48         49     }50     return 0;51 } 

 

 

 

vijos p1512——SuperBrother打鼹鼠(树状数组)(复习)