Dreamoon Likes Strings

Dreamoon likes strings. Today he created a game about strings:

String $s_1, s_2, \ldots, s_n$ is beautiful if and only if for each $1 \le i < n, s_i \ne s_{i+1}$.

Initially, Dreamoon has a string $a$. In each step Dreamoon can choose a beautiful substring of $a$ and remove it. Then he should concatenate the remaining characters (in the same order).

Dreamoon wants to use the smallest number of steps to make $a$ empty. Please help Dreamoon, and print any sequence of the smallest number of steps to make $a$ empty.Input

The first line contains an integer $t$ ($1 \leq t \leq 200\,000$), denoting the number of test cases in the input.

For each test case, there’s one line with a non-empty string of lowercase Latin letters $a$.

The total sum of lengths of strings in all test cases is at most $200\,000$.Output

For each test case, in the first line, you should print $m$: the smallest number of steps to make $a$ empty. Each of the following $m$ lines should contain two integers $l_i, r_i$ ($1 \leq l_i \leq r_i \leq |a|$), denoting, that the $i$-th step is removing the characters from index $l_i$ to $r_i$ in the current string. (indices are numbered starting from $1$).

Note that after the deletion of the substring, indices of remaining characters may change, and $r_i$ should be at most the current length of $a$.

If there are several possible solutions, you can print any.Exampleinput

4
aabbcc
aaabbb
aaa
abacad

output

3
3 3
2 4
1 2
3
3 4
2 3
1 2
3
1 1
1 1
1 1
1
1 6

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}

template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
}
return res;
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

class node {
 public:
  int id;
  node* l;
  node* r;
  node* p;
  bool rev;
  int sz;
  // declare extra variables:
  int P;

  node(int _id) {
    id = _id;
    l = r = p = nullptr;
    rev = false;
    sz = 1;
    // init extra variables:
    P = rng();
  }

  void unsafe_reverse() {
    rev ^= 1;
    swap(l, r);
    pull();
  }

  // apply changes:
  void unsafe_apply() {

  }

  void push() {
    if (rev) {
      if (l != nullptr) {
        l->unsafe_reverse();
}
if (r != nullptr) {
r->unsafe_reverse();
}
rev = 0;
}
// now push everything else:

}

void pull() {
sz = 1;
// now init from self:

if (l != nullptr) {
l->p = this;
sz += l->sz;
// now pull from l:

}
if (r != nullptr) {
r->p = this;
sz += r->sz;
// now pull from r:

}
}
};

void debug_node(node* v, string pref = "") {
#ifdef LOCAL
if (v != nullptr) {
debug_node(v->r, pref + " ");
cerr << pref << "-" << " " << v->id << '\n';
      debug_node(v->l, pref + " ");
} else {
cerr << pref << "-" << " " << "nullptr" << '\n';
    }
  #endif
}

namespace treap {

pair<node*, int> find(node* v, const function<int(node*)> &go_to) {
// go_to returns: 0 -- found; -1 -- go left; 1 -- go right
// find returns the last vertex on the descent and its go_to
if (v == nullptr) {
return {nullptr, 0};
}
int dir;
while (true) {
v->push();
dir = go_to(v);
if (dir == 0) {
break;
}
node* u = (dir == -1 ? v->l : v->r);
if (u == nullptr) {
break;
}
v = u;
}
return {v, dir};
}

node* get_leftmost(node* v) {
return find(v, [&](node*) { return -1; }).first;
}

node* get_rightmost(node* v) {
return find(v, [&](node*) { return 1; }).first;
}

node* get_kth(node* v, int k) { // 0-indexed
pair<node*, int> p = find(v, [&](node* u) {
if (u->l != nullptr) {
if (u->l->sz > k) {
return -1;
}
k -= u->l->sz;
}
if (k == 0) {
return 0;
}
k--;
return 1;
});
return (p.second == 0 ? p.first : nullptr);
}

int get_position(node* v) { // 0-indexed
int k = (v->l != nullptr ? v->l->sz : 0);
while (v->p != nullptr) {
if (v == v->p->r) {
k++;
if (v->p->l != nullptr) {
k += v->p->l->sz;
}
}
v = v->p;
}
return k;
}

node* get_bst_root(node* v) {
while (v->p != nullptr) {
v = v->p;
}
return v;
}

pair<node*, node*> split(node* v, const function<bool(node*)> &is_right) {
if (v == nullptr) {
return {nullptr, nullptr};
}
v->push();
if (is_right(v)) {
pair<node*, node*> p = split(v->l, is_right);
if (p.first != nullptr) {
p.first->p = nullptr;
}
v->l = p.second;
v->pull();
return {p.first, v};
} else {
pair<node*, node*> p = split(v->r, is_right);
v->r = p.first;
if (p.second != nullptr) {
p.second->p = nullptr;
}
v->pull();
return {v, p.second};
}
}

pair<node*, node*> split_leftmost_k(node* v, int k) {
return split(v, [&](node* u) {
int left_and_me = (u->l != nullptr ? u->l->sz : 0) + 1;
if (k >= left_and_me) {
k -= left_and_me;
return false;
}
return true;
});
}

node* merge(node* v, node* u) {
if (v == nullptr) {
return u;
}
if (u == nullptr) {
return v;
}
if (v->P > u->P) {
//    if (rng() % (v->sz + u->sz) < (unsigned int) v->sz) {
v->push();
v->r = merge(v->r, u);
v->pull();
return v;
} else {
u->push();
u->l = merge(v, u->l);
u->pull();
return u;
}
}

int count_left(node* v, const function<bool(node*)> &is_right) {
if (v == nullptr) {
return 0;
}
v->push();
if (is_right(v)) {
return count_left(v->l, is_right);
}
return (v->l != nullptr ? v->l->sz : 0) + 1 + count_left(v->r, is_right);
}

node* add(node* r, node* v, const function<bool(node*)> &go_left) {
pair<node*, node*> p = split(r, go_left);
return merge(p.first, merge(v, p.second));
}

node* remove(node* v) { // returns the new root
v->push();
node* x = v->l;
node* y = v->r;
node* p = v->p;
v->l = v->r = v->p = nullptr;
v->push();
v->pull(); // now v might be reusable...
node* z = merge(x, y);
if (p == nullptr) {
if (z != nullptr) {
z->p = nullptr;
}
return z;
}
if (p->l == v) {
p->l = z;
}
if (p->r == v) {
p->r = z;
}
while (true) {
p->push();
p->pull();
if (p->p == nullptr) {
break;
}
p = p->p;
}
return p;
}

node* next(node* v) {
if (v->r == nullptr) {
while (v->p != nullptr && v->p->r == v) {
v = v->p;
}
return v->p;
}
v->push();
v = v->r;
while (v->l != nullptr) {
v->push();
v = v->l;
}
return v;
}

node* prev(node* v) {
if (v->l == nullptr) {
while (v->p != nullptr && v->p->l == v) {
v = v->p;
}
return v->p;
}
v->push();
v = v->l;
while (v->r != nullptr) {
v->push();
v = v->r;
}
return v;
}

int get_size(node* v) {
return (v != nullptr ? v->sz : 0);
}

template<typename... T>
void apply(node* v, T... args) {
v->unsafe_apply(args...);
}

void reverse(node* v) {
v->unsafe_reverse();
}

}  // namespace treap

