给出一个区间以及两种区间操作，[1 l,r,c]把l~r的点染成c色，[2,l,r,c]查询l~r内颜色为c的点的数目。
因为c的数目太大，用线段树是存不下的，所以只能另辟蹊径了。虽然网上有线段树的方法，但那个Max-Min剪枝完全是没有作用的，随便出一组数据，把所有点间隔染成3，5，然后查4，这样用线段树不知道要跑多久。。。
题解说这题是裸的分块HASH。。还没写过，学习了。其实就是将原区间划分乘sqrt(n)个区间，每次暴力查询和跟新两边的区间，中间的区间直接用hash存每种颜色的节点的数量。这里用到了类似线段树的lazy思想，区间成段修改直接打个标记，等到要划分这个区间的时候先把标记传下去，然后跟新。
复杂度可以保证在每次操作sqrt(n)左右，这里为了方便我就直接写map了。。
1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 #include <map> 5 #define MAXN 100005 6 int n,m,bsize,bnum,x[MAXN]; 7 struct hash_block{ 8 int cls,size; 9 std::map<int,int> mp; 10 }b[350]; 11 //下传标记,当这个块化整为零的时候需要下传标记并跟新所有元素 12 void pushdown(int id){ 13 hash_block &hb=b[id]; 14 if(hb.cls!=-1){ 15 for(int i=id*bsize;i<id*bsize+hb.size;i++)x[i]=hb.cls; 16 hb.mp.clear(),hb.mp[hb.cls]=hb.size; 17 hb.cls=-1; 18 } 19 } 20 //跟新,中间的部分打标记就可以了,两边的sqrt(n)暴力跟新 21 void update(int l,int r,int c){ 22 int lb=l/bsize,rb=r/bsize,ans=0; 23 for(int i=lb+1;i<rb;i++)b[i].cls=c; 24 if(lb!=rb){ 25 pushdown(lb);pushdown(rb); 26 for(int i=l;i<lb*bsize+b[lb].size;i++) 27 b[lb].mp[x[i]]--,b[lb].mp[c]++,x[i]=c; 28 for(int i=rb*bsize;i<=r;i++) 29 b[rb].mp[x[i]]--,b[rb].mp[c]++,x[i]=c; 30 }else{ 31 pushdown(lb); 32 for(int i=l;i<=r;i++) 33 b[lb].mp[x[i]]--,b[lb].mp[c]++,x[i]=c; 34 } 35 } 36 //中间的部分根据标记或者hash表可以直接查询,两边的sqrt(n)暴力查询 37 int query(int l,int r,int c){ 38 int lb=l/bsize,rb=r/bsize,ans=0; 39 for(int i=lb+1;i<rb;i++){ 40 //一直错在这个地方了,如果有标记,直接判断标记是不是需要的颜色 41 //如果没标记,要先判map中有没有这个元素然后在操作,否则会MLE! 42 if(b[i].cls==c)ans+=b[i].size; 43 else if(b[i].cls==-1&&b[i].mp.find(c)!=b[i].mp.end())ans+=b[i].mp[c]; 44 } 45 if(lb!=rb){ 46 pushdown(lb);pushdown(rb); 47 for(int i=l;i<lb*bsize+b[lb].size;i++)ans+=(x[i]==c); 48 for(int i=rb*bsize;i<=r;i++)ans+=(x[i]==c); 49 }else{ 50 pushdown(lb); 51 for(int i=l;i<=r;i++)ans+=(x[i]==c); 52 } 53 return ans; 54 } 55 void initblock(){ 56 bsize=(int)sqrt(n+1e-8); 57 bnum=(n-1)/bsize+1; 58 for(int i=0;i<bnum;i++){ 59 b[i].mp.clear(); 60 b[i].cls=-1; 61 b[i].size=std::min(i*bsize+bsize,n)-i*bsize; 62 } 63 for(int i=0;i<n;i++){ 64 scanf("%d",&x[i]); 65 b[i/bsize].mp[x[i]]++; 66 } 67 } 68 int q,l,r,z; 69 int main(){ 70 //freopen("test.in","r",stdin); 71 while(scanf("%d%d",&n,&m)!=EOF){ 72 initblock(); 73 while(m--){ 74 scanf("%d%d%d%d",&q,&l,&r,&z); 75 if(q==1)update(l,r,z); 76 else printf("%d\n",query(l,r,z)); 77 } 78 } 79 return 0; 80 }