冤哥y佬和他的happy茶（E题の吐槽）

【E题题解】

槽点：居然没看出来可以直接动态前缀和，我的，我的，下次我请y佬喝茶

OKK回顾下这题： 有钱的y佬带着 元钱去了围成一圈的 个happy茶商铺（第 家和第 家（首尾）相接），第 个茶铺以 元一杯出售happy茶，这y佬转圈买，走到一家，够钱就买一杯，不够就啥也不干，不论买不买都去下一个茶铺，钱花光为止

这哥们太富了下次V我50

看了一眼数据范围：



哇亚雷，前面一直在想怎么模拟转圈买，直到后来，想怎么模拟转到那个位置不买也不计数，好像线段树或者树状数组就能做了这样的话...

Whatever~

证明几个东西：

1.对于y佬绕到任意一圈（设第 圈），如果他买不了某家店铺（设第 家）的happy茶，那么他下一圈（如果还有的话）再转到这家店铺也一定买不了：
显然后面就算再逛到这第 家店之前不再花钱，情况一样，该买不起还是买不起，更别说万一还花钱了...

2.对于y佬之后都会不够钱的店，按茶价贵到便宜来确定并选择无视（经过但不买，也不计数，体现在线段树/树状数组中就是直接清了那家店铺的数据，价格清零，计次数也清零）逻辑上正确：
（下设 ) 由于（按价格从大到小排序意义上）价格贵的会先被清零，则考虑两种情况，一是价格贵的在价格便宜的店前面，即 ，则贵的店清零了以后再看便宜的店会不会清零具有显然的先后依据，不赘述；二是价格便宜的在价格贵的前面，即 ，此时依题意，不可能在买不起 店happy茶的同时买得起 店的茶，以上得证。
暗示做法：以价格为依据，对这组数据的副本排序（结构体排序更方便）

则，建树（线段树或前缀树状数组）按照原店铺顺序建，一圈算一轮，最终目的是为了搜索出一轮下来，剩下 元的y佬能经过 家店，花费 的钱去买奶茶，这样y佬就买到了 杯奶茶
复杂度情况：
建树
每次求区间操作
清理操作 总复杂度：
如果是线段树，常数 更大点儿
（可怜的我们都是y佬的队友耶）

