HDU - 2642 Stars

本文主要是介绍HDU - 2642 Stars，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：就是求每个矩形内的亮的星星的个数

思路：二维的树状数组，相当于优化了的矩阵求和的题目

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1005;int arr[MAXN][MAXN];
int vis[MAXN][MAXN];int lowbit(int x){return x & (-x);
}void update(int i,int j,int d){int tmpj;while (i < MAXN){tmpj = j;while (tmpj < MAXN){arr[i][tmpj] += d;tmpj += lowbit(tmpj);}i += lowbit(i);}
}int sum(int i,int j){int tmpj,sum = 0;while (i > 0){tmpj = j;while (tmpj > 0){sum += arr[i][tmpj];tmpj -= lowbit(tmpj);}i -= lowbit(i);}return sum;
}int main(){memset(vis,0,sizeof(vis));memset(arr,0,sizeof(arr));int t,a,b,c,d;char op;scanf("%d",&t);while (t--){getchar();scanf("%c",&op);if (op == 'B'){scanf("%d%d",&a,&b);a++,b++;if (!vis[a][b]){vis[a][b] = 1;update(a,b,1);}}else if (op == 'D'){scanf("%d%d",&a,&b);a++,b++;if (vis[a][b]){vis[a][b] = 0;update(a,b,-1);}}else {scanf("%d%d%d%d",&a, &b, &c, &d);a++,b++,c++,d++;if (b > a)swap(a,b);if (d > c)swap(c,d);int ans = sum(a,c)+sum(b-1,d-1)-sum(a,d-1)-sum(b-1,c);printf("%d\n",ans);	}}return 0;
}

这篇关于HDU - 2642 Stars的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---