http://www.lydsy.com/JudgeOnline/problem.php?id=1452
題意：n×m的矩陣上每個點有個顏色，現在有q個操作：1 x y c 將點(x,y)的顏色改為c；2 x1 x2 y1 y2 c 詢問矩陣x1y1-x2y2顏色為c的格子數目
#include <bits/stdc++.h>
using namespace std;
const int N=301;
int n, m;
int S[101][N][N], col[N][N];
void upd1(int c[N], int x, int w) { for(; x<=m; x+=x&-x) c[x]+=w; }
void upd2(int c[N][N], int x, int y, int w) { for(; x<=n; x+=x&-x) upd1(c[x], y, w); }
int sum1(int c[N], int x) { int ret=0; for(; x; x-=x&-x) ret+=c[x]; return ret; }
int sum2(int c[N][N], int x, int y) { int ret=0; for(; x; x-=x&-x) ret+=sum1(c[x], y); return ret; }
void upd(int c[N][N], int x, int y, int s) {
upd2(c, x, y, s);
}
int sum(int c[N][N], int xa, int ya, int xb, int yb) {
int ret=0;
ret+=sum2(c, xb, yb); // cout << " ret: " << ret << endl;
ret-=sum2(c, xb, ya-1);
ret-=sum2(c, xa-1, yb);
ret+=sum2(c, xa-1, ya-1);
return ret;
}
int main() {
scanf("%d %d", &n, &m);
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) {
int x; scanf("%d", &x);
col[i][j]=x;
upd(S[x], i, j, 1);
}
int q;
scanf("%d", &q);
for(int cc=0; cc<q; ++cc) {
int ch;
scanf("%d", &ch);
if(ch==1) {
int x, y, cl;
scanf("%d %d %d", &x, &y, &cl);
upd(S[col[x][y]], x, y, -1);
col[x][y]=cl;
upd(S[col[x][y]], x, y, 1);
}
else {
int xa, xb, ya, yb, w;
scanf("%d%d%d%d%d", &xa, &xb, &ya, &yb, &w);
printf("%d\n", sum(S[w], xa, ya, xb, yb));
}
}
return 0;
}
?
二維bit......
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
