Submission #70613791

---

Source Code Expand

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#include <vector>
#include <iostream> 
template<typename T>
struct RangeAddArithmeticProgression {// 区間に等差数列をAddする
	RangeAddArithmeticProgression(int sz) :sz(sz) {
		v.resize(sz + 1);
		sub.resize(sz + 1);
	}
	void set(T x, T y, int l, int r) {
		//初項x等差yの数列を[l,r)にAddする
		if (r < l) {
			x += (l - r - 1)*y;
			y *= -1;
			l++, r++;
			std::swap(l, r);
		}
		if (sz < r)r = sz;
		if (l < 0)x += abs(l)*y, l = 0;
		v[l] += y, v[r] -= y;
		sub[r] -= y * (r - l);
		sub[l] += x - y, sub[r] -= x - y;
	}
	void build() {
		for (int i = 0; i < sz; ++i)v[i + 1] += v[i];
		for (int i = 0; i < sz + 1; ++i)v[i] += sub[i];
		for (int i = 0; i < sz; ++i)v[i + 1] += v[i];
	}
	void debug() {
		for (int i = 0; i < sz; ++i) std::cout << v[i] << " ";
		std::cout << std::endl;
	}
	int sz;
	std::vector<T>v, sub;
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		string s; cin >> s;
		RangeAddArithmeticProgression<int> rapL(n), rapR(n);
		for (int i = 0; i < n - 1;) {
			int j = i + 1;
			while (j < n - 1 && s[i] == s[j])j++;
			int sz = j - i;
			//cout << i << " " << j << endl;
			if (s[i] == 'R') {
				rapR.set(sz, -1, i, j + 1);
				rapL.set(0, 1, i, j + 1);
			}
			else {
				rapL.set(sz, -1, i, j + 1);
				rapR.set(0, 1, i, j + 1);
			}
			i = j;
		}
		rapL.build();
		rapR.build();
		//rep(i, n) {
		//	cout << rapL.v[i] << " " << rapR.v[i] << endl;
		//}
		vector<int>imos(n + 1);
		rep(i, n) {
			int p = rapL.v[i];
			int q = rapR.v[i];
			imos[p]++;
			imos[n - q]--;
		}
		rep(i, n)imos[i + 1] += imos[i];
		rep(i, n)cout << imos[i] << " ";
		cout << endl;
	}
	return 0;
}

Submission Info

Judge Result