Codeforces #684 Div1 C. Greedy Shopping

これは方針はすぐ立ったなぁ。
http://codeforces.com/contest/1439/problem/C

問題

単調減少な整数列Aが与えられる。
以下のクエリに順次答えよ。

• Aにおいてx番目以降の要素iがyより大きい場合、それらをA[i]=yにする
• A[x]、A[x+1]…と順次要素を選択していくとき時、総和がy以下の範囲で最大何個まで選択できるか答える。

解法

前者のクエリでは常時Aが単調減少になる点に注意。
Aの区間加算と区間和の算出ができるようになっていれば、前者のクエリはAの更新箇所に区間加算、後者のクエリはAの区間和の二分探索で処理できる。

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	int lower_bound(V val) {
		V v0=0,v1=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) {
			if((ent+(1<<i)-1)*(v0+bit[0][ent+(1<<i)-1])+(v1+bit[1][ent+(1<<i)-1])<val) {
				v0+=bit[0][ent+(1<<i)-1];
				v1+=bit[1][ent+(1<<i)-1];
				ent+=(1<<i);
			}
		}
		return ent;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
};
BIT_r<ll,20> bt;

int N,Q;
int A[202020];
int T,X,Y;
map<int,int> M,R;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	A[0]=M[0]=1<<30;
	R[-(1<<30)]=0;
	scanf("%d%d",&N,&Q);
	for(i=1;i<=N;i++) {
		scanf("%d",&A[i]);
		if(A[i-1]>A[i]) {
			M[i]=A[i];
			R[-A[i]]=i;
		}
		
		bt.add(i,i,A[i]);
	}
	bt.add(N+1,N+1,1LL<<32);
	M[N+1]=0;
	R[0]=N+1;
	while(Q--) {
		scanf("%d%d%d",&T,&X,&Y);
		if(T==1) {
			auto it=M.lower_bound(X+1);
			if(prev(it)->second>=Y) continue;
			y=1<<30;
			if(it->first!=X+1) {
				y=prev(it)->second;
				R[-y]=X+1;
				M[X+1]=y;
			}
			int px=X+1;
			while(1) {
				auto it=prev(M.lower_bound(X+1));
				if(it->second>Y) break;
				bt.add(it->first,px-1,Y-it->second);
				px=it->first;
				if(it->second!=y) R.erase(-it->second);
				M.erase(it);
			}
			M[px]=Y;
			R[-Y]=px;
		}
		else {
			int num=0;
			while(X<=N) {
				ll co=bt.total(X-1);
				auto p=bt.lower_bound(co+Y+1)-1;
				Y-=bt.total(p)-co;
				num+=p-(X-1);
				X=max(p+1,R.lower_bound(-Y)->second);
				//cout<<"!now" <<" "<<X<<" "<<Y<<" "<<num<<endl;
			}
			//FORR(r,M) cout<<r.first<<":"<<r.second<<" ";
			//cout<<endl;
			cout<<num<<endl;
		}
		
	}
	
	
}

まとめ

方針はすぐ立ったけど、実装がわりとめんどい。