好难...

Problem

话说 Nan 在海边等人，预计还要等上 M 分钟。为了打发时间，他玩起了石子。Nan 搬来了 N 堆石子，编号为 1 到 N，每堆

包含 Ai 颗石子。每 1 分钟，Nan 会在编号在 [Li,Ri] 之间的石堆中挑出任意 Ki 颗扔向大海（好疼的玩法），如果 [Li,R

i] 剩下石子不够 Ki 颗，则取尽量地多。为了保留扔石子的新鲜感，Nan 保证任意两个区间 [Li,Ri] 和[Lj,Rj]，不会

存在 Li<=Lj&Rj<=Ri 的情况，即任意两段区间不存在包含关系。可是，如果选择不当，可能无法扔出最多的石子，

这时 NN 就会不高兴了。所以他希望制定一个计划，他告诉你他 m 分钟打算扔的区间 [Li,Ri] 以及 Ki。现在他想你告诉

他，在满足前 i - 1 分钟都取到你回答的颗数的情况下，第 i 分钟最多能取多少个石子。

Solution

什么鬼输入...

考虑一个询问向一个区间连边，要求一个询问每次都得到一个能得到完备匹配的最大值。

显然这个最大值也许可以考虑二分或计算得到，现在问题在于如何验证是否存在完备匹配。

我们考虑霍尔定理。霍尔定理是原询问的一个子集，但此处不用。

我们假设将原询问右端点从小到大排序，对于询问的任意一个区间查看是否满足霍尔定理即可。
因为假设我们对于任意两个不相交区间询问，显然我们只需分别查看两个不相交区间是否符合条件即可。

那么问题在于我们怎么快速得知任意区间是否满足霍尔定理。

考虑维护石子个数前缀和 $A_i$，令排序后询问选择的个数前缀和为 $B_i$。令询问 $i$ 询问石子的区间为 $[L_i,R_i]$。

则对于任意 $i\leq j$，存在：
$$ B_j-B_{i-1} \le A_{R_j} - A_{L_i-1}$$
整理得：
$$ B_j-A_{R_j}\leq B_{i-1}-A_{L_i-1}$$

我们令 $C_i=B_i-A_{R_i},D_i=B_{i-1}-A_{L_i-1}$，则化为对于任意 $i\leq j$，存在：
$$C_j \leq D_i$$

考虑这次选择的石子数 $b_x=y$。那么对于 $C_x$ 到 $C_m$ 和 $D_{x+1}$ 到 $D_m$ 会整体加 $y$。

则由于 $j\geq i$，所以存在有 $j \in [x,m], i \in [1, x], C_j+y\leq D_i$。

所以有 $y\leq min(D_i-C_j)$。因此查询 $[x,m]$ 中 $C_j$ 的最大值和 $[1,x]$ 中 $D_i$ 的最小值即可。

感谢我一上午总算看懂了题解（里面虽然写错了一点）

PS: 无需去除没被覆盖过的石子。
由于这只会让前缀和变得更大，因此会影响到两个不相交区间的询问判断（更可能符合霍尔定理），但事实上我们也会分解成两个相交区间的询问，所以我们可以直接（也确实会）忽略掉这类被影响的询问。

Code

// Code by ajcxsu
// Problem: stone

#include<bits/stdc++.h>
using namespace std;

const int N=4e5+10;
int a[N], S[N];

struct Query { int l, r, k, t; } q[N];
bool cmp(const Query &a, const Query &b) { return a.r<b.r; }
int idx[N];
bool cmp2(const int &a, const int &b) { return q[a].t<q[b].t; }

#define ls x<<1
#define rs x<<1|1
int C[N<<3], D[N<<3], lazyc[N<<3], lazyd[N<<3];
void pud(int x) {
    if(lazyc[x])
        C[ls]+=lazyc[x], C[rs]+=lazyc[x], lazyc[ls]+=lazyc[x], lazyc[rs]+=lazyc[x];
    if(lazyd[x])
        D[ls]+=lazyd[x], D[rs]+=lazyd[x], lazyd[ls]+=lazyd[x], lazyd[rs]+=lazyd[x];
    lazyc[x]=lazyd[x]=0;
}
void build(int x, int l, int r) {
    if(l==r) {  C[x]=-S[q[l].r], D[x]=-S[q[l].l-1]; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    C[x]=max(C[ls], C[rs]), D[x]=min(D[ls], D[rs]);
}
void updata(int x, int l, int r, int xl, int xr, int w, int t) {
    pud(x);
    if(xl<=l && r<=xr) { C[x]+=t?w:0, D[x]+=!t?w:0, lazyc[x]+=t?w:0, lazyd[x]+=!t?w:0; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr, w, t);
    if(xr>mid) updata(rs, mid+1, r, xl, xr, w, t);
    C[x]=max(C[ls], C[rs]), D[x]=min(D[ls], D[rs]);
}
int queryc(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return C[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return queryc(ls, l, mid, xl, xr);
    else if(xl>mid) return queryc(rs, mid+1, r, xl, xr);
    else return max(queryc(ls, l, mid, xl, mid), queryc(rs, mid+1, r, mid+1, xr));
}
int queryd(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return D[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return queryd(ls, l, mid, xl, xr);
    else if(xl>mid) return queryd(rs, mid+1, r, xl, xr);
    else return min(queryd(ls, l, mid, xl, mid), queryd(rs, mid+1, r, mid+1, xr));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, x, y, z, p;
    cin>>n>>x>>y>>z>>p;
    for(int i=1;i<=n;i++) a[i]=((i-x)*(i-x)+(i-y)*(i-y)+(i-z)*(i-z))%p, S[i]=a[i]+S[i-1];
    int m;
    cin>>m>>q[1].k>>q[2].k>>x>>y>>z>>p;
    if(!m) exit(0);
    for(int i=3;i<=m;i++) q[i].k=(x*q[i-1].k+y*q[i-2].k+z)%p;
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r, q[i].t=i, idx[i]=i;
    sort(q+1, q+1+m, cmp), sort(idx+1, idx+1+m, cmp2), build(1, 1, m);
    int b;
    for(int i=1;i<=m;i++) {
        b=min(queryd(1, 1, m, 1, idx[i])-queryc(1, 1, m, idx[i], m), q[idx[i]].k);
        updata(1, 1, m, idx[i], m, b, 1);
        if(idx[i]+1<=m) updata(1, 1, m, idx[i]+1, m, b, 0); // 注意...
        cout<<b<<endl;
    }
    return 0;
}