【二维树状数组】See you~

https://www.bnuoj.com/v3/contest_show.php?cid=9148#problem/F

【题意】

给定一个矩阵，每个格子的初始值为1。现在可以对矩阵有四种操作：

A x y n1 :给格点(x,y)的值加n1

D x y n1: 给格点(x,y)的值减n1,如果现在格点的值不够n1，把格点置0

M x1 y1 x2 y2：(x1,y1)移动给(x2,y2)n1个

S x1 y1 x2 y2 查询子矩阵的和

【思路】

当然是二维树状数组

但是一定要注意：lowbit(0)是死循环，一定不能是0。所以初始化格点为1的时候要从1开始，以及对于输入的坐标，我们要加1处理。

【Accepted】

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 int n;

 const int maxn=1e3+;

 int bit[maxn][maxn];

 int lowbit(int x)

 {

     return (-x)&x;

 }

 void add(int x,int y,int val)

 {

     while(x<maxn)

     {

         int temp=y;

         while(temp<maxn)

         {

             bit[x][temp]+=val;

             temp+=lowbit(temp);

         }

         x+=lowbit(x);

     }

 }

 int sum(int x,int y)

 {

     int ans=;

     while(x>)

     {

         int temp=y;

         while(temp>)

         {

             ans+=bit[x][temp];

             temp-=lowbit(temp);

         }

         x-=lowbit(x);

      }

     return ans;

 }

 int solve(int x1,int y1,int x2,int y2)

 {

     return sum(x2,y2)-sum(x1-,y2)-sum(x2,y1-)+sum(x1-,y1-);

 }

 char op[];

 int main()

 {

     int T;

     scanf("%d",&T);

     int cas=;

     while(T--)

     {

         printf("Case %d:\n",++cas);

         memset(bit,,sizeof(bit));

         for(int i=;i<maxn;i++)

         {

             for(int k=;k<maxn;k++)

             {

                 add(i,k,);

             }

         }

         scanf("%d",&n);

         for(int i=;i<n;i++)

         {

         //    getchar();

             scanf("%s",op);

             if(op[]=='S')

             {

                 int x1,y1,x2,y2;

                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

                 x1++;y1++;x2++;y2++;

                 if(x1>x2)

                 {

                     swap(x1,x2);

                 }

                 if(y1>y2)

                 {

                     swap(y1,y2);

                 }

                 printf("%d\n",solve(x1,y1,x2,y2));

             }

             if(op[]=='A')

             {

                 int x,y,n1;

                 scanf("%d%d%d",&x,&y,&n1);

                 x++;y++;

                 add(x,y,n1);

             }

             if(op[]=='D')

             {

                 int x,y,n1;

                 scanf("%d%d%d",&x,&y,&n1);

                 x++;y++;

                 if(solve(x,y,x,y)<n1)

                 {

                     n1=solve(x,y,x,y);

                 }

                 add(x,y,-n1);

             }

             if(op[]=='M')

             {

                 int x1,y1,x2,y2,n1;

                 scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n1);

                 x1++;y1++;x2++;y2++;

                 if(solve(x1,y1,x1,y1)<n1)

                 {

                     n1=solve(x1,y1,x1,y1);

                 }

                 add(x1,y1,-n1);

                 add(x2,y2,n1);

             }

         }

     }

     return ;

 }

二维树状数组

【知识点】

1. 树状数组是O(logn)的，是因为n的二进制里最多有logn个1

2. 注意：树状数组的下标必须从1开始，，因为lowbit(0)=0,如果从0开始的话就会陷入死循环！！树状数组适用于所有满足结合律的运算（加法，乘法，异或等）

3. 所有树状数组能完成的操作线段树都能够完成，但是线段树的代码复杂，时间复杂度也比较高，查询、修改需要递归完成，而，树状数组的操作不仅代码简洁，便于理解，而且一切都是递推完成的，所以能用树状数组解决的问题尽量不要用线段树来写。

4. 树状数组可以查找逆序对，对于LIS问题可以查找方案数。

巴特西

【二维树状数组】See you~

最新文章

热门文章