AtCoder ARC #068 : E - Snuke Line

シンプルな解法がある問題を力技で解くのあんまりよくないなぁ…。
http://arc068.contest.atcoder.jp/tasks/arc068_c

問題

0～Mの(M+1)個の駅が順に並んでいる。
i番目の種類のお土産は、L[i]～R[i]のいずれかの駅で購入できる。

ここで、0番の駅をはじめ、k=1,2,3...,M個毎の駅で止まる計M個の電車を考える。
各電車の停車駅で購入可能なお土産の種類を答えよ。

解法

本番は平方分割でゴリ押しで解いた。
SegTreeまたはBITを使った方がもう少しシンプルに解ける。

今k個毎の駅に止まる電車について考える。
販売する駅の区間がk個以上であるお土産は必ず買えるので、L[i],R[i]の細かい値は無視して買えるとカウントしてよい。

また、区間がk個未満であるようなお土産iについて、その電車が買える駅は高々1個である。
よって、SegTreeやBITを用いて、そのようなお土産に関し区間L[i]～R[i]に1加算するということを行おう。
このSegTreeにおいて、0,k,2k,3k,...の位置の値の総和を取れば、k未満の区間であるお土産の購入数が求められる。
上記のとおり同じお土産が２回買われることはないので同じお土産を重複カウントする危険はない。

上記考察をもとに実際に解く際には、kを小さい順に処理していき、kの処理が終わったら、区間の長さがkであるお土産をSegTreeに追加していくとよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};

BIT<ll,20> bt;
int N,M;
vector<int> E[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		E[y-x+1].push_back(x);
	}
	
	int morethan=N;
	for(i=1;i<=M;i++) {
		int ret=0;
		for(x=i;x<=M;x+=i) ret+=bt(x);
		
		FORR(e,E[i]) bt.add(e,1), bt.add(e+i,-1);
		cout<<morethan+ret<<endl;
		morethan -= E[i].size();
	}
}

まとめ

ARC/AGCは最近実装軽めで考察重めな問題が多い気が。