题目：P5848 [IOI2005] mou

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

inline long long maxi(long long a, long long b) {
	return a > b ? a : b;
}

inline long long mini(long long a, long long b) {
	return a < b ? a : b;
}

#define lch (root<<1)
#define rch ((root<<1)|1)
#define mids() int mid = (lrange[root] + rrange[root]) >> 1
#define lcall lch, maxi(lrange[root], l), mini(mid, r)
#define rcall rch, maxi(mid+1, l), mini(rrange[root], r)

constexpr int N = 2e6, Q = 6e6, ST = 8e6, INF = 1e9;
constexpr long long SUPER = 1e12;
int lrange[ST], rrange[ST];
long long value[ST], delta[ST], lazy[ST];	// value stands for maximum in the block
bool has_lazy[ST];

char type[Q];
vector<int> distr;
vector<int>::iterator dend;
int as[Q], bs[Q], cs[Q], n;

inline int refer(int x) {
	return lower_bound(distr.begin(), dend, x) - distr.begin();
}

inline long long actual_len(int root) {
//	if (rrange[root]+1 >= distr.size()) return SUPER;
//	return distr[rrange[root]+1] - distr[lrange[root]];
	return distr[rrange[root]] - ((lrange[root] == 0) ? 0 : distr[lrange[root]-1]);
}

void build(int root, int l, int r) {
	if (l > r) return;
	lrange[root] = l;
	rrange[root] = r;
	mids();
	if (l == r) return;
	build(lch, l, mid);
	build(rch, mid+1, r);
}

void pushdown(int root) {
	if (has_lazy[root]) {
		has_lazy[lch] = has_lazy[rch] = true;
		lazy[lch] = lazy[rch] = lazy[root];
		delta[lch] = value[lch] = actual_len(lch) * lazy[root];
		delta[rch] = value[rch] = actual_len(rch) * lazy[root];
		has_lazy[root] = false;
	}
}

void pushup(int root) {
	delta[root] = delta[lch] + delta[rch];
	value[root] = maxi(value[lch], delta[lch] + value[rch]);
}

void update(int root, int l, int r, long long val) {
	if (l > r) return;
	if (lrange[root] >= l && rrange[root] <= r) {
		has_lazy[root] = true;
		lazy[root] = val;
		delta[root] = value[root] = actual_len(root) * val;
		return;
	}
	pushdown(root);
	mids();
	update(lcall, val); update(rcall, val);
	pushup(root); 
}

// Ensure a block (can only ensure a starting point), then perform operations

struct qresult {
	long long value = 0, delta = 0;
	qresult() {
		
	}
	qresult(long long value, long long delta) : value(value), delta(delta) {
		
	}
};

qresult query(int root, int l, int r) {
//	cerr << "call query(" << root << "," << l << "," << r << ")\n";
	if (l > r) return qresult();
	if (lrange[root] >= l && rrange[root] <= r) {
//		cerr << "direct ret.\n";
		return qresult(value[root], delta[root]);
	}
	pushdown(root);
	mids();
	qresult lres = query(lcall), rres = query(rcall);
	return qresult(maxi(lres.value, lres.delta + rres.value), lres.delta + rres.delta);
}
/*
long long query_single(int root, int pos) {
	if (lrange[root] == pos && rrange[root] == pos) return value[root];
	pushdown(root);
	mids();
	if (pos <= mid) {
		return query_single(lch, pos);
	} else {
		return query_single(rch, pos);
	}
}
*/

// Baoli
long long heights[N];
int m = 0;

inline void baoli_processor() {
//	cerr << "baoli on\n";
	int a,b,c;
	for (int i = 0; i < m; i++) {
		char op = type[i];
		a = as[i];
		if (op == 'Q') {
			int cnt = 0;
			long long ch = 0;
			for (int i = 1; i <= n; i++) {
				ch += heights[i];
//				cerr << "Going " << i << " reaching " << ch << endl;
				if (ch > a) break;
				cnt++;
			}
			cout<<cnt<<'\n';
		} else {
			b = bs[i]; c = cs[i];
			for (int i = a; i <= b; i++) heights[i] = c;
		}
	}
}

signed main() {

	train();
	
	cin>>n;
	distr.push_back(0); 
	while (true) {
		int &i = m;
		cin>>type[i];
		if (type[i] == 'E') break;
		cin>>as[i];
		distr.push_back(as[i]);
		if (type[i] == 'I') {
			cin>>bs[i]>>cs[i];
			distr.push_back(bs[i]);
			distr.push_back(as[i]-1);
		}
		i++;
	}
	
	long long expected = 1ll * n * m;
	distr.push_back(n);
	distr.push_back(INF);
	sort(distr.begin(), distr.end());
	dend = unique(distr.begin(), distr.end());
	int dsz = dend - distr.begin();
	build(1, 0, dsz-1);
	for (int i = 0; i < m; i++) {
		if (type[i] == 'I') {
			update(1, refer(as[i]), refer(bs[i]), cs[i]);
		} else {
			int l = 0, r = dsz-2, ans = -1;
			long long stage;
			while (l <= r) {
				int mid = (l+r) >> 1;
				qresult qs = query(1, 0, mid);
				if (qs.value <= as[i]) {
					l = mid + 1;
					stage = qs.delta;
					ans = mid;
				} else {
					r = mid - 1;
				}
			}
			if (ans >= dsz-2) {
				cout<<mini(distr[dsz-2],n)<<'\n';
				continue;
			}
			qresult qd = query(1, 0, ans+1);
			long long dself = (ans < 0) ? 1 : (distr[ans]);
			long long actl = distr[ans+1]-dself;
			long long elevate = (qd.delta - stage) / actl;	// Elevation per unit
			long long possible = 0;
			if (elevate) possible = (as[i] - stage) / elevate;
			cout<<mini(n,dself+possible)<<'\n';
		}
	}
	
	cout<<flush;

	return 0;
}