TopCoder SRM 839 : Div1 Hard Proximity

Mediumより簡単では…？
https://community.topcoder.com/stat?c=problem_statement&pm=17859

問題

許容誤差Dが与えられたとき、整数列の類似度とは、差がD以下である要素の対の個数とする。
整数列Cに対し、N通りの区間が与えられる。
各区間に対応するCの連続部分列に対する類似度の総和を求めよ。

解法

BITで、区間内に含まれる値の登場頻度を管理し、その総和を高速に計算できるようにしよう。
区間の端を１伸び縮みさせるとき、上記BITを用いれば類似度の辺分は高速に計算できる。
あとは各区間に対しMo's Algorithmで類似度を適宜求めて行けばよい。

ll A[101010],B[101010],C[101010];
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bit;
const int DI=350;
vector<pair<int,int>> ev[DI];
const ll mo=1000000007;

class Proximity {
	public:
	int count(int N, int Q, int D, int M, int L, int seed) {
		ll state = seed;
		int i;
		FOR(i,N) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			C[i] = state%M+123456;
		}
		FOR(i,DI) ev[i].clear();
		FOR(i,Q) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			ll ql = L + (state % (N-L+1));
			state = (state * 1103515245 + 12345)%(1LL<<31);
			A[i] = state % (N-ql+1);
			B[i] = A[i] + ql;
			ev[A[i]/DI].push_back({B[i],i});
		}
		ll ret=0;
		FOR(i,DI) {
			sort(ALL(ev[i]));
			int L=-1,R=-1;
			ll sum=0;
			FORR(e,ev[i]) {
				int cur=e.second;
				if(L==-1) L=R=A[cur];
				while(R<B[cur]) {
					sum+=bit(C[R]+D)-bit(C[R]-D-1);
					bit.add(C[R],1);
					R++;
				}
				while(A[cur]<L) {
					L--;
					sum+=bit(C[L]+D)-bit(C[L]-D-1);
					bit.add(C[L],1);
				}
				while(L<A[cur]) {
					bit.add(C[L],-1);
					sum-=bit(C[L]+D)-bit(C[L]-D-1);
					L++;
				}
				(ret+=sum)%=mo;
			}
			
			while(L<R) {
				bit.add(C[L],-1);
				L++;
			}
			
		}
		
		return ret;
	}
}

まとめ

Moは毎回1から書いてるんだけど、なんかライブラリ化した方がいいんかな。