poj 3467 Cross Counting
題意:1つのM*Nのマトリックスを与えて、マトリックスの中で各要素はすべて1種の色(1≦N、M、C≦100)、10000本のクエリがあって、ある要素の色を変更してあるいはある色のcorssが何個あるかをクエリします.
We say there exists a cross of size k centered at the cell (x,y)iff all cells lying in the x-th row or the y-th column and within a distance of k from (x,y) share the same color. if two crosses have the same center but different sizes we consider they are distinct
解法:各色は互いに相関しないため、色に分けて考慮して、行列を100個の01行列に変えることができて、このように初期の時に各色がどれだけのcrossがあるかを統計することができます.
ある要素(i,j)が変更されると、i行またはj列を中心としたcrossにのみ影響するため、各中心のcrossの変化を1つずつ考慮するだけで、クエリごとに200の要素のcross数を変更するだけである.どのようにして各要素を中心としたcrossの数を迅速に統計しますか?定義によれば、01行列中の各要素が上下左右4方向に連続して1つの個数を記録するだけで、最小値をとり、1つの要素が1から0または0から1になると、同業者要素の左右方向に連続して1つの個数と同列要素の上下方向に連続して1つの個数を変更し、cross数の増加減少数を記録するだけでよい.
線分樹もメンテナンスできるようですが、まさかメンテナンスするとは思わなかったので、とりあえずこれより複雑度が高いと思います(囧).
We say there exists a cross of size k centered at the cell (x,y)iff all cells lying in the x-th row or the y-th column and within a distance of k from (x,y) share the same color. if two crosses have the same center but different sizes we consider they are distinct
解法:各色は互いに相関しないため、色に分けて考慮して、行列を100個の01行列に変えることができて、このように初期の時に各色がどれだけのcrossがあるかを統計することができます.
ある要素(i,j)が変更されると、i行またはj列を中心としたcrossにのみ影響するため、各中心のcrossの変化を1つずつ考慮するだけで、クエリごとに200の要素のcross数を変更するだけである.どのようにして各要素を中心としたcrossの数を迅速に統計しますか?定義によれば、01行列中の各要素が上下左右4方向に連続して1つの個数を記録するだけで、最小値をとり、1つの要素が1から0または0から1になると、同業者要素の左右方向に連続して1つの個数と同列要素の上下方向に連続して1つの個数を変更し、cross数の増加減少数を記録するだけでよい.
線分樹もメンテナンスできるようですが、まさかメンテナンスするとは思わなかったので、とりあえずこれより複雑度が高いと思います(囧).
import java.util.Scanner;
public class CountCross3467 {
int maxn = 110;
class Matrix {
int map[][] = new int[maxn][maxn];
int left[][] = new int[maxn][maxn], right[][] = new int[maxn][maxn],
up[][] = new int[maxn][maxn], down[][] = new int[maxn][maxn];
int sum, n, m;
Matrix(int n,int m){
this.n=n;
this.m=m;
}
void init(int i, int j) {
map[i][j] = 1;
left[i][j] = right[i][j] = j;
up[i][j] = down[i][j] = i;
}
void count() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (map[i][j] == 1 && map[i][j - 1] == 1)
left[i][j] = left[i][j - 1];
for (int j = m; j > 0; j--)
if (map[i][j] == 1 && map[i][j + 1] == 1)
right[i][j] = right[i][j + 1];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if (map[j][i] == 1 && map[j - 1][i] == 1)
up[j][i] = up[j - 1][i];
for (int j = n; j > 0; j--)
if (map[j][i] == 1 && map[j + 1][i] == 1)
down[j][i] = down[j + 1][i];
}
sum = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
sum += cross(i, j);
}
int cross(int i, int j) {
if(map[i][j]==0)
return 0;
int a = Math.min(i - up[i][j], down[i][j] - i);
int b = Math.min(j-left[i][j], right[i][j] - j);
return Math.min(a, b);
}
void update1(int a, int b) {
// 0-->1
map[a][b] = 1;
left[a][b] = b;
if (map[a][b - 1] == 1)
left[a][b] = left[a][b - 1];
right[a][b] = b;
if (map[a][b + 1] == 1)
right[a][b] = right[a][b + 1];
up[a][b] = a;
if (map[a - 1][b] == 1)
up[a][b] = up[a - 1][b];
down[a][b] = a;
if (map[a + 1][b] == 1)
down[a][b] = down[a + 1][b];
sum+=cross(a,b);
for (int i = 1; i < b; i++) {
if (right[a][i] != b - 1)
continue;
int temp = cross(a, i);
right[a][i] = right[a][b];
sum += cross(a, i) - temp;
}
for (int i = b + 1; i <= m; i++) {
if (left[a][i] != b + 1)
continue;
int temp = cross(a, i);
left[a][i] = left[a][b];
sum += cross(a, i) - temp;
}
for(int i=1;i<a;i++){
if(down[i][b]!=a-1)
continue;
int temp=cross(i,b);
down[i][b]=down[a][b];
sum += cross(i,b) - temp;
}
for(int i=a+1;i<=n;i++){
if(up[i][b]!=a+1)
continue;
int temp=cross(i,b);
up[i][b]=up[a][b];
sum += cross(i,b) - temp;
}
}
void update0(int a, int b) {
// 1-->0
sum-=cross(a,b);
map[a][b] = 0;
left[a][b] =right[a][b]=up[a][b]=down[a][b]=0;
for (int i = 1; i < b; i++) {
if (map[a][i]==0||right[a][i]<b)
continue;
int temp = cross(a, i);
right[a][i] =b-1;
sum -= temp-cross(a, i);
}
for (int i = b + 1; i <= m; i++) {
if (map[a][i]==0||left[a][i]>b)
continue;
int temp = cross(a, i);
left[a][i] = b+1;
sum -= temp-cross(a, i);
}
for(int i=1;i<a;i++){
if(map[i][b]==0||down[i][b]<a)
continue;
int temp=cross(i,b);
down[i][b]=a-1;
sum-= temp-cross(i,b);
}
for(int i=a+1;i<=n;i++){
if(map[i][b]==0||up[i][b]>a)
continue;
int temp=cross(i,b);
up[i][b]=a+1;
sum -= temp-cross(i,b);
}
}
}
Scanner scan=new Scanner(System.in);
void run(){
int n=scan.nextInt();
int m=scan.nextInt();
int c=scan.nextInt();
int q=scan.nextInt();
int map[][]=new int[n+1][m+1];
Matrix mat[]=new Matrix[c+1];
for(int i=1;i<=c;i++)
mat[i]=new Matrix(n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
map[i][j]=scan.nextInt();
mat[map[i][j]].init(i, j);
}
for(int i=1;i<=c;i++)
mat[i].count();
while(q-->0){
String s=scan.next();
if(s.charAt(0)=='Q'){
int v=scan.nextInt();
System.out.println(mat[v].sum);
}
else{
int i=scan.nextInt();
int j=scan.nextInt();
int v=scan.nextInt();
int t=map[i][j];
map[i][j]=v;
mat[t].update0(i, j);
mat[v].update1(i, j);
}
}
}
public static void main(String[] args) {
new CountCross3467().run();
}
}