Codeforces ECR #124 : F. Tower Defense

確かにタワーディフェンスゲームっぽい。
https://codeforces.com/contest/1651/problem/F

問題

1次元の数直線上に1の間隔でN個の塔が並んでいる。
各塔は、マナの最大容量と秒間回復量が与えられる。

ここにQ体のモンスターがやってくる。モンスターの登場時刻と体力がそれぞれ与えられる。
モンスターは1秒ごとに距離1を移動する。塔の前を通過する際、min(残体力,塔のマナ)だけ、体力と塔のマナを消費する。

モンスターがN個の塔を通りすぎたときの残体力の総和を求めよ。

解法

まず塔が離れているという設定は無視してよい。
全部同じ場所にあり、タイムラグなく同時にマナを消費するとして考える。

基本的には塔の残マナのprefix sumがモンスターの体力に到達するところまで、マナを消費していく。
問題は、一旦マナを消費しきった塔がその後またマナが最大になるまでの時間が塔ごとに異なる点である。

これはPrefix sumを取れる永続SegTreeを使い、前回のモンスター来襲後の時間で塔の状態がどうなっているかを保持・更新していくとよい。

int N;
ll C[202020],R[202020];

struct node {
	node *lef, *ri;
	ll SC,SR;
	node(): lef(NULL),ri(NULL),SC(0),SR(0) {};
	node(node* L,node* R,ll SC,ll SR): lef(L),ri(R),SC(SC),SR(SR) {};
	
	void build(int L,int R) {
		if(L+1==R) {
			SR=::R[L];
			return;
		}
		int M=(L+R)/2;
		lef=new node();
		ri=new node();
		lef->build(L,M);
		ri->build(M,R);
		SC=lef->SC+ri->SC;
		SR=lef->SR+ri->SR;
	}
	
	node* update(int L,int R,int P,int V) {
		if(L+1==R) {
			return new node(NULL,NULL,V,0);
		}
		int M=(L+R)/2;
		node* cur=new node(this->lef,this->ri,0,0);
		if(P<M) {
			cur->lef=this->lef->update(L,M,P,V);
		}
		else {
			cur->ri=this->ri->update(M,R,P,V);
		}
		cur->SC=cur->lef->SC+cur->ri->SC;
		cur->SR=cur->lef->SR+cur->ri->SR;
		return cur;
	}
	
	ll sum(ll m) {
		return SC+SR*m;
	}
	int search(int L,int R,int x,int y,ll* v,ll m) {
		if(x>=y||L>=R) return 0;
		if(L==x&&R==y&&*v>=this->sum(m)) {
			*v-=this->sum(m);
			return R-L;
		}
		if(L+1==R) return 0;
		int M=(L+R)/2;
		ll tar=this->lef->search(L,M,x,min(y,M),v,m);
		if(tar==max(0,min(M,y)-x)) {
			tar+=this->ri->search(M,R,max(M,x),y,v,m);
		}
		return tar;
	}
};

struct segment {
	int L,R;
	ll tim,vol;
};
int Q;
vector<pair<ll,int>> pos;
vector<node*> nodes;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>C[i]>>R[i];
		pos.push_back({C[i]/R[i],i});
	}
	sort(ALL(pos));
	nodes.push_back(new node());
	nodes.back()->build(0,N);
	FOR(i,N) {
		x=pos[i].second;
		nodes.push_back(nodes.back()->update(0,N,x,C[x]));
	}

	vector<segment> segs;
	for(i=N-1;i>=0;i--) segs.push_back({i,i+1,0LL,C[i]});


	ll ret=0;
	cin>>Q;
	while(Q--) {
		int T;
		ll H;
		cin>>T>>H;
		
		while(segs.size()&&H) {
			auto s=segs.back();
			segs.pop_back();
			if(s.L+1==s.R) {
				x=s.L;
				//単一項目
				ll now=min(C[x],s.vol+R[x]*(T-s.tim));
				if(now<=H) {
					H-=now;
				}
				else {
					segs.push_back({s.L,s.R,T,now-H});
					H=0;
				}
			}
			else {
				int tar=lower_bound(ALL(pos),make_pair(T-s.tim,0))-pos.begin();
				int cnt=nodes[tar]->search(0,N,s.L,s.R,&H,T-s.tim);
				if(cnt!=s.R-s.L) {
					if(cnt<=(s.R-s.L)-2) {
						segs.push_back({s.L+cnt+1,s.R,s.tim,0});
					}
					x=s.L+cnt;
					ll now=min(C[x],s.vol+R[x]*(T-s.tim));
					segs.push_back({s.L+cnt,s.L+cnt+1,T,now-H});
					H=0;
				}
			}
		}
		
		
		//なくなったセグメントを埋める
		if(segs.empty()) {
			segs.push_back({0,N,T,0});
		}
		else if(segs.back().L!=0) {
			segs.push_back({0,segs.back().L,T,0});
		}
		
		ret+=H;
	}
	cout<<ret<<endl;
}

まとめ

永続SegTree系、久々に使ったかも。