C - Truck Driver
核心问题分析
题目的要求是统计所有满足以下两个条件的子串 (l, r)：
1.a 的数量 >= A
2.b 的数量 < B
思路:
问题要求统计所有满足两个条件的子串：1. 'a'的数量 ≥ A；2. 'b'的数量 < B。
面对 N 高达 3×10⁵ 的数据规模， O(N²) 的暴力枚举所有 (l, r) 区间显然会超时。题目的特点是，当我们固定一个左端点 i 并向右移动右端点 j 时，子串中 a 和 b 的数量都是单调增加的。这种单调性是使用 滑动窗口（或多指针） 算法来优化的关键信号。
传统双指针的困境与三指针的引入
传统的双指针 (l, r) 通常用于维护一个 同时满足所有条件 的“有效窗口”。但在这道题里，两个条件的方向不同：一个是“大于等于”（希望窗口更大），另一个是“小于”（希望窗口更小）。这导致对于一个固定的起点 i，合法的终点 j 不是一个点，而是一个连续的区间。
让我们把这个合法终点区间称为 [j_min, j_max]：
*ja是第一个满足[i,j_min]中a的数量>=A的位置。
*jb是最后一个满足[i,j_max]中b的数量<B的位置。
只要我们为每个起点 i 找到这两个边界，那么对于这个 i，就有 max(0, j_max- j_min+1)个合法的子串。
这自然而然地引出了三指针解法：
i 指针 (起点指针): 在主循环中遍历，代表我们正在考察的子串的起点。
l 指针 (下界指针): 它的任务是为当前的 i 找到 j_min。我们向右移动 ja，直到窗口 [i, ja-1] 首次满足 a 的数量 ≥ A。由于单调性，当 i 右移时，ja 无需回退，只需从当前位置继续右移即可。
r 指针 (上界指针): 它的任务是为当前的 i 找到 j_max。我们向右移动 jb，直到窗口 [i, jb-1] 恰好满足 b 的数量 < B，而窗口 [i, jb] 将要不满足条件。同样，jb 也无需回退。
为什么是三个指针，而不是两个？
因为传统双指针旨在寻找一个“最优解点”，而本题需要寻找一个“最优解区间”。一个 left 指针和 一个 right 指针可以定义一个窗口，但无法同时界定一个区间的两个端点。因此，我们需要一个指针 i 来锚定所有子串的起点，然后用另外两个指针 l 和 r 去“扫描”出合法终点区间的左右边界。这三个指针各司其职，共同协作，将寻找 [j_min, j_max] 的过程从 O(N) 优化到了均摊 O(1)，从而保证了整体 O(N) 的时间复杂度。
代码如下:
#include <bits/stdc++.h>
using namespace std;
//CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p<<1
#define rc p<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x)&(-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps=1e-5;
const int N = 1e5 + 10,M=2*N,K=26;
const ll MOD = 1e9 + 7,Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template<typename T> bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random { mt19937_64 rng; Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {} ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); } ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); } bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); } template<typename T> void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); } };
ll qmi(ll a, ll b, ll p) { ll res = 1 % p; a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }
/*
}
*/
void solve()
{
ll n,na,nb; cin>>n>>na>>nb;
string s; cin>>s;
s=" "+s;
ll cnta=0,cntb=0,ans=0;//记录区间内 a b字符的数量 ans记录合法的区间数
for(int i = 1, ja = 1, jb = 1; i <= n; i++)
{
while(ja<=n&&cnta<na)
{
cnta+=s[ja]=='a';
ja++;
}
while(jb<=n&&cntb+(s[jb]=='b')<nb)
{
cntb += ((s[jb]=='b'));
jb++;
}
if(cnta>=na&&cntb<nb&&ja<=jb){
ans+=jb-ja+1;
}
/**
* 准备处理下一个起点(i+1)：从当前计数中移除起点i处的字符
* 这是因为下一轮循环i会递增，窗口起点变为i+1
* 需要从计数中移除不再属于新窗口的字符s[i]
*/
cnta-=(s[i]=='a');
cntb-=(s[i]=='b');
}
cout<<ans<<endl;
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}D - Neighbor Distance
AC代码:
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, res = 0, x;
cin >> n;
set<ll> st;
map<ll, ll> mp;
cin >> x;
st.insert(0);
st.insert(x);
mp[0] = x;
mp[x] = x;
res += 2 * x;
cout << res << endl;
for (int i = 1; i < n; i++)
{
cin >> x;
vector<ll> h;
auto it = st.lower_bound(x);
if (it != st.end())
h.push_back(*it);
if (it != st.begin())
{
it--;
h.push_back(*it);
}
st.insert(x);
mp[x] = 2e9;
for (auto &nxt : h)
{
res -= mp[nxt]; // 从总和中去掉邻居旧的距离
mp[nxt] = min(mp[nxt], abs(nxt - x)); // 更新邻居的距离
res += mp[nxt]; // 将邻居的新距离加回总和
mp[x] = min(mp[x], abs(nxt - x));
}
res += mp[x];
cout << res << endl;
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}E - Shift String
题意:
您将获得由‘ 0 ’和‘ 1 ’组成的长度相等的字符串 A 和 B 。A 可以执行0次或多次以下操作。—将 A 的第一个字符移到末尾。求生成 A=B 所需的最小操作数。如果无论你怎么操作都不能做出 A=B ，那就打印 −1 。给你 T 个测试用例；找出每个问题的答案。
思路:
我们先从最朴素的思路出发，操作是将A的第一个字符移动最后一个位置，显然这个过程具有周期性，我们不妨把A字符扩大一倍，然后控制首尾指针保证A串的长度，看看整个模拟过程是否有与B字符串相等的时候，如果没有输出-1，有则输出开头指针即可(默认字符串下标从1开始)。
代码如下:
#include <bits/stdc++.h>
using namespace std;
//CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p<<1
#define rc p<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x)&(-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps=1e-5;
const int N = 2e6 + 10,M=2*N,K=26;
const ll MOD = 1e9 + 7,Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template<typename T> bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random { mt19937_64 rng; Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {} ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); } ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); } bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); } template<typename T> void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); } };
ll qmi(ll a, ll b, ll p) { ll res = 1 % p; a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }
/*
*/
void solve()
{
string a,b; cin>>a>>b;
ll n=a.size();
a+=a;
ll cnt=-1;
for(int i=0;i<n;i++){
string s=a.substr(i,n);
if(s==b){
cnt=i;
break;
}
}
cout<<cnt<<endl;
}
int main()
{
IOS;
int _ = 1;
cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}然而朴素的模拟会TLE，于是我们想到我们曾写过的KMP算法，用于主串与模式串的匹配，正好符合题意。由于题目比较板，不会复习一下KMP算法即可AC，这里不对思路做多余的赘述了。
KMP解法如下:
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
// N 的大小需要足够容纳 ' ' + B + '#' + A + A
// |A| <= 10^6, |B| <= 10^6, |A+A| <= 2*10^6
// 总长度约为 1 + 10^6 + 1 + 2*10^6 = 3*10^6 + 2, 所以 N 开大一点
const int N = 3e6 + 20;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int pi[N];
void solve()
{
string a, b;
cin >> a >> b;
if (a.size() != b.size())
{
cout << -1 << endl;
return;
}
string t = a + a;
string p = b;
int m = p.size();
if (m == 0)
{
cout << 0 << endl;
return;
}
string s = " " + p + '#' + t;
int lens = s.size() - 1;
for (int i = 0; i <= lens; i++) pi[i] = 0;
for (int i = 2, j = 0; i <= lens; i++)
{
while (j > 0 && s[i] != s[j + 1])
{
j = pi[j];
}
if (s[i] == s[j + 1])
{
j++;
}
pi[i] = j;
if (pi[i] == m)
{
int pos = i - 2 * m - 1;
if (pos < m)
{
cout << pos << endl;
return;
}
}
}
cout << -1 << endl;
}
int main()
{
IOS;
int T = 1;
cin >> T; // 如果是多组数据
while (T--)
{
solve();
}
return 0;
}
由于我的KMP板子在其他博客难以查到，后续有时间再单独写一篇自己KMP的算法专栏，考虑到当前只是想写题解，这个后续有时间再补。
另外一种解法:
双哈希解法：高效的模式匹配利器
在解决了朴素模拟法的效率瓶颈后，我们还可以利用双哈希技术来优化此问题。这种方法的核心思想是：通过计算两个独立的哈希值来代表字符串，当且仅当两个哈希值都匹配时，才判定子串相等，从而将哈希冲突的概率降至极低水平（约为两个哈希函数单独冲突概率的乘积）
那么思路就很简单了，预处理一下用B串来匹配一下即可。
双哈希解法如下（附带部分注释）:
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 2e6 + 10;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
ull h1[N], p1[N];
ll h2[N], p2[N];
void pre(int max_len) {
p1[0] = 1;
p2[0] = 1;
for (int i = 1; i <= max_len; ++i) {
p1[i] = p1[i-1] * base1;
p2[i] = mod(p2[i-1] * base2, Md7);
}
}
PLL get_hash(int l, int r, int len) {
ull v1 = h1[r] - h1[l-1] * p1[len];
ll v2 = mod(h2[r] - mod(h2[l-1] * p2[len], Md7), Md7);
return {v1, v2};
}
void solve()
{
string a, b;
cin >> a >> b;
int n = a.size();
if (n != b.size()) {
cout << -1 << endl;
return;
}
if (n == 0) {
cout << 0 << endl;
return;
}
ull bh1 = 0;// b的第一个哈希值
ll bh2 = 0;// b的第二个哈希值
for (char c : b) {
// 滚动哈希计算：新哈希值 = 旧哈希值 * base + 当前字符
bh1 = bh1 * base1 + c;
bh2 = mod(bh2 * base2 + c, Md7);
}
string s = a + a;
h1[0] = h2[0] = 0;// 计算s的前缀哈希
for (int i = 0; i < s.size(); ++i) {
h1[i+1] = h1[i] * base1 + s[i];
h2[i+1] = mod(h2[i] * base2 + s[i], Md7);
}
// 查找匹配
for (int i = 0; i < n; ++i) {
PLL hv = get_hash(i + 1, i + n, n);
if (hv.fi == bh1 && hv.se == bh2) {
cout << i << endl;
return;
}
}
cout << -1 << endl;
}
int main()
{
IOS;
pre(2000000);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}F - Back and Forth Filling
题意:
问题陈述你得到一个整数 N 和一个长度为 N−1 的字符串 S ，由‘ L ’和‘ R ’组成。考虑将整数写入排成一行的 N 单元格中，以满足以下条件：—每个单元格上写一个整数。—每个整数 1,2,…,N 只出现在一个单元格中。—当 S 的第 i \第一个字符为‘ L ’时， i+1 被写到 i 的左边。—当 S 的 i \第一个字符为“R”时， i+1 被写到 i 的右侧。设 C i为可以写入左边第 i \单元格的整数个数。 C 1 ,C ,…,C N 。给你 T 个测试用例；找出每个问题的答案。
思路:
这个问题类似与萝卜填坑，我们很难确定每个坑填了那些萝卜，但是我们可以直到这些萝卜可以填在那些坑里面，于是我们想到了求每个萝卜的"活动范围"，我们求出每个萝卜的活动范围，然后用差分数组来算对活动范围内坑的贡献，然后差分数组累加之后就可以救出最后每个坑可以放多少种萝卜。
我们来深入探讨这道题的核心——如何确定每个萝卜 i 能到达的最左和最右位置。很多题解会直接给出公式 l = rp[i] + ls[i+1]，但这个公式是怎么来的？为什么它能精确地算出极限位置？现在，我们一步步把它讲清楚。首先，我们要明确一点：规则 L 和 R 只定义了相邻萝卜的相对位置，并不意味着任何一个萝卜的最终位置是固定的。一个萝卜 i 的最终位置取决于所有 n-1 条规则共同作用下的结果。因此，我们要求的不是萝卜 i “必然”在哪里，而是它在所有可能的、合法的排列中，能够占据的位置范围我们要求的是这个范围的两个端点：
最左极限 l：存在一种合法的排列，让萝卜 i 落在位置 l，且不存在任何合法排列能让它落在比 l 更左的位置。
最右极限 r：同理，r 是萝卜 i 能到达的最右边的位置。
第二步：极限思维——如何构造最左极限？
为了把萝卜 i 尽可能地推向左边，我们需要把尽可能多的其他萝卜都安排到它的右边。
现在，我们把除 i 之外的所有萝卜分成两组：
A 组（左侧组）：萝卜 0, 1, ..., i-1
B 组（右侧组）：萝卜 i+1, i+2, ..., n-1
萝卜 i 的最终位置，就等于排在它左边的萝卜总数。这个总数由两部分构成：
最终位置 = (来自 A 组，且排在 i 左边的数量) + (来自 B 组，且排在 i 左边的数量)
我们的目标，就是让这个总数变得最小。
第三步：分而治之——分析两组萝卜的贡献
现在我们来玩一场“拔河比赛”，萝卜 i 是中心点。我们想让它尽量向左移动。
- 分析 B 组（右侧组）{i+1, ..., n-1}：
这组萝卜天然在 i 的“右边”。为了让 i 最靠左，我们希望 B 组的萝卜全都待在 i 的右边。
但是，有些规则会阻止我们这么做。考虑规则 k L k+1，它意味着 k 必须在 k+1 的左边。
想象一下，如果 k 和 k+1 都在 B 组里，这条 L 规则就像一根绳子，把 k “锚定”在 k+1 的左边。如果 i 在 k 的左边，k+1 也在 k 的右边，那么 i, k, k+1 的顺序是 pos(i) < pos(k) < pos(k+1)，这很和谐。
但如果规则是 i L i+1 呢？i 就必须在 i+1 的左边。
如果规则是 i+1 L i+2 呢？i+1 就必须在 i+2 的左边。
现在，把所有这些 L 规则串联起来。每一条位于 s[k] (k > i) 的 L 规则，都像一个“拉力”，试图把萝卜 k-1 拉到萝卜 k 的左边。
这是一个非常深刻的组合学结论：
当我们试图将 i 推到最左时，对于 B 组的萝卜，有多少条 L 规则，最终就会有多少个萝卜从 B 组被“拉”到 i 的左边。
这些 L 规则形成了一个无法挣脱的“依赖链”。ls[i+1] 正是 s[i+1] 到 s[n-1] 中 L 规则的总数。所以，B 组对 i 左侧萝卜数量的最小贡献就是 ls[i+1]。
- 分析 A 组（左侧组）{0, ..., i-1}：
这组萝卜天然在 i 的“左边”。为了让 i 最靠左，我们希望 A 组的萝卜尽可能多地移动到 i 的右边。
什么规则会阻止它们移动呢？是 R 规则。
规则 k R k+1 意味着 k 必须在 k+1 的右边。
如果 k 和 k+1 都在 A 组，这条 R 规则就像一个“反向的锚”，把 k+1 “钉”在了 k 的左边。它加强了 k+1 留在 i 左侧的趋势。
我们可以得出与 B 组对称的结论：
当我们试图将 i 推到最左时，对于 A 组的萝卜，有多少条 R 规则，最终就会有多少个萝卜被“锁”在 i 的左边，无法移动到右侧。
rp[i] 正是 s[1] 到 s[i] 中 R 规则的总数。所以，A 组对 i 左侧萝卜数量的最小贡献就是 rp[i]。
第四步：汇总——公式的诞生
通过上面的分析，我们得出了结论：
为了让萝卜 i 到达最左极限位置，我们需要最小化它左边的萝卜数量。
这个最小数量 = (从 B 组被拉过来的最小数量) + (从 A 组被锁在左边的最小数量)
最小数量 = ls[i+1] + rp[i]
因为位置下标是从 0 开始的，如果左边有 k 个萝卜，那么自己的位置就是 k。所以，萝卜 i 的最左极限位置 l 就是：
l = rp[i] + ls[i+1]
最右极限 r 的分析完全对称：
要让 i 最靠右，就要让它右边的萝卜数量最少。
右边的萝卜数量 = (A 组中被拉到右边的) + (B 组中被锁在右边的)。
A 组中，L 规则是“拉力”，会把 lp[i] 个萝卜拉到 i 的右边。
B 组中，R 规则是“锁”，会把 rs[i+1] 个萝卜锁在 i 的右边。
所以 i 右侧最少有 lp[i] + rs[i+1] 个萝卜。
总共有 n 个位置 (0 到 n-1)。从最右边的位置 n-1，减去右侧必须有的萝卜数量，就是 i 能到达的最右位置：
r = (n-1) - (lp[i] + rs[i+1])。这个证明仍然不够严谨，但希望可以给读者一些启发，我们在写题目的时候在考虑某个变量难以解决的时候，不妨换一个角度思考，正如我们考虑每一个萝卜，我们才发现萝卜其实是可以用一个活动范围的，最后才能累加贡献算出最后的答案，换成思考每个坑可以放那些萝卜，就有些无从下手了。
最后给出AC代码:
#include <bits/stdc++.h>
using namespace std;
//CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p<<1
#define rc p<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x)&(-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps=1e-5;
const int N = 1e5 + 10,M=2*N,K=26;
const ll MOD = 1e9 + 7,Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template<typename T> bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
struct Random { mt19937_64 rng; Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {} ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); } ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); } bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); } template<typename T> void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); } };
ll qmi(ll a, ll b, ll p) { ll res = 1 % p; a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }
/*
*/
void solve()
{
ll n; cin>>n;
string s; cin>>s;
s=" "+s+" ";
vll lp(n+1,0),rp(n+1,0),ls(n+1,0),rs(n+1,0);
rep(i,1,n-1){
// lp[i]=lp[i-1]+(s[i]=='L');
// rp[i]=rp[i-1]+(s[i]=='R');
if(s[i]=='L') lp[i]=lp[i-1]+1;
if(s[i]=='R') rp[i]=rp[i-1]+1;
}
dep(i,n-1,1){
// ls[i]=ls[i+1]+(s[i]=='L');
// rs[i]=rs[i+1]+(s[i]=='R');
if(s[i]=='L') ls[i]=ls[i+1]+1;
if(s[i]=='R') rs[i]=rs[i+1]+1;
}
vll ans(n+1,0);
rep(i,0,n-1){
ll l=0,r=n-1;
l+=(rp[i]+ls[i+1]);
r-=(lp[i]+rs[i+1]);
ans[l]++;
ans[r+1]--;
}
rep(i,0,n-1){
if (i) ans[i] += ans[i-1];
cout << ans[i] << (i == n-1 ? "" : " ");
}
cout<<endl;
}
int main()
{
IOS;
int _ = 1;
cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}最后读者还可以思考一下为什么我在处理前缀和后缀数组的时候为什么用注释掉的会错误呢，什么情况会错误，什么时候不会错误呢。