Попробуйте рассмотреть такие отрезки, где $$$l \le \lfloor \frac{r}{2} \rfloor + 1$$$.

Теперь подумайте, что делать, если это условие не выполняется.

#include <iostream>

using namespace std;

int l, r;

void solve() {
    if (r < l * 2) {
        cout << r - l << endl;
    }
    else {
        cout << (r - 1) / 2 << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> l >> r;
        solve();
    }
}

Попробуйте рассмотреть небольшие числа, например, состоящие из трех цифр.

Теперь подумайте, какое максимальное количество цифр может быть в оптимальном ответе.

#include <iostream>

using namespace std;

int n;

string s;

bool prime[100];

void solve() {
    for (int i = 0; i < n; i++) {
        if (s[i] == '1' || s[i] == '4' || s[i] == '6' || s[i] == '8' || s[i] == '9') {
            cout << 1 << endl;
            cout << s[i] << endl;
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!prime[(s[i] - '0') * 10 + (s[j] - '0')]) {
                cout << 2 << endl;
                cout << s[i] << s[j] << endl;
                return;
            }
        }
    }
    exit(42);
}

int main() {
    for (int i = 2; i < 100; i++) {
        prime[i] = true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                prime[i] = false;
            }
        }
    }
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> s;
        solve();
    }
}

Попробуйте доказать, что авторское решение работает за $$$O(k)$$$ на один тестовый случай.

Поиск ответа, состоящего из одной цифры, работает за $$$O(k)$$$. Теперь посмотрим, за сколько выполнится цикл. В самом деле, нетрудно видеть, что после того, как будут рассмотрены пары индексов $$$(0,1)$$$, $$$(0,2)$$$ и $$$(1,2)$$$, всегда будет найден ответ. Это так потому, что в любом числе из трех цифр можно найти ответ, состоящий из двух цифр (это было доказано ранее). Поэтому это равносильно тому, что мы удалили все цифры, кроме первых трех, а потом решили задачу для них (при условии, что длина оптимального ответа равна двум).

Попробуйте придумать такой способ перебирать пары индексов и такой тест, чтобы этот перебор работал за $$$O(k^2)$$$ на один тестовый случай.

в качестве строки возьмем строку \t{3737 \ldots 37}. Перебирать пары индексов будем следующим образом: сначала будем перебирать все пары индексов с разными четностями, а потом все пары индексов с одинаковыми четностями. Нетрудно видеть, что такой перебор будет работать за $$$O(k^2)$$$ на один тестовый случай, т.к. все пары индексов с разными четностями будут давать числа $$$37$$$ и $$$73$$$, которые являются простыми, а таких пар индексов $$$O(k^2)$$$.

подумайте, можно ли сделать так, чтобы подходящее $$$k$$$ (такое, что $$$f(t) = f(w) \cdot k$$$) было небольшим? На какие маленькие $$$k$$$ легко умножать двоичные числа?

такими $$$k$$$ могут являться числа $$$0$$$, $$$1$$$ и $$$2$$$~--- умножение на $$$0$$$ дает $$$0$$$, умножение на $$$1$$$ оставляет число как есть, а умножение на $$$2$$$ добавляет ноль в конец. Подумайте, как можно этим воспользоваться.

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        bool solved = false;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                solved = true;
                if (i >= n / 2) {
                    cout << 1 << " " << i + 1 << " " << 1 << " " << i << endl;
                    break;
                } else {
                    cout << i + 2 << " " << n << " " << i + 1 << " " << n << endl;
                    break;
                }
            }
        }
        if (!solved) {
            cout << 1 << " " << n - 1 << " " << 2 << " " << n << endl;
        }
    }
}

Подумайте, как решалась бы задача, если бы при всех прежних условиях (строка состоит из цифр $$$0$$$ и $$$1$$$, в строке есть хотя бы одна единица) была выбрана любая произвольная система счисления.

