Codeforces 232(#144 Div1) D - Fence

問題

n項からなる数列a[i]が与えられる。これに対してq個のクエリに答えよ。

クエリ：　区間l, rが指定される。
[l, r]と長さが等しく、[l, r]に交わらない区間[s, t]で、a[l + i] = a[s + i] = constとなる区間はいくつあるか求めよ。

制約条件

n, q≦10^5
a[i]≦10^9

方針

まずはa[i]の差分を取り、d[i] = a[i + 1] - a[i]とする。e[i] = -d[i]とする。
で、d[i]（区切り文字）e[i]と並べた数列を文字列と見てsuffix arrayを作る。
suffix arrayの転置とLCP, LCPに対するRMQも作っておく。

クエリに対して、sa[l + n + 1] = xとなるxを転置により求める。（マイナスの符号をつけたほうの[l, r]のsuffix array上での位置を探す）

LCP上を二分探索して、x, y間のLCPの最小値がr - l以上であるような最大、最小のyを求める。
このminy〜maxyを使えば、suffix array上で[l, r]に一致する区間の先頭の添え字が{sa[i] | miny <= i <= maxy}と書ける。
この中から[l, r]に交わらないものを求めればよいので、数列の区間内でxx以上の個数を数える問題に帰着される。
つまり、range treeを作っておいて、[l, r]上でr + 1以上またはl - (r - l) - 1以下の数の個数を求めればよい。

range treeは蟻本のK番目の数字を解くのに使ったデータ構造で、
segment treeの各ノードにその区間の葉すべてを昇順に並べたものを持つやつ。
ここで二分探索をすればxx以上の個数は効率的に求められる。

range treeに最初全てのノードを入れてしまうとマイナスの区間の要素（e[i]由来のインデックス）もカウントしてしまうので、葉の初期化のときにはd[i]由来のやつのときだけ代入するようにする。

ソースコード

range treeのとこは挿入順をがんばってクエリをソートしてってやればsenment treeでもできてオーダーもO(qlog n)になる（けどめんどかった）。

int a[MAX_LEN], b[MAX_LEN];

const int N = 262144;
vi dat[2 * N - 1];

inline int qu(int a, int b, int k, int l, int r, int lo, int hi){//lo以下or, hi以上
	if(a <= l && r <= b) return
		(upper_bound(all(dat[k]), lo) - dat[k].begin())
		+ (dat[k].end() - lower_bound(all(dat[k]), hi));
	if(a >= r || b <= l) return 0;
	int x = qu(a, b, k * 2 + 1, l, (l + r) / 2, lo, hi);
	int y = qu(a, b, k * 2 + 2, (l + r) / 2, r, lo, hi);
	return x + y;
}

int main(){
	
	int m;
	scanf("%d", &m);
	vi v(m), d;
	rep(i, m){
		scanf("%d", &v[i]);
		if(i) d.pb(v[i] - v[i - 1]);
	}
	v = d;
	n = m - 1;
	rep(i, n) v.pb(-d[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	
	rep(i, n){
		a[i] = lower_bound(all(v), d[i]) - v.begin() + 2;
		a[i + n + 1] = lower_bound(all(v), -d[i]) - v.begin() + 2;
	}
	a[n] = 1;
	n = 2 * n + 1;
	
	buildSA(a);
	buildLCP(a);
	int *rmq = buildRMQ(lcp, n + 1);
	
	rep(i, n + 1) if(si[i] < m - 1) dat[i + N - 1].pb(si[i]);
	for(int i = N - 2; i >= 0; i--){
		int l = i * 2 + 1, r = i * 2 + 2;
		dat[i].resize(dat[l].size() + dat[r].size());
		merge(all(dat[l]), all(dat[r]), dat[i].begin());
	}
	
	int q; scanf("%d", &q);
	while(q--){
		
		int l, r; scanf("%d%d", &l, &r);
		
		if(l == r){
			printf("%d\n", m - 1);
			continue;
		}
		l--; r--;
		
		int t = is[l + m], x, y;
		int lo = -1, hi = t, mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			if(minimum(mid + 1, t, rmq, n + 1) >= r - l) hi = mid;
			else lo = mid;
		}
		x = hi;
		lo = t, hi = n + 1, mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			if(minimum(t + 1, mid, rmq, n + 1) >= r - l) lo = mid;
			else hi = mid;
		}
		y = hi;
		
		int ans = qu(x, y, 0, 0, N, l - (r - l) - 1, r + 1);
		printf("%d\n", ans);
	}
	return 0;
}