hdu 4391 Paint The Wall

hdu 4391 Paint The Wall
ブロックhash、その时の试合の时はまだ神马のものだと知らないで、问题を解いて报告して正解はブロックhashだと言って、実はあまり难しくないと感じて、これらのマークのデバッグを维持するのは少し面倒で、もし思惟がはっきりしないならばきっとデバッグできないので、私のは1つの间违いが私をデバッグして1晩
各ブロックには、現在のブロックの全体的な色を表すマークvisがあり、-1の場合、現在のブロックが統一された色ではないことを示すmpが機能し、対応する色の数にマッピングされる

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

const int maxn=100010;
struct Flag
{
    int vis;
    map<int,int> mp;
}flag[800];
int a[maxn],n,q,block_num,block_size;

void rehash(int block_no)
{
    flag[block_no].vis=-1;
    int sta=block_no*block_size;
    flag[block_no].mp.clear();
    for(int i=0;i<block_size&&i+sta<n;i++) flag[block_no].mp[a[sta+i]]++;
}
void build()
{
    block_size=(int)sqrt(n*1.0+1e-8);
    block_num=n/block_size+(n%block_size!=0);
    for(int i=0;i<n;i++)
       scanf("%d",&a[i]);
    for(int i=0;i<block_num;i++)  rehash(i);
}
void pushdown(int block_no)
{
    if(flag[block_no].vis!=-1){
        flag[block_no].mp.clear();
        int sta=block_no*block_size,sz=0;
        int &cc=flag[block_no].vis;
        for(int i=0;i<block_size&&i+sta<n;i++) a[sta+i]=cc,sz++;

        flag[block_no].mp[cc]=sz;
        cc=-1;
    }
}

void update(int l,int r,int c)
{
    int lx=l/block_size;
    int rx=r/block_size;
    if(lx==rx){
        pushdown(lx);
        for(int i=l;i<=r;i++) a[i]=c;
        rehash(lx);
    }else{
        pushdown(lx);pushdown(rx);
        int sta=(lx+1)*block_size;
        for(int i=l;i<sta;i++) a[i]=c;
        rehash(lx);
        sta=rx*block_size;
        for(int i=sta;i<=r;i++) a[i]=c;
        rehash(rx);
        for(int i=lx+1;i<rx;i++) flag[i].vis=c;
    }
}
int query(int l,int r,int c)
{
    int lx=l/block_size;
    int rx=r/block_size;
    int ret=0;
    if(lx==rx){
        pushdown(lx);
        for(int i=l;i<=r;i++)
           ret+= (a[i]==c);
    }else{
        pushdown(lx);pushdown(rx);
        int sta=(lx+1)*block_size;
        for(int i=l;i<sta;i++) ret+=(a[i]==c);
        sta=rx*block_size;
        for(int i=sta;i<=r;i++) ret+=(a[i]==c);
        for(int i=lx+1;i<rx;i++)
          if(flag[i].vis!=-1){
              if(flag[i].vis==c) ret+=block_size;
          }
          else if(flag[i].mp.find(c)!=flag[i].mp.end()) ret+=flag[i].mp[c];
    }
    return ret;
}
int main()
{
    int id,l,r,c;
    while(scanf("%d%d",&n,&q)==2)
    {
        build();
        while(q--)
        {
            scanf("%d%d%d%d",&id,&l,&r,&c);
            if(id==1)  update(l,r,c);
            else printf("%d
",query(l,r,c));
        }
    }
    return 0;
}