人生不过一场呼吸。呼吸不停，则生命与思考不止。

绝世难题。

题意

给出一个

1\sim n

的排列

a_1, \ldots, a_n

和常数

k

，保证

1 \le k \le n

。

q

次查询，每次查询给出区间

[l,r]

和

x

（保证

1 \le l \le r \le n

且

1 \le x \le n

），若一个区间长度 $\ge k$ 且中位数 $\ge x$ ，则称这个区间是好区间。求只保留

a_l, \ldots, a_r

时，有多少个好区间满足其不包含任何一个其他的好区间。

中位数：定义长为

\mathit{len}

的序列的中位数为升序排序后第

\bigl\lfloor\frac{\mathit{len}}{2}\bigr\rfloor +1

个数。

多测，

T\le 6

，

n,q\le 10^5

。

一个经典的转化是，对于一个数

m

，将序列中

< m

的位置赋成

-1

，

\ge m

的位置赋成

1

，则中位数

\ge x

等价于序列的和

\ge 0

。

显然一个右端点至多有一个对应的左端点，并且是最靠右的那个。接下来是一些记号：

$A(i,x)=(-1)^{[a_i<x]}$ 。容易注意到对于一个 $i$ 而言， $A(i,x)$ 随着 $x$ 的增大不升。
$s(i,x)=\sum\limits_{j=1}^iA(j,x)$ 。
$S(l,r,x)=\sum\limits_{i=l}^rA(i,x)=s(r,x)-s(l-1,x)$ 。
$f(i,x)$ 表示最大的 $j$ 使得 $[j,i]$ 这个区间的中位数 $\ge x$ 且长度 $\ge k$ ，即最大的 $j\le i-k+1$ 使得 $S(j,i,x)\ge 0$ 。容易注意到对于一个 $i$ 而言， $f(i,x)$ 随着 $x$ 的增大不升。

那么对于一个

x

，一个区间

[f(i,x),i]

合法当且仅当不存在

j<i

使得

[f(j,x),j]\sube [f(i,x),i]

。我们称之为区间

[f(j,x),j]

支配了区间

[f(i,x),i]

，简称在

x

时刻

j

支配了

i

。

观察 $1$ ：若对于 $x$ 和 $i$ ，存在 $j<i$ 使得 $[f(j,x),j]\sube [f(i,x),i]$ ，则 $[f(j,x+1),j]\sube [f(i,x+1),i]$ 。保证 $f(i,x+1)$ 存在。

证明

1

首先，若

f(i,x+1)

存在，那么

f(j,x+1)

也一定存在。考虑此时

f(i,x+1)\le f(i,x)\le f(j,x)\le j

，说明

S(j+1,i,x+1)<0

。那么对于任意

p\in [1,j]

，均满足

S(p,j,x+1)>S(p,i,x+1)

。因此

S(f(i,x+1),j,x+1)>0

。故

f(j,x+1)

存在。

同时从上面我们可以看到，

f(j,x+1)\ge f(i,x+1)

。因此有

[f(j,x+1),j]\sube [f(i,x+1),i]

。

观察

1

告诉我们，在某一个

x

的时候，若

j

能支配

i

，那么在比

x

大且

i

合法的时刻中，

j

仍然支配

i

。那么在

x

之后，这个

i

就不会再产生贡献。

而显而易见的是每个

i\ge k

的位置

i

在

1

时刻都是合法的。因此，对于一个 $i$ 而言，它能产生贡献的 $x$ 形如一个前缀。考虑对于每个

i

找到其对应的前缀

[1,P_i]

。

先考虑如何判定

i

能否对一个固定的

x

产生贡献。找到最大的

j<i

使得

[f(j,x),j]

合法。此时我们要求

f(i,x)>f(j,x)

。那么就是要让

i

不被

j

支配。由于

j

合法所以不用考虑

i

被更小的右端点支配。这样会产生两种情形。

情形

1

：

S(j+1,i,x)>0

。

此时

i

一定不会被

j

支配。因为你考虑

S(f(j,x)+1,i)\ge 0

，且

i-f(j,x)\ge k

。

情形

2

：

S(j+1,i,x)\le 0

。

考虑在这种情形下怎样才能使得

f(j,x)< f(i,x)

。若

f(i,x)>j

则一定满足。否则，

f(j,x)<f(i,x)\le j

。注意到此时对于任意

p\in [1,j]

，有

S(p,j,x)\ge S(p,i,x)

，因此

S(f(i,x),j)\ge 0

。然而

f(i,x)

对于

j

来说不合法，只能是因为其不满足长度限制，即

j-f(i,x)+1<k

。此时可以得到

