ToB企服应用市场:ToB评测及商务社交产业平台

标题: [ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理 [打印本页]

作者: 嚴華 时间: 2024-7-26 09:07
标题: [ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理
思路：

对于插入操作，设插入 \(\{t,p\}\)：

若当前 \(1 \sim t\) 有空位，那么就放进去。
否则，\(1 \sim t\) 是被塞满了的：
- 起首容易想到的是找到 \(1 \sim t\) 中贡献最小的那个工作，若贡献比 \(p\) 还小，可以与之更换掉。
- 但是假了，考虑这样一种情况：在 \(1 \sim t\) 外有一个更小的值，可以跟 \(1 \sim t\) 中的某个工作换一个位置，然后再将这个更换过来的工作更换掉，这样无疑是更优的。
- 考虑如何快速维护这个东西，使用两棵线段树：
  - 第一棵线段树维护所有停止时间在区间 \([l,r]\) 的时刻完成的任务的停止时间的最大值。
  - 第二棵线段树维护所有停止时间在区间 \([l,r]\) 的时刻完成的任务的贡献的最小值。
- 我们需要找到经过更换能更换到的最远时刻：
  - 令 \(A_{fi}\) 表示当前 \(1 \sim t\) 中停止时间最晚的时间，\(A_{se}\) 为 \(1 \sim t\) 中停止时间最晚的工作完成的时刻。
  - 令 \(B_{fi}\) 表示当前 \(1 \sim A_{fi}\) 中停止时间最晚的时间，\(B_{se}\) 为 \(1 \sim A_{fi}\) 中停止时间最晚的工作完成的时刻。
  - 那么若 \(A_{fi} < B_{fi}\)：
    - 说明可以将 \(A_{se}\) 与 \(B_{se}\) 时刻的工作调换一下。
    - 因为可以使得 \(1 \sim t\) 内的工作的最晚停止时刻更长。
  - 然后一直重复交换操作，直到不满足 \(A_{fi} < B_{fi}\) 为止。
- 经过上述的操作，\(A_{fi}\) 达到了最大值；令 \(C_{fi}\) 表示当前 \(1 \sim A_{fi}\) 中工作贡献的最小值，\(C_{se}\) 表示完成最小贡献的工作所处的时刻。
- 若 \(C_{se} > t\)，可以将 \(A_{se}\) 与 \(C_{se}\) 交换一下。
- 此时的 \(C_{fi}\) 就是可以找到更换的最小值，若 \(p > C_{fi}\)，则可以更换。

对于删除操作：

若删除的工作我们选择完成了，设在 \(t\) 时刻完成：
- 那么容易想到，可以找到停止时间在 \(t \sim T\) 中贡献最大且没有完成的工作，顶替上来即可。
- 但是也假了，考虑这样一种情况，可以将 \(t\) 与 \(1 \sim t-1\) 时刻的某个工作 \(t'\) 交换，使得 \(t' \sim T\) 的最大贡献在 \(t' \sim t\) 中，则只看 \(t \sim T\) 是不优的。
- 我们需要将 \(t\) 换到尽可能前面去，考虑二分：
  - 若 \(1 \sim mid\) 中停止时间最晚的时间是大于等于 \(t\) 的，说明 \(1 \sim mid\) 中有一个位置可以与 \(t\) 换，令 \(r=mid-1\)；否则 \(l=mid+1\)。
  - 设当前找到的最靠前的时刻为 \(t'\)，令 \(t \gets t'\)，然后再在 \(1 \sim t\) 的范围内二分。
  - 重复二分直到找不到 \(1 \sim t-1\) 范围内的点与 \(t\) 交换，即不存在 \(t'\)。
- 此时我们得到了最小的 \(t\)，找 \(t \sim T\) 内贡献最大且没有完成的工作顶替即可。
- 可以使用第三棵线段树：维护所有停止时间在区间 \([l,r]\) 的时刻未完成的任务的贡献的最大值。
若并没有完成该工作，则直接在第三棵线段树上将这个点的贡献消除即可。

第三棵线段树需要支持一个撤销操作，因为可能有完全一模一样的工作，需要在叶子节点处使用 multiset 维护最大值。
时间复杂度为 \(O(N \log^3 N)\)。
该做法码量和常数较大，审慎使用。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e5+10,INF=1e18;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)