Codeforces #850 : Div1 C. Monsters (hard version)

Bより短い時間で解いてる。
https://codeforces.com/contest/1785/problem/C

問題

N体のモンスターがおり、それぞれのHPが与えられる。
これらを以下の手順を使い倒していく。

• 任意のモンスターのHPを1減らす
• 全モンスターのHPを1減らす。この際、もしHPを0にした敵がいるのであれば、再び全モンスターのHPを1減らすことを繰り返せる。

全モンスターのHPを0にするまでの前者の手順の実行回数の最小値を求めたい。
N体のモンスターのprefix K体に対する解をそれぞれ求めよ。

解法

HP 1～Mの敵がそれぞれ1匹以上いるような状態を作ろう。
そうするとM回後者の手順を取ることができる。
Kを増やしながら、そのようなMの最大値をSegTreeやsetを使い求めて行こう。

int T,N;
int A[202020];


static ll const def=-1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	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]+=v;
			ma[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);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<int,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<1<<19;i++) st.update(i,1<<19,-1);
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		ll anum=0;
		ll sum=0;
		
		multiset<int> M;
		
		FOR(i,N) {
			cin>>x;
			st.update(x,1<<19,1);
			M.insert(x);
			sum+=x;
			anum++;
			while(1) {
				x=st.getval(0,N+1);
				if(x<=0) break;
				x=N+1;
				for(j=19;j>=0;j--) if(x>(1<<j)&&st.getval(0,x-(1<<j))>=1) x-=1<<j;
				
				M.erase(M.find(x-1));
				anum--;
				sum-=x-1;
				st.update(x-1,1<<19,-1);
			}
			cout<<sum-(1LL*anum*(anum+1)/2)<<" ";
		}
		cout<<endl;
		
		
		FORR(m,M) st.update(m,1<<19,-1);
		
	}
}

まとめ

やることは割と自明で、実装にちょっと戸惑うタイプの問題。