bzoj1452 [JSOI2009]Count ——二维树状数组
2024-08-31 01:43:27
中文题面,给你一个矩阵,每一个格子有数字,有两种操作。
1. 把i行j列的值更改
2. 询问两个角坐标分别为(x1,y1) (x2,y2)的矩形内有几个值为z的点。
这一题的特点就是给出的z的数据范围很小,只有1~100,所以我们可以开100个300X300的二维树状数组来解决问题。
#include<bits/stdc++.h>
using namespace std;
int a[][][];
int s[][];
int n,m,k;
int lowbit(int x)
{
return x&-x;
}
int add(int x,int y,int z,int w)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)) a[i][j][z]+=w;
}
int find(int x,int y,int z)
{
int ans=;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
{
ans+=a[i][j][z];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&s[i][j]);
add(i,j,s[i][j],);
}
scanf("%d",&k);
int ddd,x,y,z,xx,yy;
for(int i=;i<k;i++)
{
scanf("%d",&ddd);
if(ddd==)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,s[x][y],-);
add(x,y,z,);
s[x][y]=z;
}
else
{
scanf("%d%d%d%d%d",&x,&xx,&y,&yy,&z);
int ans=find(xx,yy,z)-find(xx,y-,z)-find(x-,yy,z)+find(x-,y-,z);
//cout<<find(xx,yy,z)<<find(xx,y-1,z)<<find(x-1,yy,z)<<find(x-1,y-1,z)<<endl;
printf("%d\n",ans);
}
}
}
最新文章
- IO口
- ZKM混淆工具
- 20 seq 某个数到另外一个数之间的所有整数
- redis Transaction支持
- public <;T>; void show(T t),void前面的泛型T是什么作用
- 使用新的AppleID更新Xcode
- makefile missing separator. Stop
- WCF 第五章 会话级别的实例
- 小强的HTML5移动开发之路(4)——CSS2和CSS3
- Oracle11g创建表空间、创建用户、角色授权、导入导出表以及中文字符乱码问题
- 1)requests模块
- js设置元素不能编辑
- Docker:Docker搭建Redis集群(6)
- 概念:CountDownLatch、CyclicBarrier、Semaphore,以及guava的RateLimiter
- while_else
- 常用算法3 - 字符串查找/模式匹配算法(BF &; KMP算法)
- activate mod_rewrite How To Set Up mod_rewrite for Apache on Ubuntu 14.04 Apache Rewrite url重定向功能的简单配置
- hive连接数
- PJOI PKU Campus 2011 B:A Problem about Tree LCA 求随意点x为根的y的父节点
- Ubuntu免安装配置MySQL