Codeforces 351(#204 Div1) D. Jeff and Permutation

Codeforces データ構造

問題

数列a[i]に対して次の操作を行うことができる。

  • 位置が等差数列になっている同じ値を選ぶ（a[i] = a[i + m] = a[i + 2*m] = ...)
  • この値を数列から削除する
  • 残った数を好きに並び替える


数列b[i]が与えられる。この数列に対して次のクエリm個に答えよ。
区間(li, ri)が与えられる。数列の(li, ri)を抜き出してa[i]とする。
a[i]を上の操作を行って全ての要素を削除するとき、必要な操作の最小回数を求める。

制約条件

b[i]≦10^9
b[i]の要素≦10^5個
m≦10^5

方針

クエリの答えは、区間(li, ri)中の異なる数字の数は最低必要。
どれかの数字の並びが等間隔になっているとき、その数を消せば並び替えで他の数を全部並べられる。そうでないときは+1回余分にかかる。


なので、(li, ri)中のdistinctな値の数と、値が等差数列で出現しているものの個数が（1個以上あるか）わかればよい。


よくある感じで区間クエリを平方分割して頑張る。(l, r)を(l / B, r)の順で並び替える。(B = √n)
すると、左端の調整は一回当たりO(√n)で、それがn回なので合計O(n√n)回。
右端の調整は、一つのバケットでは昇順になっているので、一つのバケットで最大n回。
それが√nバケットなのでO(n√n)回。
で、調整の回数がO(n√n)で抑えられる。


調整はどうやればいいかというと、a[i]の値ごとにdequeを作って、そこに要素を出し入れする。
入れたところの間隔がpos[k] - pos[k - 1] != pos[k - 1] - pos[k - 2]になっていたら、
その不連続点を記録しておく。不連続点もdequeで管理する。
空になるときだけ、異なる要素の数、不連続なa[i]の数を加減する。


これで一回の調整はO(1).
popの判定ほうを先にしてしまって、L≧Rにするというバグを埋め込んでしまい時間内に通せなかった。悲しい。

ソースコード

const int B = 400;
const int MX = 100010;
int n, m, a[MX], ans[MX];
vector<pair<pi, pi> > q; //(bkt, r, l, id)

int pt_cnt, jmp_cnt;
deque<int> jmp[MX], pt[MX];

#define PT pt[val]
#define JM jmp[val]

inline void pop_front(int val){
	PT.pop_front();
	if(PT.empty()) pt_cnt--;
	if(PT.size() && JM.size() && JM.front() == PT.front()){
		JM.pop_front();
		if(JM.empty()) jmp_cnt--;
	}
}
inline void pop_back(int val){
	PT.pop_back();
	if(PT.empty()) pt_cnt--;
	if(PT.size() && JM.size() && JM.back() == PT.back()){
		JM.pop_back();
		if(JM.empty()) jmp_cnt--;
	}
}
inline void push_front(int pos){
	int val = a[pos];
	if(PT.empty()) pt_cnt++;
	PT.push_front(pos);
	if(PT.size() > 2 && PT[1] - PT[0] != PT[2] - PT[1]){
		if(JM.empty()) jmp_cnt++;
		JM.push_front(PT[1]);
	}
}
inline void push_back(int pos){
	int val = a[pos];
	if(PT.empty()) pt_cnt++;
	PT.pb(pos);
	int k = PT.size();
	if(k > 2 && PT[k - 1] - PT[k - 2] != PT[k - 2] - PT[k - 3]){
		if(JM.empty()) jmp_cnt++;
		JM.pb(PT[k - 2]);
	}
}

int main(){
	scanf("%d", &n);
	vi v;
	rep(i, n){
		scanf("%d", a + i);
		v.pb(a[i]);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	rep(i, n) a[i] = lower_bound(all(v), a[i]) - v.begin();
	
	scanf("%d", &m);
	rep(i, m){
		int l, r; scanf("%d%d", &l, &r); --l;
		q.pb(mp(mp(l / B, r), mp(l, i)));
	}
	sort(all(q));
	
	int L = 0, R = 0;
	
	rep(it, m){
		int l = q[it].second.first, r = q[it].first.second;
		int id = q[it].second.second;
		
		while(l < L) push_front(--L);
		while(r > R) push_back(R++);
		while(l > L) pop_front(a[L++]);
		while(r < R) pop_back(a[--R]);
		
		ans[id] = pt_cnt + (jmp_cnt == pt_cnt);
	}
	rep(i, m) printf("%d\n", ans[i]);
	
	return 0;
}