1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

inline int next2pow(int n) {
    n = 2 * n - 1;
    int k = 0;
    while (n /= 2) ++k;
    return 1 << k;
}
inline int left(int p) {
    return 2 * p;
}

inline int right(int p) {
    return 2 * p + 1;
}

inline int parent(int p) {
    return p / 2;
}

template <typename M>
concept TreeOp = requires (M::TYPE a, M::TYPE b) {
    { M::op_get(a, b) } -> std::same_as<typename M::TYPE>;
    { M::op_set(a, b) } -> std::same_as<typename M::TYPE>;
    { M::op_set_get(a, b, int(), int()) } -> std::same_as<typename M::TYPE>;
    { M::ZERO_GET } -> convertible_to<typename M::TYPE>;
    { M::ZERO_SET } -> convertible_to<typename M::TYPE>;
};

template<TreeOp M>
struct SegmentSegmentTree {
    using T = typename M::TYPE;
    static constexpr auto op_get = M::op_get;
    static constexpr auto op_set = M::op_set;
    static constexpr auto op_set_get = M::op_set_get;
    static constexpr auto ZERO_GET = M::ZERO_GET;
    static constexpr auto ZERO_SET = M::ZERO_SET;

    void init(int _size) {
        if (_size & (_size - 1)) cerr << "size of segment tree MUST be a power of 2 " << _size << " provided" << endl;
        size = _size;
        TREE_SET.resize(2 * size, ZERO_SET);
        TREE_GET.resize(2 * size, ZERO_GET);
    }

    vector<T> TREE_GET, TREE_SET;
    int size;

    T get(int a) {
        return get(a, a + 1);
    }

    T get(int a, int b) {
        return get(a, b, 1, 0, size);
    }

    T get(int a, int b, int u, int lo, int hi) {
        if (a == lo && b == hi) {
            return TREE_GET[u];
        }
        if (b <= a) return ZERO_GET;
        int mid = (lo + hi) / 2;
        T L = get(a, min(b, mid), left(u), lo, mid);
        T R = get(max(a, mid), b, right(u), mid, hi);
        return op_set_get(op_get(L, R), TREE_SET[u], a, b);
    }

    void set(int a, T v) {
        set(a, a + 1, v);
    }

    void set(int a, int b, T v) {
        set(a, b, 1, 0, size, v);
    }

    void set(int a, int b, int u, int lo, int hi, T v) {
        if (a == lo && b == hi) {
            TREE_SET[u] = op_set(TREE_SET[u], v);
            TREE_GET[u] = op_set_get(TREE_GET[u], v, lo, hi);
            return;
        }
        if (b <= a) return;
        int mid = (lo + hi) / 2;
        if (TREE_SET[u] != ZERO_SET) {
            // push the value down the tree to ensure it works with non-commutative operations
            // this is effectively no-op
            TREE_SET[left(u)] = op_set(TREE_SET[left(u)], TREE_SET[u]);
            TREE_SET[right(u)] = op_set(TREE_SET[right(u)], TREE_SET[u]);
            TREE_GET[left(u)] = op_set_get(TREE_GET[left(u)], TREE_SET[u], lo, mid);
            TREE_GET[right(u)] = op_set_get(TREE_GET[right(u)], TREE_SET[u], mid, hi);
            TREE_SET[u] = ZERO_SET;
        }
        int la = a, lb = min(b, mid), ra = max(a, mid), rb = b;
        set(la, lb, left(u), lo, mid, v);
        set(ra, rb, right(u), mid, hi, v);
        TREE_GET[u] = op_get(TREE_GET[left(u)], TREE_GET[right(u)]);
    }
};

template<typename I>
struct SUM {
    using TYPE = I;
    static constexpr TYPE ZERO = TYPE(0);
    static inline auto op = plus<TYPE>();
};

template<typename I>
struct SET {
    using TYPE = I;
    static constexpr I ZERO = numeric_limits<I>::min();

    static TYPE op(TYPE l, TYPE r) {
        return r == ZERO ? l : r;
    }
};

template<typename I>
struct SET_SUM {
    using TYPE = I;
    static constexpr TYPE ZERO_SET = SET<TYPE>::ZERO;
    static constexpr TYPE ZERO_GET = SUM<TYPE>::ZERO;
    static constexpr auto op_set = SET<TYPE>::op;
    static constexpr auto op_get = SUM<TYPE>::op;

    static auto op_set_get(TYPE l, TYPE r, int a, int b) {
        return l == ZERO_GET ? r : r == ZERO_SET ? l : l + r * (b - a);
    }
};

string in;
int res[300'000];

SegmentSegmentTree<SET_SUM<int>> l2r, r2l;

int main() {
    int n;
    cin >> n;
    in.resize(n + 1);
    l2r.init(next2pow(n));
    r2l.init(next2pow(n));
    for (int i = 0; i < n; ++i) cin >> in[i];
    for (int i = 0; i < n; ++i) {
        (in[i] == 'P' ? l2r : r2l).set(i, 1);
    }
    for (int i = 0; i < n; ++i) {
        int leftBounces = 2 * l2r.get(0, i) + (in[i] == 'P');
        int rightBounces = 2 * r2l.get(i + 1, n) + (in[i] == 'L');
        cout << min(leftBounces, rightBounces) << ' ';
    }
    cout << '\n';
}