Codeforces Global Round 23 : F. Kazaee

なんだこの問題名。
https://codeforces.com/contest/1746/problem/F

問題

整数列Aが与えられる。
以下のクエリに答えよ。

• Aの1要素を指定された値に上書きする。
• Aの部分列A[L,R]と正整数Kが与えられる。A[L,R]の中に、登場回数がKの倍数でない値があるかどうか答えよ

解法

乱択で解く。
Aの各値に対し、ランダムな値を割り当てておく。
sum(A[L,R])がKの倍数であれば、A[L,R]内の同じ値の登場回数もおそらくKの倍数である。
Aに割り当てるランダム値を30回ぐらい切り替えれば、まずこれで判定できる。

int N,Q;
int A[303030],C[303030];
int T[303030],L[303030],R[303030],K[303030];
int ng[303030];

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<ll,20> bt;

std::random_device rnd;
std::mt19937 mt(rnd());

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> V;
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
		V.push_back(A[i]);
	}
	FOR(i,Q) {
		cin>>T[i]>>L[i]>>R[i];
		if(T[i]==1) {
			L[i]--;
			V.push_back(R[i]);
		}
		else {
			L[i]--,R[i]--;
			cin>>K[i];
		}
	}
	sort(ALL(V));
	FOR(i,N) A[i]=lower_bound(ALL(V),A[i])-V.begin();
	FOR(i,Q) if(T[i]==1) R[i]=lower_bound(ALL(V),R[i])-V.begin();
	
	for(int step=0;step<30;step++) {
		vector<int> table;
		FOR(i,V.size()) table.push_back(mt());
		ZERO(bt.bit);
		
		FOR(i,N) {
			C[i]=A[i];
			bt.add(i,table[C[i]]);
		}
		FOR(i,Q) {
			if(T[i]==1) {
				x=L[i];
				bt.add(x,-table[C[x]]);
				C[x]=R[i];
				bt.add(x,table[C[x]]);
			}
			else {
				ll a=bt(R[i])-bt(L[i]-1);
				if(a%K[i]) ng[i]=1;
			}
		}
	}
	FOR(i,Q) if(T[i]==2) {
		if(ng[i]) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	
	
}

まとめ

乱択で行けることに気付けば実装はさほど難しくない。
とはいえそこに本番中に気付けないよなぁ。