[BZOJ2138]stone

Description

有 $n$ 堆石子,$m$ 次操作。第 $i$ 次操作是在 $[l, r]$ 这堆石子中选出至多 $k$ 个石子扔掉。问在保证前 $i - 1$ 次操作全部最优(即扔掉石子最多)的前提下,第 $i$ 次操作最多能扔出多少石子。

操作区间互不包含

设 $a _i$ 表第 $i$ 堆石子数目,则有:

$$
1 \le m \le n \le 40000, 1 \le a _i \le 500
$$

Solution

比较巧妙的一道题…

操作之间互有影响,说明这不是一道简单的数据结构题,处理起来很麻烦。

看到 $a _i$ 的数据范围比较小,先考虑建立一个二分图匹配的模型:左部为石子,每堆石子拆为 $a _i$ 个石子,右部为操作,每次操作都相当于加入了 $k$ 个右部节点,这些右部节点每个节点均向那些所属堆在 $[l, r]$ 之内的石子连边。

问题变为在前面匹配数量不变的情况下,当前这些新加节点所能匹配的最大数量。

网络流 + 线段树优化建边思博题这样复杂度太高了撑不住。

先想想前面的操作都能把其对应区间内石子全部扔掉的情况,也就相当于是完全匹配

看到这个东西应该有一个敏感度:Hall 定理!

如果不知道这里介绍一下:

Hall 定理:若二分图 $G = (S \cup T, E)$(不妨设 $|S| \le |T|$)满足任取 $S$ 子集 $X$ 均满足:对于与 $X$ 相邻(即与 $X$ 中节点有直接连边的 $T$ 部节点)的集合 $Y$,有 $|X| \le |Y|$,则二分图 $G$ 有完全匹配。

证明很简单:

考虑反证。假设存在一个满足上述条件的二分图,且其最大匹配非完全匹配。

那么左部肯定存在一个未匹配的点 $x$。根据 $|X| \le |Y|$,它至少和右部的一个点 $y$ 有连边。

若 $y$ 没匹配过,那么 $x$ 和 $y$ 可以匹配,矛盾。

若 $y$ 已有匹配,设 $y$ 和左边的 $z$ 点匹配,根据 $|X| \le |Y|$,点集 ${x, z}$ 与右边至少有两个点有连边,设除了 $y$ 之外的那个点为 $p$。

再对 $p$ 进行类似讨论,递归地得到一定会存在一条增广路。这与最大匹配的定义矛盾,故得证。

在这题里并不需要考虑子集,只需要考虑连续堆即可,反正每 $k$ 个右部节点都会向同样的石子连边。

回顾一下之前的话:

在保证前面完全匹配的情况下最优化当前答案。

也就是要在加入 $k$ 个右部节点之后任取左部区间(石子堆) $[i, j]$,均满足包含了这个区间 $[i, j]$ 的那些操作的 $k$ 的总和比其小。

记 $s _i$ 为右端点 $\le i$ 的操作的 $k$ 的和,$p _i$ 为左端点 $\le i$ 的操作的 $k$ 的和。

上述条件等价于:

$$
\forall 0 \le i < j \le n, \sum _{l = i} ^j a _i \ge s _j - p _{i - 1}
$$

记 $S _i$ 表示 $\sum \limits _{j = 1} ^i a _j$,则有:

$$
S _j - S _{i - 1} \ge s _j - p _{i - 1} \\
S _j - s _j \ge S _{i - 1} - p _{i - 1}
$$

再记 $f(i) = S _i - s _i, g(i) = S _i - p _i$,上式等价于

$$
\forall 0 \le i < j \le n, f(j) - g(i - 1) \ge 0
$$

留意 $f, g$ 是动态变化的。

再考虑当前增加了一个操作 $(l, r, k)$ 的影响。

注意:从此开始 $k$ 改变意义,变为满足条件的情况下当前操作最多能扔掉的石子数。可以看作只加入了这 $k$ 个右部节点,其他的直接删除,反正不会影响答案。

那么当前影响是:$\forall i \in [r, n], f(i) \gets f(i) - k$,$\forall i \in [l, n], g(i) \gets g(i) - k$。

由于仍要满足上面的那个式子,此时需要讨论几种 $i, j$ 取值情况,综合得到对 $k$ 的限制。

易知只有 $i \in [0, l - 1], j \in [r, n]$ 这部分根据 $k$ 的取值有可能变化。于是列出不等式:

