题解：AT_abc467_f [ABC467F] Email Scheduling Optimization
fish_love_cat · · 题解
没测样例，压哨交。我草没过样例。
21:40:00 发现单点修改的地方复制过来一个区间修改，没改。
21:40:10 获得 AC 代码。
R.I.P.
好像是个很常见的贪心，已知策略是按照
那么答案就是排序后每个
因为带修所以考虑上数据结构维护这个东西。
对着
如果是对单点修改，那么求最值就要对多个区间做查询，这太困难了，考虑转变操作形式变成区间修改，求单点的时候变成单点查询的形式，这样求区间最值就只是区间查询了。
每个点对于所有后面的位置做区间加法，然后开个桶统计每个数字的出现次数，如果新出现的数字就把下标也扔进去。注意是单点修改！！！
查询直接做全局最大值就好了。
动态开点线段树即可。
时间复杂度
#include<bits/stdc++.h>
#define eps (1e-12)
#define inf ((int)1e18)
#define lowbit(x) ((x)&(-(x)))
#define mod 998244353
#define int long long
#define N 100005
using namespace std;
inline char get_char(bool op);
inline int read();
inline void print(int x);
inline int qpow(int a,int b=mod-2);
inline int gcd(int a,int b);
map<int,int>t;
struct seg_tr{
int tr[N<<7],lz[N<<7];
int ls[N<<7],rs[N<<7];
int top=0;
void pushup(int x){
tr[x]=max(tr[ls[x]],tr[rs[x]]);
}
void pushdown(int x,int l,int r){
if(!lz[x])return;
if(!ls[x])ls[x]=++top;
if(!rs[x])rs[x]=++top;
int mid=(l+r)>>1;
tr[ls[x]]+=lz[x];
tr[rs[x]]+=lz[x];
lz[ls[x]]+=lz[x];
lz[rs[x]]+=lz[x];
lz[x]=0;
}
void upd(int &u,int l,int r,int L,int R,int x){
if(!u)u=++top;
if(L<=l&&r<=R){
tr[u]+=x;
lz[u]+=x;
return;
}
pushdown(u,l,r);
int mid=(l+r)>>1;
if(L<=mid)upd(ls[u],l,mid,L,R,x);
if(R>mid)upd(rs[u],mid+1,r,L,R,x);
pushup(u);
}
int qry(int u,int l,int r,int L,int R){
if(L<=l&&r<=R)return tr[u];
pushdown(u,l,r);
int mid=(l+r)>>1;
int ans=0;
if(mid>=L)ans=max(ans,qry(ls[u],l,mid,L,R));
if(mid<R)ans=max(ans,qry(rs[u],mid+1,r,L,R));
return ans;
}
}tr;
int rt=0;
struct fish{
int a,b;
}a[100005];
inline void solve(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i].a;
for(int i=1;i<=n;i++)
cin>>a[i].b;
for(int i=1;i<=n;i++){
if(t[a[i].b]==0){
tr.upd(rt,1,1e9,a[i].b,a[i].b,a[i].b);
}
tr.upd(rt,1,1e9,1,a[i].b,a[i].a);
t[a[i].b]++;
}
while(q--){
int op,id,x;
cin>>op>>id>>x;
if(op==1){
tr.upd(rt,1,1e9,1,a[id].b,x-a[id].a);
a[id].a=x;
}else{
t[a[id].b]--;
tr.upd(rt,1,1e9,1,a[id].b,-a[id].a);
if(t[a[id].b]==0){
tr.upd(rt,1,1e9,a[id].b,a[id].b,-a[id].b);
}
a[id].b=x;
t[a[id].b]++;
tr.upd(rt,1,1e9,1,a[id].b,a[id].a);
if(t[a[id].b]==1){
tr.upd(rt,1,1e9,a[id].b,a[id].b,a[id].b);
}
}
cout<<tr.qry(rt,1,1e9,1,1e9)<<'\n';
}
}
signed main(){
int t=1;
// t=read();
while(t--)solve();
return 0;
}
inline int gcd(int a,int b){
int flc=min(__builtin_ctz(a),__builtin_ctz(b)),tmp;
b>>=__builtin_ctz(b);
while(a){
a>>=__builtin_ctz(a);
tmp=b-a;
if(a<b)b=a;
a=abs(tmp);
}
return (b<<flc);
}
inline char get_char(bool op=1){
if(op)return getchar();
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int sum=0,fish=1;
char c=get_char();
while((c<'0'||c>'9')&&c!='-')c=get_char();
if(c=='-')fish=-1,c=get_char();
while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=get_char();
return sum*fish;
}
inline void print(int x){
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else print(x/10),putchar(x%10+'0');
}
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
//「回过神来她就倒在地上，吓了我一跳。可是对不起，我在事件发生当下一直坐在这个位子上，所以什么也不知道……希望你们能尽早逮到犯人。」
// 在窗边座位庆祝交往一周年纪念日的女子如此替红酒小姐担心。
// 她人真好。
//「没想到交往一周年纪念日居然发生这种憾事……」
// 这么说的是早就坐回座位上，看著蛋糕慢慢变温，来店庆祝交往一周年纪念日的男子。
//「餐厅一定会招待蛋糕吧？如果能顺便拿点赔偿金就好了。」
// 看来他满脑子都是钱。
// 我们问完两人之后离开他们的座位，侦探小姐依然让布偶啃著自己的嘴巴，露出复杂的表情。
//「真奇怪……」
//「你想到什么了吗？」
//「那个女生到底喜欢他的什么地方……」