Description
有 N 个位置, M 个操作. 操作有两种, 每次操作如果是 1 a b c 的形式表示在第 a 个位置到第 b 个位置, 每个位置加入一个数 c.
如果是 2 a b c 形式, 表示询问从第 a 个位置到第 b 个位置, 第 C 大的数是多少.
Input
第一行 N, M
接下来 M 行, 每行形如 1 a b c 或 2 a b c
Output
输出每个询问的结果
Sample Input
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3Sample Output
1
2
1Sample Explanation
- 第一个操作后位置 1 的数只有 1, 位置 2 的数也只有 1.
- 第二个操作后位置 1 的数有 1、2, 位置 2 的数也有 1、2.
- 第三次询问位置 1 到位置 1 第 2 大的数是 1.
- 第四次询问位置 1 到位置 1 第 1 大的数是 2.
- 第五次询问位置 1 到位置 2 第 3 大的数是 1.
Data Range
100% 的数据保证 \(N, M \leq 50000, N, M \leq 50000, a \leq b \leq N\)
其中 1 操作中 \(|c| \leq N\),2 操作中 \(c \leq 2^{63}-1\)
Solution
参见了一下这位大神的博客:https://blog.sengxian.com/solutions/bzoj-3110
一道树套树的题, 外层是权值线段树, 里层是普通区间线段树.
对于权值线段树的节点 \(u\) 表示权值区间 \([l,r)\), 其对应的普通线段树的节点 \(v\) 表示 序列 \([l_1,r_1)\) 中一共有多少个在权值区间 \([l,r)\) 的树.
这样不难得到我们的查询算法, 要查 \([a,b]\) 的第 \(k\) 大, 如果权值线段树根的右儿子代表的线段树区间 \([a,b]\) 的和为 \(s\), 如果 \(s\) 大于 \(k\), 说明第 \(k\) 大在右儿子代表的权值区间. 否则在左儿子代表的权值区间上面.
修改也很好修改, 只有一个区间加标记, 如果要在 \([a,b]\) 中加一个 \(c\), 那么应该在外 层线段树中将所有包含权值 \(c\) 的节点对应的线段树的 \([a,b]\) 区间全部+1.
剩下唯一的问题就是空间, 理论上需要 \(O(n^2)\) 的空间, 我们可以动态开点, 未开的点给到 null, 如果查询的时候走到 null, 不需新建直接返回 0; 如果修改的时候走到 null, 那就新建节点, 每次操作第一层最多影响 \(\log n\) 个节点, 第二层最对影响 \(\log n\) 个节点, 所以总空间复杂度是 \(O(m \cdot \log^2 n)\).
然而 hzwer 代码巨坑啊~ 直接交上去就 WA~
是因为新数据的问题: 新的数据加上了负数和超大整数, 然而 hzwer 并没有考虑到这个问题 233
所以就手写了一个 class 加上了一个离散化的小 Trick 然后踩着 19. 6 秒的时限 AC 了
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 200100, maxm = 20001000;
class MultiPointSegmentTree
{
public:
int n, ncnt;
int ch[maxm][2], root[maxn];
lli sum[maxm], lazy[maxm];
void dispatch_lazy(int p, int l, int r)
{
// Nothing to dispatch
if (!lazy[p] || l == r)
return ;
// Tending to create children, if not exist.
if (!ch[p][0]) ch[p][0] = ++ncnt;
if (!ch[p][1]) ch[p][1] = ++ncnt;
// Dispatching lazy.
lazy[ch[p][0]] += lazy[p];
lazy[ch[p][1]] += lazy[p];
// Adding sum.
int mid = (l + r) / 2;
sum[ch[p][0]] += (mid - l + 1) * lazy[p];
sum[ch[p][1]] += (r - mid) * lazy[p];
lazy[p] = 0;
return ;
}
void change(int& p, int l, int r, int left, int right)
{
// Create new node, if necessary.
if (!p) p = ++ncnt;
// Dispatch lazy values
dispatch_lazy(p, l, r);
// Matches left boundaries and right boundaries
if (l == left && r == right) {
sum[p] += r - l + 1;
lazy[p]++;
return ;
}
// Dispatch to lower children
int mid = (l + r) / 2;
if (right <= mid) {
change(ch[p][0], l, mid, left, right);
} else if (left > mid) {
change(ch[p][1], mid + 1, r, left, right);
} else {
change(ch[p][0], l, mid, left, mid);
change(ch[p][1], mid + 1, r, mid + 1, right);
}
sum[p] = sum[ch[p][0]] + sum[ch[p][1]];
return ;
}
lli query(int p, int l, int r, int left, int right)
{
// Fail-safe check on things
if (!p) return 0;
// Dispatch lazy values
dispatch_lazy(p, l, r);
// Normal non-heap segment trees
if (l == left && r == right)
return sum[p];
int mid = (l + r) / 2;
if (right <= mid) {
return query(ch[p][0], l, mid, left, right);
} else if (left > mid) {
return query(ch[p][1], mid + 1, r, left, right);
} else {
return query(ch[p][0], l, mid, left, mid)
+ query(ch[p][1], mid + 1, r, mid + 1, right);
}
// Fail-safe check (should not happen!)
return 0;
}
void insert(int l, int r, lli val)
{
// Preprocess position
val = n - val + 1;
int p = 1, // heap-like node traversal
left = 1, right = n; // Binary-search-like worker
while (left != right) {
int mid = (left + right) / 2;
change(root[p], 1, n, l, r);
if (val <= mid) {
right = mid;
p = 2 * p;
} else {
left = mid + 1;
p = 2 * p + 1;
}
}
change(root[p], 1, n, l, r);
return ;
}
lli query(int l, int r, lli pos)
{
int p = 1, // Binary-search-like traversal.
left = 1, right = n;
while (left != right) {
int mid = (left + right) / 2;
lli res = query(root[2 * p], 1, n, l, r);
if (res >= pos) {
right = mid;
p = p * 2;
} else {
left = mid + 1;
p = p * 2 + 1;
pos -= res;
}
}
return n - left + 1;
}
} st;
struct srtr { lli val; int pos; };
bool operator < (srtr a, srtr b) { return a.val < b.val; }
class DiscreteProcessor
{
public:
srtr srt[maxn];
lli arr[maxn];
lli val[maxn];
int cnt;
void eval(void)
{
for (int i = 1; i <= cnt; i++)
srt[i].val = arr[i], srt[i].pos = i;
sort(srt + 1, srt + 1 + cnt);
// Restoring values
for (int i = 1; i <= cnt; i++) {
int rel_pos = 0;
if (i == 1 || srt[i].val != srt[i - 1].val)
rel_pos = arr[srt[i - 1].pos] + 1;
else
rel_pos = arr[srt[i - 1].pos];
arr[srt[i].pos] = rel_pos;
val[rel_pos] = srt[i].val;
}
return ;
}
} dcp;
int n, m;
lli op[maxn][4];
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
st.n = n;
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld%lld", &op[i][0], &op[i][1], &op[i][2], &op[i][3]);
if (op[i][0] == 1) {
// printf("%lld ", op[i][3]);
dcp.arr[++dcp.cnt] = op[i][3];
op[i][3] = dcp.cnt;
}
}
// Processing discrete numbers
dcp.eval();
// printf("\n");
// for (int i = 1; i <= dcp.cnt; i++)
// printf("%lld ", dcp.arr[i]);
// printf("\n");
// Redoing operations
for (int i = 1; i <= m; i++) {
if (op[i][0] == 1)
st.insert(op[i][1], op[i][2], dcp.arr[op[i][3]]);
else
printf("%lld\n", dcp.val[st.query(op[i][1], op[i][2], op[i][3])]);
}
return 0;
}