AtCoder ABC #441 (Promotion of Engineer Guild Fes) : G - Takoyaki and Flip

割とゴリ押した感がある。
https://atcoder.jp/contests/abc441/tasks/abc441_g

問題

N個のお皿が並んでおり、初期状態で各皿の上には何もなく、表を向いている。
以下のクエリに順次答えよ。

• 区間[L,R]と正整数Xが与えられる。お皿の区間[L,R]のうち表のお皿の上にX個ずつたこ焼きを追加する。
• 区間[L,R]が与えられる。区間内の各お皿のたこ焼きを取り除いたうえで、表裏逆にする。
• 区間[L,R]が与えられる。区間内の各お皿のうち、たこ焼きの置かれた数の最大値を答える。

解法

想定解はSegTreeだが、自分は平方分割で解いた。
ブロック毎に、最後に各お皿の個別の情報を更新した後に行われた、たこ焼き追加クエリの総和・表裏逆にした回数・(表のお皿が1個以上ある場合)たこ焼きの個数の最大値、を管理する。

各クエリについて、ブロック単位で情報を更新・参照する。
ただし区間の両端に相当するブロックだけはお皿単位で情報を更新する。
そうすればクエリあたりO(√N)程度で処理できる。

int N,Q;
const int DI=500;

int flip[252525];
ll val[252525];
ll add[DI],ma[DI];
ll F[DI];
int NF[DI];

void prop(int id) {
	int i;
	ma[id]=0;
	if(F[id]) {
		for(i=id*DI;i<(id+1)*DI;i++) {
			val[i]=0;
			flip[i]^=F[id]%2;
		}
	}
	NF[id]=0;
	for(i=id*DI;i<(id+1)*DI;i++) {
		if(flip[i]==0) {
			val[i]+=add[id];
			ma[id]=max(ma[id],val[i]);
			NF[id]++;
		}
	}
	F[id]=add[id]=0;
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,DI) prop(i);
	
	cin>>N>>Q;
	while(Q--) {
		int T,L,R,X;
		cin>>T>>L>>R;
		L--;
		if(T==1) {
			cin>>X;
			if(L/DI==R/DI) {
				prop(L/DI);
				for(i=L;i<R;i++) {
					if(flip[i]==0) val[i]+=X;
				}
				prop(L/DI);
			}
			else {
				if(L%DI) {
					prop(L/DI);
					while(L%DI) {
						if(flip[L]==0) val[L]+=X;
						L++;
					}
					prop(L/DI-1);
				}
				if(R%DI) {
					prop(R/DI);
					while(R%DI) {
						R--;
						if(flip[R]==0) val[R]+=X;
					}
					prop(R/DI);
				}
				for(i=L/DI;i<R/DI;i++) {
					add[i]+=X;
					if(NF[i]) ma[i]+=X;
				}
				
			}
		}
		else if(T==2) {
			if(L/DI==R/DI) {
				prop(L/DI);
				for(i=L;i<R;i++) {
					flip[i]^=1;
					val[i]=0;
				}
				prop(L/DI);
			}
			else {
				if(L%DI) {
					prop(L/DI);
					while(L%DI) {
						flip[L]^=1;
						val[L]=0;
						L++;
					}
					prop(L/DI-1);
				}
				if(R%DI) {
					prop(R/DI);
					while(R%DI) {
						R--;
						flip[R]^=1;
						val[R]=0;
					}
					prop(R/DI);
				}
				for(i=L/DI;i<R/DI;i++) {
					F[i]++;
					add[i]=0;
					ma[i]=0;
					NF[i]=DI-NF[i];
				}
				
			}
		}
		else {
			ll ret=0;
			prop(L/DI);
			while(L%DI&&L<R) {
				if(flip[L]==0) ret=max(ret,val[L]);
				L++;
			}
			while(L+DI<R) {
				ret=max(ret,ma[L/DI]);
				L+=DI;
			}
			prop(L/DI);
			while(L<R) {
				if(flip[L]==0) ret=max(ret,val[L]);
				L++;
			}
			cout<<ret<<endl;
		}
		
	}
}

まとめ

TLが2秒だったので、平方分割は想定じゃなさそうだな…と思いながら解いてた。