yukicoder : No.618 labo-index

むしろ元ネタが勉強になりました。
https://yukicoder.me/problems/no/618

問題

研究室のLabo-Index Lとは、L以上の研究力の研究員がL人以上いるような最大のLとする。
以下のクエリを順次処理したとき、そのつど研究室のLabo-Indexを答えよ。

• 研究力xの研究員が追加される
• 最初からx番目に追加された研究員が研究室をさる
• 研究室にいる全研究員の研究力がx上昇する

解法

３つ目のクエリは研究室にいるいない関係なく全員に効果があると考えよう。
こう考えると、常に３つ目のクエリは全員に効果があるので、研究員同士の相対的な研究力の差は変化しない。
そこで、全研究員の初期状態の(研究室追加前の上昇クエリ分を差し引いた)研究力を考え、その順で研究員を昇順ソートする。

あとは研究員の有無を0/1で表し、BITを用いることで、一定の研究力以上の研究員の人数を高速に求めることができる。
そこで、各クエリ後、BITを二分探索することでLを求めていこう。

//さらに短縮
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,bt2;

vector<int> V;
int Q;
ll T[101010],X[101010],F[101010],rev[101010];
int O[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	ll tadd=0;
	FOR(i,Q) {
		cin>>T[i]>>X[i];
		if(T[i]==1) {
			rev[i]=V.size();
			V.push_back(i);
		}
		else if(T[i]==3) {
			tadd+=X[i];
			bt.add(0,X[i]);
			bt.add(V.size(),-X[i]);
		}
	}
	
	vector<pair<ll,int>> P;
	FOR(i,Q) if(T[i]==1) {
		F[i]=X[i]+bt(rev[i]);
		P.push_back({F[i],i});
	}
	sort(ALL(P));
	FOR(i,P.size()) O[P[i].second]=i;
	
	ll add=0;
	FOR(i,Q) {
		if(T[i]==1) {
			bt2.add(O[i],1);
		}
		else if(T[i]==2) {
			bt2.add(O[V[X[i]-1]],-1);
		}
		else {
			add+=X[i];
		}
		
		ll dif=add-tadd;
		int L=0;
		for(j=20;j>=0;j--) {
			if(L+(1<<j)>V.size()) continue;
			
			ll t=L+(1<<j)-dif;
			x=lower_bound(ALL(P),make_pair(t,0))-P.begin();
			int num=bt2(Q)-(x?bt2(x-1):0);
			if(num>=L+(1<<j)) L+=1<<j;
		}
		cout<<L<<endl;
		
		
	}
	
	
}

まとめ

研究員を先にソートすることを思いつけたのでよかった。