Processing math: 86%
Solutions of Apple trees 3 - MarisaOJ: Marisa Online Judge

Solutions of Apple trees 3

Select solution language

Write solution here.

User Avatar beiv    Created at    10 likes

Theo dữ kiện đề bài thì xét đến vị trí xi thì chúng ta mới bắt đầu mua ai cây táo trong đoạn [li,ri] . Vậy thay vì đến vị trí xi mới mua thì bây giờ chúng ta bắt đầu mua từ vị trí 1 và ai bây giờ được cộng thêm 1 lượng k với k là số lượng số thoả mãn li≤Aj≤ri với j=[1,xi). Đế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</⋅Authorfxt⋅#∈clude<bitsstdc++.h>usingnamespacestd;#def∈ef∗ios::syncwithstdio(0);c∈.tie(0);cout.tie(0);#def∈e∫longlong#def∈eel′n′#def∈epbpushback#def∈eFOU(i,a,b)for(∫i=(a),b=(b);i≤b;++i)#def∈eFOD(i,a,b)for(∫i=(a),b=(b);i≥b;--i)#def∈eREP(i,n)for(∫i=0,n=(n);i<n;++i)const∫N=2e5+7;structnode{∫l,r,x;};∫n,k,m,q,bit[N],a[N],cnt[N],res[N];nodeQ[N];→→r<∫>run;→→r<node>l∗x[N];vop(∫x,∫v=1){for(;x<N;x+=x&-x)bit[x]+=v;}∫≥t(∫x){∫s=0;for(;x>0;x≡x&-x)s+=bit[x];returns;}∫query(∫l,∫r){return≥t(r)-≥t(l-1);}voalc(∫l,∫r,→→r<∫>&rec){if