Thoughts:
For the insert operation, set the insert\(\{t,p\}\)：
-
if\(1 \sim t\) There's an empty space, then put it in.
-
Otherwise.\(1 \sim t\) It's stuffed:
-
The first thing that comes readily to mind is finding\(1 \sim t\) The job that contributes the least to the work, if it contributes more than the\(p\) It's still small enough to replace it with.
-
But false, consider a situation in which the\(1 \sim t\) There is a smaller value outside that can be compared to the\(1 \sim t\) It is undoubtedly preferable to change the position of one of the jobs in the program, and then replace that replaced job.
-
Consider how to maintain this quickly, using two line segment trees:
-
The first line segment tree maintains all deadlines in the interval\([l,r]\) The maximum value of the deadline for the task completed at the moment of the
-
The second line segment tree maintains all deadlines in the interval\([l,r]\) The minimum value of the contribution of the task completed at the moment of the
-
-
We need to find the furthest moment that can be replaced by substitution:
-
honorific title\(A_{fi}\) represent the current\(1 \sim t\) The latest of the deadlines in the\(A_{se}\) because of\(1 \sim t\) The moment when the work with the latest deadline is completed.
-
honorific title\(B_{fi}\) represent the current\(1 \sim A_{fi}\) The latest of the deadlines in the\(B_{se}\) because of\(1 \sim A_{fi}\) The moment when the work with the latest deadline is completed.
-
if\(A_{fi} < B_{fi}\)：
-
Explain that it is possible to set the\(A_{se}\) together with\(B_{se}\) Time to work on switching things up a bit.
-
Because it is possible to make\(1 \sim t\) The latest deadline for work within is longer.
-
-
Then keep repeating the swap operation until it does not satisfy\(A_{fi} < B_{fi}\) Until.
-
-
As a result of the above operations, the\(A_{fi}\) reaches its maximum value; so that\(C_{fi}\) represent the current\(1 \sim A_{fi}\) The minimum value of the contribution of the work in the\(C_{se}\) Indicates the moment at which the least contributing work is completed.
-
as\(C_{se} > t\)The\(A_{se}\) together with\(C_{se}\) Swap it.
-
at this time\(C_{fi}\) is the minimum value for which a replacement can be found, if\(p > C_{fi}\)and can be replaced.
-
For the delete operation:
-
If the deletion is complete we choose to set up the\(t\) The moment is complete:
-
It's easy to think, then, that one can find deadlines in\(t \sim T\) The most contributing and unfinished work in the program can just be filled in.
-
But also falsely, consider a situation where it would be possible to put the\(t\) together with\(1 \sim t-1\) Some job at some point in time\(t'\) exchange, making the\(t' \sim T\) The greatest contribution of the\(t' \sim t\) In this case, only the\(t \sim T\) is not superior.
-
We need to put\(t\) Switch to as far ahead as you can and consider two points:
-
as\(1 \sim mid\) The latest of the cutoff times is greater than or equal to\(t\) of the state of the art.\(1 \sim mid\) There is a position in the program that can be linked to the\(t\) exchange, so that the\(r=mid-1\)Otherwise.\(l=mid+1\)。
-
Let the most forward moment currently found be\(t'\)warrant\(t \gets t'\)and then in the\(1 \sim t\) The scope of the dichotomy.
-
Repeat bisection until you can't find it.\(1 \sim t-1\) The points in the range are the same as the\(t\) exchange, i.e., there is no\(t'\)。
-
-
At this point we get the smallest\(t\)call on sb.\(t \sim T\) It is sufficient to replace the most contributing and unfinished work within the organization.
-
A third line tree can be used: maintaining all deadlines in the interval\([l,r]\) The maximum value of the contribution of unfinished tasks at the moment of the
-
-
If it does not complete that work, it is sufficient to eliminate the contribution of this point directly in the third line segment tree.
The third line tree needs to support an undo operation, as there may be exactly the same work that needs to be done at the leaf nodes using themultiset Maintenance Maximum.
The time complexity is\(O(N \log^3 N)\)。
This practice has a large amount of yardage and constants and should be used with caution.
Full Code:
#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 safeguard 1 ~ x Maximum value of deadlines for tasks to be completed in the time period
// T2 safeguard 1 ~ x The minimum value of the score for the task completed in the time interval
// T3 safeguard 1 ~ x Maximum value of the score for tasks not completed in the time period
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]; //{maximum values,placement}
pi add(pi a,pi b){
if(>)
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]; //{minimum value,placement}
pi add(pi a,pi b){
if(<)
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(>)
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]={{-,-},-};
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]={{-,-},-};
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=(1,1,n,1,x);
B=(1,1,n,1,);
if(<){
(,);
(,);
}
else
break;
}
A=(1,1,n,1,x);
C=(1,1,n,1,);
if(>x){
(,);
(,);
}
C=(1,1,n,1,x);
if(<y){
ans+=;
if(){
(1,1,n,X[],Y[],Z[]);
(1,1,n,);
(1,1,n,);
}
(1,1,n,,x);
(1,1,n,,x,y,c);
}
else
(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((1,1,n,1,mid).fi>=z){
t=mid;
r=mid-1;
}
else
l=mid+1;
}
if(t==-1)
break;
(t,z);
(t,z);
}
z=F[{{x,y},c}];
(1,1,n,z);
(1,1,n,z);
iip A=(1,1,n,z,n);
if(){
ans+=;
(1,1,n,z,);
(1,1,n,z,,,);
(1,1,n,,,);
}
}
else
(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();
(1,1,n);
(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] Calendar Management
int main(){
n=read(),q=read();
(1,1,n);
(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;
}
*/