Processing math: 41%
Solutions of Marisa plays poker - MarisaOJ: Marisa Online Judge

Solutions of Marisa plays poker

Select solution language

Write solution here.


User Avatar lenhanbo    Created at    11 likes

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 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 :

#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();
}