[ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理
思路：对于插入操作，设插入 \(\{t,p\}\)：
[*]若当前 \(1 \sim t\) 有空位，那么就放进去。
[*]否则，\(1 \sim t\) 是被塞满了的：
[*]起首容易想到的是找到 \(1 \sim t\) 中贡献最小的那个工作，若贡献比 \(p\) 还小，可以与之更换掉。
[*]但是假了，考虑这样一种情况：在 \(1 \sim t\) 外有一个更小的值，可以跟 \(1 \sim t\) 中的某个工作换一个位置，然后再将这个更换过来的工作更换掉，这样无疑是更优的。
[*]考虑如何快速维护这个东西，使用两棵线段树：
[*]第一棵线段树维护所有停止时间在区间 \(\) 的时刻完成的任务的停止时间的最大值。
[*]第二棵线段树维护所有停止时间在区间 \(\) 的时刻完成的任务的贡献的最小值。
[*]我们需要找到经过更换能更换到的最远时刻：
[*]令 \(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\) 内贡献最大且没有完成的工作顶替即可。
[*]可以使用第三棵线段树：维护所有停止时间在区间 \(\) 的时刻未完成的任务的贡献的最大值。
[*]若并没有完成该工作，则直接在第三棵线段树上将这个点的贡献消除即可。
第三棵线段树需要支持一个撤销操作，因为可能有完全一模一样的工作，需要在叶子节点处使用 multiset 维护最大值。
时间复杂度为 \(O(N \log^3 N)\)。
该做法码量和常数较大，审慎使用。
完整代码：
#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
页:
[1]