hdoj4391 Paint The Wall

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2015年12月15日 星期二 15时00分34秒
  4File Name :code/hdoj/4391.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E5+7; //sqrt(n),n最大100000
 34int n,q,c[N];
 35int len ,cnt;
 36struct HashBlock{
 37    int  siz; //块的大小，因为最后一个快的长度可能不足len,
 38    int col;//整块的颜色。当快没有被标记成统一的颜色的时候，为-1
 39    map<int,int>mp;
 40}a[400];
 41
 42void init()
 43{
 44    len = (int)sqrt(n*1.0);
 45    cnt = (n-1)/len+1;
 46    for ( int i = 0 ; i < cnt ; i++)
 47    {
 48	a[i].siz = min(n,(i+1)*len)-i*len;
 49	a[i].col = -1;
 50	a[i].mp.clear();
 51    }
 52
 53    for ( int i = 0 ; i < n ; i++)
 54    {
 55	scanf("%d",&c[i]);
 56	a[i/len] .mp[c[i]]++;
 57    }
 58}
 59
 60void Push_Down( int step)
 61{
 62    if (a[step].col!=-1)
 63    {
 64	a[step].mp.clear();
 65	for ( int i = step*len ; i<min((step+1)*len,n); i++)
 66	{
 67	    c[i] = a[step].col;
 68	    a[step].mp[c[i]]++;
 69	}
 70	a[step].col = -1;
 71    }
 72}
 73
 74void update(int l,int r,int col)
 75{
 76    int la=l/len,ra=r/len;
 77    for(int i=la+1;i<ra;i++) a[i].col=col;
 78    if(la!=ra)
 79    {
 80        Push_Down(la);Push_Down(ra);
 81        for(int i=l;i<len*(1+la);i++)
 82        {
 83            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
 84        }
 85        for(int i=ra*len;i<=r;i++)
 86        {
 87            a[ra].mp[c[i]]--;a[ra].mp[col]++;c[i]=col;
 88        }
 89    }
 90    else
 91    {
 92        Push_Down(la);
 93        for(int i=l;i<=r;i++)
 94        {
 95            a[la].mp[c[i]]--;a[la].mp[col]++;c[i]=col;
 96        }
 97    }
 98}
 99int query(int l,int r,int col)
100{
101    int la = l/len;
102    int ra = r/len;
103    int ans = 0 ;
104    for ( int i = la+1 ; i < ra ; i++)
105    {
106	if (a[i].col==col) ans +=a[i].siz;
107	    else if(a[i].col==-1&&a[i].mp.find(col)!=a[i].mp.end()) ans+=a[i].mp[col];
108    }
109    if (la!=ra)   //首尾两段暴力查询...
110    {
111	Push_Down(la);
112	Push_Down(ra);
113	for ( int i = l ; i < len*(la+1);  i++)
114	{
115	    ans+=col==c[i];
116	    //if (c[i]==col) ans++;
117	}
118	for ( int i = ra*len ; i <= r ; i++)
119	{
120	    ans+=col==c[i];
121	}
122
123
124    }
125    else
126    {
127	Push_Down (la);
128	for ( int i = l ; i <= r ; i++)
129	{
130	    ans+=col==c[i];
131	    //if (c[i]==col) ans++;
132	}
133    }
134    return ans;
135}
136int main()
137{
138	#ifndef  ONLINE_JUDGE 
139	freopen("code/in.txt","r",stdin);
140  #endif
141
142	while (scanf("%d%d",&n,&q)!=EOF)
143	{
144	    init();
145	    while (q--)
146	    {
147		int k,l,r,c;
148		scanf("%d%d%d%d",&k,&l,&r,&c);
149		if (k==1) update(l,r,c);
150		else printf("%d\n",query(l,r,c));
151	    }
152	}
153
154  #ifndef ONLINE_JUDGE  
155  fclose(stdin);
156  #endif
157    return 0;
158}