题意
一共有 (n) 堆石子，每堆石子有一个数量 (a) ，你要进行 (m) 次操作，每次操作你可以在满足前 (i-1) 次操作的回答的基础上选择在 ([L_i,R_i]) 区间中拿走至多 (b) 颗石子，保证区间不存在包含关系，求每次你最多拿走多少颗石子。
(nle 4 imes 10^4)
分析
-
二分图匹配复杂度太高，考虑霍尔定理。
-
假设某次操作时我们已经知道了每次操作取走多少颗石子，我们选择判断的操作集合一定是按 (L) 排序之后连续的(因为能够选择的区间不相互包含)，根据霍尔定理可以得到：
[sumlimits_{i=l}^rb(i)lesumlimits_{i=L(l)}^{R(r)}a(i) ][sb(r)-sb(l-1)le sa(R(r))-sa(L(l)-1) ]其中 (sa,sb) 表示 (a,b) 的前缀和。
-
将位置相同的信息放到一起：
[sb(r)-sa(R(r))le sb(l-1)-sa(L(l)-1) ]记 (C(i)=sb(i)-sa(R(i)))，(D=sb(i-1)-sa(L(i)-1))。
-
按照时间顺序处理操作。记某次操作按照 (L) 排序后所处的位置为 (p) 。拿走石子影响的一定是跨越 (p) 的连续区间。查询 (p) 右边操作的 (C) 的最大值 (x) 和左边 (D) 的最小值 (y) ，由于要满足 (xle y) ，此次最多可以拿走 (y-x) 颗石子，这个可以用两棵线段树维护。
-
假设我们得到了这次的答案 (ans) ，维护 (C) 的线段树中 ([p,m]) 区间和维护 (D) 的线段树中 ([p+1,m]) 区间的 (sb) 都增加了 (ans) ，线段树区间修改即可。
-
总时间复杂度为 (O(nlogn))。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline void Max(T &a, T b){if(a < b) a = b;}
template <typename T> inline void Min(T &a, T b){if(a > b) a = b;}
const int N = 4e4 + 7;
int n, m;
int a[N], R[N], L[N], sa[N], k[N], tt[N], rk[N];
#define Ls o << 1
#define Rs (o << 1 | 1)
struct sgt {
int adv[N << 2], val[N << 2], id;
void st1(int o, int v) {
adv[o] += v;
val[o] += v;
}
void pushdown(int o) {
if(adv[o]) {
st1(Ls, adv[o]);
st1(Rs, adv[o]);
}
adv[o] = 0;
}
void pushup(int o) {
if(!id) val[o] = max(val[Ls], val[Rs]);
else val[o] = min(val[Ls], val[Rs]);
}
void build(int l, int r, int o) {
if(l == r) {
if(!id) val[o] = -sa[R[tt[l]]];
else val[o] = -sa[L[tt[l]] - 1];
return;
}int mid = l + r >> 1;
build(l, mid, Ls);
build(mid + 1, r, Rs);
pushup(o);
}
void modify(int L, int R, int l, int r,int o, int v) {
if(L > R) return;
if(L <= l && r <= R) {
st1(o, v);
return;
}
pushdown(o);int mid = l + r >> 1;
if(L <= mid) modify(L, R, l, mid, Ls, v);
if(R > mid) modify(L, R, mid + 1, r, Rs, v);
pushup(o);
}
int query(int L, int R, int l, int r, int o) {
if(L > R) return 0;
if(L <= l && r <= R) return val[o];
pushdown(o);int mid = l + r >> 1;
if(R <= mid) return query(L, R, l, mid, Ls);
if(L > mid) return query(L, R, mid + 1, r, Rs);
if(!id) return max(query(L, R, l, mid, Ls), query(L, R, mid + 1, r, Rs));
else return min(query(L, R, l, mid, Ls), query(L, R, mid + 1, r, Rs));
}
}t[2];
bool cmp(int a, int b) {
return L[a] < L[b];
}
int main() {
n = gi();
int x = gi(), y = gi(), z = gi(), P = gi();
rep(i, 1, n) {
a[i] = ((i - x) * (i - x) + (i - y) * (i - y) + (i - z) * (i - z)) % P;
sa[i] = sa[i - 1] + a[i];
}
m = gi(), k[1] = gi(), k[2] = gi(), x = gi(), y = gi(), z = gi(), P = gi();
if(!m) return 0;
rep(i, 3, m) {
k[i] = (x * k[i - 1] + y * k[i - 2] + z) % P;
}
rep(i, 1, m) L[i] = gi(), R[i] = gi();
rep(i, 1, m) tt[i] = i;
sort(tt + 1, tt + 1 + m, cmp);
rep(i, 1, m) rk[tt[i]] = i;
t[1].id = 1; t[0].build(1, m, 1); t[1].build(1, m, 1);
rep(i, 1, m) {
int a = t[0].query(rk[i], m, 1, m, 1), b = t[1].query(1, rk[i], 1, m, 1);
int ans = min(b - a, k[i]);
printf("%d
", ans);
t[0].modify(rk[i], m, 1, m, 1, ans);
t[1].modify(rk[i] + 1, m, 1, m, 1, ans);
}
return 0;
}