- 区间覆盖[l,r]变成c
- 区间查询[l,r]里有几个c
分块求,然后配合map,map好处就是不需要离散化,而且长度可以变话
有一点就是在求某个数字在分块出现次数时,先进行查找,看这个数字是否出现过。这样可以节省内存,这道题卡内存,要不然直接开一个tag[分块个数][N]
map[x]操作时,如果map没有x这个数字,它会直接加入x这个数字,但值为0
初始统计每个分块数字出现的情况,对于某区间修改,中间段采用tag标记,左右两端暴力。每次操作都需要把左右两端的分块进行pushdwon,修改好着一块才能进行暴力
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
struct Block{
int a[N], tag[320];
int unt;
std::map<int, int> mp[320];
void init(int n){
unt = sqrt(n);
memset(tag, -1, sizeof(tag));
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < 320; i++)
mp[i].clear();
for(int i = 1; i <= n; i++)
mp[(i - 1) / unt + 1][a[i]]++;
}
void pushdown(int k){
if(!~tag[k])return;
for(int i = (k - 1) * unt + 1; i <= k * unt; i++)
a[i] = tag[k];
tag[k] = -1;
}
void Modify(int l, int r, int val){
int le = (l - 1) / unt + 1;
int re = (r - 1) / unt + 1;
pushdown(le), pushdown(re);
if(le == re){
for(int i = l; i <= r; i++){
mp[le][a[i]]--;
a[i] = val;
mp[le][a[i]]++;
}
return;
}else{
for(int i = l; i <= le * unt; i++){
mp[le][a[i]]--;
a[i] = val;
mp[le][a[i]]++;
}
for(int i = (re - 1) * unt + 1; i <= r; i++){
mp[re][a[i]]--;
a[i] = val;
mp[re][a[i]]++;
}
for(int i = le + 1; i <= re - 1; i++){
mp[i].clear();
mp[i][val] += unt;
tag[i] = val;
}
}
}
int Query(int l, int r, int val){
int le = (l - 1) / unt + 1;
int re = (r - 1) / unt + 1;
int ans = 0;
pushdown(le), pushdown(re);
if(le == re){
for(int i = l; i <= r; i++)
ans += a[i] == val;
return ans;
}else{
for(int i = l; i <= le * unt; i++)
ans += a[i] == val;
for(int i = le + 1; i <= re - 1; i++)
if(mp[i].find(val) != mp[i].end()) ans += mp[i][val];
for(int i = (re - 1) * unt + 1; i <= r; i++)
ans += a[i] == val;
}
return ans;
}
}B;
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
B.init(n);
for(int i = 1; i <= m; i++){
int op, l, r, val;
scanf("%d%d%d%d", &op, &l, &r, &val);
if(op == 1)B.Modify(l + 1, r + 1, val);
if(op == 2)printf("%d\n", B.Query(l + 1, r + 1, val));
}
}
return 0;
}