Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。
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}