显然我们只关心能获奖的取球方案，不妨先令询问 $L=0,R=n-1$。

二分答案求是否能取 $K$ 轮，若存在 $x_i+y_i<K$ 显然无解。

假设最终方案中袋 $i$ 取了 $a_i$ 个红球，那么有 $mn_i \le a_i \le mx_i$，其中 $mn_i=\max(K-y_i,0),mx_i=\min(x_i,K)$。

问题转为给定 $mn_i \le mx_i$ 和初始为 0 的 $a_i$，需要进行 $K$ 次操作，每次选择 $\frac{n}{2}$ 个 $a_i$ +1，询问是否存在操作方案，使得最终 $\forall i,mn_i \le a_i \le mx_i$。

可以证明，存在操作方案等价于 $\sum mn_i \le \frac{nK}{2} \le \sum mx_i$，必要性易证，对于充分性，考虑若最终存在合法的 $a_i$，进行 $K$ 轮操作，每轮操作找 $\frac{n}{2}$ 次最大的 $a_i$ 并令其 -1，归纳可得 $K$ 轮操作后一定有 $a_i=0$，将 -1 的合法操作方案逆序即可得到 +1 的合法操作方案，又因为 $\sum mn_i \le \frac{nK}{2} \le \sum mx_i$，最终合法的 $a_i$ 是容易构造的。

那么可取 $K$ 轮等价于 $\sum \max(K-y_i,0) \le \frac{nK}{2} \le \sum \min(x_i,K)$，也即 $\frac{nK}{2} \le \min(\sum \min(x_i,K),\sum \min(y_i,K))$。

对 $x_i,y_i$ 建立权值线段树，即可 $O(\log^2{V})$ 地解决每次全局询问，注意到二分答案和权值树查询可以合并，线段树二分即可做到 $O(\log{V})$。

对于区间询问，建立主席树即可，总复杂度 $O((n+q)\log{V})$。

#include <bits/stdc++.h>
using namespace std;
namespace staring
{
    using LL = long long;
    using ULL = unsigned long long;
    #define fir first
    #define sec second

    #define FOR(i,a,b) for(int i = (a), i##E = (b); i <= i##E; i ++)
    #define ROF(i,a,b) for(int i = (a), i##E = (b); i >= i##E; i --)

    template <typename TYPE>
    int gmax(TYPE &x, const TYPE& y) {return x < y ? x = y, 1 : 0;}
    template <typename TYPE>
    int gmin(TYPE &x, const TYPE& y) {return y < x ? x = y, 1 : 0;}

    static constexpr int SIZE = 1 << 20;
    static char buffin[SIZE]{}, *pin1{}, *pin2{};
    static char buffout[SIZE]{}, *pout{buffout};
    #define GETC() (pin1 == pin2 && (pin2 = (pin1 = buffin) + fread(buffin, 1, SIZE, stdin), pin1 == pin2)? EOF : *pin1++)
    #define PUTC(c) (pout - buffout == SIZE && (fwrite(buffout, 1, SIZE, stdout), pout = buffout), (*pout++ = c))
    template <typename TYPE>
    void read(TYPE &x)
    {
        static int signf{0}, chin{0};
        x = signf = 0, chin = GETC();
        while(chin < '0' || chin > '9') signf |= chin == '-', chin = GETC();
        while(chin >= '0' && chin <= '9') x = (x << 3) + (x << 1) + (chin ^ 48), chin = GETC();
        if(signf) x = -x;
    }
    template <typename TYPE>
    void write(TYPE x, char ch = ' ')
    {
        static int stack[64]{}, top{0};
        !x && PUTC('0'), x < 0 && (x = -x, PUTC('-'));
        while(x) stack[top++] = x % 10, x /= 10;
        while(top) PUTC(stack[--top] | 48);
        if(ch) PUTC(ch);
    }

}using namespace staring;

using VEC  = vector <int>;
constexpr int N = 2e5 + 5, A = (1ll << 31) - 1;
constexpr int K = 20, M = N << 6;

int st[K][N];
int tot, rt[N], lc[M], rc[M];
LL sum[M][2], cnt[M][2];

#define mid (l + (r - l >> 1))

int ask(int l, int r)
{
    int k = __lg(r - l + 1);
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

void insert(int idx, int pre, int v, int k)
{
    auto copy = [&](int p, int q)
    {
        lc[p] = lc[q], rc[p] = rc[q];
        sum[p][!k] = sum[q][!k], cnt[p][!k] = cnt[q][!k];
        sum[p][k] = sum[q][k] + v, cnt[p][k] = cnt[q][k] + 1;
    };

    int p = ++tot, q = rt[pre], l = 0, r = A;
    rt[idx] = p, copy(p, q);
    while(l < r)
    {
        if(v <= mid)
            lc[p] = ++tot, p = lc[p], q = lc[q], r = mid;
        else rc[p] = ++tot, p = rc[p], q = rc[q], l = mid + 1;
        copy(p, q);
    }
}

void init(int n, int q, VEC x, VEC y)
{
    FOR(i, 1, n)
    {
        st[0][i] = x[i - 1] + y[i - 1];
        insert(i, i - 1, x[i - 1], 0);
        insert(i, i, y[i - 1], 1);
    }

    FOR(j, 1, K - 1)
        FOR(i, 1, n - (1 << j) + 1)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}

int max_prize(int L, int R)
{
    ++L, ++R;
    int p = rt[R], q = rt[L - 1], l = 0, r = A, maxk = ask(L, R);
    LL len = R - L + 1 >> 1, xsum = 0, xcnt = 0, ysum = 0, ycnt = 0;
    int res = 0;

    while(l < r)
        if(mid <= maxk
        && xsum + sum[lc[p]][0] - sum[lc[q]][0] + (xcnt + cnt[rc[p]][0] - cnt[rc[q]][0]) * mid >= len * mid
        && ysum + sum[lc[p]][1] - sum[lc[q]][1] + (ycnt + cnt[rc[p]][1] - cnt[rc[q]][1]) * mid >= len * mid)
        {
            res = mid;
            if(maxk == mid) break;
            xsum += sum[lc[p]][0] - sum[lc[q]][0], ysum += sum[lc[p]][1] - sum[lc[q]][1];
            p = rc[p], q = rc[q], l = mid + 1;
        }
        else
        {
            xcnt += cnt[rc[p]][0] - cnt[rc[q]][0], ycnt += cnt[rc[p]][1] - cnt[rc[q]][1];
            p = lc[p], q = lc[q], r = mid;
        }
    
    return res;
}