[ZOJ3335 Filtering]矩阵维护类型的题目

【题目大意】
给出一个a[i][j]。
然后ans[i][j]=以(i , j)为中心的一个m*n的矩形内所有数字的中位数。
如果m*n超出了边框。那么ans[i][j]=a[i][j]。
0<=a[i][j]<256。
【算法分析】
首先，注意到键值的范围为[0，255]。
我们容易想到弄一个桶来维护。或许桶里还可以搞个线段树什么的。
然后显然ans[i][j]和ans[i][j-1]所包含的数里，只有两列不同。于是我们可以在O(p*q*n)里维护一个所包含数字的桶。
有这个桶呢，暴力找中位数，那么复杂度是O(p*q*(n+256))。
但是依然MS可能超时。
于是我们可以加入一个优化：
ans[i][j]和ans[i][j-1]一般相差不是很远。
那么我们就在ans[i][j]的基础上，先前滑动和向后滑动，一般而言就可以很快出解了。
【时间复杂度】O(p*q*(n+256)) 一般达不到。
【CODE】
#include #include #include const int N=505;
int a[N][N],b[N][N],T[256];
int m,n,p,q,L;

void input(){
int i,j;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
scanf("%d%d",&p,&q);
L=p*q/2+1;
}

int Cal(int x,int y){
int i,j;
for (i=x-p;i<=x+p;i++)
for (j=y-q;j<=y+q;j++)
T[a[i][j]]++;
j=0;
for (i=0;i<256;i++){
j+=T[i];
if (j>=L) return i;
}
}

void solve(){
p/=2; q/=2;
int i,j,k,pre,next;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
b[i][j]=-10000;
bool first;
for (i=1+p;i+p<=m;i++){
memset(T,0,sizeof(T));
first=true;
for (j=1+q;j+q<=n;j++)
if (first){
first=false;
b[i][j]=Cal(i,j);
pre=0; next=0;
for (k=0;k for (k=b[i][j]+1;k<256;k++) next+=T[k];
}else{
int &t=b[i][j];
t=b[i][j-1];
for (k=i-p;k<=i+p;k++){
T[a[k][j-q-1]]–;
if (a[k][j-q-1] if (a[k][j-q-1]>t) next–;
T[a[k][j+q]]++;
if (a[k][j+q] if (a[k][j+q]>t) next++;
}
while (pre>=L){
next+=T[t];
t–;
pre-=T[t];
}
while (next>=L){
pre+=T[t];
t++;
next-=T[t];
}
}
}
}

void output(){
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (b[i][j]<0) b[i][j]=a[i][j];
printf("%d",b[i][j]);
if (j==n) putchar(‘n’);
else putchar(‘ ‘);
}
putchar(‘n’);
}

int main(){
while (scanf("%d%d",&m,&n)!=EOF){
input();
solve();
output();
}
}