решение бы никак не изменилось. В самом деле, в системе счисления с основанием $$$k$$$ приписывание нуля слева не меняет число (умножение на $$$1$$$), а дописывание нуля справа увеличивает число в $$$k$$$ раз (умножение на $$$k$$$).

Подумайте, как решалась бы задача, если бы условие звучало так: \textit{необходимо, чтобы $$$f(t)$$$ делилось на $$$f(w)$$$ без остатка. В строке есть хоть бы одна единица. Ноль делится на все числа, но никакое число не делится на ноль. Ноль не делится на ноль.}

На самом деле, задача становится несколько сложнее. Например, рассмотрим такой тест: \t{111000000}. В данном случае нельзя было бы выводить $$$4$$$ $$$9$$$ $$$5$$$ $$$9$$$, поскольку ноль не делится на ноль.

Будем выполнять старое решение, но проверять, что мы не пытаемся делить ноль на ноль (если мы делим что-то на ноль, то поменяем числа местами). А если ответ не нашелся, значит, либо вся левая половина строки состоит из нулей, либо вся правая. Пусть самая левая единица имеет позицию $$$p1$$$, а самая правая единица~--- позицию $$$p2$$$. Тогда в первом случае можно вывести $$$1$$$ $$$p2$$$ $$$2$$$ $$$p2$$$, а во втором случае~--- $$$p1$$$ $$$n$$$ $$$p1$$$ $$$n-1$$$.

Нетрудно видеть, что такое решение также всегда будет находить ответ.

На самом деле, можно действовать проще: когда мы встречаем ноль в левой половине, мы дополнительно проверяем, есть ли среди символов справа хотя бы одна единица. Если есть, то выводим ответ, иначе идем дальше. Аналогично, когда мы встречаем ноль в правой половине, мы дополнительно проверяем, есть ли среди символов слева хотя бы одна единица. Можно показать, что такое решение также будет всегда находить ответ.

Интересно, что мы решили \textbf{более сильную версию задачи}, так как полученное нами решение корректно работает и для старой задачи.

Подумайте: как связана четность длины отрезка и четность количества элементов, которое необходимо из него удалить?

Подумайте, насколько сильно и как отличается значение знакопеременной суммы при удалении только одного элемента, и при удалении только его соседа.

Рассмотрите отрезки нечетной длины. Попробуйте взять небольшие отрезки и для каждого элемента узнать, какой будет знакопеременная сумма после его удаления. После этого можно будет заметить кое-что интересное.

#include <iostream>

using namespace std;

int a[1000000 + 5], p[1000000 + 5];

int get_sum(int l, int r) {
    if (l > r) {
        return 0;
    }
    return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        string ss;
        cin >> ss;
        for (int i = 1; i <= n; i++) {
            a[i] = (ss[i - 1] == '+' ? 1 : -1);
        }
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]);
        }
        for (int o = 0; o < q; o++) {
            int l, r;
            cin >> l >> r;
            if (get_sum(l, r) == 0) {
                cout << "0\n";
                continue;
            }
            if ((r - l + 1) % 2 == 0) {
                cout << "2\n";
            }
            else {
                cout << "1\n";
            }
        }
    }
}

Смотрите соответствующие подсказки из задачи D1.

Подумайте, как быстро проверять значение знакопеременной суммы на отрезке, если известно, что из него удален ровно один элемент (и известен номер этого элемента).

Из решения задачи D1 становится понятно, что для любого нечетного отрезка достаточно удалить всего лишь один элемент. Подумайте, как искать такой элемент, опираясь на доказательство его существования, приведенное выше.

#include <iostream>

using namespace std;

int a[1000000 + 5], p[1000000 + 5];

int get_sum(int l, int r) {
    if (l > r) {
        return 0;
    }
    return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r];
}

int check_elimination(int l, int r, int m) {
    return ((m - l + 1) % 2 == 1)
    ? get_sum(l, m - 1) + get_sum(m + 1, r)
    : get_sum(l, m - 1) - get_sum(m + 1, r);
}