$$
\forall i \in [0, l - 1], j \in [r, n], f(j) - g(i) - k \ge 0
$$

易得需满足 $k \le \min \limits_{j = r} ^n f(j) - \max \limits_{i = 0} ^{l - 1} g(i)$。显然取等号最优。

因为每次把那些剩下的右部节点直接删除,那么每次做完之后均为完全匹配,所以上述讨论一直成立。

于是用线段树维护 $f, g$ 即可,区间加和区间询问 $\min / \max$,$O(n \log n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-09-01 21:35
* FileName : wib.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>

typedef long long LL;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21 | 1)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[50];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0, flag = 1;
register char ch;
while (!isdigit(ch = getchar()))
if (ch == '-')
flag = -1;
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x * flag;
}

template <typename _INT>
inline void write(_INT x)
{
if (x < 0)
putchar('-'), x = -x;
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 4e4 + 2;
const int INF = 0x3F3F3F3F;

int n, m;
int a[maxN], K[maxN];

namespace SEG
{
typedef struct Node* ptr;

struct Node
{
int l, r;
int val, tag;
ptr lson, rson;

void* operator new(size_t size)
{
static char buf[int(1e8)], *p = buf;
return (p += size) - size;
}

Node() { }

Node(int _l, int _r) : l(_l), r(_r)
{ tag = 0; }

void Add(int addval)
{ this->tag += addval, this->val += addval; }

void Pushup_min()
{ Chkmin(this->val = this->lson->val, this->rson->val); }

void Pushup_max()
{ Chkmax(this->val = this->lson->val, this->rson->val); }

void Pushdown()
{
if (this->tag)
{
this->lson->Add(this->tag);
this->rson->Add(this->tag);
this->tag = 0;
}
}
};

int fg; // flag / f and g ? whatever
ptr f, g;

void Build(int l, int r, ptr& cur)
{
cur = new Node(l, r);
if (l == r)
{
cur->val = a[l];
return;
}
int mid = (l + r) >> 1;
Build(l, mid, cur->lson), Build(mid + 1, r, cur->rson);
fg ? cur->Pushup_max() : cur->Pushup_min();
}

void Add(int ql, int qr, int addval, ptr cur)
{
if (ql <= cur->l and cur->r <= qr)
{
cur->Add(addval);
return;
}
int mid = (cur->l + cur->r) >> 1;
cur->Pushdown();
if (ql <= mid)
Add(ql, qr, addval, cur->lson);
if (mid < qr)
Add(ql, qr, addval, cur->rson);
fg ? cur->Pushup_max() : cur->Pushup_min();
}

int Query(int ql, int qr, ptr cur)
{
if (ql <= cur->l and cur->r <= qr)
return cur->val;
int mid = (cur->l + cur->r) >> 1;
cur->Pushdown();
int res = fg ? -INF : INF;
if (ql <= mid)
fg ? Chkmax(res, Query(ql, qr, cur->lson))
: Chkmin(res, Query(ql, qr, cur->lson));
if (mid < qr)
fg ? Chkmax(res, Query(ql, qr, cur->rson))
: Chkmin(res, Query(ql, qr, cur->rson));
return res;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("wib.in", "r", stdin);
freopen("wib.out", "w", stdout);
#endif
n = read();
int x = read(), y = read(), z = read(), P = read();
for (int i = 1; i <= n; ++i)
a[i] = (LL(i - x) * (i - x) + (i - y) * (i - y) + (i - z) * (i - z)) % P;
for (int i = 1; i <= n; ++i)
a[i] += a[i - 1];
m = read();
K[1] = read(), K[2] = read(), x = read(), y = read(), z = read(), P = read();
for (int i = 3; i <= m; ++i)
K[i] = ((LL)x * K[i - 1] + (LL)y * K[i - 2] + z) % P;
SEG::fg = 0, SEG::Build(1, n, SEG::f);
SEG::fg = 1, SEG::Build(0, n, SEG::g);
for (int i = 1; i <= m; ++i)
{
int k = 0, l = read(), r = read();
SEG::fg = 0, k += SEG::Query(r, n, SEG::f);
SEG::fg = 1, k -= SEG::Query(0, l - 1, SEG::g);
Chkmin(k, K[i]);
write(k), putchar('\n');
SEG::fg = 0, SEG::Add(r, n, -k, SEG::f);
SEG::fg = 1, SEG::Add(l, n, -k, SEG::g);
}
return 0;
}