Hướng dẫn giải của Bedao Mini Contest 23 - KCOUNT
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ta có nhận xét quan trọng và cũng dễ để nhận ra đó là một phần tử nó sẽ có ~2~ trạng thái là "~\le k~" hoặc "~> k~". Một phần tử chỉ chuyển từ trạng thái "~> k~" sang trạng thái "~\le k~" đúng ~1~ lần duy nhất.
Thì ở trong mảng ~a~, phần tử có khả năng chuyển trạng thái nhiều nhất đó là phần tử hiện tại đang mang giá trị nhỏ nhất.
Vậy nên để thực hiện truy vấn loại ~1~ và tìm ra được vị trí của phần tử mang giá trị nhỏ nhất trong mảng hiện tại, ta có thể sử dụng Segment Tree Lazy.
Trong quá trình cài đặt, khi một phần tử chuyển trạng thái thành "~\le k~", ta gán giá trị của nó thành ~1~ số đủ to để ảnh hưởng đến việc cập nhật (không bị chuyển trạng thái lần nữa) có thể gán bằng ~10^{18}~.
#include <bits/stdc++.h>
using namespace std;
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
#define all(a) a.begin(), a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
const int MAX_N = 5e5 + 5;
const ll inf = 1e18;
int n, k;
int a[MAX_N];
pii ST[MAX_N << 2];
int lazy[MAX_N << 2];
int BIT[MAX_N];
void build(int id, int l, int r) {
if (l == r) {
ST[id] = {a[l], l};
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
ST[id] = min(ST[id << 1], ST[id << 1 | 1]);
}
void down(int id) {
int k = lazy[id];
if (!k) return;
ST[id << 1].fi -= k;
ST[id << 1 | 1].fi -= k;
lazy[id << 1] += k;
lazy[id << 1 | 1] += k;
lazy[id] = 0;
}
void update_mark(int id, int l, int r, int i, int val) {
if (l == r) {
ST[id] = {val, i};
return;
}
down(id);
int mid = (l + r) >> 1;
if (i <= mid) {
update_mark(id << 1, l, mid, i, val);
}
else {
update_mark(id << 1 | 1, mid + 1, r, i, val);
}
ST[id] = min(ST[id << 1], ST[id << 1 | 1]);
}
void update(int id, int l, int r, int u, int v, int val) {
if (u > r || v < l) {
return;
}
if (u <= l && r <= v) {
ST[id].fi -= val;
lazy[id] += val;
return;
}
down(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
ST[id] = min(ST[id << 1], ST[id << 1 | 1]);
}
pii get(int id, int l, int r, int u, int v) {
if (u > r || v < l) {
return {inf, inf};
}
if (u <= l && r <= v) {
return ST[id];
}
down(id);
int mid = (l + r) >> 1;
return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
void BIT_update(int id, int val) {
while (id <= n) {
BIT[id] += val;
id += id & -id;
}
}
int BIT_get(int id) {
int ans = 0;
while (id > 0) {
ans += BIT[id];
id -= id & -id;
}
return ans;
}
int BIT_getRange(int l, int r) {
return BIT_get(r) - BIT_get(l - 1);
}
void process() {
while (true) {
if (ST[1].fi > k) break;
BIT_update(ST[1].se, 1);
update_mark(1, 1, n, ST[1].se, inf);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
process();
int numCase;
cin >> numCase;
for (int testCase = 1; testCase <= numCase; testCase++) {
char type;
cin >> type;
int l, r;
cin >> l >> r;
if (type == '1') {
int x;
cin >> x;
update(1, 1, n, l, r, x);
}
else {
process();
cout << BIT_getRange(l, r) << '\n';
}
}
return 0;
}
/*
Thursday, 25 January 2024
09:41:43
*/
Bình luận