My Blogs
P10542 [THUPC2024] RPG
一个有配合的“状态加攻击”一定是一个连续段，段内都在摸鱼。所以设 \(f_i\) 表示考虑了前 \(i\) 个人的最大收益：
\[f_i=\begin{cases} f_{i-1}+d_{b_i}\\ \max_{(x,y,z)\in \mathbb{E},y=b_i}g_x+z+d_{b_i} \end{cases} \]其中 \(g_i\) 表示满足 \(a_j=i\) 的最大的 \(f_{j-1}\)。暴力做是 \(n^2\) 的，原因在于一个 \(y\) 对应的 \(x\) 可能会过多。
然后第二个式子只和 \(y\) 有关。所以考虑根号分治，对于一种 \(y\)，如果其入度过多，将其单独处理（每转移一位统计存在 \(x=a_i\) 的 \(y\)）。取阈值为 \(\sqrt n\) 可以做到 \(\mathcal O(n\sqrt n)\)。实现不能太烂（有点卡常）。
int n,m,X,Y,d[200010],a[200010],b[200010];
int val[200010],now[200010],f[200010];
vector<pii> ve[200010];
vector<pii> nex[200010];
vi tmp;
const int B=700;
inline void mian()
{
read(n,m,X,Y);int x,y,z;
for(int i=1;i<=X;++i)read(d[i]);
for(int i=1;i<=n;++i)read(a[i],b[i]);
while(m--)read(x,y,z),ve[y].eb(mp(x,z));
memset(val,128,sizeof(val)),memset(now,128,sizeof(now));
for(int i=1;i<=X;++i)if(ve[i].size()>B)
for(auto p:ve[i])nex[p.fi].eb(mp(i,p.se));
for(int i=1;i<=n;++i)
{
f[i]=f[i-1]+d[b[i]];
if(ve[b[i]].size()<=B)
{
for(auto p:ve[b[i]])
Mmax(f[i],val[p.fi]+p.se+d[b[i]]);
}
else Mmax(f[i],now[b[i]]+d[b[i]]);
Mmax(val[a[i]],f[i-1]);
for(auto p:nex[a[i]])Mmax(now[p.fi],p.se+f[i-1]);
}
write(f[n]);
}