j-k+1<f(i,x)\le i-k+1

。

所以我们只需要在这个范围内寻找合法的

f(i,x)

即可。上文这样推过来得出的是必要性，反过来容易说明充分性。

考虑对于一个固定的

x

怎样维护。从左往右扫描序列，记

i

左边第一个合法位置为

j_x

，维护

w_x=s(i,x)+\max\limits_{p=\max\{0,j_x-k+1\}}^{i-k}(-s(p,x))

，

t_x=s(i,x)-s(j_x,x)

，

h_x=s(i,x)-s(i-k,x)

。当

i-1\rightarrow i

时发生的变化是

t_x\leftarrow t_x+A(i,x)

，

w_x\leftarrow w_x+A(i,x)

，

h_x\leftarrow h_x+A(i,x)-A(i-k,x)

。如果

i\ge k

还要令

w_x\leftarrow \max\{w_x,h_x\}

。只要

w_x\ge 0

或

t_x\ge 0

成立

i

就合法。如果

i

合法，就要令

j_x\leftarrow i

，相应的

w_x\leftarrow -\infty

，

t_x\leftarrow 0

。注意判断

t_x\ge 0

时还应满足

i\ge k

。判断

w_x\ge 0

时不需要这样做因为保证了

i<k

时

w_x=-\infty

。

现在考虑扫描序列的过程中对于所有

x

一起维护。先用

\mathcal{O}(1)

次区间操作刻画右移时各个量的变化，再线段树二分找到最大的

y

使得

w_{y}\ge 0

或

t_y\ge 0

。然后对于

[1,y]

这个范围内的

x

要令

j_x\leftarrow i

，也要使用

\mathcal{O}(1)

次区间操作刻画。容易使用线段树维护上述操作。

维护方法

其实不是很容易。讲一下如何构造双半群信息。

先考虑

w_x

以及与之相关的

h_x

怎样维护。我们要支持的是：

区间 $h_x$ 加 $v$ 。
区间 $w_x$ 加 $v$ 。
区间 $w_x\leftarrow \max\{w_x,h_x\}$ 。

考虑设计信息二元组

(w,h)

，标记三元组

(x,y,z)

。定义：

信息之间的运算： $(w_1,h_1)\oplus (w_2,h_2)=(\max\{w_1,w_2\},\max\{h_1,h_2\})$ 。
信息与标记之间的运算： $(w,h)\otimes (x,y,z)=(\max\{w+x,h+y\},h+z)$ 。

那么三种操作都可以用信息和标记之间的运算刻画。

容易证明

\otimes

对

\oplus

有分配律。接下来要构造标记之间的运算

\circ

，满足

(w,h)\otimes (x,y,z)\otimes (u,v,w)=(w,h)\otimes ((x,y,z)\circ (u,v,w))

。

手推一下可以发现构造

(x,y,z)\circ (u,v,w)=(x+u,\max\{y+u,z+v\},z+w)

即可。

那么就可以使用带懒标记的线段树维护了。

t_x

的双半群构造方式是类似的。

使用上述方法倒着扫一遍序列可以得到每个左端点的存在前缀。而对于一个时刻而言合法的区间一定是左右端点从小到大依次匹配过去。按照

x

从小到大扫描线，用树状数组维护不超过

v

的左端点个数和右端点个数，查询询问区间端点对应的值就可以得到最左边合法区间的排名

L

和最右边合法区间的排名

R

，答案就是

R-L+1

。注意要判断不存在的情况。

认为

n,q

同阶，时间复杂度

\mathcal{O}(Tn\log n)

，空间复杂度

\mathcal{O}(n)

。封装了一个双半群线段树，所以常数巨大。

一份常数巨大但是比较简洁的实现

CPP

#include <bits/stdc++.h>
#define eb emplace_back
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; c < 48 || c > 57; c = getchar()) if (c == '-') f = -1;
    for (; c > 47 && c < 58; c = getchar()) x = (x << 3) + (x << 1) + c - 48;
	x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
