HDU 4391 - Paint The Wall - 分块哈希入门

题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=4391

题意 :

给一段区间, 有两种操作

1 : 给 x 到 y 的区间染色为 z

2 : 查询 x 到 y 的区间内颜色z的数目

思路 :

这题的z最大2^31-1, 区间长度最大1e5, 用线段树将颜色离散化之后维护也存不下

所以用分块哈希, 将一个长度为n的区间分为sqrt(n)块分块维护, 每一块中都用map记录某些颜色的个数

分块哈希 :

修改, 查询一段区间, 对于完整覆盖到的区间, 是可以很快进行修改和查询的

而不完整覆盖的区间至多只有两个, 可以暴力修改

创建一个结构体HashBlock, 其中记录本身长度, 覆盖情况flag, 初始化为-1(代表未被完整覆盖)

确定长度为n的区间, 每块长度为len, 故一共分成了 tot = (n - 1) / s + 1 块

特殊的是最后一段长度是 min(n, (tot) * len) - (tot-1) * len

修改一个区间l, r时, 令la = l / len, ra = r / len, 从[la+1, ra]都被完整覆盖可以直接更新

而区间 [l, (l / len + 1) * len] 和 [r * len, r] 这两段可能未被完整覆盖, 需要手动更新

我细节讲这么多就也为了提醒自己, 再细节的说不下去了, 请看代码吧

第一次写分块哈希的代码, 参考了CXlove, 感谢

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map> using namespace std; const int MAXN = 1e5+; struct HashBlock{
int sizee, color;
map<int, int> m;
} block[]; int c[MAXN];
int len;
int n; void Init()
{
len = (int)sqrt(n);
int tot = (n - ) / len + ;
for(int i = ; i < tot; i++) {
block[i].sizee = min(n, (i+) * len) - i * len;
block[i].color = -;
block[i].m.clear();
}
} //如果一个区间要手动更新, 需要将上一次整块更新的颜色先覆盖, 再重新手动更新
//与线段树中pushdown异曲同工
void PushDown(int step)
{
if(block[step].color != -) {
block[step].m.clear();
for(int i = step * len; i < n && i < (step+) * len; i++) {
c[i] = block[step].color;
block[step].m[c[i]]++;
}
block[step].color = -;
}
} void Update(int l, int r, int color)
{
int la = l / len, ra = r / len;
//完整覆盖的区间可直接更新
for(int i = la + ; i < ra; i++) {
block[i].color = color;
}
//暴力更新未被完整覆盖的部分
if(la != ra) {
PushDown(la), PushDown(ra);
for(int i = l; i < (la+) * len; i++) {
block[la].m[c[i]]--, block[la].m[color]++, c[i] = color;
}
for(int i = ra * len; i <= r; i++) {
block[ra].m[c[i]]--, block[ra].m[color]++, c[i] = color;
}
}
else { //是同一段区间
PushDown(la);
for(int i = l; i <=r; i++) {
block[la].m[c[i]]--, block[la].m[color]++, c[i] = color;
}
}
} int Query(int l, int r, int color)
{
int ans = ;
int la = l / len, ra = r / len;
for(int i = la + ; i < ra; i++) {
if(block[i].color == color) ans += block[i].sizee;
else if(block[i].color == - && \
block[i].m.find(color) != block[i].m.end()) {
ans += block[i].m[color];
}
}
if(la != ra) {
PushDown(la), PushDown(ra);
for(int i = l; i < (la+) * len; i++) {
ans += c[i] == color;
}
for(int i = ra * len; i <= r; i++) {
ans += c[i] == color;
}
}
else {
PushDown(la);
for(int i = l; i <=r ; i++) {
ans += c[i] == color;
}
} return ans;
} int main()
{
int q; while(scanf("%d %d", &n, &q) != EOF) {
Init();
for(int i = ; i < n; i++) {
scanf("%d", &c[i]);
block[i/len].m[c[i]]++;
}
while(q--) {
int cmd, l, r, z;
scanf("%d %d %d %d", &cmd, &l, &r, &z);
if(cmd == ) Update(l, r, z);
else printf("%d\n", Query(l, r, z));
}
} return ;
}
上一篇:HDU 4391 Paint The Wall(分块的区间维护)


下一篇:使用Mongo进行分页