int get_sign(int m) {
    return m > 0 ? 1 : -1;
}

int calculate_odd_segment(int l, int r) {
    if (l == r) {
        return l;
    }
    int pos = 0;
    int lb = l;
    int rb = r;
    while (lb < rb) {
        int mb = (lb + rb) / 2;
        int lq = check_elimination(l,r,lb);
        int mq = check_elimination(l,r,mb);
        int rq = check_elimination(l,r,rb);
        if (lq == 0) {
            pos = lb;
            break;
        }
        if (mq == 0) {
            pos = mb;
            break;
        }
        if (rq == 0) {
            pos = rb;
            break;
        }
        if (get_sign(lq) == get_sign(mq)) {
            lb = mb;
        } else {
            rb = mb;
        }
    }
    return pos;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        string ss;
        cin >> ss;
        for (int i = 1; i <= n; i++) {
            a[i] = (ss[i - 1] == '+' ? 1 : -1);
        }
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]);
        }
        for (int o = 0; o < q; o++) {
            int l, r;
            cin >> l >> r;
            if (get_sum(l, r) == 0) {
                cout << "0\n";
                continue;
            }
            bool even = false;
            if ((r - l + 1) % 2 == 0) {
                even = true;
                l++;
            }
            int pos = calculate_odd_segment(l, r);
            if (even) {
                cout << "2\n" << l - 1 << " "<< pos << '\n';
            } else {
                cout << "1\n" << pos << '\n';
            }
        }
    }
}

Существует ли решение с асимптотикой $$$O(n + q)$$$ на один тестовый случай?

Для решения понадобится быстро (за О(1)) искать наибольший общий префикс двух подстрок.

Возьмите несколько небольших строк и попробуйте построить наибольшую возрастающую подпоследовательность. Быть может, в ней есть какая-то особенность?

Используйте динамическое программирование.

#include <iostream>

using namespace std;

int16_t lcp[10000 + 5][10000 + 5];

int dp[10000 + 5];

bool is_greater(const string& s, int x, int y) {
    if (lcp[x][y] == static_cast<int>(s.size()) - x) {
        return false;
    }
    return s[x + lcp[x][y]] > s[y + lcp[x][y]];
}

