考虑构造一个新串 \(t\),只保留原串 \(s_{i - 1} = s_i\) 的字符 \(s_i\)。设 \(a_i\) 为 \(t_i\) 在原串的位置。
那么新串上我们有两种操作:
- \(\forall i\),删除 \(t_i\)(相当于删除原串中的 \([a_i, a_i]\));
- \(\forall t_i \ne t_{i + 1}\),删除 \(t_i, t_{i + 1}\)(相当于删除原串中的 \([a_i, a_{i + 1} - 1]\))。
设 \(t\) 中字符 \(i\) 出现了 \(c_i\) 次,出现次数最多的字符为 \(p\)。
若 \(2c_p \ge |t|\),我们可以不断将 \(p\) 与其他字符配对,最后剩下一些 \(p\) 逐个删除即可。
若 \(2c_p < |t|\),我们可以先随意让一些字符配对,若删到某一步发现存在 \(2c_p \ge |t|\) 了就换上面的做法。
实现时这部分可以用栈。
注意因为我们要还原串的下标,因此使用线段树每个字符是否还没被删。每次删除一段相当于区间赋值。
时间复杂度 \(O(n (\log n + |\Sigma|))\)。
code
// Problem: D. Dreamoon Likes Strings
// Contest: Codeforces - Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov!
// URL: https://codeforces.com/problemset/problem/1329/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 200100;
int n, a[maxn], m, c[26], stk[maxn], top;
bool vis[maxn];
char s[maxn], t[maxn];
namespace SGT {
int a[maxn << 2], b[maxn << 2];
inline void pushup(int x) {
a[x] = a[x << 1] + a[x << 1 | 1];
}
inline void pushdown(int x) {
if (!b[x]) {
return;
}
a[x << 1] = a[x << 1 | 1] = 0;
b[x << 1] = b[x << 1 | 1] = 1;
b[x] = 0;
}
void build(int rt, int l, int r) {
b[rt] = 0;
if (l == r) {
a[rt] = 1;
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
a[rt] = 0;
b[rt] = 1;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr);
}
pushup(rt);
}
int query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return a[rt];
}
pushdown(rt);
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) {
res += query(rt << 1, l, mid, ql, qr);
}
if (qr > mid) {
res += query(rt << 1 | 1, mid + 1, r, ql, qr);
}
return res;
}
}
inline bool check() {
int mx = 0, s = 0;
for (int i = 0; i < 26; ++i) {
mx = max(mx, c[i]);
s += c[i];
}
return mx * 2 < s;
}
void solve() {
scanf("%s", s + 1);
n = strlen(s + 1);
m = top = 0;
for (int i = 2; i <= n; ++i) {
if (s[i] == s[i - 1]) {
t[++m] = s[i];
a[m] = i;
}
}
SGT::build(1, 1, n);
mems(c, 0);
for (int i = 1; i <= m; ++i) {
++c[t[i] - 'a'];
vis[i] = 0;
}
vector<pii> vc, ans;
for (int i = 1; i <= m && check(); ++i) {
if (!top || t[i] == t[stk[top]]) {
stk[++top] = i;
} else {
--c[t[i] - 'a'];
--c[t[stk[top]] - 'a'];
vis[i] = vis[stk[top]] = 1;
vc.pb(a[stk[top--]], a[i] - 1);
}
}
int mx = -1, p = -1;
for (int i = 0; i < 26; ++i) {
if (c[i] > mx) {
mx = c[i];
p = i;
}
}
top = 0;
for (int i = 1; i <= m; ++i) {
if (vis[i]) {
continue;
}
if (top && (t[i] == 'a' + p || t[stk[top]] == 'a' + p) && t[i] != t[stk[top]]) {
vis[i] = vis[stk[top]] = 1;
vc.pb(a[stk[top--]], a[i] - 1);
} else {
stk[++top] = i;
}
}
for (int i = 1; i <= m; ++i) {
if (!vis[i]) {
vc.pb(a[i], a[i]);
}
}
for (pii p : vc) {
int l = p.fst, r = p.scd;
ans.pb(SGT::query(1, 1, n, 1, l), SGT::query(1, 1, n, 1, r));
SGT::update(1, 1, n, l, r);
}
ans.pb(1, SGT::a[1]);
printf("%d\n", (int)ans.size());
for (pii p : ans) {
printf("%d %d\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- CodeForces Dreamoon Strings 1329D Likescodeforces dreamoon strings 1329d codeforces dreamoon 1329e loves dreamoon报告1329e loves 题解dreamoon 1329e loves codeforces round likes 857 codeforces multiset strings 1709f hyperregular codeforces bracket strings educational codeforces strings binary codeforces version 1092d1 d likes