hdu 3648 Median Filter

http://acm.hdu.edu.cn/showproblem.php?pid=3648

　　题意相当简单，就是要找出所有给定大小的r*r的矩阵的中位数。

　　这题理论上可以用各种各样的数据结构完成，可以用线段树（或线段树的退化版，点树），treap，AVL树，或者树状数组等。不过，由于数据规模的限制，这题就只能用树状数组来过了。因为其他以上提到的数据结构都是因为常数太大，所以会超时。另外，这题还要模拟矩阵移动的过程，要蛇形移动，否则元素进出树状数组的次数过多也会超时！

AC精简版：

View Code

  1 #include <cstdio>
  2 #include <cassert>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 
  9 #define lson l, m, rt << 1
 10 #define rson m + 1, r, rt << 1 | 1
 11 
 12 const int maxn = 1000005;
 13 int mp[501][501], out[500][500];
 14 
 15 void scan(int &a){
 16     char ch;
 17 
 18     while ((ch = getchar()) < '0' || ch > '9');
 19     a = ch - '0';
 20     while ((ch = getchar()) >= '0' && ch <= '9')
 21         a = a * 10 + ch - '0';
 22 }
 23 int C[maxn], Max;
 24 
 25 void add(int p){
 26     p++;
 27     while (p <= Max){
 28         C[p]++;
 29         p += p & (-p);
 30     }
 31 }
 32 
 33 void sub(int p){
 34     p++;
 35     while (p <= Max){
 36         C[p]--;
 37         p += p & (-p);
 38     }
 39 }
 40 
 41 int find(int k){
 42     int pos = 0, cnt = 0;
 43 
 44     k++;
 45     for(int i = 20; i >= 0; i--){
 46         pos += (1 << i);
 47         if (pos >= Max || cnt + C[pos] >= k) pos -= (1 << i);
 48         else cnt += C[pos];
 49     }
 50     return pos;
 51 }
 52 
 53 void deal(int n, int r){
 54     int len = r << 1 | 1;
 55     int end = n - len + 1;
 56     int pos = (len * len + 1) >> 1;
 57 
 58     Max = 0;
 59     for (int i = 0; i < n; i++){
 60         for (int j = 0; j < n; j++){
 61             scan(mp[i][j]);
 62             Max = max(Max, mp[i][j]);
 63         }
 64     }
 65     Max++;
 66     fill(C, C + Max + 1, 0);
 67 
 68     for (int i = 0, endi = len - 1; i < endi; i++){
 69         for (int j = 0; j < len; j++){
 70             add(mp[i][j]);
 71         }
 72     }
 73     for (int i = 0; i < end; i++){
 74         if (i & 1){
 75             for (int j = 0; j < len; j++){
 76                 add(mp[i + len - 1][j + end - 1]);
 77             }
 78             out[i][end - 1] = find(pos - 1);
 79             for (int j = end - 2; j >= 0; j--){
 80                 for (int k = 0; k < len; k++){
 81                     sub(mp[i + k][j + len]);
 82                     add(mp[i + k][j]);
 83                 }
 84                 out[i][j] = find(pos - 1);
 85             }
 86             for (int j = 0; j < len; j++){
 87                 sub(mp[i][j]);
 88             }
 89         }
 90         else{
 91             for (int j = 0; j < len; j++){
 92                 add(mp[i + len - 1][j]);
 93             }
 94             out[i][0] = find(pos - 1);
 95             for (int j = 1; j < end; j++){
 96                 for (int k = 0; k < len; k++){
 97                     sub(mp[i + k][j - 1]);
 98                     add(mp[i + k][j + len - 1]);
 99                 }
100                 out[i][j] = find(pos - 1);
101             }
102             for (int j = 0; j < len; j++){
103                 sub(mp[i][end + j - 1]);
104             }
105         }
106     }
107     for (int i = 0; i < end; i++){
108         for (int j = 0; j < end; j++){
109             printf("%d ", out[i][j]);
110         }
111         puts("");
112     }
113 }
114 
115 int main(){
116     int n, m;
117 
118     while (~scanf("%d%d", &n, &m) && (n || m)){
119         deal(n, m);
120     }
121 
122     return 0;
123 }

