首页 > 其他分享 >[ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理

[ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理

时间：2024-07-26 09:50:56浏览次数：8  
标签：return ll Dynamic sim Scheduling fi ABC363G se define

思路：

对于插入操作，设插入 \(\{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)\)。

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

完整代码：

#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;
}
*/

标签：return,ll,Dynamic,sim,Scheduling,fi,ABC363G,se,define
From： https://www.cnblogs.com/rgw2010/p/18324711

相关文章

  • 动态规划（Dynamic programming）
    什么是动态规划？动态规划（英语：Dynamicprogramming，简称DP），是一种在数学、管理科学、计算机科学经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。以上定义来自维基百科，看定义感觉还......
  • 何时使用static_cast、dynamic_cast、const_cast和reinterpret_cast
    在C++中，类型转换操作符static_cast、dynamic_cast、const_cast和reinterpret_cast各有其特定的使用场景。下面是每种类型转换操作符的基本用途和何时使用它们的指南：1. static_cast用途：主要用于基本数据类型之间的转换，以及有明确定义的类层次结构中的向上转换（派生类到基类）和......
  • AIGC-DynamiCrafter: Animating Open-domain Images with Video Diffusion Priors-ECC
    论文:https://arxiv.org/pdf/2310.12190代码:https://github.com/Doubiiu/DynamiCrafter?tab=readme-ov-fileMOTIVATIONTraditionalimageanimationtechniquesmainlyfocusonanimatingnaturalsceneswithstochasticdynamics(e.g.cloudsandfluid)ordom......
  • c++中const_cast和dynamic_cast的用法
    `const_cast`和`dynamic_cast`是C++中的两个类型转换运算符，用于转换指针或引用的类型。它们的使用方式如下：1.`const_cast`：  -`const_cast`用于去除指针或引用的`const`或`volatile`限定符，以便对其进行修改。  -`const_cast`只能用于转换掉对象的常量性，......
  • 大模型长度扩展：直接外推, PI, NTK-aware, NTK-by-parts, Dynamic NTK, ALiBi, YaRN, S
    目录第一部分背景知识：从进制表示谈到直接外推、线性内插、进制转换1.1从进制表示到直接外推1.1.1进制表示1.1.2直接外推1.2从线性内插到进制转换1.2.1线性内插1.2.2进制转换第二部分从RoPE、直接外推到位置内插PositionInterpolation2.1旋转位置嵌入2.1.1RoPE的快速回......
  • dynamic_cast
    是什么:动态类型转换，确保类型转换是有效转换什么时候工作：在程序运行时计算怎么工作：有运行时类型信息RTTI存储了我们所以类型运行时的类型信息所以能够判断类型转换是否合理写法：dynamic_cast<要转换的类型>(变量名)；代码示例：classEntity{public: virtual~Entity() ......
  • SpringBoot+dynamic+druid的多数据源配置
    一、模块环境SpringBoot版本：2.7.12MySQL版本：8.0.33Druid版本：1.2.23Dynamic版本：3.6.1二、数据源配置文件spring:autoconfigure:#排除Druid自动配置exclude:com.alibaba.druid.spring.boot.autoconfigure.DruidDataSourceAutoConfiguredatasource:......
  • WPF generate rows and columns via C# dynamically
    //xaml<Windowx:Class="WpfApp214.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.mi......
  • 【反悔贪心】P2949WorkSchedulingG+P4053[JSOI2007]建筑抢修题解
    这两天遇到了几个很神奇的题目——能反悔的贪心。赶紧记录一下。例1（用时一定模型）用时一定：每个任务完成的耗时都是一样的。题面：Luogu-P2949WorkSchedulingG大体思路是：先把所有任务按照截止时间从小到大排序，然后枚举，遇到一个能做任务的就把他做了，把他的贡献加入一个......
  • Asp .Net Core 系列：基于 Castle DynamicProxy + Autofac 实践 AOP 以及实现事务、用户
    目录什么是AOP？.NetCore中有哪些AOP框架？基于CastleDynamicProxy实现AOPIOC中使用CastleDynamicProxy实现事务管理实现用户自动填充什么是AOP？AOP（Aspect-OrientedProgramming，面向切面编程）是一种编程范式，旨在通过将横切关注点（cross-cuttingconcerns）从主要业务逻辑......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99