【学习笔记】CF1651F Tower Defense

本文主要是介绍【学习笔记】CF1651F Tower Defense，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先转换一下题意。令 $cur_i$ 表示第 $i$ 个塔当前的魔力，每次操作，我们将过程描述为：

对于每个 $i$ ， $cur_i:=\min(a_i+t\cdot r_i,c_i)$ ，其中 $t$ 表示和上一个怪兽出现的时间之差
找到一段前缀，将这段前缀推平成 $0$

考虑对塔分块。对于每个块，我们维护是否有推平标记，以及上一次被推平的时间。我们只需预处理出，假设当 $t = 0$ 时这段区间被推平，过了 $x$ 秒后这段区间的和即可。根据推平标记的均摊可以得到复杂度为 $O(n\sqrt{n})$ 。

考虑优化。首先我们知道单个位置的 $cur_i$ 关于时间 $t$ 是分段函数，而若干个一次函数的和可以简单维护，因此可以考虑对于每个时间 $t$ 建立一个线段树（用可持久化线段树实现），这样我们能快速求出区间 $[l, r]$ 的和；其次，类似于颜色段均摊，每次区间推平时颜色段会减少，并且每次操作时颜色段只会增加常数段，因此复杂度均摊为 $O(n\log n)$ 。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=2e5+5;
const int M=N*30;
int n,m,tot,st[N],f[N],pre[N],rt[N];
ll c[N],re[N],cur[N],res;
vector<int>q[N];
struct node{int l,r;ll k,b;
}t[M];
void pushup(int p){t[p].k=t[t[p].l].k+t[t[p].r].k;t[p].b=t[t[p].l].b+t[t[p].r].b;
}
void build(int &p,int l,int r){if(!p)p=++tot;if(l==r){t[p].k=re[l];return;}int mid=l+r>>1;build(t[p].l,l,mid),build(t[p].r,mid+1,r);pushup(p);
}
int upd(int p,int l,int r,int x){int q=++tot;if(l==r){t[q].b=c[x];return q;}t[q]=t[p];int mid=l+r>>1;if(x<=mid)t[q].l=upd(t[q].l,l,mid,x);else t[q].r=upd(t[q].r,mid+1,r,x);pushup(q);return q;
}
void del(int p,int l,int r,int ql,int qr,ll d,ll &h){if(ql>qr)return;if(ql<=l&&r<=qr){h-=d*t[p].k+t[p].b;return;}int mid=l+r>>1;if(ql<=mid)del(t[p].l,l,mid,ql,qr,d,h);if(mid<qr)del(t[p].r,mid+1,r,ql,qr,d,h);
}
ll sm1[M],sm2[M];
void dfs(int p,int l,int r,int x){if(l==r){sm1[p]=t[p].k,sm2[p]=t[p].b;return;}int mid=l+r>>1;if(x>mid){dfs(t[p].r,mid+1,r,x);sm1[p]=sm1[t[p].r];sm2[p]=sm2[t[p].r];}else{dfs(t[p].l,l,mid,x);sm1[p]=sm1[t[p].l]+t[t[p].r].k;sm2[p]=sm2[t[p].l]+t[t[p].r].b;}
}
int query(int p,int l,int r,int x,ll d,ll h){if(l==r){if(h>=d*t[p].k+t[p].b)return l;return l-1;}int mid=l+r>>1;if(x>mid)return query(t[p].r,mid+1,r,x,d,h);if(x<=l){if(h>=t[t[p].l].k*d+t[t[p].l].b){return query(t[p].r,mid+1,r,x,d,h-t[t[p].l].k*d-t[t[p].l].b);}else{return query(t[p].l,l,mid,x,d,h);}}else{if(h>=sm1[t[p].l]*d+sm2[t[p].l]){return query(t[p].r,mid+1,r,x,d,h-sm1[t[p].l]*d-sm2[t[p].l]);}else{return query(t[p].l,l,mid,x,d,h);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>c[i]>>re[i],cur[i]=c[i];st[i]=i,f[i]=1;ll x=(c[i]+re[i]-1)/re[i];if(x<=200000)q[x].pb(i);}build(rt[0],1,n);for(int i=1;i<=200000;i++){rt[i]=rt[i-1];for(auto e:q[i]){rt[i]=upd(rt[i],1,n,e);}}cin>>m;for(int i=1;i<=m;i++){ll t,h;cin>>t>>h;int p=1;while(p<=n){if(f[p]){cur[p]=min(c[p],cur[p]+(t-pre[p])*re[p]);pre[p]=t;ll tmp=min(h,cur[p]);cur[p]-=tmp,h-=tmp;if(!h)break;p++;}else{int d=t-pre[p];dfs(rt[d],1,n,p);int r=query(rt[d],1,n,p,d,h);if(r>=st[p]){del(rt[d],1,n,p,st[p],d,h);p=st[p]+1;}else{r++;del(rt[d],1,n,p,r-1,d,h);cur[r]=min(c[r],(t-pre[p])*re[r])-h;if(r<st[p])st[r+1]=st[p],pre[r+1]=pre[p],f[r+1]=0;st[r]=r,f[r]=1,pre[r]=t,h=0,p=r;break;}}}if(p>1){st[1]=p-1,f[1]=0,pre[1]=t;}res+=h;}cout<<res;
}