Re[2]: Комментарии
От: Serge  
Дата: 21.09.20 09:55
Оценка:
Здравствуйте, 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];
            }
        }
    }
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.