【题目链接】
点击打开链接【思路要点】
将问题转化一下，每次询问时新建\(K_{i}\)个点向一个区间连边，要求删去最少的点使得剩下的二分图存在完美匹配，并保留没有被删去的点到下一个询问。根据Hall定理，如果我们能找到一系列点，使得它们的总数大于它们对应的区间并的长度（即石头总数），那么剩下的二分图将不存在完美匹配，反之则一定存在。显然，找到的区间的并如果多于一段是没有意义的，因此，我们认为找到的这一系列区间的并也是一个连续的区间。定义区间\([L,R]\)的权值为区间中的石头总数减去连出的区间被该区间完全包含的点的个数。考虑区间\([L,R]\)的权值，应当等于\(S_{R}-S_{L-1}+Sum-Vl_{L}-Vr_{R}\)，其中\(S\)表示一个前缀和数组，\(Sum\)是当前的总点数，\(Vl_{i}\)和\(Vr_{i}\)分别是因为区间左/右端点在\(i\)处，连出的区间不被该区间完全包含的点的数量（即由于左端点太靠右，导致不包含和右端点太靠左，导致不包含）。由于区间不相互包含，\(Vl_{i}\)和\(Vr_{i}\)不会将一个区间重复计算两次。因此，我们可以将左右端点相关的部分用一颗线段树维护，每次在线段树上选取最紧的限制，即最小值，再将新增的点对线段树的贡献加在对应区间上即可。时间复杂度\(O(NLogN)\)。【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 50005; template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct SegmentTree { struct Node { int lc, rc; int tag, Min; } a[MAXN * 2]; int root, size, n; void build(int &root, int l, int r) { root = ++size; a[root].Min = a[root].tag = 0; if (l == r) return; int mid = (l + r) / 2; build(a[root].lc, l, mid); build(a[root].rc, mid + 1, r); } void init(int x) { root = size = 0; n = x; build(root, 1, n); } void update(int root) { a[root].Min = min(a[a[root].lc].Min, a[a[root].rc].Min); } void pushdown(int root) { int tmp = a[root].tag; a[root].tag = 0; a[a[root].lc].tag += tmp; a[a[root].lc].Min += tmp; a[a[root].rc].tag += tmp; a[a[root].rc].Min += tmp; } void set(int root, int l, int r, int pos, int v) { if (l == r) { a[root].Min = v; return; } pushdown(root); int mid = (l + r) / 2; if (mid >= pos) set(a[root].lc, l, mid, pos, v); else set(a[root].rc, mid + 1, r, pos, v); update(root); } void set(int pos, int v) { set(root, 1, n, pos, v); } void add(int root, int l, int r, int ql, int qr, int v) { if (l == ql && r == qr) { a[root].Min += v; a[root].tag += v; return; } pushdown(root); int mid = (l + r) / 2; if (mid >= ql) add(a[root].lc, l, mid, ql, min(qr, mid), v); if (mid + 1 <= qr) add(a[root].rc, mid + 1, r, max(mid + 1, ql), qr, v); update(root); } void add(int l, int r, int v) { if (l > r) return; add(root, 1, n, l, r, v); } int query(int root, int l, int r, int ql, int qr) { if (l == ql && r == qr) return a[root].Min; pushdown(root); int mid = (l + r) / 2; int ans = INT_MAX; if (mid >= ql) ans = min(ans, query(a[root].lc, l, mid, ql, min(qr, mid))); if (mid + 1 <= qr) ans = min(ans, query(a[root].rc, mid + 1, r, max(mid + 1, ql), qr)); return ans; } int query(int l, int r) { return query(root, 1, n, l, r); } } LT, RT; int a[MAXN], s[MAXN], k[MAXN]; int n, m, x, y, z, P; int main() { read(n); read(x), read(y), read(z), read(P); for (int i = 1; i <= n; i++) { a[i] = ((i - x) * (i - x) % P + (i - y) * (i - y) % P + (i - z) * (i - z) % P) % P; s[i] = s[i - 1] + a[i]; } read(m), read(k[1]), read(k[2]); read(x), read(y), read(z), read(P); for (int i = 3; i <= m; i++) k[i] = (x * k[i - 1] + y * k[i - 2] + z) % P; LT.init(n), RT.init(n); for (int i = 1; i <= n; i++) { LT.set(i, -s[i - 1]); RT.set(i, s[i]); } int used = 0; for (int i = 1; i <= m; i++) { int ql, qr, ans; read(ql), read(qr); ans = min(LT.query(1, ql) + RT.query(qr, n) - used, k[i]); LT.add(ql + 1, n, ans); RT.add(1, qr - 1, ans); writeln(ans); used += ans; } return 0; }