Chia đoạn thành $\sqrt{n}$ block [$1..$$\sqrt{n}$], [$\sqrt{n}$+1..2$\times$$\sqrt{n}$],...
Với mỗi block ta sẽ sắp xếp lại từ bé đến lớn.
Với mỗi cập nhật thì những block nào được tăng hết lên thì ta cập nhật lazy[block] += $x$, còn phần dư thì ta sẽ tính lại toàn bộ block.
Vì mỗi lần cập nhật thì ta chỉ cập nhật **nhiều nhất 2 phần dư** nên chi phí tối đa cho cập nhật là $2$ $\times$ $Q$ $\times$ $\sqrt{n}$ $\times$ $\log\$($\sqrt{n}$).
Truy vấn thì ta chặt nhị phân đáp án rồi duyệt qua từng block để đếm số phần tử $\leq$ $mid$ bằng chặt nhị phân với hàm [lower_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound) của c++.
Ta có thể tối ưu bằng cách đặt cận :
+ Đặt $low$ $=$ $\min$, $high$ $=$ $\max$ của đoạn.
+ Với mỗi block thì ta có thể kiểm tra phần tử lớn nhất và bé nhất để xem có thể bỏ qua luôn cả block hay không.
+ Ta có thể tính trước $(i/j)$ để giảm thời gian chạy vì trong quá trình xử lí ta phải sử dụng nhiều lần.
Độ phức tạp trung bình $O$($Q$ $\times$ $\sqrt{n}$ $\times$ $\log$($\sqrt{n}$) $^2$), nếu đặt cận khéo thì vẫn sẽ qua (không phải test yếu đâu nhé :")).
Code mẫu :
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define TASK "main"
const int nmax = 1e5+6;
const int sz = 250;
int n,q;
int a[nmax];
vector<int> B[450];
int lz[450];
int fastdiv[nmax];
int max_val[450],min_val[450];
int BL;
void rebuildB(int pos){
B[pos].clear();
for(int i = (pos-1)*sz ;i<min(n,pos*sz);++i){
B[pos].push_back(a[i]);
}
B[pos].push_back(-2e9);
sort(all(B[pos]));
min_val[pos] = B[pos][1] ;
max_val[pos] = B[pos][B[pos].size() - 1] ;
}
void update(int l,int r,int x){
int lb = fastdiv[l] + (l%sz != 0);
int rb = fastdiv[r] - ((r+1)%sz != 0);
for(int i = lb;i<=rb;++i){
lz[i] +=x;
}
if(fastdiv[l] != fastdiv[r]){
if(l%sz != 0){
for(int i = l ;i<(lb-1)*sz;++i){
a[i] += x;
}
rebuildB(fastdiv[l]);
}
if((r+1) % sz != 0){
for(int i = rb * sz; i<=r;++i){
a[i] += x;
}
rebuildB(fastdiv[r]);
}
} else if(lb > rb){
for(int i = l;i<=r;i++){
a[i] += x;
}
rebuildB(fastdiv[l]);
}
}
int get(int l,int r,int x){
int lb = fastdiv[l] + (l%sz != 0);
int rb = fastdiv[r] - ((r+1)%sz != 0);
int ans = 0;
for(int i = lb;i<=rb;++i){
if(max_val[i]+lz[i] <= x) ans += sz;
else if(min_val[i] +lz[i] > x) continue;
else
{
ans += upper_bound(all(B[i]),x - lz[i]) - B[i].begin() - 1;
}
}
if(fastdiv[l] != fastdiv[r]){
if(l%sz != 0){
for(int i = l ;i<(lb-1)*sz;++i){
ans += ((a[i] + lz [fastdiv[l]]) <= x);
}
}
if((r+1) % sz != 0){
for(int i = rb * sz; i<=r;++i){
ans += ((a[i] + lz[fastdiv[r]]) <= x);
}
}
} else if(lb > rb){
for(int i = l;i<=r;i++){
ans += ((a[i] + lz[fastdiv[l]]) <= x);
}
}
return ans;
}
int query(int l,int r,int k){
int lb = fastdiv[l] + (l%sz != 0);
int rb = fastdiv[r] - ((r+1)%sz != 0);
int low =2e9;
int high = -2e9;
for(int i = lb;i<=rb;++i){
low = min(low,min_val[i] + lz[i]);
high = max(high,max_val[i]+ lz[i]);
}
if(fastdiv[l] != fastdiv[r]){
if(l % sz !=0 ){
for(int i = l;i<(lb-1)*sz;++i){
low = min(low,a[i] + lz[fastdiv[l]]);
high = max(high,a[i] + lz[fastdiv[l]]);
}
}
if((r+1)%sz !=0){
for(int i = rb * sz;i<=r;i++){
low = min(low,a[i] + lz[fastdiv[r]]);
high = max(high,a[i] + lz[fastdiv[r]]);
}
}
} else if(lb > rb){
for(int i = l;i<=r;++i){
low = min(low,a[i] + lz[fastdiv[l]]);
high = max(high,a[i] + lz[fastdiv[l]]);
}
}
int res;
while(low<=high){
int mid = low + (high - low) /2;
int cnt = get(l,r,mid);
if(cnt < k) {
low = mid +1;
}
else{
high = mid -1;
res=mid;
}
}
return res;
}
void solve(){
cin >> n >> q;
for(int i = 0;i<=n;i++) fastdiv[i] = i / sz + 1;
for(int i = 0;i<n;i++){
cin >> a[i];
}
BL = n / sz + (n%sz != 0);
for(int i = 1;i<=BL;++i){
rebuildB(i);
}
while(q--){
int t ;
cin >> t;
if(t==1){
int l,r,k;
cin >> l >> r >> k;
--l,r--;
cout << query(l,r,k) << '\n';
} else{
int l,r,x;
cin >> l >> r >> x;
--l,r--;
update(l,r,x);
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
if(fopen(TASK ".inp","r")){
freopen(TASK ".inp","r",stdin);
freopen(TASK ".out","w",stdout);
}
solve();
}
```
lenhanbo
Created at
8 likes