讲解 [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]\) 的时刻未完成的任务的贡献的最大值。

• 若并没有完成该工作，则直接在第三棵线段树上将这个点的贡献消除即可。

第三棵线段树需要支持一个撤销操作，因为可能有完全一模一样的工作，需要在叶子节点处使用 <code>multiset 维护最大值。

时间复杂度为 \(O(N \log^3 N)\)。

该做法码量和常数较大，谨慎使用。

完整代码：

#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#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<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

// T1 维护 1 ~ x 时刻中完成的任务的截止时间的最大值

// T2 维护 1 ~ x 时刻中完成的任务的得分的最小值

// T3 维护 1 ~ x 时刻中未完成的任务的得分的最大值

ll n,q,c,x,y,z,l,r,t,ans;

ll a[N],b[N],X[N],Y[N],Z[N];

map<pi,ll> cnt;

map<iip,ll> F;

class Tree1{

public:

pi H[N<<2]; //{最大值,位置}

pi add(pi a,pi b){

if(a.fi>b.fi)

return a;

return b;

}

void pushup(ll k){

H[k]=add(H[k<<1],H[k<<1|1]);

}

void build(ll k,ll l,ll r){

if(l==r){

H[k].fi=0;

H[k].se=l;

return ;

}

ll mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

pushup(k);

}

void update(ll k,ll l,ll r,ll i,ll v){

if(l==i&&i==r){

H[k].fi=v;

return ;

}

ll mid=(l+r)>>1;

if(i<=mid)

update(k<<1,l,mid,i,v);

else

update(k<<1|1,mid+1,r,i,v);

pushup(k);

}

void del(ll k,ll l,ll r,ll i){

if(l==i&&i==r){

H[k].fi=0;

return ;

}

ll mid=(l+r)>>1;

if(i<=mid)

del(k<<1,l,mid,i);

else

del(k<<1|1,mid+1,r,i);

pushup(k);

}

pi query(ll k,ll l,ll r,ll L,ll R){

if(L>R)

return {-INF,0};

if(l==L&&R==r)

return H[k];

ll mid=(l+r)>>1;

if(R<=mid)

return query(k<<1,l,mid,L,R);

else if(L>mid)

return query(k<<1|1,mid+1,r,L,R);

else

return add(query(k<<1,l,mid,L,mid),query(k<<1|1,mid+1,r,mid+1,R));

}

void Swap(ll x,ll y){

ll xx=query(1,1,n,x,x).fi;

ll yy=query(1,1,n,y,y).fi;

update(1,1,n,x,yy);

update(1,1,n,y,xx);

}

}T1;

class Tree2{

public:

pi H[N<<2]; //{最小值,位置}

pi add(pi a,pi b){

if(a.fi<b.fi)

return a;

return b;

}

void pushup(ll k){

H[k]=add(H[k<<1],H[k<<1|1]);

}

void build(ll k,ll l,ll r){

if(l==r){

H[k].fi=0;

H[k].se=l;

X[l]=Y[l]=Z[l]=0;

return ;

}

ll mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

pushup(k);

}

void update(ll k,ll l,ll r,ll i,ll x,ll y,ll c){

if(l==i&&i==r){

H[k].fi=y;

X[i]=x,Y[i]=y,Z[i]=c;

F[{{x,y},c}]=i;

return ;

}

ll mid=(l+r)>>1;

if(i<=mid)

update(k<<1,l,mid,i,x,y,c);

else

update(k<<1|1,mid+1,r,i,x,y,c);

pushup(k);

}

void del(ll k,ll l,ll r,ll i){

if(l==i&&i==r){

H[k].fi=0;

F[{{X[i],Y[i]},Z[i]}]=0;

X[i]=Y[i]=Z[i]=0;

return ;

}

ll mid=(l+r)>>1;

if(i<=mid)

del(k<<1,l,mid,i);

else

del(k<<1|1,mid+1,r,i);

pushup(k);

}

pi query(ll k,ll l,ll r,ll L,ll R){

if(L>R)

return {INF,0};

if(l==L&&R==r)

return H[k];

ll mid=(l+r)>>1;

if(R<=mid)

return query(k<<1,l,mid,L,R);

else if(L>mid)

return query(k<<1|1,mid+1,r,L,R);

else

return add(query(k<<1,l,mid,L,mid),query(k<<1|1,mid+1,r,mid+1,R));

}

void Swap(ll x,ll y){

ll xx1=X[x],yy1=Y[x],cc1=Z[x],xx2=X[y],yy2=Y[y],cc2=Z[y];

update(1,1,n,x,xx2,yy2,cc2);

update(1,1,n,y,xx1,yy1,cc1);

}

}T2;

