【Ynoi 2017】由乃打扑克

ProtectEMmm / 2024-09-02 / 原文

Luogu P5356 由乃打扑克

题意

给定一个长度为 $n$ 的序列 $a$。

有 $m$ 次操作：

查询区间 $[l,r]$ 中的第 $k$ 小。
区间 $[l,r]$ 加上 $k$。

数据范围与约定

$1 \le n,m \le 10^5$，$-2*10^4 \le k,a_i \le 2*10^4$。

题解

看到区间操作，首先考虑线段树。

对于操作 1 来说：外层二分答案，线段树套平衡树求区间排名可以做。

对于操作 2 来说：发现线段树不好进行 pushup。

所以把线段树从 $logn$ 层变成分块 $3$ 层即可。假设块长为 $S$，一共有 $B= \frac{N}{S}$ 块。

先来说操作 2。发现操作 2 在分块套平衡树上还是比较好做的。分两种情况讨论，整块和角块。

整块：块内打上一个 tag 即可，复杂度 $O(B)$。
角块：暴力重建这个块，复杂度 $O(SlogS)$。发现角块复杂度有点高，发现没必要每次都重建，之前已经是有序的了，被操作的部分整体也是有序的。所以可以直接合并两个有序序列，不需要使用平衡树了。merge 优化后复杂度 $O(S)$，因为我们 merge 的时候同时还要给原数组加上改变量，所以这里维护的是原数组的下标。

算下来总复杂度为 $O(B+S)$。

再来说操作 1。外层套一个二分，复杂度为 $logV$。这里有一个常数优化，先查询一下区间的最值，然后再在这个最值区间上二分，二分次数会少一些。因为块内已经有序了，块外可以暴力，所以代价是复杂度加上了 $O(B+S)$。二分的 check 需要块内查询。这里也分两种情况讨论，整块和角块。

整块：因为块内本身有序，块内二分即可，这里我使用了 upper_bound，复杂度 $O(BlogS)$。
角块：暴力，复杂度 $O(S)$。

算下来总复杂度为 $O(logV*(BlogS+S))$。

发现主要瓶颈在操作 1 上。求一下块长 $S$ 取多少时复杂度最低。代入后得到函数式 $f(S)=\frac{NlogS}{S}+S$ 。发现多了一个 $logS$ 很不好处理，考虑到 $S$ 的上界是 $N$ 后，放缩一下，变成 $f(S)=\frac{NlogN}{S}+S$，得出 $S=\sqrt{NlogN}$ 时复杂度最低。

然而，Ynoi 喜欢卡常。所以最后经过不断测试，发现 $S=\sqrt{NlogN}/4\approx 300$ 时代码跑得最快。当然每个人代码实现细节不一样常数也不一样，这个地方不一定以我的为准。

