首页 > 代码库 > 【BZOJ】1452: [JSOI2009]Count 树状数组

【BZOJ】1452: [JSOI2009]Count 树状数组

2024-08-13 21:15:55   209人阅读

Description

技术分享

Input

技术分享

Output

技术分享

Sample Input

技术分享

Sample Output

1
2

HINT

技术分享

  题解：

　　二维的树状数组啊+一维的颜色状态，然后直接做就好……实际上比照一维的树状数组就是多了一个for循环，然后查询操作的时候就相当于查询某一矩阵的大小，树状数组起到一个类似前缀和的作用。

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #define lowbit(x) x&(-x) 6 using namespace std; 7 const int MAXN = 301; 8 int a[MAXN][MAXN], Tree[101][MAXN][MAXN]; 9 int n, m;10 void Modify(int x, int y, int s, int tar)11 {12     int i, j;13     for (i = x; i <= n; i += lowbit(i))14         for (j = y; j <= m; j += lowbit(j))15             Tree[s][i][j] += tar;16 }17 inline int Query(int x, int y, int s)18 {19     int i, j;20     int sum = 0;21     for (i = x; i; i -= lowbit(i))22         for (j = y; j; j -= lowbit(j))23             sum += Tree[s][i][j];24     return sum;25 }26 int main(int argc, char *argv[])27 {28     int c, i, j, x, Q, op, y;29     int x1, y1, x2, y2;30     int ans;31     scanf("%d%d", &n, &m);32     for (i = 1; i <= n; i++)33         for (j = 1; j <= m; j++)34         {35         scanf("%d", &a[i][j]);36         Modify(i, j, a[i][j], 1);37         }38     scanf("%d", &Q);39     while (Q--)40     {41         scanf("%d", &op);42         if (op == 1)43         {44             scanf("%d%d%d", &x, &y, &c);45             Modify(x, y, a[x][y], -1);46             a[x][y] = c;47             Modify(x, y, a[x][y], 1);48         }49         else if (op == 2)50         {51             scanf("%d%d%d%d%d", &x1, &x2, &y1, &y2, &c);52             ans = 0;53             ans = Query(x1 - 1, y1 - 1, c) + Query(x2, y2, c) - Query(x1 - 1, y2, c) - Query(x2 , y1 - 1, c);54             printf("%d\n", ans);55         }56     }57     return 0;58 }

 

【BZOJ】1452: [JSOI2009]Count 树状数组


联系
我们