hdoj4391 Paint The Wall

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

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

 1void init()
 2{
 3    len = (int)sqrt(n*1.0);
 4    cnt = (n-1)/len+1;
 5    for ( int i = 0 ; i < cnt ; i++)
 6    {
 7	a[i].siz = min(n,(i+1)*len)-i*len;
 8	a[i].col = -1;
 9	a[i].mp.clear();
10    }

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

 1void Push_Down( int step)
 2{
 3    if (a[step].col!=-1)
 4    {
 5	a[step].mp.clear();
 6	for ( int i = step*len ; i<min((step+1)*len,n); i++)
 7	{
 8	    c[i] = a[step].col;
 9	    a[step].mp[c[i]]++;
10	}
11	a[step].col = -1;
12    }
13}

 1void update(int l,int r,int col)
 2{
 3    int la=l/len,ra=r/len;
 4    for(int i=la+1;i<ra;i++) a[i].col=col;
 5    if(la!=ra)
 6    {
 7        Push_Down(la);Push_Down(ra);
 8        for(int i=l;i<len*(1+la);i++)
 9        {
10            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
11        }
12        for(int i=ra*len;i<=r;i++)
13        {
14            a[ra].mp[c[i]]--;a[ra].mp[col]++;c[i]=col;
15        }
16    }
17    else
18    {
19        Push_Down(la);
20        for(int i=l;i<=r;i++)
21        {
22            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
23        }
24    }
25}
26int query(int l,int r,int col)
27{
28    int la = l/len;
29    int ra = r/len;
30    int ans = 0 ;
31    for ( int i = la+1 ; i < ra ; i++)
32    {
33	if (a[i].col==col) ans +=a[i].siz;
34	    else if(a[i].col==-1&&a[i].mp.find(col)!=a[i].mp.end()) ans+=a[i].mp[col];
35    }
36    if (la!=ra)   //首尾两段暴力查询...
37    {
38	Push_Down(la);
39	Push_Down(ra);
40	for ( int i = l ; i < len*(la+1);  i++)
41	{
42	    ans+=col==c[i];
43	    //if (c[i]==col) ans++;
44	}
45	for ( int i = ra*len ; i <= r ; i++)
46	{
47	    ans+=col==c[i];
48	}

 1    }
 2    else
 3    {
 4	Push_Down (la);
 5	for ( int i = l ; i <= r ; i++)
 6	{
 7	    ans+=col==c[i];
 8	    //if (c[i]==col) ans++;
 9	}
10    }
11    return ans;
12}
13int main()
14{
15	#ifndef  ONLINE_JUDGE 
16	freopen("code/in.txt","r",stdin);
17  #endif

 1	while (scanf("%d%d",&n,&q)!=EOF)
 2	{
 3	    init();
 4	    while (q--)
 5	    {
 6		int k,l,r,c;
 7		scanf("%d%d%d%d",&k,&l,&r,&c);
 8		if (k==1) update(l,r,c);
 9		else printf("%d\n",query(l,r,c));
10	    }
11	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}