Google Code Jam 2022 Round 3 : B. Duck, Duck, Geese

これは考察そこまで難しくないし、解きたかったな…。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4/0000000000b45244

問題

N人の人が円形に並んでいる。
各人、C色のうちいずれかの帽子をかぶっている。

この人々のうち、2人以上(N-1)人以下の連続した人の区間を考える。
各色の帽子cに対し、帽子cをかぶっている人の人数が、0人または(A[c]人以上B[c]人以下)を達成しているような区間は、何通りか。

解法

区間の左端を固定して考える。
各色において、区間の右端の取りえる範囲は最大2つの範囲になる。
そこで、区間加算が可能で、区間最大値とその最大値を満たすキーの個数を答えるSegTreeを持とう。
上記範囲に対し、1を加算するようにする。
そうすると、SegTree上で和がCを取れるようなキーの個数が、取りえる右端の数となる。

あとは左端をずらしながら、SegTreeを更新し、適宜和がCとなるキーの個数を数え上げて行けばよい。

int N,C;
int A[101010],B[101010];
int P[301010];
vector<int> Cs[101010];
int L[2][101010],R[2][101010];
static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<pair<int,int>> val;
	vector<int> add;
	SegTree_3(){
		reinit();
	};
	void reinit() {
		int i;
		val.clear();
		add.clear();
		val.resize(NV*2,{0,1});
		add.resize(NV*2,0);
		for(i=NV-1;i>=1;i--) val[i].second=val[2*i].second+val[2*i+1].second;
	}
	pair<int,int> merge(pair<int,int> a,pair<int,int> b) {
		if(a.first<b.first) return b;
		if(a.first>b.first) return a;
		return {a.first,a.second+b.second};
	}
	
	pair<int,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return {-1,0};
		if(x<=l && r<=y) return val[k];
		auto v=merge(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		v.first+=add[k];
		return v;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k].first+=v;
			add[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			val[k]=merge(val[k*2],val[k*2+1]);
			val[k].first+=add[k];
		}
	}
};
SegTree_3<int,1<<20> st;

void update(int c,int n) {
	int f=lower_bound(ALL(Cs[c]),n)-Cs[c].begin()-1;
	R[0][c]=3*N;
	L[1][c]=R[1][c]=3*N;
	if(f+1<Cs[c].size()) {
		R[0][c]=Cs[c][f+1];
		if(A[c]) {
			if(f+A[c]<Cs[c].size()) {
				L[1][c]=Cs[c][f+A[c]];
			}
			if(f+B[c]+1<Cs[c].size()) {
				R[1][c]=Cs[c][f+B[c]+1];
			}
		}
	}
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	st.reinit();
	
	cin>>N>>C;
	FOR(i,C) {
		cin>>A[i]>>B[i];
		Cs[i].clear();
		if(B[i]>=1&&A[i]==0) A[i]++;
	}
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		Cs[P[i]].push_back(i);
		Cs[P[i]].push_back(N+i);
		Cs[P[i]].push_back(2*N+i);
	}
	FOR(i,C) {
		sort(ALL(Cs[i]));
		if(B[i]>=1&&A[i]==0) A[i]++;
		update(i,0);
		st.update(L[0][i],R[0][i],1);
		st.update(L[1][i],R[1][i],1);
	}
	ll ret=0;
	FOR(i,N) {
		auto p=st.getval(i+1,i+N-1);
		if(p.first==C) ret+=p.second;
		x=P[i];
		st.update(L[0][x],R[0][x],-1);
		st.update(L[1][x],R[1][x],-1);
		update(x,i+1);
		st.update(L[0][x],R[0][x],1);
		st.update(L[1][x],R[1][x],1);
		
	}
	
	cout<<"Case #"<<_loop<<": "<<ret<<endl;
}

まとめ

本番は、区間の積集合を取ろうとして破綻してた。
普通に各キーを覆う区間を数え上げればよかったか…。