思路理顺，c++代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll readll(){
	ll x=0,f=1;
	char k=getchar();
	while(k<'0'||k>'9'){
		if(k=='-')f=-1;
		k=getchar();
	}
	while(k>='0'&&k<='9'){
		x=(x<<3)+(x<<1)+(k-'0');
		k=getchar();
	}
	return x*f;
}
int readint(){
	int x=0,f=1;
	char k=getchar();
	while(k<'0'||k>'9'){
		if(k=='-')f=-1;
		k=getchar();
	}
	while(k>='0'&&k<='9'){
		x=(x<<3)+(x<<1)+(k-'0');
		k=getchar();
	}
	return x*f;
}
const int maxn=2e5+10;
ll a[maxn];
struct dat{
    ll val;
    int id;//按照原来店家的位置找到线段树叶子节点来清
}d[maxn];//结构体排序，作为对店清零的依据
bool cmp(dat a,dat b){
	return a.val>b.val;
}
ll tree[maxn*4]/*树的主体，记录价格总和*/,tstand[maxn*4]/*记还有多少家店没被清零*/,rec[maxn]/*我选择了在建树的时候存储某单家店对应的叶子节点，便于反向找到该节点并执行log_2n级别的清零*/;
void maketree(int x,int l,int r){
	//cout<<"Now going to tree "<<x<<endl;
	if(l==r){
		rec[l]=x;
		tree[x]=a[l];
		tstand[x]=1;
		//cout<<"Storing "<<a[l]<<"(pos:"<<l<<") at tree "<<x<<endl;
		return ;
	}
	int mid=(l+r)/2;
	maketree(x*2,l,mid);
	maketree(x*2+1,mid+1,r);
	tree[x]=tree[x*2]+tree[x*2+1];
	tstand[x]=tstand[x*2]+tstand[x*2+1];
	return ;
}
void clear_(int l){
	int now=rec[l],w=tree[rec[l]];
	while(now){
		tree[now]-=w;
		tstand[now]-=1;
		now>>=1;
	}
	return ;
}
int qpos(int x,int l,int r,ll w){
	//cout<<"Going to tree "<<x<<" (from "<<l<<" to "<<r<<", remain value:"<<w<<")"<<endl;
	if(l==r){
		//cout<<"Get a position ";
		if(w<tree[x]){
			//cout<<l-1<<endl;
			return l-1;
		}
		else{
			//cout<<l<<endl;
			return l;
		}
	}
	int mid=(l+r)/2;
	if(w>tree[x*2]){
		return qpos(x*2+1,mid+1,r,w-tree[x*2]);
	}
	else{
		return qpos(x*2,l,mid,w);
	}
}
ll q_sum(int x,int l,int r,int sl,int sr){
	//cout<<"Querying sum at tree "<<x<<"("<<sl<<" to "<<sr<<" & demand:"<<l<<" to "<<r<<")"<<endl;
	if(sl>=l&&sr<=r){
		//cout<<"Returning "<<tree[x]<<endl;
		//system("pause");
		return tree[x];
	}
	int mid=(sl+sr)/2;
	if(r<=mid){
		return q_sum(x*2,l,r,sl,mid);
	}
	else if(l>mid){
		return q_sum(x*2+1,l,r,mid+1,sr);
	}
	else{
		return q_sum(x*2,l,r,sl,mid)+q_sum(x*2+1,l,r,mid+1,sr);
	}
}
ll q_stand(int x,int l,int r,int sl,int sr){
	//cout<<"  Querying stands at tree "<<x<<"("<<sl<<" to "<<sr<<" & demand:"<<l<<" to "<<r<<")"<<endl;
	if(sl>=l&&sr<=r){
		//cout<<"  Found "<<tstand[x]<<" stands."<<endl;
		//system("pause");
		return tstand[x];
	}
	int mid=(sl+sr)/2;
	if(r<=mid){
		return q_stand(x*2,l,r,sl,mid);
	}
	else if(l>mid){
		return q_stand(x*2+1,l,r,mid+1,sr);
	}
	else{
		return q_stand(x*2,l,r,sl,mid)+q_stand(x*2+1,l,r,mid+1,sr);
	}
}
int n;
bool chk(ll rem,int pos){
	ll w=0;
	if(pos>1)w=q_sum(1,1,pos-1,1,n);
	return rem-w<a[pos];
}
int main(){
    n=readint();
    //cout<<n<<endl;
    ll t=readll(),sum=0,ans=0;
    for(int i=1;i<=n;i++){
    	a[i]=readll();
        sum+=a[i];
        d[i].id=i;
        d[i].val=a[i];
    }
    sort(d+1,d+1+n,cmp);
    maketree(1,1,n);
    //cout<<"Make tree done!"<<endl;
    int st=1;
    while(st<=n){
    	while(st<=n&&chk(t,d[st].id)){
    		//cout<<"!!!CLEARING STAND NO."<<d[st].id<<"!!!"<<endl;
    		clear_(d[st].id);
    		st++;
		}
		if(st>n)break;
		int pos=qpos(1,1,n,t);
		//cout<<"Remain "<<t<<" while found position "<<pos<<endl;
		if(pos<=0)break;
		ll w=q_sum(1,1,pos,1,n),stand_=q_stand(1,1,pos,1,n);
		//cout<<"  * sum up "<<w<<" ("<<stand_<<" stand(s)"<<endl;
		ans+=t/w*(stand_);
		t%=w;
	}
	printf("%lld\n",ans);
    return 0;
}