Title address:
https://www.acwing.com/problem/content/2308/
have
N
N
N positions,
M
M
M operations. Each location can store multiple numbers at the same time. There are two types of operations, each operation:
If it is in the form of 1 a b c, it means that the
a
a
position a to position
b
b
b positions, add a number to each position
c
c
c.
If it is in the form of 2 a b c, it means that the query starts from the
a
a
position a to position
b
b
b position, no.
c
c
What is the largest number c.
Input format:
The first line contains two integers
N
,
M
N,M
N,M.
Next
M
M
M lines, each line contains one instruction, in the form of 1 a b c or 2 a b c.
Output format:
Print the results of each query, one line per result.
data range:
1
≤
N
,
M
≤
50000
1≤N,M≤50000
1≤N,M≤50000,
1
≤
a
≤
b
≤
N
1≤a≤b≤N
1≤a≤b≤N,
1
1
1 in operation
c
c
The absolute value of c does not exceed
N
N
N,
2
2
2 in operation
c
c
c satisfies
1
≤
c
≤
2
31
?
1
1≤c≤2^{31}?1
1≤c≤231?1.
All operations are guaranteed to be legal.
Discretize first, then open a weight line segment tree, and imagine that there is an array in the node of each weight line segment tree. The array maintains how many numbers there are at each position within this weight range. So there is:
operate
1
1
1 For the outer weight segment tree, it is a single point operation, but for the inner array, it is an interval addition.
1
1
1 operation;
operate
2
2
2 can be done with a bipartite answer. For each node of the weight line segment tree, the midpoint of the weight range maintained by it can be used as the midpoint of each bisection.
m
m
m, then do the positioning of the internal array of its right child node
[
a
,
b
]
[a,b]
Sum the interval of [a, b], that is, know the position
[
a
,
b
]
[a,b]
[a,b] is greater than
c
c
How many numbers are there in c? If this number
d
d
d is greater than or equal to
c
c
c, explain the
c
c
c A large number is greater than
m
m
m, recurse to the right half; otherwise, recurse to the left half and find the
c
?
d
c-d
c?d is a large number.
Since the array in the outgoing node requires interval addition
1
1
1 and the operation of summing intervals, so it can also be maintained by line segment trees, so that the entire data structure is a tree within a tree. The outer layer is a weighted line segment tree that maintains weighted intervals, and the inner layer is an ordinary line segment tree that maintains weights. The number of numbers in each position if the value is within the range.
The inner segment tree requires a
s
s
s records the interval sum, and there is a lazy mark
a
a
a record interval plus
1
1
1 this operation. Since there is only one modification operation, we can use the mark persistence technique. redefine
s
s
s,
s
s
s is the sum when only considering the lazy mark of the current node and its children, that is
s
s
s does not consider the father’s lazy mark, that is, all lazy marks are not passed down. Therefore, the real lazy mark of each node is actually the sum of the lazy marks of all its parents, and this sum can be passed down during recursion. The definition of lazy tags remains unchanged, but each lazy tag will not pushdown to change the child’s
s
s
s value.
code show as below:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 5e4 + 10, P = N * 17 * 17;
int n, m;
vector<int> nums;
struct Query {<!-- -->
int op, a, b, c;
} q[N];
// Find the value of x after discretization
int find(int x) {<!-- -->
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
namespace inner {<!-- -->
struct Node {<!-- -->
#define lc(u) tr[u].lc
#define rc(u) tr[u].rc
// [l, r] is the range of positions maintained by this node, that is, the "N positions" in the question
int l, r;
// lc and rc are the subscripts of the left and right children of this node
int lc, rc;
// sum is the total number of numbers in the position range of [l, r], add is a lazy mark
ll sum, add;
} tr[P];
int idx;
// Find the intersection length of [a, b] and [c, d]
int intersection(int a, int b, int c, int d) {<!-- -->
return min(b, d) - max(a, c) + 1;
}
// u is the node that maintains the position [l, r]. Add a number to each position in the range [ql, qr]
void update(int u, int l, int r, int ql, int qr) {<!-- -->
// [l, r] The total number of numbers in these positions must be added to the intersection length
tr[u].sum + = intersection(l, r, ql, qr);
if (ql <= l & amp; & amp; r <= qr) {<!-- -->
tr[u].add + + ;
return;
}
int mid = l + r >> 1;
if (ql <= mid) {<!-- -->
if (!lc(u)) lc(u) = + + idx;
update(lc(u), l, mid, ql, qr);
}
if (qr > mid) {<!-- -->
if (!rc(u)) rc(u) = + + idx;
update(rc(u), mid + 1, r, ql, qr);
}
}
// u is the node maintaining position [l, r], and returns the total number of all numbers in the position within the range [ql, qr],
// add is the sum of lazy markers of all fathers of u
ll get_cnt(int u, int l, int r, int ql, int qr, int add) {<!-- -->
// sum has already considered the lazy mark of the current node and all children, and only needs to add the influence of the father's lazy mark.
if (ql <= l & amp; & amp; r <= qr) return tr[u].sum + add * (r - l + 1LL);
int mid = l + r >> 1;
ll res = 0;
add + = tr[u].add;
if (ql <= mid) {<!-- -->
if (lc(u))
res + = get_cnt(lc(u), l, mid, ql, qr, add);
else
res + = add * intersection(l, mid, ql, qr);
}
if (qr > mid) {<!-- -->
if (rc(u))
res + = get_cnt(rc(u), mid + 1, r, ql, qr, add);
else
res + = add * intersection(mid + 1, r, ql, qr);
}
return res;
}
} // namespace inner
// Outer weight segment tree
namespace outer {<!-- -->
struct Node {<!-- -->
// [l, r] is the weight range maintained by this node
int l, r;
// rt is the subscript of the root of the line segment tree that maintains the subscript of the weight range
int rt;
} tr[N << 2];
//Construct the outer segment tree, [l, r] is the weight range maintained by each node
void build(int u, int l, int r) {<!-- -->
tr[u] = {<!-- -->l, r, + + inner::idx};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
// Add a number c to each position within the range of position [ql, qr]
void change(int u, int ql, int qr, int c) {<!-- -->
inner::update(tr[u].rt, 1, n, ql, qr);
if (tr[u].l == tr[u].r) return;
int mid = tr[u].l + tr[u].r >> 1;
if (c <= mid)
change(u << 1, ql, qr, c);
else
change(u << 1 | 1, ql, qr, c);
}
int query(int u, int ql, int qr, int c) {<!-- -->
if (tr[u].l == tr[u].r) return tr[u].l;
int mid = tr[u].l + tr[u].r >> 1;
ll cnt = inner::get_cnt(tr[u << 1 | 1].rt, 1, n, ql, qr, 0);
if (cnt >= c)
return query(u << 1 | 1, ql, qr, c);
else
return query(u << 1, ql, qr, c - cnt);
}
} // namespace outer
int main() {<!-- -->
scanf("%d%d", & amp;n, & amp;m);
for (int i = 0; i < m; i + + ) {<!-- -->
scanf("%d%d%d%d", & amp;q[i].op, & amp;q[i].a, & amp;q[i].b, & amp;q[i] .c);
if (q[i].op == 1) nums.push_back(q[i].c);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
outer::build(1, 0, nums.size() - 1);
for (int i = 0; i < m; i + + ) {<!-- -->
int op = q[i].op, a = q[i].a, b = q[i].b, c = q[i].c;
if (op == 1)
outer::change(1, a, b, find(c));
else
printf("%d\
", nums[outer::query(1, a, b, c)]);
}
}
Preprocessing time complexity
O
(
n
log
?
n
)
O(n\log n)
O(nlogn), each operation time
O
(
log
?
2
n
)
O(\log^2n)
O(log2n), space
O
(
n
log
?
n
+
m
log
?
2
n
)
O(n\log n + m\log ^2n)
O(nlogn + mlog2n).