传送门
Solution
2D BIT模板
Code
//By Menteur_Hxy#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define Re register#define Ms(a,b) memset(a,(b),sizeof(a))#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)#define Lof(i,a,b) for(Re int i=(a),_=(b);i<=_;i+=i&-i)#define Lor(i,a) for(Re int i=(a);i;i-=i&-i)using namespace std;inline int read() { ???int x=0,f=1;char c=getchar(); ???while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();} ???while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); ???return x*f;}const int N=310;int n,m,q;int mp[N][N];struct TDBIT{ ???int da[N][N][N]; ???void clear() {Ms(da,0);} ???void Modify(int p,int x,int y,int d) { Lof(i,x,n) Lof(j,y,m) da[p][i][j]+=d;} ???int qry(int p,int x,int y) {int t=0;Lor(i,x) Lor(j,y) t+=da[p][i][j];return t;} ???int query(int p,int x1,int y1,int x2,int y2) {return qry(p,x2,y2)+qry(p,x1-1,y1-1)-qry(p,x1-1,y2)-qry(p,x2,y1-1);}}T;int main() { ???n=read(),m=read(); ???Fo(i,1,n) Fo(j,1,m) T.Modify(mp[i][j]=read(),i,j,1); ???q=read(); ????while(q--) { ???????int opt=read(); ???????if(opt==1) { ???????????int x=read(),y=read(),c=read(); ???????????T.Modify(mp[x][y],x,y,-1); ???????????T.Modify(mp[x][y]=c,x,y,1); ???????} else { ???????????int x1=read(),x2=read(),y1=read(),y2=read(),c=read(); ???????????printf("%d\n",T.query(c,x1,y1,x2,y2)); ???????} ???} ???return 0;}[luogu4054 JSOI2009] 计数问题(2D BIT)
原文地址：https://www.cnblogs.com/Menteur-Hxy/p/9798679.html