SuperBrother打鼹鼠

Vijos链接

题目描述：

在一个矩阵中，有三种操作：

1.后面跟着3个数x,y,k，表示在点(x,y)处新出现了k只鼹鼠。

2.后面跟着4个数x1,y1,x2,y2，表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量。

3.表示结束。

思路：

一个树状数组就可以搞定了，不过需要二维的树状数组，才能实现二维的区间查询。

代码：

 #include<cstdio>

 long long n,m,dis[][],tot,a,b,c,d;

 using namespace std;

 void add(long long x,long long y,long long z){

     for(long long i=x;i<=n;i+=i&(-i))

         for(long long j=y;j<=n;j+=j&(-j))

             dis[i][j]+=z;

 }

 long long q(long long x,long long y){

     tot=;

     for(long long i=x;i;i-=i&(-i))

         for(long long j=y;j;j-=j&(-j))

             tot+=dis[i][j];

     return tot;

 }

 int main(){

     scanf("%lld",&n);

     while(){

         scanf("%lld",&m);

         if(m==){

             scanf("%lld%lld%lld",&a,&b,&c);

             a++;b++;

             add(a,b,c);

         }

         else

         if(m==){

             scanf("%lld%lld%lld%lld",&a,&b,&c,&d);

             a++;b++;c++;d++;

             printf("%lld\n",q(c,d)-q(a-,d)-q(c,b-)+q(a-,b-));

         }

         else

             break;

     }

     return ;

 }

巴特西

Vijos1512 SuperBrother打鼹鼠

SuperBrother打鼹鼠

最新文章

热门文章