みんなのプロコン 2019 決勝 : D - Dangerous Hopscotch

これはさほど迷わず。
https://atcoder.jp/contests/yahoo-procon2019-final-open/tasks/yahoo_procon2019_final_d

問題

N個の石が並んでいる。
i番の石の上に乗っているとき、(i+1)番または(i+2)番の石のいずれか障害物が乗ってない方に移動することができるものとする。
初期状態ではどの石にも障害物が乗っていない。
以下のクエリに順次答えよ。

• 指定された番号の石の障害物有り無しを反転する。
• 区間[L,R]が与えられる、L番の石からR番の石に至る経路は何通りあるか。

解法

フィボナッチ数らしき遷移をすることがわかるので、行列乗算・行列累乗を使うことは容易に想像がつく。
まずクエリを先読みし、クエリに現れる番号を用いて座標圧縮しよう。
その際、障害物の有無が切り替わる石は、圧縮後も単独で１個分の座標を占めるものとする。

あとは圧縮後の各区間に漸化式に相当する行列(およびその累乗を)を載せたSegTreeを作り、区間の積を高速に求められるようにしておけばよい。

int N,Q;
int T[101010],L[101010],R[101010];
vector<int> cand;

const int MAT=2;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);v[0][0]=v[1][1]=1;};}; //
ll mo=1000000007;

Mat mulmat(Mat a,Mat b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

Mat okm,ngm;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	
	SegTree_1(){
		val=vector<V>(NV*2);
		Mat m;
		FORR(v,val) v=m;
	};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) {
			Mat m;
			return m;
		}
		if(x<=l && r<=y) return val[k];
		return mulmat(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry) {
		entry += NV;
		if(val[entry].v[0][0]==1) val[entry]=ngm;
		else val[entry]=okm;
		while(entry>1) entry>>=1, val[entry]=mulmat(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<Mat,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	cand.push_back(0);
	FOR(i,Q) {
		cin>>T[i];
		if(T[i]==1) {
			cin>>L[i];
			cand.push_back(L[i]);
			cand.push_back(L[i]+1);
		}
		else {
			cin>>L[i]>>R[i];
			cand.push_back(L[i]);
			cand.push_back(R[i]+1);
		}
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	okm.v[0][0]=okm.v[0][1]=okm.v[1][0]=1;
	okm.v[1][1]=0;
	ngm.v[1][0]=1;
	ngm.v[0][0]=ngm.v[0][1]=ngm.v[1][1]=0;
	FOR(i,cand.size()-1) st.val[(1<<20)+i]=powmat(cand[i+1]-cand[i],okm);
	for(i=(1<<20)-1;i>=1;i--) st.val[i]=mulmat(st.val[i*2],st.val[i*2+1]);
	
	FOR(i,Q) {
		if(T[i]==1) {
			x=lower_bound(ALL(cand),L[i])-cand.begin();
			st.update(x);
		}
		else {
			x=lower_bound(ALL(cand),L[i])-cand.begin();
			y=lower_bound(ALL(cand),R[i]+1)-cand.begin();
			Mat m=st.getval(x,y);
			cout<<m.v[0][1]<<endl;
		}
	}
	
	
}

まとめ

座標圧縮が絡むとなんか実装が面倒になるなぁ。