Count(二维树状数组)
2024-08-26 20:45:32
【bzoj1452】[JSOI2009]Count
Description
Input
Output
Sample Input
Sample Output
1
2
2
HINT
题解:对于每一个颜色建一个二维的树状数组O(c*logn*logm),试了试对每个颜色,每行建一个一维数组,超时了。。。O(c*n*logm)
若一维树状数组不会:http://www.cnblogs.com/haoabcd2010/p/6657393.html
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std;
#define MAXN 302 int n,m;
int G[MAXN][MAXN];
int tree[][MAXN][MAXN]; // 颜色,行,列 int lowbit(int x) {return x&(-x);} void update(int c,int x,int y,int add)
{
for(int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=m;j+=lowbit(j))
tree[c][i][j]+=add;
} int getsum(int c,int x,int y)
{
int ans =;
for (int i=x;i>;i-=lowbit(i))
for (int j=y;j>;j-=lowbit(j))
ans += tree[c][i][j];
return ans;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
scanf("%d",&G[i][j]); for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
update(G[i][j],i,j,); int q;
scanf("%d",&q);
while (q--)
{
int op;
scanf("%d",&op);
if (op==)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
update(c,x,y,);//c颜色x,y +1
update(G[x][y],x,y,-);//原来颜色xy -1
G[x][y]=c;
}
if (op==)
{
int x1,x2,y1,y2,c;
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
int ans = getsum(c,x2,y2)+getsum(c,x1-,y1-); //c 颜色 i行y1-y2;
ans -= getsum(c,x1-,y2);
ans -= getsum(c,x2,y1-);
printf("%d\n",ans);
}
}
return ;
}
最新文章
- Gold Game
- C#窗体文件的操作
- Effective C++ -----条款47:请使用traits classes表现类型信息
- 开源的Android开发框架-------PowerFramework使用心得(三)内置浏览器BrowserActivity
- 【转】android蓝牙开发---与蓝牙模块进行通信--不错
- tensorflow-线性函数训练例子一
- 基于MVC4+EasyUI的Web开发框架形成之旅(6)--基类控制器CRUD的操作
- three.js学习:纹理Texture之平面纹理
- Logstash收集nginx日志之使用grok过滤插件解析日志
- SQLSERVER中的元数据锁
- JSON中JObject和JArray的修改
- linux下的usb转串口的使用(修改)【转】
- VS2010/MFC编程入门之五十三(Ribbon界面开发:为Ribbon Bar添加控件)
- Linux——软件包简单学习笔记
- h5笔记
- uliweb框架数据库操作
- Android学习笔记(四) 定时器Timer
- JNI字段描述符
- 2017.10.26 ECN + product spec+ cypress ble module test+
- Codeforces Round 536 (Div. 2) (E)