int get_score(const string& s, int x, int y) {
    if (is_greater(s, x, y)) {
        return dp[y] + static_cast<int>(s.size()) - x - lcp[x][y];
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        if (s.size() != n) return 42;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                lcp[i][j] = 0;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == j) {
                    lcp[i][j] = n - i;
                } else
                if (s[i] != s[j]) {
                    lcp[i][j] = 0;
                } else {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }
        int ans = n;
        dp[0] = n;
        for (int i = 1; i < n; i++) {
            dp[i] = n - i;
            for (int j = 0; j < i; j++) {
                dp[i] = max (dp[i], get_score(s, i, j));
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }
}

Насколько мне известно, используя бор (trie), можно отсортировать все подстроки заданной строки за $$$O(n^2)$$$. Также, насколько мне известно, в языке программирования С++ \textit{std::lower\textunderscore bound} работает настолько быстро, что в массиве размера $$$1.25 \cdot 10^7$$$ такое же количество операций \textit{std::lower\textunderscore bound} выполняется чуть меньше, чем за секунду. Известно также, что при помощи \textit{std::lower\textunderscore bound} можно написать поиск наибольшей возрастающей подпоследовательности в массиве. Вопрос такой: можно ли на основании этого написать решение за $$$O(n^2 \cdot log(n))$$$, которое бы проходило тесты?

Придумайте решение, которое бы использовало $$$\frac{n \cdot (n-1)}{2}$$$ запросов.

При $$$n < 100$$$ примените решение, которое использует $$$\frac{n \cdot (n-1)}{2}$$$ запросов. Теперь предположим, что $$$n \geq 100$$$. Придумайте решение, которое бы использовало $$$\lceil\frac{3n}{2}\rceil$$$ запросов.

При $$$n < 10000$$$ примените решение, которое использует $$$2n$$$ запросов. Теперь предположим, что $$$n \geq 5000$$$. Скорее всего, в решении за $$$2n$$$ запросов, которое вы придумали, необходимо найти наибольшее простое число на отрезке. Подумайте, а так ли вам надо наибольшее простое число? Может быть, будет достаточно просто достаточно большого простого числа? Как найти такое число?

Используйте вероятностные алгоритмы для нахождения такого числа. С помощью вероятностных алгоритмов также убедитесь, что вы нашли подходящее число.

Теперь используйте найденное простое число, чтобы найти наибольшее простое число. Возможно, при его нахождении вы уже узнаете большую часть чисел, и с помощью наибольшего простого числа вы сможете узнать оставшиеся.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <random>

using namespace std;

#define int long long

mt19937 rnd(time(NULL));

int swnmb[1000000+5];

int swnmbr[1000000+5];

int b[1000000+5];

bool p[1000000+5];

vector<int> primes;

int get_lcm(int x, int y)
{
    cout<<"? "<<swnmb[x]<<" "<<swnmb[y]<<endl;
    int u;
    cin>>u;
    return u;
}

int max_fact(int d)
{
    for (int j=(int)primes.size()-1; j>=0; j--)
    {
        if (d%primes[j]==0) return primes[j];
    }
}

vector<int> fact(int d)
{
    vector<int> ans;
    for (auto j:primes)
    {
        if (d==1) break;
        while (d%j==0)
        {
            ans.push_back(j);
            d/=j;
        }
    }
    return ans;
}

bool is_prime(int d)
{
    for (int j=0; j<(int)primes.size(); j++)
    {
        if (primes[j]>500) return true;
        if (d%primes[j]==0) return false;
    }
    return true;
}

int paired_get_lcm[100+5][100+5];

void solve_quadric(int n)
{
    for (int i=1; i<=n; i++) {
        for (int j=i+1; j<=n; j++) {
            paired_get_lcm[i][j]=get_lcm(i,j);
            paired_get_lcm[j][i]=paired_get_lcm[i][j];
        }
    }
    int m1=0;
    int m2=0;
    int mx=0;
    for (int i=1; i<=n; i++) {
        for (int j=i+1; j<=n; j++) {
            if (paired_get_lcm[i][j]>mx)
            {
                mx=paired_get_lcm[i][j];
                m1=i;
                m2=j;
            }
        }
    }
    int u=0;
    for (int i=1; i<=200000; i++)
    {
        if (mx==i*(i+1))
        {
            u=i+1;
            break;
        }
    }
    for (int i=1; i<=n; i++)
    {
        if (i==m1||i==m2) continue;
        if (paired_get_lcm[m1][i]%u!=0)
        {
            swap(m1,m2);
            break;
        }
    }
    b[m1]=u;
    int pos=m2;
    for (int v=u-1; v>u-n-1; v--)
    {
        int m0=0;
        int mx=0;
        for (int j=1; j<=n; j++) {
            if (b[j]!=0) continue;
            if (pos==j) continue;
            if (paired_get_lcm[pos][j]>mx)
            {
                mx=paired_get_lcm[pos][j];
                m0=j;
            }
        }
        b[pos]=v;
        pos=m0;
    }
    b[pos]=u-n+1;
}

void solve_pair(int n)
{
    int maxnum=0;
    int maxpos=0;
    int notmaxpos=0;
    for (int i=1; i<=n; i+=2)
    {
        int u;
        if (i!=n) u=get_lcm(i,i+1);
        else u=get_lcm(i-1,i);
        int w=max_fact(u);
        if (w>maxnum)
        {
            maxnum=w;
            maxpos=min(i+1,n);
        } else {
            notmaxpos=i;
        }
    }
    int cur=get_lcm(notmaxpos,maxpos);
    if (cur%maxnum!=0) {
        maxpos--;
    }
    b[maxpos]=maxnum;
    for (int i=1; i<=n; i++)
    {
        if (i==maxpos) continue;
        int u=get_lcm(i,maxpos)/maxnum;
        b[i]=u;
    }
}

void print_ans(int n)
{
    cout<<"! ";
    for (int i=1; i<=n; i++) {
        cout<<b[swnmbr[i]];
        if (i!=n) cout<<" ";
    }
    cout<<endl;
}

int32_t main()
{
    for (int i=2; i<=200000; i++)
    {
        if (p[i]) continue;
        for (int j=i*i; j<=200000; j+=i)
        {
            p[j]=true;
        }
        primes.push_back(i);
    }
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        for (int i=1; i<=n; i++) {
            swnmb[i]=0;
            swnmbr[i]=0;
            b[i]=0;
        }
        for (int i=1; i<=n; i++) {
            swnmb[i]=i;
        }
        for (int i=1; i<=n*5; i++) {
            swap(swnmb[rnd()%n+1], swnmb[rnd()%n+1]);
        }
        for (int i=1; i<=n; i++) {
            swnmbr[swnmb[i]]=i;
        }
        if (n<100) {
            solve_quadric(n);
            print_ans(n);
            continue;
        }
        if (n<10000) {
            solve_pair(n);
            print_ans(n);
            continue;
        }
        int t1=0;
        int t2=0;
        int pos1=0;
        int pos2=0;
        for (int i=1; i<=4000; i++)
        {
            int i1=rnd()%n+1;
            int i2=rnd()%n+1;
            while (i1 == i2) {
                i2=rnd()%n+1;
            }
            vector<int> f=fact(get_lcm(i1,i2));
            if (f.size()==2&&f[0]>500&&f[1]>500)
            {
                bool first1=true;
                bool first2=true;
                for (int j=0; j<100; j++)
                {
                    int t=rnd()%n+1;
                    while (t==i1||t==i2)
                    {
                        t=rnd()%n+1;
                    }
                    if (get_lcm(i1,t)%f[0]!=0)
                    {
                        first1=false;
                        break;
                    }
                }
                for (int j=0; j<100; j++)
                {
                    int t=rnd()%n+1;
                    while (t==i1||t==i2)
                    {
                        t=rnd()%n+1;
                    }
                    if (get_lcm(i1,t)%f[1]!=0)
                    {
                        first2=false;
                        break;
                    }
                }
                if (first1&&first2)
                {
                    bool second1=true;
                    for (int j=0; j<100; j++)
                    {
                        int t=rnd()%n+1;
                        while (t==i1||t==i2)
                        {
                            t=rnd()%n+1;
                        }
                        if (get_lcm(i2,t)%f[1]!=0)
                        {
                            second1=false;
                            break;
                        }
                    }
                    if (second1)
                    {
                        t2=f[0]*f[1];
                        t1=f[0];
                    }
                    else
                    {
                        t2=f[0]*f[1];
                        t1=f[1];
                    }
                    pos1=i2;
                    pos2=i1;
                }
                else
                {
                    if (!first1)
                    {
                        t1=f[1];
                        t2=f[0];
                    }
                    else
                    {
                        t1=f[0];
                        t2=f[1];
                    }
                    pos1=i1;
                    pos2=i2;
                }
                b[pos1]=t1;
                b[pos2]=t2;
                int posf=0;
                int maxf=0;
                for (int j=1; j<=n; j++)
                {
                    if (j==i1||j==i2) continue;
                    int u=get_lcm(pos1,j);
                    if (u/t1>500)
                    {
                        b[j]=u/t1;
                        if (is_prime(b[j]))
                        {
                            if (b[j]>maxf)
                            {
                                maxf=b[j];
                                posf=j;
                            }
                        }
                    }
                }
                for (int j=1; j<=n; j++)
                {
                    if (b[j]!=0) continue;
                    b[j]=get_lcm(posf,j)/b[posf];
                }
                break;
            }
        }
        print_ans(n);
    }
}