using namespace treap;

const int ALPHA = 26;

int cnt[ALPHA];
vector<int> good[ALPHA];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
string s;
cin >> s;
int n = (int) s.size();
node* r = nullptr;
for (int i = 0; i < n; i++) {
      r = merge(r, new node(i));
    }
    vector<pair<int, int>> st;
vector<pair<int, int>> ops;
auto Do = [&](int L, int R) {
auto q = split(r, [&](node* nd) { return nd->id >= L; });
auto w = split(q.second, [&](node* nd) { return nd->id >= R; });
int sz = get_size(q.first);
ops.emplace_back(sz, sz + get_size(w.first) - 1);
r = merge(q.first, w.second);
};
for (int i = 0; i < n - 1; i++) {
      if (s[i] == s[i + 1]) {
        pair<int, int> p = make_pair(i + 1, (int) (s[i] - 'a'));
st.push_back(p);
}
}
int sz = (int) st.size();
vector<int> pr(sz);
vector<int> ne(sz);
for (int i = 0; i < sz; i++) {
      pr[i] = i - 1;
      ne[i] = i + 1;
    }
    vector<bool> alive(sz, true);
for (int i = 0; i < ALPHA; i++) {
      cnt[i] = 0;
      good[i].clear();
    }
    auto IsGood = [&](int i) -> bool {
return (alive[i] && ((pr[i] != -1 && st[pr[i]].second != st[i].second) || (ne[i] != sz && st[ne[i]].second != st[i].second)));
};
auto Check = [&](int i) {
if (0 <= i && i < sz && IsGood(i)) {
        good[st[i].second].push_back(i);
      }
    };
    auto Remove = [&](int i) {
      if (pr[i] != -1) {
        ne[pr[i]] = ne[i];
      }
      if (ne[i] != sz) {
        pr[ne[i]] = pr[i];
      }
      alive[i] = false;
      cnt[st[i].second] -= 1;
      Check(pr[i]);
      Check(ne[i]);
    };
    for (int i = 0; i < sz; i++) {
      cnt[st[i].second] += 1;
      Check(i);
    }
    while (true) {
      int id = 0;
      int sum = 0;
      for (int i = 0; i < ALPHA; i++) {
        if (cnt[i] > cnt[id]) {
id = i;
}
sum += cnt[i];
}
if (sum == cnt[id]) {
break;
}
while (!good[id].empty() && !IsGood(good[id].back())) {
good[id].pop_back();
}
assert(!good[id].empty());
int x = good[id].back();
int y = ((pr[x] != -1 && st[pr[x]].second != st[x].second) ? pr[x] : ne[x]);
assert(0 <= y && y < sz);
      if (x > y) {
swap(x, y);
}
Do(st[x].first, st[y].first);
Remove(x);
Remove(y);
}
vector<int> all(1, 0);
for (int i = 0; i < sz; i++) {
      if (alive[i]) {
        all.push_back(st[i].first);
      }
    }
    all.push_back(n);
    for (int i = 0; i < (int) all.size() - 1; i++) {
      Do(all[i], all[i + 1]);
    }
    cout << ops.size() << '\n';
    for (int i = 0; i < (int) ops.size(); i++) {
      cout << ops[i].first + 1 << " " << ops[i].second + 1 << '\n';
    }
  }
  return 0;
}