Irreducible Anagrams

Created by LXC on Tue Sep 26 00:10:26 2023

https://codeforces.com/problemset/problem/1290/B

ranting: 1800

tag: binary search, constructive algorithms, data structures, strings, two pointers

problem

给出一个字符串s和若干询问。

定义不可约的字谜为两个串，其中一个重新排列可以得到另一个。

每个询问是子串s[l,r]在重新排列后得到t[l,r]，选择多个分割点，同时对两个串进行分割。问是否无论怎么分割，一定存在一对分割的串是不可约的字谜。

solution

三种情况是不可约的字谜。

只有一个字符的串是不可约的字谜。

首尾字符不相同。

首尾字符相同，但是存在三个不同的字符。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    string s;
    cin >> s;
    int n = s.size();
    vector c(n + 1, vector<int>(26, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++)
            c[i][j] = c[i - 1][j];
        c[i][s[i - 1] - 'a']++;
    }
    auto check = [&](int l, int r) {
        int d = 0;
        for (int i = 0; i < 26; i++) {
            d += c[r][i] != c[l - 1][i];
        }
        return d >= 3;
    };
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        if (l == r || s[l - 1] != s[r - 1] || check(l, r)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}