提出 #70626512

---

ソースコード 拡げる

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;



using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)

const ll dy[] = {-1, 0, 0, 1};
const ll dx[] = {0, -1, 1, 0};

template <class T, class T1, class T2> bool isrange(T target, T1 low, T2 high) { return low <= target && target < high; }
template <class T, class U> T min(const T &t, const U &u) { return t < u ? t : u; }
template <class T, class U> T max(const T &t, const U &u) { return t < u ? u : t; }
template <class T, class U> bool chmin(T &t, const U &u) { if (t > u) { t = u; return true; } return false; }
template <class T, class U> bool chmax(T &t, const U &u) { if (t < u) { t = u; return true; } return false; }

// #include "titan_cpplib/others/print.cpp"

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;

// print

// -------------------------
// pair<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const pair<K, V>& p);
// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3> ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t);
// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4> ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t);
// vector<T>
template<typename T> ostream& operator<<(ostream& os, const vector<T>& a);
// vector<vector<T>>
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& a);
// array<T, 2>
template<typename T> ostream& operator<<(ostream& os, const array<T, 2>& a);
// set<T>
template<typename T> ostream& operator<<(ostream& os, const set<T>& s);
// multiset<T>
template<typename T> ostream& operator<<(ostream& os, const multiset<T>& s);
// unordered_set<T>
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& a);
// map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& mp);
// unordered_map<K, V>
template<typename K, typename V> ostream& operator<<(ostream& os, const unordered_map<K, V>& mp);
// -------------------------

// color
static const string PRINT_RED = "\033[91m"; // 赤字
static const string PRINT_GREEN = "\033[92m"; // 緑字
static const string PRINT_BLUE = "\033[94m";  // 青字
static const string PRINT_NONE = "\033[m"; // 色を元に戻す
static const string PRINT_BOLD = "\u001b[1m"; // 太字

string to_red(const string &s)   { return PRINT_RED + s + PRINT_NONE; }
string to_green(const string &s) { return PRINT_GREEN + s + PRINT_NONE; }
string to_blue(const string &s)  { return PRINT_BLUE + s + PRINT_NONE; }
string to_bold(const string &s)  { return PRINT_BOLD + s + PRINT_NONE; }

string spacefill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += " ";
    t += s;
    return t;
}

string zfill(const string s, const int f) {
    int n = s.size();
    string t;
    for (int i = 0; i < f-n; ++i) t += "0";
    t += s;
    return t;
}

string bin(long long s) {
    string t;
    while (s) {
        t += (s & 1) ? '1' : '0';
        s >>= 1;
    }
    reverse(t.begin(), t.end());
    return t;
}

void DEBUG_LINE() { cerr << "[Line] : " << __LINE__ << std::endl; }

// pair<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const pair<K, V>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

// tuple<T1, T2, T3>
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
    return os;
}

// tuple<T1, T2, T3, T4>
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
    os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", " << get<3>(t) << ")";
    return os;
}

// array<T, 2>
template<typename T>
ostream& operator<<(ostream& os, const array<T, 2>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<T>
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
    os << "[";
    for (int i = 0; i < (int)a.size(); ++i) {
        if (i > 0) os << ", ";
        os << a[i];
    }
    os << "]";
    return os;
}

// vector<vector<T>>
template<typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& a) {
    os << "[\n";
    int h = (int)a.size();
    for (int i = 0; i < h; ++i) {
        os << "  " << a[i] << '\n';
    }
    os << "]";
    return os;
}