原始版本（把线段树和树状数组都写进去了。。。。囧）：

View Code

  1 #include <cstdio>
  2 #include <cassert>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 
  9 #define lson l, m, rt << 1
 10 #define rson m + 1, r, rt << 1 | 1
 11 
 12 int mp[501][501], out[500][500];
 13 
 14 /*
 15 const int maxn = 1000005;
 16 int sum[maxn << 2];
 17 
 18 void up(int rt){
 19     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
 20 }
 21 
 22 void update(int pos, int val, int l, int r, int rt){
 23     if (l == r){
 24         assert(l == pos);
 25         sum[rt] += val;
 26         return ;
 27     }
 28     if (!sum[rt] && (sum[rt << 1] || sum[rt << 1 | 1])) sum[rt << 1] = sum[rt << 1 | 1] = 0;
 29 
 30     int m = (l + r) >> 1;
 31 
 32     if (pos <= m) update(pos, val, lson);
 33     else update(pos, val, rson);
 34     up(rt);
 35 }
 36 
 37 int query(int k, int l, int r, int rt){
 38     if (l == r){
 39         return l;
 40     }
 41     int m = (l + r) >> 1;
 42 
 43     if (sum[rt << 1] >= k) return query(k, lson);
 44     else return query(k - sum[rt << 1], rson);
 45 }
 46 */
 47 
 48 void scan(int &a){
 49     char ch;
 50 
 51     while ((ch = getchar()) < '0' || ch > '9');
 52     a = ch - '0';
 53     while ((ch = getchar()) >= '0' && ch <= '9')
 54         a = a * 10 + ch - '0';
 55 }
 56 
 57 
 58 /*
 59 
 60 const int maxn = 1 << 20;
 61 int sum[maxn << 1], Max;
 62 
 63 void add(int n){
 64     int i = Max + n;
 65 
 66     for (++sum[i]; i > 1; i >>= 1){
 67         if (~i & 1){
 68             sum[i >> 1]++;
 69         }
 70     }
 71 }
 72 
 73 void sub(int n){
 74     if (!sum[n += Max]) return ;
 75     for (--sum[n]; n > 1; n >>= 1){
 76         if (~n & 1){
 77             --sum[n >> 1];
 78         }
 79     }
 80 }
 81 
 82 int find(int n){
 83     int i = 1;
 84 
 85     while (i < Max){
 86         if (n < sum[i]) i <<= 1;
 87         else n -= sum[i], i = i << 1 | 1;
 88     }
 89 
 90     return i - Max;
 91 }
 92 */
 93 
 94 const int maxn = 1000005;
 95 int C[maxn], Max;
 96 
 97 void add(int p){
 98     p++;
 99     while (p <= Max){
100         C[p]++;
101         p += p & (-p);
102     }
103 }
104 
105 void sub(int p){
106     p++;
107     while (p <= Max){
108         C[p]--;
109         p += p & (-p);
110     }
111 }
112 
113 int find(int k){
114     int pos = 0, cnt = 0;
115 
116     k++;
117     for(int i = 20; i >= 0; i--){
118         pos += (1 << i);
119         if (pos >= Max || cnt + C[pos] >= k) pos -= (1 << i);
120         else cnt += C[pos];
121     }
122     return pos;
123 }
124 
125 
126 void deal(int n, int r){
127     int len = r << 1 | 1;
128     int end = n - len + 1;
129     int pos = (len * len + 1) >> 1;
130     //int maxSize = -1, minSize = maxn;
131 
132     Max = 0;
133     //printf("len %d end %d pos %d\n", len, end, pos);
134     for (int i = 0; i < n; i++){
135         for (int j = 0; j < n; j++){
136             scan(mp[i][j]);
137             //scanf("%d", &mp[i][j]);
138             Max = max(Max, mp[i][j]);
139             //maxSize = max(mp[i][j], maxSize);
140             //minSize = min(mp[i][j], minSize);
141         }
142     }
143     Max++;
144     fill(C, C + Max + 1, 0);
145     /*
146     if (Max){
147         Max = 1 << (int)(log((double)Max) / log(2.0) + 1);
148     }
149     */
150 
151     //sum[1] = 0;
152     for (int i = 0, endi = len - 1; i < endi; i++){
153         for (int j = 0; j < len; j++){
154             //printf("push %d %d\n", i, j);
155             add(mp[i][j]);
156             //update(mp[i][j], 1, minSize, maxSize, 1);
157         }
158     }
159     for (int i = 0; i < end; i++){
160         if (i & 1){
161             for (int j = 0; j < len; j++){
162                 //printf("push %d %d\n", i + len - 1, j + end - 1);
163                 add(mp[i + len - 1][j + end - 1]);
164                 //update(mp[i + len - 1][j + end - 1], 1, minSize, maxSize, 1);
165             }
166             out[i][end - 1] = find(pos - 1);
167             //out[i][end - 1] = query(pos, minSize, maxSize, 1);
168             for (int j = end - 2; j >= 0; j--){
169                 for (int k = 0; k < len; k++){
170                     //printf("pop %d %d\n", i + k, j + len);
171                     sub(mp[i + k][j + len]);
172                     //update(mp[i + k][j + len], -1, minSize, maxSize, 1);
173                     //printf("push %d %d\n", i + k, j);
174                     add(mp[i + k][j]);
175                     //update(mp[i + k][j], 1, minSize, maxSize, 1);
176                 }
177                 out[i][j] = find(pos - 1);
178                 //out[i][j] = query(pos, minSize, maxSize, 1);
179             }
180             for (int j = 0; j < len; j++){
181                 //printf("pop %d %d\n", i, j);
182                 sub(mp[i][j]);
183                 //update(mp[i][j], -1, minSize, maxSize, 1);
184             }
185         }
186         else{
187             for (int j = 0; j < len; j++){
188                 //printf("push %d %d\n", i + len - 1, j);
189                 add(mp[i + len - 1][j]);
190                 //update(mp[i + len - 1][j], 1, minSize, maxSize, 1);
191             }
192             out[i][0] = find(pos - 1);
193             //out[i][0] = query(pos, minSize, maxSize, 1);
194             for (int j = 1; j < end; j++){
195                 for (int k = 0; k < len; k++){
196                     //printf("pop %d %d\n", i + k, j - 1);
197                     sub(mp[i + k][j - 1]);
198                     //update(mp[i + k][j - 1], -1, minSize, maxSize, 1);
199                     //printf("push %d %d\n", i + k, j + len - 1);
200                     add(mp[i + k][j + len - 1]);
201                     //update(mp[i + k][j + len - 1], 1, minSize, maxSize, 1);
202                 }
203                 out[i][j] = find(pos - 1);
204                 //out[i][j] = query(pos, minSize, maxSize, 1);
205             }
206             for (int j = 0; j < len; j++){
207                 //printf("pop %d %d\n", i, end + j - 1);
208                 sub(mp[i][end + j - 1]);
209                 //update(mp[i][end + j - 1], -1, minSize, maxSize, 1);
210             }
211         }
212     }
213     for (int i = 0; i < end; i++){
214         for (int j = 0; j < end; j++){
215             //if (j) putchar(' ');
216             printf("%d ", out[i][j]);
217         }
218         puts("");
219     }
220 }
221 
222 int main(){
223     int n, m;
224 
225     while (~scanf("%d%d", &n, &m) && (n || m)){
226         deal(n, m);
227     }
228 
229     return 0;
230 }

——written by Lyon