Editorial for Bedao Mini Contest 23 - KCOUNT
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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
*/
Comments