// set<T>
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// multiset<T>
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{";
    auto it = s.begin();
    while (it != s.end()) {
        os << *it;
        ++it;
        if (it != s.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_set<T>
template<typename T>
ostream& operator<<(ostream& os, const unordered_set<T>& a) {
    set<T> s(a.begin(), a.end());
    os << s;
    return os;
}

// map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& mp) {
    os << "{";
    auto it = mp.begin();
    while (it != mp.end()) {
        os << it->first << ": " << it->second;
        ++it;
        if (it != mp.end()) {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

// unordered_map<K, V>
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_map<K, V>& mp) {
    map<K, V> m(mp.begin(), mp.end());
    os << m;
    return os;
}


#include <vector>
#include <queue>
using namespace std;

// dijkstra
namespace titan23 {
/**
 * @brief dijkstra
 *
 * @tparam T weight type
 * @param G weighted graph
 * @param start start
 * @param INF inf
 * @return vector<T> dist from start
 */
template<typename T>
vector<T> dijkstra(
        const vector<vector<pair<int, T>>> &G,
        const int start,
        const T INF) {
    int n = G.size();
    vector<T> dist(n, INF);
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> hq;
    hq.emplace(0, start);
    dist[start] = 0;
    while (!hq.empty()) {
        auto [d, v] = hq.top();
        hq.pop();
        if (dist[v] < d) continue;
        for (const auto &[x, c] : G[v]) {
            if (dist[x] > d + c) {
                dist[x] = d + c;
                hq.emplace(dist[x], x);
            }
        }
    }
    return dist;
}
}  // namespace titan23


struct ST{
    long long value;
    int size;
};
using FT = long long;

ST op(ST a, ST b){ return {a.value+b.value, a.size+b.size}; }
ST e(){ return {0, 0}; }
ST mapping(FT f, ST x){ return {x.value + f*x.size, x.size}; }
FT composition(FT f, FT g){ return f+g; }
FT id(){ return 0; }
#include <iostream>
#include <vector>
// #include "titan_cpplib/data_structures/fenwick_tree.cpp"
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// FenwickTree
namespace titan23 {

template<typename T>
struct FenwickTree {
    int _n, _s;
    vector<T> _tree;

    FenwickTree() {}

    FenwickTree(const int n) {
        _n = n;
        _s = 1 << (32 - __builtin_clz(_n));
        _tree.resize(n+1, 0);
    }

    FenwickTree(const vector<T> &a)
                : _n(a.size()),
                _s(1 << (32 - __builtin_clz(_n-1))),
                _tree(_n+1, 0) {
        for (int i = 1; i <= _n; ++i) _tree[i] = a[i-1];
        for (int i = 1; i < _n; ++i) {
            if (i + (i & (-i)) <= _n) {
                _tree[i + (i & (-i))] += _tree[i];
            }
        }
    }

    T pref(int r) const {
        T res = 0;
        while (r > 0) {
            res += _tree[r];
            r -= r & (-r);
        }
        return res;
    }

    T suff(int l) const {
        return pref(_n) - pref(l);
    }

    T sum(const int l, const int r) const {
        return pref(r) - pref(l);
    }

    void add(int k, const T x) {
        ++k;
        while (k <= _n) {
            _tree[k] += x;
            k += k & (-k);
        }
    }

    T get(const int k) const {
        return pref(k+1) - pref(k);
    }

    void set(const int k, const T x) {
        T pre = get(k);
        add(k, x-pre);
    }

    int bisect_left(T w) const {
        int i = 0, s = _s;
        while (s) {
            if (i+s <= _n && _tree[i+s] < w) {
                w -= _tree[i+s];
                i += s;
            }
            s >>= 1;
        }
        return (w ? i : -1);
    }

    int bisect_right(T w) const {
        int i = 0, s = _s;
        while (s) {
            if (i+s <= _n && _tree[i+s] <= w) {
                w -= _tree[i+s];
                i += s;
            }
            s >>= 1;
        }
        return i;
    }

    vector<T> tovector() const {
        vector<T> sub(_n+1), res(_n);
        for (int i = 0; i <= _n; ++i) sub[i] = pref(i);
        for (int i = 0; i < _n; ++i) res[i] = sub[i+1] - sub[i];
        return res;
    }

    void clear() {
        fill(_tree.begin(), _tree.end(), 0);
    }

    void print() const {
        vector<T> fw = tovector();
        cout << "[";
        for (int i = 0; i < _n-1; ++i) cout << fw[i] << ", ";
        cout << fw[_n-1] << "]\n";
    }
};
}  // namespace titan23

using namespace std;

namespace titan23 {

/// 定数倍の軽い range add point get
template<typename T>
class FenwickTreeRAQ {
private:
    int n;
    titan23::FenwickTree<T> fw;

public:
    FenwickTreeRAQ() : n(0), fw(0) {}
    FenwickTreeRAQ(int n) : n(n), fw(n) {}
    FenwickTreeRAQ(vector<T> a) : n(n), fw(a) {}

    /// all 0
    void clear() {
        fw.clear();
    }

    /// add x to a[l, r)
    void add_range(int l, int r, T x) {
        fw.add(l, x);
        if (r < n) fw.add(r, -x);
    }

    /// a[k] += x;
    void add(int k, T x) {
        add_range(k, k+1, x);
    }

    /// a[k]
    T get(int k) const {
        return fw.pref(k+1);
    }

    /// a[k] <- x
    void set(int k, T x) {
        T pre = get(k);
        add(k, x-pre);
    }

    vector<T> tovector() const {
        vector<T> res(n);
        for (int i = 0; i < n; ++i) {
            res[i] = get(i);
        }
    }

    friend ostream& operator<<(ostream& os, const titan23::FenwickTreeRAQ<T> &fw) {
        os << fw.tovector();
        return os;
    }
};
} // namespace titan23

void solve() {
    int n; cin >> n;
    string S; cin >> S;
    vector<vector<pair<int, int>>> G(n+1);
    int START = n;
    rep(i, n-1) {
        if (S[i] == 'L') {
            G[i+1].push_back({i, 1});
        } else {
            G[i].push_back({i+1, 1});
        }
    }
    vector<int> deg(n, 0);
    rep(i, n) {
        for (auto [x, c] : G[i]) {
            deg[x]++;
        }
    }
    rep(i, n) if (deg[i] == 0) {
        G[START].push_back({i, 0});
    }
    // vector<int> dist = titan23::dijkstra<int>(G, START, 1e9);


    vector<int> dp1(n+1, 0);
    auto dfs = [&] (auto &&dfs, int v) -> void {
        dp1[v] = 1;
        for (auto [x, c] : G[v]) {
            dfs(dfs, x);
            dp1[v] += dp1[x];
        }
    };
    dfs(dfs, START);

    vector<vector<pair<int, int>>> F(n+1);
    START = n;
    rep(i, n-1) {
        if (S[i] == 'R') {
            F[i+1].push_back({i, 1});
        } else {
            F[i].push_back({i+1, 1});
        }
    }
    vector<int> deg2(n, 0);
    rep(i, n) {
        for (auto [x, c] : F[i]) {
            deg2[x]++;
        }
    }
    rep(i, n) if (deg2[i] == 0) {
        F[START].push_back({i, 0});
    }
    vector<int> dp2(n+1, 0);
    auto efs = [&] (auto &&efs, int v) -> void {
        dp2[v] = 1;
        for (auto [x, c] : F[v]) {
            efs(efs, x);
            dp2[v] += dp2[x];
        }
    };
    efs(efs, START);

    // cerr << dp1 << endl;
    // cerr << dp2 << endl;
    // atcoder::lazy_segtree<ST, op, e, FT, mapping, composition, id> seg(n);
    titan23::FenwickTreeRAQ<int> fw(n+1);
    vector<int> U(n);
    rep(i, n) {
        int r = n-(dp1[i]-1);
        int l = dp2[i]-1;
        if (r <= l) continue;
        // for (int j = l; j < r; ++j) U[j]++;
        fw.add_range(l, r, 1);
    }
    // cerr << U << endl;
    rep(i, n) {
        cout << fw.get(i) << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);

    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}

提出情報

ジャッジ結果