题意：给出几个操作，把l-r赋值为z，询问l-r有几个z，其中z < INT_MAX
思路：因为z很大，所以很难直接用线段树去维护。这里可以使用分块来解决。我们可以让每个块用map去储存map[i]的个数，用类似线段树的lazy标记来给整个块更新，当需要对块内某些数操作时再pushdown。
注意一下不要随意开辟map的空间，在计算区间的z的个数时应采用
if(b[i].num.find(z) != b[i].num.end()) ans += b[i].num[z];
减少空间开辟。
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
struct Block{
map<int, int> num;
int lazy, L, R;
}b[];
int belong[maxn], a[maxn], block, sz;
int n, m;
void init(){
block = sqrt(n * 1.0);
for(int i = ; i < n; i++)
belong[i] = i / block + ;
sz = belong[n - ];
for(int i = ; i <= sz; i++){
b[i].lazy = -;
b[i].L = (i - ) * block;
b[i].R = min(b[i].L + block - , n - );
b[i].num.clear();
for(int j = b[i].L; j <= b[i].R; j++){
b[i].num[a[j]]++;
}
}
}
void push_down(int x){
b[x].num.clear();
for(int i = b[x].L; i <= b[x].R; i++)
a[i] = b[x].lazy;
b[x].num[b[x].lazy] = b[x].R - b[x].L + ;
b[x].lazy = -;
}
void update(int ll, int rr, int z){
int l = belong[ll], r = belong[rr];
int L, R;
if(l == r){
if(b[l].lazy != -) push_down(l);
for(int i = ll; i <= rr; i++){
b[l].num[a[i]]--;
b[l].num[z]++;
a[i] = z;
}
}
else{
L = ll, R = b[l].R;
if(b[l].lazy != -) push_down(l);
for(int i = L; i <= R; i++){
b[l].num[a[i]]--;
b[l].num[z]++;
a[i] = z;
} L = l + , R = r - ;
for(int i = L; i <= R; i++)
b[i].lazy = z; L = b[r].L, R = rr;
if(b[r].lazy != -) push_down(r);
for(int i = L; i <= R; i++){
b[r].num[a[i]]--;
b[r].num[z]++;
a[i] = z;
}
}
}
int query(int ll, int rr, int z){
int l = belong[ll], r = belong[rr];
int L, R, ans = ; if(l == r){
if(b[l].lazy != -) push_down(l);
for(int i = ll; i <= rr; i++){
if(a[i] == z) ans++;
}
return ans;
}
else{
L = ll, R = b[l].R;
if(b[l].lazy != -) push_down(l);
for(int i = L; i <= R; i++){
if(a[i] == z) ans++;
} L = l + , R = r - ;
for(int i = L; i <= R; i++){
if(b[i].lazy != -){
if(b[i].lazy == z) ans += b[i].R - b[i].L + ;
}
else{
if(b[i].num.find(z) != b[i].num.end()) ans += b[i].num[z]; //不开辟新空间
}
} L = b[r].L, R = rr;
if(b[r].lazy != -) push_down(r);
for(int i = L; i <= R; i++){
if(a[i] == z) ans++;
}
return ans;
}
}
int main(){
while(~scanf("%d%d", &n, &m)){
for(int i = ; i < n; i++){
scanf("%d", &a[i]);
}
init();
while(m--){
int o, l, r, z;
scanf("%d%d%d%d", &o, &l, &r, &z);
if(o == ){
update(l, r, z);
}
else{
printf("%d\n", query(l, r, z));
}
}
}
return ;
}