AtCoder ABC #242 : G - Range Pairing Query

こっちは普通に解けた。
https://atcoder.jp/contests/abc242/tasks/abc242_g

問題

1～N番の人がおり、それぞれ来ている服の色が与えられる。
以下のクエリに答えよ。

• 区間[L,R]が与えられる。この区間に該当する番号の人を集め、同じ色の服を着た2名をペアにしていくとき、最大何組のペアが作れるか。

解法

区間内において登場頻度が奇数である服の色の数がわかればよい。
区間の両端を1伸び縮みさせたとき、その差分はO(1)で求められる。
よってクエリを先読みして並べ替え、Mo's algorithmを適用しよう。

int N,Q;
int A[101010];
int L[1010101],R[1010101];
vector<pair<int,int>> cand[1010];
int ret[1010101];
int vis[101010];
const int DI=330;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>Q;
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		L[i]--;
		cand[L[i]/DI].push_back({R[i],i});
	}
	FOR(i,DI) {
		ZERO(vis);
		int CL=0,CR=0;
		sort(ALL(cand[i]));
		int num=0;
		FORR2(r,cur,cand[i]) {
			while(CR<r) {
				num-=vis[A[CR]];
				vis[A[CR]]^=1;
				num+=vis[A[CR]];
				CR++;
			}
			while(CL<L[cur]) {
				num-=vis[A[CL]];
				vis[A[CL]]^=1;
				num+=vis[A[CL]];
				CL++;
			}
			while(L[cur]<CL) {
				CL--;
				num-=vis[A[CL]];
				vis[A[CL]]^=1;
				num+=vis[A[CL]];
			}
			ret[cur]=((CR-CL)-num)/2;
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

以前もABCでMo出なかったけか。