首页 > 代码库 > Vijos1512 SuperBrother打鼹鼠
Vijos1512 SuperBrother打鼹鼠
SuperBrother打鼹鼠
Vijos链接
题目描述：
在一个矩阵中，有三种操作：
1.后面跟着3个数x,y,k，表示在点(x,y)处新出现了k只鼹鼠。
2.后面跟着4个数x1,y1,x2,y2，表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量。
3.表示结束。
思路：
一个树状数组就可以搞定了，不过需要二维的树状数组，才能实现二维的区间查询。
代码：
1 #include<cstdio> 2 long long n,m,dis[10010][10010],tot,a,b,c,d; 3 using namespace std; 4 void add(long long x,long long y,long long z){ 5 for(long long i=x;i<=n;i+=i&(-i)) 6 for(long long j=y;j<=n;j+=j&(-j)) 7 dis[i][j]+=z; 8 } 9 long long q(long long x,long long y){ 10 tot=0; 11 for(long long i=x;i;i-=i&(-i)) 12 for(long long j=y;j;j-=j&(-j)) 13 tot+=dis[i][j]; 14 return tot; 15 } 16 int main(){ 17 scanf("%lld",&n); 18 while(1){ 19 scanf("%lld",&m); 20 if(m==1){ 21 scanf("%lld%lld%lld",&a,&b,&c); 22 a++;b++; 23 add(a,b,c); 24 } 25 else 26 if(m==2){ 27 scanf("%lld%lld%lld%lld",&a,&b,&c,&d); 28 a++;b++;c++;d++; 29 printf("%lld\n",q(c,d)-q(a-1,d)-q(c,b-1)+q(a-1,b-1)); 30 } 31 else 32 break; 33 } 34 return 0; 35 }
Vijos1512 SuperBrother打鼹鼠
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。