yukicoder : No.833 かっこいい電車

B,Cが難しくてDが典型で簡単でした。
https://yukicoder.me/problems/no/833

問題

N個の車両が並んでおり、それぞれの格好よさが与えられる。
以下のクエリに順次答えよ。
クエリは指示と車両番号xが与えられる。

• 車両xと(x+1)を連結する
• 車両xと(x+1)の間を切断する
• 車両xの格好よさをインクリメントする
• 車両xと連結する全車両の格好よさの総和を求める。

解法

BITで連続する車両の格好よさの総和を取れるようにしておけば、あとは連結状態の管理をするだけ。
以下のコードでは、setで各連結成分の先頭車両の番号を保持している。

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;

set<int> S;
int N,Q;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	for(i=1;i<=N;i++) {
		cin>>x;
		bt.add(i,x);
		S.insert(i);
	}
	S.insert(0);
	S.insert(N+1);
	while(Q--) {
		cin>>i>>x;
		if(i==1) S.erase(x+1);
		if(i==2) S.insert(x+1);
		if(i==3) bt.add(x,1);
		if(i==4) {
			auto it=S.lower_bound(x);
			if(*it==x) {
				it++;
				y=*it;
			}
			else {
				y=*it;
				it--;
				x=*it;
			}
			cout<<(bt(y-1)-bt(x-1))<<endl;
		}
	}
}

まとめ

末尾の番号を持っておいた方が楽だった。