LOJ3282 「JOISC 2020 Day4」治疗计划 (Treatment Project) 题解
首先考虑一个简单的 \(n^2\) dp，令 \(f_i\) 表示在 \(t_i\) 天， \(1\) 到 \(r_i\) 的所有人都已经被治疗完毕了的最小花费。
然后考虑 Dijkstra 一样的方式进行 dp，每次找到所有尚未松弛的 \(i\) 中 \(f_i\) 最小的那个进行转移，可以从 \(i\) 向 \(j\) 转移的条件是 \(r_i-l_j+1 \ge |t_i-t_j|\)（非常容易理解）.
最后只需找到满足 \(r_i=n\) 的所有 \(f_i\) 的最小值即可。
于是得到了复杂度为 \(O(m^2)\) 的做法。
然后考虑优化这一个过程。
对转移条件的绝对值进行分类讨论后可以简化为：
若 \(t_i \ge t_j\) 为 \(r_i-t_i+1 \ge l_j-t_j\)
若 \(t_i
然后考虑对所有治疗方案按 \(t_i\) 排序，维护一个堆来确定转移顺序，每次转移的时候分为两段在线段树上查询，可以保证正确性。
由于采用了类似 Dijkstra 的转移方式，\(f_i\) 只与向他转移的 \(f_j\) 的大小有关，可以保证每个点只需要被转移到一次，然后只要在线段树上把对应点的权值设为 \(\inf\) 即可。
于是得到了复杂度为 \(O(m\log m)\) 的做法。
Code(\(O(m^2)\)):
#include
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define INF ((int)1e18)
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair pii;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
#define N 5005
int t[N],l[N],r[N],w[N];
int f[N],vis[N],n,m;
int get()
{
int pos=0;
for(int i=1;i<=m;i++)
{
if(vis[i]) continue;
if(f[i]>n>>m;
for(int i=0;i<=m;i++) f[i]=INF;
for(int i=1;i<=m;i++)
{
t[i]=read(),l[i]=read(),r[i]=read(),w[i]=read();
if(l[i]==1) f[i]=w[i];
}
int pos=get();
while(pos)
{
vis[pos]=1;
for(int i=1;i<=m;i++)
{
if(r[pos]-l[i]>=abs(t[pos]-t[i])-1)
{
int R=f[pos]+w[i];
if(R Code(\(O(m\log m)\)):
#include
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define INF ((int)1e18)
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
typedef pair pii;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
#define N 100005
struct Node{int t,l,r,w;};
Node a[N];
bool cmp(Node x,Node y){return x.t,greater> q;
vector v;
struct Seg_tr
{
#define ls (u<<1)
#define rs (u<<1|1)
int tx[N*4],ty[N*4];
void pushup(int u)
{
tx[u]=min(tx[ls],tx[rs]);
ty[u]=min(ty[ls],ty[rs]);
}
void update(int u,int l,int r,int p,int dx,int dy)
{
if(l==r)
{
tx[u]=dx,ty[u]=dy;
return ;
}
int mid=(l+r)/2;
if(p<=mid) update(ls,l,mid,p,dx,dy);
else update(rs,mid+1,r,p,dx,dy);
pushup(u);
}
void queryx(int u,int l,int r,int L,int R,int d)
{
if(l>r) return ;
if(tx[u]>d) return ;
if(l==r)
{
v.pb(l); return ;
}
int mid=(l+r)/2;
if(mid>=L) queryx(ls,l,mid,L,R,d);
if(midr) return ;
if(ty[u]>d) return ;
if(l==r)
{
v.pb(l); return ;
}
int mid=(l+r)/2;
if(mid>=L) queryy(ls,l,mid,L,R,d);
if(mid>n>>m;
for(int i=1;i<=m;i++) a[i].t=read(),a[i].l=read(),a[i].r=read(),a[i].w=read();
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(a[i].l==1)
{
f[i]=a[i].w;
t.update(1,1,m,i,INF,INF);
q.push(mp(f[i],i));
}
else
{
f[i]=INF;
t.update(1,1,m,i,a[i].l+a[i].t,a[i].l-a[i].t);
}
}
while(!q.empty())
{
pii u=q.top(); q.pop();
int pos=u.sec;
if(f[pos]!=u.fir) continue;
v.clear();
t.queryy(1,1,m,1,pos-1,a[pos].r-a[pos].t+1);
t.queryx(1,1,m,pos+1,m,a[pos].r+a[pos].t+1);
for(int i:v)
{
int R=u.fir+a[i].w;
if(R