Здравствуйте, Chorkov, Вы писали:
private class Solver {
private int next[][] = {
new int[] { 0, 1, 0 }, // I
new int[] { 0, 1, 2 }, // /
new int[] { 2, 2, 3 }, // /*
new int[] { 2, 4, 3 }, // *
new int[] { 0, 1, 0 }, // */
};
private int mark[][] = {
new int[] { 0, 0, 0 }, // I
new int[] { 0, 0, 1 }, // /
new int[] { 1, 1, 1 }, // /*
new int[] { 1, 1, 1 }, // *
new int[] { 1, 1, 1 }, // */
};
private int state[][][];
private int chars[];
public Solver(String s) {
chars = new int[s.length() + 2];
for (int i = 0; i < s.length(); ++i) {
chars[i + 1] = "./*".indexOf(s.charAt(i));
}
state = new int[4 * chars.length][][];
for (int i = 0; i < state.length; ++i) {
state[i] = new int[5][];
for (int j = 0; j < 5; ++j) {
state[i][j] = new int[2];
}
}
build(0, 0, chars.length - 1);
}
public void set(int pos, char c) {
set(0, 0, chars.length - 1, pos, c);
}
private void set(int node, int lo, int hi, int pos, char c) {
if (lo == hi) {
chars[pos] = "./*".indexOf(c);
} else {
int xx = (lo + hi) / 2;
if (pos <= xx) {
set(2 * node + 1, lo, xx, pos, c);
} else {
set(2 * node + 2, xx + 1, hi, pos, c);
}
update(node, xx);
}
}
public boolean get(int pos) {
return mark[get(0, 0, 0, chars.length - 1, pos)][chars[pos + 1]] > 0;
}
private int get(int node, int init, int lo, int hi, int pos) {
if (lo == pos) {
return state[node][init][0];
}
if (hi == pos) {
return state[node][init][1];
} else {
int xx = (lo + hi) / 2;
if (pos <= xx) {
return get(2 * node + 1, init, lo, xx, pos);
} else {
int l[] = state[2 * node + 1][init];
int t = next[l[1]][chars[xx + 1]];
int r[] = state[2 * node + 2][t];
return get(2 * node + 2, r[0], xx + 1, hi, pos);
}
}
}
private void build(int node, int lo, int hi) {
if (lo == hi) {
for (int s = 0; s < 5; ++s) {
state[node][s][0] = s;
state[node][s][1] = s;
}
} else {
int xx = (lo + hi) / 2;
build(2 * node + 1, lo, xx);
build(2 * node + 2, xx + 1, hi);
update(node, xx);
}
}
private void update(int node, int xx) {
for (int s = 0, t; s < 5; ++s) {
int[] l = state[2 * node + 1][s];
t = next[l[1]][chars[xx + 1]];
int[] r = state[2 * node + 2][t];
state[node][s][0] = s;
state[node][s][1] = r[1];
}
}
}