イベントソー

past 第一回の過去問を解いていてN問題で壁に当たった
似たようなのを一年近く前にやったことがあるが当時もきつかった記憶がある
abc128Eのroad workだった
これらの問題を解く方法をイベントソートというらしい。
ex プログラミング王決定戦D　deforestation
N本の竹があり1からNまでの番号が付けられている。時刻0において全ての竹の長さは0
それぞれの竹は時刻が1経過するごとに高さが1増えるなおさんが竹を伐採するイベントがm回予定されている。i番目のイベントは時刻Tiに行われ、このイベントでは番号がLi以上Ri以下の竹をすべて伐採します。なおさんが高さxの竹を伐採するとき彼女はx点を得る。また伐採された竹は高さが0になるがその竹はこれ以上も伸び続ける
m回のイベントでナオさんが得る得点の総和をもとめてください
けんちょんさんのブログから。これは解法が2通りある
一連の操作は各ステップにおいて過去の履歴を破壊してしまうという性質がある。これには操作列を後ろから逆順に見るという視点が功を奏す
後ろから見ると区間[l,r)について時刻tに伐採した時その区間のスコアはtで確定するよって
.整数全体をあらかじめsetで持っておく
.区間クエリ[l,r),tが来るたびにset中の[l,r)に含まれる要素を消しながら答えにtを加算していく

int main(){
	int N, M; cin >> N >> M;
	vector<int>T(M), L(M), R(M);
	for (int i = 0; i < M; ++i)cin >> T[i] >> L[i] >> R[i], --L[i];
	set<int>se;
	for (int i = 0; i < N; ++i)se.insert(i);
	ll res = 0;
	for (int i = M - 1; i >= 0; --i) {
		auto it = se.lower_bound(L[i]);//setの中からL[i]以上となるポインタを見つける
		//set内を走査していく
		while (it != se.end() && *it < R[i]) {
			res += T[i];
			auto it2 = it;
			++it2;
			se.erase(it);
			it = it2;
		}
	}
	cout << res << endl;
	return 0;
}

別解法
操作がvとのmaxをとる、のところをvを加算するにするとimosっぽくできる
今回も各区間クエリに対してその両端の情報をためておいて最後にそれを総合するいもす法的方法がとれる各情報につき区間のL側でinsertしR側でeraseする感じの実装をする

int main(){
	int N, M; cin >> N >> M;
	Graph begin, end;
	begin.resize(N+1);
	end.resize(N+1);
	REP(i, M) {
		int t, l, m; cin >> t >> l >> m;
		l--;															
		begin[l].push_back(t);
		end[m].push_back(t);
	}
	ll ans = 0;
	set<int>st;
	st.insert(0);
	REP(i, N) {
		for (auto a : begin[i])st.insert(a);
		for (auto a : end[i])st.erase(a);
		ans += *prev(st.end());
	}
	cout << ans << endl;
	return 0;
}

abc 128 E
これ感動

int main(){
	int n, q; cin >> n >> q;
	int ind[200020];
	int l[200020], r[200020], x[200020];
	for (int i = 0; i < n; ++i) {
		int s, t; cin >> s >> t >> x[i];
		ind[i] = i;
		l[i] = s - x[i], r[i] = t - x[i];
	}
	int d[200020];
	for (int i = 0; i < q; ++i) {
		cin >> d[i];
	}
	vector<int>ps[200020], pp[200020];
	//ps[k]:=dの中でl[i]以上を示すイテレータがkになるようなx
	//pp[k]:=dの中でr[i]以上を示すイテレータがkになるようなx
	for (int i = 0; i < n; ++i) {
		int k = lower_bound(d, d + q, l[i]) - d;
		ps[k].push_back(x[i]);
		k = lower_bound(d, d + q, r[i]) - d;
		pp[k].push_back(x[i]);
	}
	multiset<int>st;
	for (int i = 0; i < q; ++i) {
		for (auto y : ps[i]) {
			st.insert(y);
		}
		for (auto y : pp[i]) {
			st.erase(st.lower_bound(y));
		}
		if (st.empty())cout << -1 << endl;
		else cout << (*st.begin()) << endl;
	}
	return 0;
}

ex past 整地

ll l[100010], r[100010], p[100010];
using pI = pair<ll, int>;
ll s1[100010]; 
int main(){
    s1[0] = 0;
	ll n, w, c; cin >> n >> w >> c;
	ll tot = 0;
	for (int i = 0; i < n; ++i) {
		cin >> l[i] >> r[i] >> p[i];
		tot += p[i];
	}
	vector<pI>vr(n), vl(n);
	for (int i = 0; i < n; ++i) {
		vr[i] = { r[i],i };
		vl[i] = { l[i],i };
	}
	sort(vr.begin(), vr.end());
	sort(vl.begin(), vl.end());
	for (int i = 0; i < n; ++i) {
		s1[i + 1] = s1[i] + p[vr[i].second];
	}
	ll s2[100010]; s2[0] = 0;
	for (int i = 0; i < n; ++i) {
		s2[i + 1] = s2[i] + p[vl[i].second];
	}
	ll ans = tot;
	int k = lower_bound(vl.begin(), vl.end(),pI(c,0)) - vl.begin();
	//左の石から探索
	ans = min(ans, s2[k]);
	for (int i = 0; i < n; ++i) {
		if (vr[i].first + c > w)break;
		k = lower_bound(vl.begin(), vl.end(), pI(vr[i].first + c, 0)) - vl.begin();
		ans = min(ans, s2[k] - s1[i + 1]);
	}
	cout << ans << endl;
	return 0;
}

全く同じ型ではないが前処理してから左から見ていくのは同じ