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
************************************************ */
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}