警示后人（附数据生成器）

如果你的二分用的是形如 while(l < r) 的形式，那么请注意这个地方：

你的初始边界应该设为 r = R[i] + 1，否则当 r 二分到 r[i] 时，r[i]-r+1=1，这并不符合我们预期的 0。

而当将边界设为 r[i] + 1 时，如果当前块内不符合要求，会直接二分到 r[i] + 1，此时 r[i] - r + 1 = 0，就是我们要的答案。

这里是数据生成器，其中 n,q 为自定参数。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>

using namespace std;

int main()
{
    srand(time(0));
    int n = 5, q = 2;
    printf("%d %d\n", n, q);
    for(int i(1); i <= n; ++ i) printf("%d ", rand() % n);
    puts("");
    for(int i(1); i <= q; ++ i)
    {
        int flag = rand() % 2;
        if(flag == 1) printf("M ");
        else printf("A ");
        int a = rand() % n + 1, b = rand() % n + 1, c = rand() % n;
        if(a > b) swap(a, b);
        printf("%d %d %d\n", a, b, c);
    }
    return 0;
}

为了方便，我在生成器中将 a_i, C 的范围设置为 0 \le a_i, C < n。

以及以及一份 checker

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>

using namespace std;

int main()
{
    while(true)
    {
        system("data.exe>data.in");
        system("b.exe<data.in>b.out");
        system("std.exe<data.in>std.out");
        if(system("fc std.out b.out"))
        {
            puts("Wrong Answer");
            return 0;
        }
        else puts("Accepted");
    }
    return 0;
}