代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
/*====================*/
const int S = 300;
const int B = N / S + 10;
/*====================*/
const int INF = INT_MAX;
/*====================*/
int n, m, arr[N];
/*====================*/
int belong[N];
/*====================*/
int tree[N];
struct Block
{
	int l, r;
	int delta;
	Block(void)
	{
		l = r = 0; delta = 0;
	}
	void Maintain(int delta)
	{
		this->delta += delta;
	}
	static bool cmp_Maintain(const int& idx1, const int& idx2)
	{
		return arr[idx1] < arr[idx2];
	}
	void Maintain(int l, int r, int delta)
	{
		int idx1 = 0, idx2 = 0;
		static int temp1[N], temp2[N];
		for (int i = this->l; i <= this->r; ++i)
		{
			if (l <= tree[i] && tree[i] <= r)
			{
				arr[tree[i]] += delta;
				temp1[++idx1] = tree[i];
			}
			else
			{
				temp2[++idx2] = tree[i];
			}
		}
		merge(temp1 + 1, temp1 + idx1 + 1, temp2 + 1, temp2 + idx2 + 1, tree + this->l, cmp_Maintain);
	}
};
Block block[B];
/*====================*/
void Change(int l, int r, int delta)
{
	if (belong[l] == belong[r])
	{
		block[belong[l]].Maintain(l, r, delta);
	}
	else
	{
		block[belong[l]].Maintain(l, block[belong[l]].r, delta);
		for (int i = belong[l] + 1; i <= belong[r] - 1; ++i)
		{
			block[i].Maintain(delta);
		}
		block[belong[r]].Maintain(block[belong[r]].l, r, delta);
	}
}
void GetMinMaxVal(int l, int r, int& minval, int& maxval)
{
	if (belong[l] == belong[r])
	{
		for (int i = l; i <= r; ++i)
		{
			minval = min(minval, arr[i] + block[belong[i]].delta);
			maxval = max(maxval, arr[i] + block[belong[i]].delta);
		}
	}
	else
	{
		for (int i = l; i <= block[belong[l]].r; ++i)
		{
			minval = min(minval, arr[i] + block[belong[i]].delta);
			maxval = max(maxval, arr[i] + block[belong[i]].delta);
		}
		for (int i = belong[l] + 1; i <= belong[r] - 1; ++i)
		{
			minval = min(minval, arr[tree[block[i].l]] + block[i].delta);
			maxval = max(maxval, arr[tree[block[i].r]] + block[i].delta);
		}
		for (int i = block[belong[r]].l; i <= r; ++i)
		{
			minval = min(minval, arr[i] + block[belong[i]].delta);
			maxval = max(maxval, arr[i] + block[belong[i]].delta);
		}
	}
}
bool cmp_GetRank(const int& idx1, const int& idx2)
{
	return arr[idx1] + block[belong[idx1]].delta < arr[idx2] + block[belong[idx2]].delta;
}
int GetRank(int l, int r, int val)
{
	int res = 0;
	if (belong[l] == belong[r])
	{
		for (int i = l; i <= r; ++i)
		{
			res += ((arr[i] + block[belong[i]].delta) <= val);
		}
	}
	else
	{
		for (int i = l; i <= block[belong[l]].r; ++i)
		{
			res += ((arr[i] + block[belong[i]].delta) <= val);
		}
		arr[0] = val;
		for (int i = belong[l] + 1; i <= belong[r] - 1; ++i)
		{
			if (arr[tree[block[i].l]] + block[i].delta > val)
			{
				res += 0; continue;
			}
			if (arr[tree[block[i].r]] + block[i].delta <= val)
			{
				res += block[i].r - block[i].l + 1; continue;
			}
			res += upper_bound(tree + block[i].l, tree + block[i].r + 1, 0, cmp_GetRank) - (tree + block[i].l);
		}
		for (int i = block[belong[r]].l; i <= r; ++i)
		{
			res += ((arr[i] + block[belong[i]].delta) <= val);
		}
	}
	return res;
}
/*====================*/
void Solve(void)
{
	do
	{
		cin >> n >> m;
		for (int i = 1; i <= n; ++i)
		{
			cin >> arr[i]; tree[i] = i;
		}
	} while (false);//读入

	do
	{
		for (int i = 1; i <= n; ++i)
		{
			belong[i] = i / S + 1;
			if (block[belong[i]].l == 0)
			{
				block[belong[i]].l = i;
			}
			block[belong[i]].r = i;
		}
	} while (false);//预处理块

	do
	{
		for (int i = 1; i <= belong[n]; ++i)
		{
			sort(tree + block[i].l, tree + block[i].r + 1, cmp_GetRank);
		}
	} while (false);//预处理块内序列

	do
	{
		while (m--)
		{
			int op; cin >> op;
			if (op == 1)
			{
				int l, r, k; cin >> l >> r >> k;
				if (r - l + 1 < k)
				{
					cout << "-1" << endl;
				}
				else
				{
					int ans = -1;
					int minval = +INF, maxval = -INF;
					GetMinMaxVal(l, r, minval, maxval);
					if (k == 1)
					{
						cout << minval << endl; continue;
					}
					if (k == r - l + 1)
					{
						cout << maxval << endl; continue;
					}
					while (minval <= maxval)
					{
						int mid = (1ll * minval + maxval) >> 1;
						if (GetRank(l, r, mid) < k)
						{
							minval = mid + 1;
						}
						else
						{
							ans = mid;
							maxval = mid - 1;
						}
					}
					cout << ans << endl;
				}
			}
			if (op == 2)
			{
				int l, r, delta;
				cin >> l >> r >> delta;
				Change(l, r, delta);
			}
		}
	} while (false);//回答询问
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}