Try to consider such segments where $$$l \le \lfloor \frac{r}{2} \rfloor + 1$$$.

Now think about what to do if this condition is not satisfied.

#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();
    }
}

Try to consider small numbers, such as those consisting of three digits.

Now think about what the maximum number of digits can be in the optimal answer.

#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();
    }
}

Try to prove that the author's solution works for $$$O(k)$$$ for one test case.

Finding an answer consisting of one digit works in $$$O(k)$$$. Now let's see how long the loop takes to complete. Indeed, it is easy to see that once the pairs of indexes $$$(0,1)$$$, $$$(0,2)$$$, and $$$(1,2)$$$ are considered, an answer will always be found. This is so because in any number of three digits you can find an answer consisting of two digits (this was proved earlier). So this is equivalent to removing all but the first three digits, and then solving the problem for them (assuming that the length of the optimal answer is two).

Try to think of a way to search index pairs and a test such that this search works for $$$O(k^2)$$$ per test case.

Let's take the string \t{3737 \ldots 37} as a string. We will search pairs of indices in the following way: first we will search all pairs of indices with different parities, and then all pairs of indices with the same parity. It is easy to see that such a search will work for $$$O(k^2)$$$ for one test case, because all pairs of indices with different parity will give numbers $$$37$$$ and $$$73$$$, which are prime, and there are $$$O(k^2)$$$ such pairs.

Think about whether a suitable $$$k$$$ (such that $$$f(t) = f(w) \cdot k$$$) can be made small? What small $$$k$$$ is easy to multiply binary numbers by?

Such $$$k$$$ can be the numbers $$$0$$$, $$$1$$$, and $$$2$$$~--- multiplying by $$$0$$$ gives $$$0$$$, multiplying by $$$1$$$ leaves the number as is, and multiplying by $$$2$$$ adds a zero to the end. Think about how you can take advantage of this.

#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;
        }
    }
}

Think about how the problem would be solved if any other number system was chosen, given all the previous conditions (the string consists of the digits $$$0$$$ and $$$1$$$, the string contains at least one one).

The solution would not change in any way. In fact, in a number system with base $$$k$$$, adding a zero to the left side does not change the number (multiplication by $$$1$$$), but adding a zero to the right side increases the number $$$k$$$ times (multiplication by $$$k$$$).

Think about how the problem would be solved if the condition sounded like this: \textit{it is necessary that $$$f(t)$$$ is divisible by $$$f(w)$$$. There are at least one one in the array. Zero is divisible by all numbers, but no number is divisible by zero. Zero is not divisible by zero.}

In fact, the problem gets a little more complicated. For example, consider this test: \t{111000000}. In this case, we could not output $$$4$$$ $$$9$$$ $$$5$$$ $$$9$$$ because zero is not divisible by zero.

We will perform the old solution, but check that we are not trying to divide zero by zero (if we divide something by zero, we will swap the numbers). And if the answer is not found, then either the whole left half of the string consists of zeros, or the whole right half. Let the leftmost unit have position $$$p1$$$, and the rightmost unit ~--- position $$$p2$$$. Then in the first case you can output $$$1$$$ $$$p2$$$ $$$2$$$ $$$p2$$$, and in the second case~--- $$$p1$$$ $$$n$$$ $$$p1$$$ $$$n-1$$$.

It is not hard to see that such a solution will always find the answer.

In fact, we can solve the problem even simpler: when we meet zero in the left half, we additionally check whether there is at least one one among the characters on the right. If there is, we print the answer, otherwise we move on. Similarly, when we encounter zero in the right half, we additionally check if there is at least one one among the characters on the left. We can show that this solution will also always find the answer.

It is interesting that we have solved \textbf{a stronger version of the problem}, since the solution we obtained works correctly for the old problem as well.

Think about: how is the parity of the length of the segment and the parity of the number of elements to be removed related?

Think about how much and how the value of the sign-variable sum differs when only one element is removed, and when only its neighbor is removed.

Consider odd-length segments. Try to take small segments and for each element find out what the sign-variable sum will be after it is removed. After that you may notice something interesting.

#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";
            }
        }
    }
}

See the corresponding hints from Problem D1.

Consider how to quickly check the value of a sign-variable sum on a segment if you know that exactly one element is removed from it (and know the number of that element).

From the solution of Problem D1 it is clear that for any odd segment only one element has to be removed. Consider how to find such an element, based on the proof of its existence given above.

#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';
            }
        }
    }
}

Is there a solution with asymptotics $$$O(n + q)$$$ for a single test case?

To solve it, you will need to quickly (in O(1)) find the largest common prefix of two substring.

Take some small strings and try to build the largest increasing subsequence. Maybe there's something special about it.

Use dynamic programming.

#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';
    }
}

As far as I know, using trie, you can sort all substrings of a given string in $$$O(n^2)$$$. Also, as far as I know, in C++ programming language std::lower_bound works so fast that in an array of size $$$1.25 \cdot 10^7$$$ the same number of std::lower_bound operations is done in a little less than a second. It is also known that std::lower_bound can be used to write a search for the largest increasing subsequence in an array. The question is: can we use this to write a $$$O(n^2 \cdot log(n))$$$ solution that passes the tests?

Come up with a solution that uses $$$\frac{n \cdot (n-1)}{2}$$$ queries.

At $$$n < 100$$$, apply a solution that uses $$$\frac{n \cdot (n-1)}{2}$$$ queries. Now suppose $$$n \geq 100$$$. Come up with a solution that would use $$$\lceil\frac{3n}{2}rceil$$$ queries.

When $$$n < 10000$$$, apply a solution that uses $$$2n$$$ queries. Now suppose $$$n \geq 5000$$$. Most likely, in the $$$2n$$$ queries solution you come up with, you need to find the largest prime number on the segment. Think about it, do you really need the largest prime number? Maybe just enough large prime number would be enough? How can you find such a number?

Use probabilistic algorithms to find such a number. Use probabilistic algorithms to also make sure that you have found the right number.

Now use the prime number you have found to find the largest prime number. You will probably already know most of the numbers when you find it, and you can use the largest prime number to find the rest.

#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);
    }
}