有nn堆石子，第ii堆有aia_i个

mm次操作(l,r,k)(l, r, k)，每次你需要从[l,r][l, r]堆中取出尽量多石子，且总共不能超过kk个，问每次最多能取多少个

注意，第ii次操作是建立在第11到i−1i-1次都取到你回答的个数下，即询问不是相互独立的

保证任意[l,r][l, r]不存在包含关系

n≤4×104,ai≤500n\le 4\times 10^4, a_i\le 500

BZOJ2138

Solution

如果暴力把每个点拆成aia_i个，每个询问拆成kik_i个，那么可以转化成二分图最大匹配的模型

考虑Hall定理：枚举XX的任意子集，看它在YY集合的相邻节点数量是否大于等于子集大小

暴力考虑子集显然不行，但是由于[l,r][l, r]互不包含，所以只需要考虑所有连续的区间，而不必考虑集合

若两个区间相交，那么显然没问题

若两个区间不交，那它们连到对面的边也不交，是完全独立的

设S[i,j]S[i, j]表示∑k=ijak\sum_{k=i}^{j}a_k，T[i,j]T[i,j]表示所有被区间[i,j][i, j]包含的子区间需要的石子数之和

SS就是一开始的aa构成的，而TT是随着操作而动态变化的

那么若某个状态合法，则需要满足∀i,j,S[i,j]≥T[i,j]\forall i, j, S[i, j] \ge T[i, j]

令TL[i]TL[i]表示左端点∈[1,i]\in [1, i]的所有区间的石子数之和，TR[i]TR[i]表示右端点∈[1,i]\in[1, i]的所有区间的石子数之和

因为区间互不包含，所以T[i,j]=TR[j]−TL[i−1]T[i, j] = TR[j] - TL[i - 1]

那么有S[j]−S[i−1]≥TR[j]−TL[i−1]S[j] - S[i - 1] \ge TR[j] - TL[i - 1]

即S[j]−TR[j]≥S[i−1]−TL[i−1]S[j] - TR[j] \ge S[i - 1] - TL[i - 1]

令f[i]=S[i]−TR[i],g[i]=S[i]−TL[i]f[i] = S[i] - TR[i], g[i] = S[i] - TL[i]，那么有f[i]≥g[i]f[i] \ge g[i]

考虑当前这次操作[l,r][l, r]，如果它要合法，则∀i<l,j≥r\forall i < l, j\ge r，都有f[j]≥g[i]f[j] \ge g[i]。即mini=rnfi≥maxi=1l−1gi\displaystyle \min_{i=r}^{n}f_i \ge \max_{i=1}^{l-1}g_i

所以这个区间的答案就是min{k,mini=rnfi−maxi=1l−1gi}\displaystyle \min\{k, \min_{i=r}^{n}f_i - \max_{i=1}^{l-1}g_i\}

用线段树维护一下minf,maxg\min f, \max g即可

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 40000 + 100;

inline LL sqr (LL x) { return x * x; }

int N, M;
int A[Maxn];

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
	struct info
	{
		LL f, g, tag_f, tag_g;
	} node[Maxn << 2];

	inline void push_up (int o)
	{
		node[o].f = min (node[ls].f, node[rs].f);
		node[o].g = max (node[ls].g, node[rs].g);
	}

	inline void push_f (int o)
	{
		LL &t = node[o].tag_f;
		if (!t) return ;
		node[ls].tag_f += t, node[rs].tag_f += t;
		node[ls].f += t, node[rs].f += t;
		t = 0;
	}

	inline void push_g (int o)
	{
		LL &t = node[o].tag_g;
		if (!t) return ;
		node[ls].tag_g += t, node[rs].tag_g += t;
		node[ls].g += t, node[rs].g += t;
		t = 0;
	}

	inline void push_down (int o) { push_f (o), push_g (o); }

	inline void build (int o, int l, int r)
	{
		if (l == r) return void (node[o].f = node[o].g = A[l]);
		build (lson), build (rson);
		push_up (o);
	}

	inline LL query_f (int o, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return node[o].f;
		push_down (o);
		LL ans = LLONG_MAX;
		if (x <= mid) Chkmin (ans, query_f (lson, x, y));
		if (y > mid) Chkmin (ans, query_f (rson, x, y));
		return ans;
	}

	inline LL query_g (int o, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return node[o].g;
		push_down (o);
		LL ans = 0;
		if (x <= mid) Chkmax (ans, query_g (lson, x, y));
		if (y > mid) Chkmax (ans, query_g (rson, x, y));
		return ans;
	}
	
	inline void update_f (int o, int l, int r, int x, int y, int val)
	{
		if (x <= l && r <= y) 
		{
			node[o].f += val, node[o].tag_f += val;
			return ;
		}
		push_down (o); 
		if (x <= mid) update_f (lson, x, y, val);
		if (y > mid) update_f (rson, x, y, val);
		push_up (o);
	}

	inline void update_g (int o, int l, int r, int x, int y, int val)
	{
		if (x <= l && r <= y) 
		{
			node[o].g += val, node[o].tag_g += val;
			return ;
		}
		push_down (o); 
		if (x <= mid) update_g (lson, x, y, val);
		if (y > mid) update_g (rson, x, y, val);
		push_up (o);
	}
#undef mid
}

LL K[Maxn];

inline void Solve ()
{
	SEG :: build (1, 0, N);
	for (int i = 1; i <= M; ++i)
	{
		int l = read<int>(), r = read<int>();
		LL now = max (0ll, min (K[i], SEG :: query_f (1, 0, N, r, N) - SEG :: query_g (1, 0, N, 1, l - 1)));
		printf("%lld\n", now);
		SEG :: update_f (1, 0, N, r, N, - now);
		SEG :: update_g (1, 0, N, l, N, - now);
	}
}

inline void Input ()
{
	N = read<int>();
	int x = read<int>(), y = read<int>(), z = read<int>(), P = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = A[i - 1] + (sqr (i - x) + sqr (i - y) + sqr (i - z)) % P;
	M = read<int>();
	K[1] = read<int>(), K[2] = read<int>(), x = read<int>(), y = read<int>(), z = read<int>(), P = read<int>();
	for (int i = 3; i <= M; ++i) K[i] = (x * K[i - 1] + y * K[i - 2] + z) % P;
}

int main()
{

#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}