CF1651F Tower Defence

其實是一道分塊題，但是我不想寫分塊，于是就寫了主席樹。

暴力是顯然的，每一個怪物出現時都讓它把塔挨個走一遍即可。現在要優化這個暴力，就要考慮如何快速處理每個怪物的情況。

發現一個怪物會讓一段塔的前綴的魔力值變成 \(0\)，然后死在一個塔上并讓這個塔的魔力值減小一部分，后面的塔不動。那么如果我們把這一段變為 \(0\) 的前綴劃分為一個段，每次模擬怪物走過的路時按照段來模擬，不難發現段數是 \(O(n)\) 的，復雜度就是正確的。

現在問題主要在于如何正確維護一段中每個塔當前的魔力值，畢竟每個塔的上限和回復值都是不一樣的。這里有一道引子題：CF837G，大體題意為給定 \(n\) 個一次分段函數 \(f_i(x)\)，求其中一段函數值的和。做法是以值域為范圍、開 \(n\) 棵主席樹，每棵主席樹維護當前分段函數在一定值域的函數值，即維護常數項和一次項系數，然后在主席樹上就能方便地查詢一段函數值的和了。那么這道題中，塔的魔力值同樣可以看作一個分段函數 \(f_i(x)=\begin{cases}r_ix&x\le\lfloor\frac{c_i}{r_i}\rfloor\\c_i&x>\lfloor\frac{c_i}{r_i}\rfloor\end{cases}\)，那么我們要求一段函數的和，同樣能套用 CF837G 的方法。

然后這道題就差不多了，我們用棧來維護所有段，對于每個怪物挨個遍歷所有段直到它死。如果當前段長度等于 \(1\)，顯然好維護；如果當前段的長度大于 \(1\)，就二分找到怪物死的位置，把這個單點維護一下剩余魔力值，之前的塔全部合并成魔力值為 \(0\) 的一個段即可。

細節不少。最后是因為各種調試而碼風極其混亂的代碼：

#include<bits/stdc++.h>
#define int long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;

char buf[1<<20],*p1=buf,*p2=buf;
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
constexpr int MAXN=2e5+5;
int n,q,c[MAXN],r[MAXN];
int rt[MAXN];
int top;
struct{
	int id,nc,lst;
}stk[MAXN];
int now,P;
struct{
	#define lp st[p].lc
	#define rp st[p].rc
	#define lq st[q].lc
	#define rq st[q].rc
	struct SegTree{
		int lc,rc;
		int a,b;
	}st[MAXN<<6];
	int tot;
	void chg(int x,int ka,int kb,int s,int t,int q,int&p){
		st[p=++tot]=st[q];
		st[p].a+=ka,st[p].b+=kb;
		if(s==t) return;
		int mid=(s+t)>>1;
		if(x<=mid) chg(x,ka,kb,s,mid,lq,lp);
		else chg(x,ka,kb,mid+1,t,rq,rp);
	}
	int ask(int l,int r,int x,int s,int t,int q,int p){
		if(l<=s&&t<=r) return (st[p].a-st[q].a)*x+st[p].b-st[q].b;
		int mid=(s+t)>>1,res=0;
		if(l<=mid) res+=ask(l,r,x,s,mid,lq,lp);
		if(mid<r) res+=ask(l,r,x,mid+1,t,rq,rp);
		return res;
	}
}T;

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		c[i]=read(),r[i]=read();
		T.chg(0,r[i],0,0,2e5+1,rt[i-1],rt[i]);
		if(c[i]/r[i]<=2e5) T.chg(c[i]/r[i]+1,-r[i],c[i],0,2e5+1,rt[i],rt[i]); 
	}
	q=read();
	stk[0]={n+1,0,0};
	for(int i=n;i;i--) stk[++top]={i,c[i],0};
	int ans=0;
	while(q--){
		int t=read(),h=read();
		while(top){
			int L=stk[top].id,R=stk[top-1].id-1,dt=t-stk[top].lst;
			if(L==R){
				int tp=min(c[L],dt*r[L]+stk[top].nc);
				if(tp>h){
					stk[top].nc=tp-h;
					stk[top].lst=t;
					break;
				}else h-=tp,top--;
			}else{
				int fk=T.ask(0,min(dt,200001ll),dt,0,2e5+1,rt[L-1],rt[R]);
				if(fk>h){
					int P=L-1;
					int l=L,r=R;
					while(l<=r){
						int mid=(l+r)>>1;
						if(T.ask(0,min(dt,200001ll),dt,0,2e5+1,rt[L-1],rt[mid])<=h) P=mid,l=mid+1;
						else r=mid-1;
					}
					int now=T.ask(0,min(dt,200001ll),dt,0,2e5+1,rt[L-1],rt[P]);
					P++;
					if(P==R) top--;
					else stk[top].id=P+1;
					h-=now;
					int tp=min(c[P],::r[P]*dt);
					stk[++top]={P,tp-h,t};
					break;
				}else h-=fk,top--;
			}
		}
		if(!top) ans+=h;
		if(stk[top].id!=1) stk[++top]={1,0,t};
	}
	printf("%lld\n",ans);
	return 0;
}