Bài này chúng ta chặt từng truy vấn với nhau, chặt truy vấn $Q/1$, $Q/2$, $Q/4$,... $Q/2^x$ .
Với mỗi lần chặt trong đoạn từ $l->r$. Đặt $mid = (l+r)/2$. chúng ta update các truy vấn từ $l->mid$ và xử lí.
Dùng $2 vector$ để lưu trạng thái đã được tưới nước đầy hay chưa ở đoạn $l->r$ đang xét. Xét đến cây vị trí $i$ , $S = get(i)$ nếu $A[i] \le S$ thì cây ở vị trí thứ $i$ đã được tưới đầy. Gán $ret[i] = mid$ và ta thêm $i$ vào vector có trạng thái đã tưới nước đủ. Còn không thì chúng ta thêm $i$ vào vector có trạng thái tưới nước $chưa$ đủ và $A[i]-=S$. Và cứ thế chặt cho đến lúc nào dừng thì thôi=).
Đây là code mẫu của mình:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define el '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define inf64 (ll)(1ll<<61)
#define inf32 int(1<<30)
#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 mod = 1e9+7;
const int maxn = 5e5+7;
const int maxm = 1e6+3;
struct event{
int l,r,x;
};
int n,q,c[maxn],a[maxn],ret[maxn];
event ev[maxn];
vector<int> water;
int bit[maxn];
void up(int x,ll v){
for (;x<=n;x += x&-x)bit[x]+=v;
}
void add(int l,int r,ll x){
up(l,x);
up(r+1,-x);
}
ll get(int x){
ll s = 0;
for (;x>0;x-=x&-x)s+=bit[x];
return s;
}
void add(int i,int v=1){
int l = ev[i].l,r = ev[i].r;
ll x = 1ll*ev[i].x*v;
add(l,r,x);
}
void del(int i){
add(i,-1);
}
void calc(int l,int r, vector<int>& type){
//cerr << l << ' ' << r << el;
if(l > r || type.empty()) return;
int mid = (l+r)>>1;
for (int i=l;i<=mid;++i)add(i);
vector<int> ok,notok;
for (int t:type){
ll sum = get(t);
// cerr << t << ' ' << sum << el;
if (sum>=a[t]){
ok.pb(t);
ret[t] = mid;
}else{
notok.pb(t);
a[t]-=sum;
}
}
for (int i=l;i<=mid;++i)del(i);
calc(l,mid-1,ok);
calc(mid+1,r,notok);
vector<int>().swap(ok);
vector<int>().swap(notok);
}
void solve(){
calc(1,q,water);
FOU(i,1,n)cout << ret[i]<< ' ';
}
signed main(){
fast
cin >> n >> q;
FOU(i,1,n){
cin >> a[i],ret[i] = -1;
water.pb(i);
}
FOU(i,1,q){
cin >> ev[i].l >> ev[i].r >> ev[i].x;
}
solve();
return 0;
}
```
lco_hacker1612
Created at
3 likes