hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。

/* ***********************************************
Author :111qqz
Created Time :2015年12月15日 星期二 15时00分34秒
File Name :code/hdoj/4391.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7; //sqrt(n),n最大100000
int n,q,c[N];
int len ,cnt;
struct HashBlock{
    int  siz; //块的大小，因为最后一个快的长度可能不足len,
    int col;//整块的颜色。当快没有被标记成统一的颜色的时候，为-1
    map<int,int>mp;
}a[400];

void init()
{
    len = (int)sqrt(n*1.0);
    cnt = (n-1)/len+1;
    for ( int i = 0 ; i < cnt ; i++)
    {
	a[i].siz = min(n,(i+1)*len)-i*len;
	a[i].col = -1;
	a[i].mp.clear();
    }

    for ( int i = 0 ; i < n ; i++)
    {
	scanf("%d",&c[i]);
	a[i/len] .mp[c[i]]++;
    }
}

void Push_Down( int step)
{
    if (a[step].col!=-1)
    {
	a[step].mp.clear();
	for ( int i = step*len ; i<min((step+1)*len,n); i++)
	{
	    c[i] = a[step].col;
	    a[step].mp[c[i]]++;
	}
	a[step].col = -1;
    }
}

void update(int l,int r,int col)
{
    int la=l/len,ra=r/len;
    for(int i=la+1;i<ra;i++) a[i].col=col;
    if(la!=ra)
    {
        Push_Down(la);Push_Down(ra);
        for(int i=l;i<len*(1+la);i++)
        {
            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
        }
        for(int i=ra*len;i<=r;i++)
        {
            a[ra].mp[c[i]]--;a[ra].mp[col]++;c[i]=col;
        }
    }
    else
    {
        Push_Down(la);
        for(int i=l;i<=r;i++)
        {
            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
        }
    }
}
int query(int l,int r,int col)
{
    int la = l/len;
    int ra = r/len;
    int ans = 0 ;
    for ( int i = la+1 ; i < ra ; i++)
    {
	if (a[i].col==col) ans +=a[i].siz;
	    else if(a[i].col==-1&&a[i].mp.find(col)!=a[i].mp.end()) ans+=a[i].mp[col];
    }
    if (la!=ra)   //首尾两段暴力查询...
    {
	Push_Down(la);
	Push_Down(ra);
	for ( int i = l ; i < len*(la+1);  i++)
	{
	    ans+=col==c[i];
	    //if (c[i]==col) ans++;
	}
	for ( int i = ra*len ; i <= r ; i++)
	{
	    ans+=col==c[i];
	}


    }
    else
    {
	Push_Down (la);
	for ( int i = l ; i <= r ; i++)
	{
	    ans+=col==c[i];
	    //if (c[i]==col) ans++;
	}
    }
    return ans;
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	while (scanf("%d%d",&n,&q)!=EOF)
	{
	    init();
	    while (q--)
	    {
		int k,l,r,c;
		scanf("%d%d%d%d",&k,&l,&r,&c);
		if (k==1) update(l,r,c);
		else printf("%d\n",query(l,r,c));
	    }
	}

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}