class Tree3{

public:

ll id[N];

multiset<pii> S[N];

iip H[N<<2]; // {{x,y},c}

iip add(iip a,iip b){

if(a.fi.se>b.fi.se)

return a;

return b;

}

void pushup(ll k){

H[k]=add(H[k<<1],H[k<<1|1]);

}

void update(ll k,ll l,ll r,ll x,ll y,ll c){

if(l==x&&x==r){

S[x].insert({-y,{-x,-c}});

auto t=(*S[x].begin());

H[k]={{-t.se.fi,-t.fi},-t.se.se};

return ;

}

ll mid=(l+r)>>1;

if(x<=mid)

update(k<<1,l,mid,x,y,c);

else

update(k<<1|1,mid+1,r,x,y,c);

pushup(k);

}

void del(ll k,ll l,ll r,ll x,ll y,ll c){

if(l==x&&x==r){

S[x].erase({-y,{-x,-c}});

auto t=(*S[x].begin());

H[k]={{-t.se.fi,-t.fi},-t.se.se};

return ;

}

ll mid=(l+r)>>1;

if(x<=mid)

del(k<<1,l,mid,x,y,c);

else

del(k<<1|1,mid+1,r,x,y,c);

pushup(k);

}

iip query(ll k,ll l,ll r,ll L,ll R){

if(l==L&&R==r)

return H[k];

ll mid=(l+r)>>1;

if(R<=mid)

return query(k<<1,l,mid,L,R);

else if(L>mid)

return query(k<<1|1,mid+1,r,L,R);

else

return add(query(k<<1,l,mid,L,mid),query(k<<1|1,mid+1,r,mid+1,R));

}

}T3;

void insert(ll x,ll y){

c=++cnt[{x,y}];

pi A,B;

pi C;

while(1){

A=T1.query(1,1,n,1,x);

B=T1.query(1,1,n,1,A.fi);

if(A.fi<B.fi){

T1.Swap(A.se,B.se);

T2.Swap(A.se,B.se);

}

else

break;

}

A=T1.query(1,1,n,1,x);

C=T2.query(1,1,n,1,A.fi);

if(C.se>x){

T1.Swap(A.se,C.se);

T2.Swap(A.se,C.se);

}

C=T2.query(1,1,n,1,x);

if(C.fi<y){

ans+=y-C.fi;

if(C.fi){

T3.update(1,1,n,X[C.se],Y[C.se],Z[C.se]);

T1.del(1,1,n,C.se);

T2.del(1,1,n,C.se);

}

T1.update(1,1,n,C.se,x);

T2.update(1,1,n,C.se,x,y,c);

}

else

T3.update(1,1,n,x,y,c);

}

void del(ll x,ll y){

c=cnt[{x,y}]--;

if(F[{{x,y},c}]){

ans-=y;

while(1){

z=F[{{x,y},c}];

l=1,r=z-1,t=-1;

while(l<=r){

ll mid=(l+r)>>1;

if(T1.query(1,1,n,1,mid).fi>=z){

t=mid;

r=mid-1;

}

else

l=mid+1;

}

if(t==-1)

break;

T1.Swap(t,z);

T2.Swap(t,z);

}

z=F[{{x,y},c}];

T1.del(1,1,n,z);

T2.del(1,1,n,z);

iip A=T3.query(1,1,n,z,n);

if(A.se){

ans+=A.fi.se;

T1.update(1,1,n,z,A.fi.fi);

T2.update(1,1,n,z,A.fi.fi,A.fi.se,A.se);

T3.del(1,1,n,A.fi.fi,A.fi.se,A.se);

}

}

else

T3.del(1,1,n,x,y,c);

}

bool End;

/*[ABC363G] Dynamic Scheduling

int main(){

n=read(),q=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=1;i<=n;i++)

b[i]=read();

T1.build(1,1,n);

T2.build(1,1,n);

for(int i=1;i<=n;i++)

insert(a[i],b[i]);

//write(ans);

//putchar('\n');

while(q--){

x=read();

del(a[x],b[x]);

a[x]=read(),b[x]=read();

insert(a[x],b[x]);

write(ans);

putchar('\n');

}

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}*/

/*P4511 [CTSC2015] 日程管理

int main(){

n=read(),q=read();

T1.build(1,1,n);

T2.build(1,1,n);

while(q--){

cin>>op;

x=read(),y=read();

if(op[0]=='A')

insert(x,y);

else

del(x,y);

write(ans);

putchar('\n');

}

return 0;

}

*/