[CF1439C] Greedy Shopping

[题目链接]

https://codeforces.com/contest/1439/problem/C

[题解]

首先对于 (1) 操作 ， 对一段前缀取 (max) 后 ， 整个序列仍然满足单调不增的性质。 在线段树上二分 ， 整体赋值即可。

对于 (2) 操作 ， 注意到取走的数必然是不超过 (log(N)) 个连续段。 这是由单调不增的性质得来的。

那么在线段树上再次二分即可。

时间复杂度 : (O(NlogN))

[代码]

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int MN = 5e5 + 5;
 
int N , M , A[MN] , tg[MN << 2] , mn[MN << 2];
LL sum[MN << 2];
 
inline void pushup(int now) {
	sum[now] = sum[now << 1] + sum[now << 1 | 1];
	mn[now] = min(mn[now << 1] , mn[now << 1 | 1]);
}
inline void build(int now , int l , int r) {
	tg[now] = -1;
	if (l == r) {
		sum[now] = mn[now] = A[l];
		return;
	}
	int mid = l + r >> 1;
	build(now << 1 , l , mid) , build(now << 1 | 1 , mid + 1 , r);
	pushup(now); 
}
inline void pushdown(int now , int l , int r) {
	if (tg[now] == -1) return;
	int mid = l + r >> 1;
	mn[now << 1] = mn[now << 1 | 1] = tg[now];
	sum[now << 1] = 1LL * (mid - l + 1) * tg[now]; sum[now << 1 | 1] = 1LL * (r - mid) * tg[now];
	tg[now << 1] = tg[now] , tg[now << 1 | 1] = tg[now]; tg[now] = -1;
	return;
}
inline LL query(int now , int l , int r , int ql , int qr) {
	if (l == ql && r == qr) return sum[now];
	int mid = l + r >> 1; pushdown(now , l , r);
	if (mid >= qr) return query(now << 1 , l , mid , ql , qr);
	else if (mid + 1 <= ql) return query(now << 1 | 1 , mid + 1 , r , ql , qr);
	else return query(now << 1 , l , mid , ql , mid) + query(now << 1 | 1 , mid + 1 , r , mid + 1 , qr);
} 
inline void modify(int now , int l , int r , int ql , int qr , int val) {
	if (l == ql && r == qr) {
		mn[now] = val; sum[now] = 1LL * (r - l + 1) * val;
		tg[now] = val; return;
	}
	int mid = l + r >> 1; pushdown(now , l , r);
	if (mid >= qr) modify(now << 1 , l , mid , ql , qr , val);
	else if (mid + 1 <= ql) modify(now << 1 | 1 , mid + 1 , r , ql , qr , val);
	else modify(now << 1 , l , mid , ql , mid , val) , modify(now << 1 | 1 , mid + 1 , r , mid + 1 , qr , val);
	pushup(now);
}
inline int ask(int now , int l , int r , LL &val) {
	if (val >= sum[now]) {
		val -= sum[now];
		return r - l + 1;
	}
	if (l == r) return 0;
	int mid = l + r >> 1; pushdown(now , l , r);
	int res = 0;
	if (mn[now << 1] <= val) res += ask(now << 1 , l , mid , val);
	if (mn[now << 1 | 1] <= val) res += ask(now << 1 | 1 , mid + 1 , r , val);
	return res;
}
 
int main() {
	
	scanf("%d%d" , &N , &M);
	for (int i = 1; i <= N; ++i) scanf("%d" , &A[i]);
	build(1 , 1 , N);
	for (int i = 1; i <= M; ++i) {
		int op , x; LL y;
		scanf("%d%d%lld" , &op , &x , &y);
		if (op == 1) {
			int l = 1 , r = x , ans = 0;
			while (l <= r) {
				int mid = l + r >> 1;
				if (query(1 , 1 , N , mid , mid) < y) {
					ans = mid;
					r = mid - 1;
				} else l = mid + 1;
			}
			if (ans) modify(1 , 1 , N , ans , x , y);
		} else {
			if (x > 1) y += query(1, 1, N, 1, x - 1);
			printf("%d
" , ask(1 , 1 , N , y) - (x - 1));
		}
	}	
	return 0;
}