https://codeforces.com/gym/580226/problem/H
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define lowbit(x) x&(-x)
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
ll c[N];
int a[N];
int n;
void add_dandian(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=k;
}
}
ll query(int l,int r){
ll sum=0;
for(int i=r;i;i-=lowbit((i)))
sum+=c[i];
for(int i=l-1;i;i-=lowbit(i))
sum-=c[i];
return sum;
}
void solve() {
ll T;
cin>>n>>T;
for(int i=1;i<=n;i++){
cin>>a[i];
add_dandian(i,a[i]);
}
ll ans=0;
int cnt=n;
while(query(1,n)){//当前不能选这颗糖,以后也选不了
ll sum=query(1,n);
ans+=T/sum*cnt;//当前的这些糖能选几轮
T-=T/sum*sum;
while(1){
int l=1,r=n;
while(l<r){//二分找第一个不能选的糖,删除
int mid=(l+r)>>1;
if(query(1,mid)>T) r=mid;
else l=mid+1;
}
if(l==n&&query(1,n)<=T) break;
else{
cnt--;
add_dandian(l,-a[l]);//选不了单点查询删除
}
}
}
cout<<ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin>>T;
while (T--) {
solve();
}
return 0;
}
标签:二分,单点,树状,int,ll,while,query,sum,const
From: https://www.cnblogs.com/laileou/p/18668192