using namespace std; using ll = long long; const int N = 100005, I = -1e9;
int n, k, q, a[N], T, tl[N], tr[N], ans[N];
vector<tuple<int, int, int>> g[N]; vector<int> vl[N], vr[N];
struct M {
	ll x, y, z; M(ll X = 0, ll Y = I, ll Z = 0) { x = X; y = Y; z = Z; }
	M operator*(const M &_) const {
		return M(x + _.x, max(y + _.x, z + _.y), z + _.z);
	}
};
struct D {
	ll h, s; D(ll H = I, ll S = 0) { h = H; s = S; }
	D operator+(const D &_) const { return D(max(h, _.h), max(s, _.s)); }
	D operator*(const M &_) const { return D(max(h + _.x, s + _.y), s + _.z); }
};
struct X {
	ll x, y; X(ll a = 0, ll b = I) { x = a; y = b; }
	X operator*(const X &_) const { return X(x + _.x, max(y + _.x, _.y)); }
};
struct Y {
	ll h; Y(ll x = 0) { h = x; }
	Y operator+(const Y &_) const { return Y(max(h, _.h)); }
	Y operator*(const X &_) const { return Y(max(h + _.x, _.y)); }
};
template<class D, class M> struct SEG {
	D s[N << 2]; M t[N << 2];
	int ls(int x) { return x << 1; } int rs(int x) { return x << 1 | 1; }
	void C(int x, M v) { s[x] = s[x] * v; t[x] = t[x] * v; }
	void P(int x) { C(ls(x), t[x]); C(rs(x), t[x]); t[x] = M(); }
	void B(int x, int l, int r, D e) {
		t[x] = M(); if (l == r) return void(s[x] = e); int m = l + r >> 1;
		B(ls(x), l, m, e); B(rs(x), m + 1, r, e); s[x] = s[ls(x)] + s[rs(x)];
	}
	void U(int x, int l, int r, int ql, int qr, M v) {
		if (ql > qr) return; if (ql <= l && r <= qr) return C(x, v);
		int m = l + r >> 1; P(x); if (ql <= m) U(ls(x), l, m, ql, qr, v);
		if (qr > m) U(rs(x), m + 1, r, ql, qr, v); s[x] = s[ls(x)] + s[rs(x)];
	}
	int Q(int x, int l, int r, int v) {
		if (s[x].h < v) return 0;
		if (l == r) return l; int m = l + r >> 1; P(x);
		return s[rs(x)].h < v ? Q(ls(x), l, m, v) : Q(rs(x), m + 1, r, v);
	}
}; SEG<D, M> t1; SEG<Y, X> t2;
struct BIT {
	int a[N]; void C() { memset(a, 0, sizeof a); }
	void U(int x, int v) { for (; x <= n; x += x & -x) a[x] += v; }
	void U(int l, int r, int v) { U(l, v); U(r + 1, -v); }
	int Q(int x) { int r = 0; for (; x; x -= x & -x) r += a[x]; return r; }
} t3, t4;
void work(int *b) {
	t1.B(1, 1, n, D()); t2.B(1, 1, n, Y());
	for (int i = 1; i <= n; ++i) {
		t1.U(1, 1, n, 1, a[i], M(1, I)); t1.U(1, 1, n, a[i] + 1, n, M(-1, I));
		t1.U(1, 1, n, 1, a[i], M(0, I, 1));
		t1.U(1, 1, n, a[i] + 1, n, M(0, I, -1));
		if (i > k)
			t1.U(1, 1, n, 1, a[i - k], M(0, -1, -1)),
			t1.U(1, 1, n, a[i - k] + 1, n, M(0, 1, 1));
		if (i == k) t1.U(1, 1, n, 1, n, M(0, 0));
		t2.U(1, 1, n, 1, a[i], X(1)); t2.U(1, 1, n, a[i] + 1, n, X(-1));
		b[i] = t1.Q(1, 1, n, 0);
		if (i >= k) b[i] = max(b[i], t2.Q(1, 1, n, 1));
		t1.U(1, 1, n, 1, b[i], M(I)); t2.U(1, 1, n, 1, b[i], X(I, 0));
	}
}
void lzyqwq() {
	read(n); read(k); read(q); for (int i = 1; i <= n; ++i) read(a[i]);
	work(tr); reverse(a + 1, a + n + 1); work(tl); reverse(tl + 1, tl + n + 1);
	for (int i = 1; i <= n; ++i) vl[tl[i]].eb(i), vr[tr[i]].eb(i);
	for (int i = 1, l, r, x; i <= q; ++i)
		read(l), read(r), read(x), g[x].eb(l, r, i);
	for (int i = n; i >= 1; --i) {
		for (int j : vl[i]) t3.U(j + 1, n, 1); vl[i].clear();
		for (int j : vr[i]) t4.U(j, n, 1); vr[i].clear();
		for (auto [l, r, j] : g[i]) ans[j] = max(t4.Q(r) - t3.Q(l), 0);
		g[i].clear();
	}
	for (int i = 1; i <= q; ++i) print(ans[i]); t3.C(); t4.C();
}
int main() { for (read(T); T--;) lzyqwq(); return 0; }

人生不过一场呼吸。呼吸不停，则生命与思考不止。

文章操作

相关推荐

评论

人生不过一场呼吸。呼吸不停，则生命与思考不止。