前置「Hall定理」

二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W)

题解

由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到
$$
\begin{aligned}
sum[l, r] &\le (r - l + 1 + d) \cdot k \\
sum[l, r] - (r - l +1) \cdot k &\le d \cdot k
\end{aligned}
$$
那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$

那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>

#define lson root << 1
#define rson root << 1 | 1

using namespace std;

typedef long long LL;

const int MAXN = 5e05 + 10;

int limit, N, k, d;

LL subsum[MAXN << 2]= {0};
LL lmax[MAXN << 2]= {0}, rmax[MAXN << 2]= {0};
LL sumax[MAXN << 2]= {0};
void maintain (int root) {
	subsum[root] = subsum[lson] + subsum[rson];
	lmax[root] = max (lmax[lson], subsum[lson] + lmax[rson]);
	rmax[root] = max (rmax[rson], rmax[lson] + subsum[rson]);
	sumax[root] = max (sumax[lson], max (sumax[rson], rmax[lson] + lmax[rson]));
}
void build (int root, int left, int right) {
	if (left == right) {
		subsum[root] = lmax[root] = rmax[root] = sumax[root] = - k;
		return ;
	}
	int mid = (left + right) >> 1;
	build (lson, left, mid), build (rson, mid + 1, right);
	maintain (root);
}
void modify (int root, int left, int right, int posi, int delta) {
	if (left == right) {
		subsum[root] += delta;
		lmax[root] += delta, rmax[root] += delta;
		sumax[root] += delta;
		return ;
	}
	int mid = (left + right) >> 1;
	posi <= mid ? modify (lson, left, mid, posi, delta) : modify (rson, mid + 1, right, posi, delta);
	maintain (root);
}

int getnum () {
	int num = 0;
	char ch = getchar ();
	bool isneg = false;

	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return isneg ? - num : num;
}

int main () {
	limit = getnum (), N = getnum (), k = getnum (), d = getnum ();
	build (1, 1, limit);
	for (int i = 1; i <= N; i ++) {
		int posi = getnum (), delta = getnum ();
		modify (1, 1, limit, posi, delta);
		LL deal = sumax[1];
		deal <= 1ll * k * d ? puts ("TAK") : puts ("NIE");
	}

	return 0;
}

/*
4 4 2 1
1 3
2 3
3 3
2 -1
*/