Theo dữ kiện đề bài thì xét đến vị trí $x_i$ thì chúng ta mới bắt đầu mua $a_i$ cây táo trong đoạn $[l_i,r_i]$ . Vậy thay vì đến vị trí $x_i$ mới mua thì bây giờ chúng ta bắt đầu mua từ vị trí $1$ và $a_i$ bây giờ được cộng thêm $1$ lượng $k$ với $k$ là số lượng số thoả mãn $l_i \le A_j \le r_i$ với $j = [1,x_i)$. Đến bước này, chúng ta chỉ cần tìm kiếm nhị phân song song và gần giống với bài Cây táo $2$ thoi.
Đây là code mẫu của mình:
```cpp
/* /\_/\
( ._. ) ~UwU~
/ >0< \
/*Author fxt*/
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define el '\n'
#define pb push_back
#define FOU(i, a, b) for(int i=(a), _b = (b); i<=_b; ++i)
#define FOD(i, a, b) for(int i=(a), _b = (b); i>=_b; --i)
#define REP(i, n) for(int i= 0, _n = (n); i<_n ;++i)
const int N = 2e5+7;
struct node
{
int l,r,x;
};
int n,k,m,q,bit[N],a[N],cnt[N],res[N];
node Q[N];
vector<int> run;
vector<node> lastx[N];
void up(int x,int v=1){
for (;x<N;x+=x&-x) bit[x]+=v;
}
int get(int x){
int s = 0;
for (;x>0;x-=x&-x) s+=bit[x];
return s;
}
int query(int l,int r){
return get(r)-get(l-1);
}
void calc(int l,int r,vector<int> & rec){
if (l>r || rec.empty()) return;
int mid = (l+r)>>1;
FOU(i,l,mid) up(a[i]);
vector<int> ok,notok;
for (int id:rec){
int s = query(Q[id].l,Q[id].r);
if (s>=cnt[id]){
ok.pb(id);
res[id] = mid;
}else{
notok.pb(id);
cnt[id]-=s;
}
}
FOU(i,l,mid) up(a[i],-1);
calc(l,mid-1,ok);
calc(mid+1,r,notok);
vector<int>().swap(ok);
vector<int>().swap(notok);
}
void solve(){
cin >> n >> q;
FOU(i,1,n) cin >> a[i];
FOU(i,1,q){
cin >> Q[i].l >> Q[i].r >> Q[i].x >> cnt[i];
run.pb(i);
lastx[Q[i].x-1].pb({Q[i].l,Q[i].r,i});
res[i] = -1;
}
FOU(i,1,n){
up(a[i]);
for (node T:lastx[i]){
cnt[T.x] +=query(T.l,T.r);
}
}
FOU(i,1,n) up(a[i],-1);
calc(1,n,run);
FOU(i,1,q) cout << res[i] << ' ';
}
signed main(){
fast
solve();
return 0;
}
```
lco_hacker1612
Created at
5 likes