http://acm.hdu.edu.cn/showproblem.php?pid=4391
题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。
思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
/* *********************************************** 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; } |
说点什么
您将是第一位评论人！