kojingharangの日記

174 C. Range Increments

19:28 |

• 0-10^5の数字が1-10^5個入った配列が与えられる。全部 0 の状態から始めて与えられた配列にするには、L番目の数からR番目の数を +1 する操作を最低何回すればいいか。

• 苦手な雰囲気がぷんぷんする
• 最大値が連続してるとこを削ってく方法だと、最大値 M, 個数 N として O(NM) かかるのでだめ

• なんかスタックを使って O(N) でできる雰囲気がする
• 左から見て行って、topの値より大きかったら push, 小さかったら top が表す区間が終わるので pop すると同時に (L, R) と呼ぶ回数を記録する
• スタックに入れる値としては、区間の高さと始まりの位置でよさそう
• ならしコストを考えると push した分しか pop しないので O(N)
• push するときの始まりの位置は、最後に pop した区間の始まりの位置と同じにするとかいうあたりが面倒
• なんかぐちゃぐちゃしてて怪しい
• どっかミスっててもおかしくないけど通った

int main() {
	int N;
	cin>>N;
	vector<PII> st(100010);
	vector<pair<PII, int> > ans(100010);
	int ansp=0;
	int anscount=0;
	int stp=0;
	REP(i, N) {
		int v;
		cin>>v;
		int push_pos=i;
		while(stp>0 && st[stp-1].second > v) {
			push_pos = st[stp-1].first;
			//cout<<"push_pos "<<push_pos<<endl;
			int prevH = max(v, stp-1>0 ? st[stp-2].second : 0);
			ans[ansp++] = MP(MP(st[stp-1].first+1, i), st[stp-1].second - prevH);
			anscount += st[stp-1].second - prevH;
			stp--;
		}
		if(stp==0) {
			if(v>0) st[stp++] = MP(push_pos, v);
		} else if(st[stp-1].second < v) {
			st[stp++] = MP(push_pos, v);
		}
		//REP(m, stp) cout<<st[m]<<" "; cout<<endl;
	}
	while(stp>0) {
		int prevH = stp-1>0 ? st[stp-2].second : 0;
		ans[ansp++] = MP(MP(st[stp-1].first+1, N), st[stp-1].second-prevH);
		anscount += st[stp-1].second-prevH;
		stp--;
	}
	
	cout<<anscount<<endl;
	REP(i, ansp) {
		REP(j, ans[i].second) {
			cout<<ans[i].first.first<<" "<<ans[i].first.second<<endl;
		}
	}
	
	return 0;
}

ツイートする