省略
省略
C++に変換後のコードはこちら
int N, M, Q, L[1d5], R[1d5], X;
char S[200002];
set<int> ones;
set<int>::iterator it1, it2;
{
int i, j, k, res = 0;
rangeTree2d_nw<int,int> t;
rd(N,M,Q,S,(L--,R--)(M));
rep(i,N) S[i] -= '0';
rep(i,N) if(S[i]) ones.insert(i);
ones.insert(-1);
ones.insert(N);
rep(i,M){
k = *(ones.lower_bound(L[i]));
if(k <= R[i]) res++;
}
t.build(M, L, R);
rep(Q){
rd(X--);
S[X] ^= 1;
if(S[X]==1){
ones.insert(X);
it1 = it2 = ones.lower_bound(X);
it1--; it2++;
res += t.query((*it1)+1, *it2, (*it1)+1, *it2);
res -= t.query((*it1)+1, X, (*it1)+1, X);
res -= t.query(X+1, *it2, X+1, *it2);
} else {
it1 = it2 = ones.lower_bound(X);
it1--; it2++;
ones.erase(X);
res -= t.query((*it1)+1, *it2, (*it1)+1, *it2);
res += t.query((*it1)+1, X, (*it1)+1, X);
res += t.query(X+1, *it2, X+1, *it2);
}
wt(res);
}
}
Current time: 2024年03月28日19時25分21秒
Last modified: 2019年12月27日22時39分02秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)