做法

我们先把所有的$A_i$按照$w_i$进行排序，可以发现答案肯定是小于等于$w_1 + n$、大于等于$w_1$的。所以我们先设$ans=w1$。接下来我们考虑剩下的$A_i(i∈(2,n))$序列如何对$ans$进行更新。由题，对于某个$i$，如果说$f_i+w_i \geq ans + 1$的话，那么就可以对答案进行更新。化简得$f_i \geq ans + 1 - w_i$。我们设$check(x)$为此时$A_i$的所有区间中$mex$小于$x$的区间数。易得$check(x)$是非严格单调函数。所以此不等式可以转换成$check(f_i) \geq check(ans + 1 - w_i)$,即$k \geq check(f_i) \geq check(ans + 1 - w_i)$，$k \geq check(ans + 1 - w_i)$。此时$ans$的值循环++，直到不满足条件再枚举下一个$A_i$ 接下来我们来讨论如何快速求出$check(x)$的值，可以使用双指针解决这个问题。对于每个右端点$r$，存在左端点$L$使得 $mex(0 \to L-1,r) \leq k,mex(L \to r,r) < k$，且$L$随$r$非严格单调递增。所以我们可以使用一个桶来维护每个数在$L \to r$间出现的次数。再用一个变量$cnt$来记录$ton[0,x-1]$间值不等于$0$的个数。当$cnt=mid$时代表在$A_{L \to r}$中包含$0 \to mid-1$中的所有数，此时左端点右移直至$cnt<mid$。如图

时间复杂度

每次$check$的时间复杂度为$Θ(n)$，因为$ans \leq w_1 + n$,所以$ans$最多加$n$次，内层while复杂度为$Θ(n)$，外层for循环的时间复杂度也为$Θ(n)$。所以综合的时间复杂度为$Θ(n*(n+n))=Θ(n²)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, a[N];
int ton[N], cnt;
struct node
{
    int k, w, m;
    unsigned long long seed;
} q[N];
int k, w, m;
bool cmp(node x, node y)
{
    if (x.w != y.w)
        return x.w > y.w;
    return x.m > y.m;
}
unsigned long long _rand(unsigned long long &seed)
{
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}
inline int check(int mid)
{
    memset(ton, 0, sizeof ton);
    int res = 0;
    cnt = 0;
    int l = 1, r = 1;
    for (; r <= n; r++)
    {
        if (ton[a[r]] == 0)
        {
            if (a[r] < mid)
            {
                cnt++;
                ton[a[r]]++;
                while (l <= r && cnt == mid)
                {
                    ton[a[l]]--;
                    if (ton[a[l]] == 0)
                        cnt--;
                    l++;
                }
            }
        }
        else
            ton[a[r]]++;
        res += r - l + 1;
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d%llu", &q[i].k, &q[i].w, &q[i].m, &q[i].seed);
    sort(q + 1, q + 1 + n, cmp);
    int ans = q[1].w;
    for (int i = 1; i <= n; i++)
    {
        k = q[i].k, w = q[i].w, m = q[i].m;
        unsigned long long se = q[i].seed;
        for (int j = 1; j <= n; j++)
        {
            a[j] = _rand(se) % q[i].m;
        }
        while (check(ans - w + 1) <= k)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}