AT_abc467_f 题解

Moya_Rao · 2026-07-19 19:25:46 · 题解

到底是谁在说 F<E？到底是谁在说 F<E？到底是谁在说 F<E？到底是谁在说 F<E？到底是谁在说 F<E？到底是谁在说 F<E？到底是谁在说 F<E？

有任何道理吗？？？

F 好难啊。

我们首先贪心一波，发现肯定是优先写 b 较大的信件会比较好，这个证明是比较简单的推式子，我这里就跳过了哈 qwq。

接着你考虑去维护这个东西，那么对于一个不带修改的情况，答案肯定就是在对 b 降序排序后的 \max_{i=1}^{n} \{ (\sum_{j=1}^{i} a_j) + b_i \}，因为这个是每封信件收到回复的时间，取 \max 就是全部收到回复的时间啦。

然后你怎么维护这个东西呢？因为 a 和 b 都是会变的，而我们要按 b 排序，就能很自然地想到以 b 为下标去维护。但是 b 的值域太大了怎么办？离线后离散化呗，反正题目也没要求强制在线，离线做是完全没问题哒。

单点修改、区间 \max 显然考虑线段树，线段树上每个节点对应一个区间，而这个区间的 b 值已经作为下标排好序了。我们维护两个信息——sum 和 mx，分别表示 a 值的和，以及这段区间独立的答案。每次操作修改后，我们都只需要取出根节点的 mx 值输出就行了。

这个值具体要怎么维护？我们发现在 push_up 函数中，mx_u 的更新可以这样写：mx_u = \max(mx_{ls} , sum_{ls} + mx_{rs})。mx_{ls} 是好懂的，但为什么 mx_{rs} 要加上 sum_{ls} 呢？因为现在是 u 的完整大区间了，左边还有一段 a 值和需要补上啦。

问题来了，操作怎么实现？很简单，修改 a 值的时候直接单点处理 b 位置删掉再加即可；修改 b 值稍显复杂，需要先从原 b 位置移去，然后再加回新 b 位置就行啦！

实现还是挺简单的嘿嘿。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
struct node{LL x,y;}a[N];
struct query{LL opt,id,val;}q[N];
int n,Q,cnt;pLL p[N];
LL sum[N<<2],mx[N<<2];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int get_rk(LL val,LL id){
    int rk=lower_bound(p+1,p+cnt+1,make_pair(-val,id))-p;
    return rk;
}
int ls(int u){return (u<<1);}
int rs(int u){return (u<<1|1);}
void push_up(int u){
    mx[u]=max(mx[ls(u)],sum[ls(u)]+mx[rs(u)]);
    sum[u]=sum[ls(u)]+sum[rs(u)];return;
}
void change(int u,int l,int r,int pos,LL A,LL B){
    if(l==r&&l==pos){
        sum[u]=A,mx[u]=A+B;return;
    }int mid=(l+r)>>1;
    if(pos<=mid)change(ls(u),l,mid,pos,A,B);
    else change(rs(u),mid+1,r,pos,A,B);
    push_up(u);return;
}
int main(){
    n=read(),Q=read();
    for(int i=1;i<=n;i++)a[i].x=read();
    for(int i=1;i<=n;i++)
        a[i].y=read(),p[++cnt]={-a[i].y,i};
    for(int i=1;i<=Q;i++){
        q[i].opt=read(),q[i].id=read(),q[i].val=read();
        if(q[i].opt==2)p[++cnt]={-q[i].val,q[i].id};
    }sort(p+1,p+cnt+1);
    cnt=unique(p+1,p+cnt+1)-p-1;
    for(int i=1;i<=n;i++){
        int id=get_rk(a[i].y,i);
        change(1,1,cnt,id,a[i].x,a[i].y);
    }
    for(int i=1;i<=Q;i++){
        auto [o,id,val]=q[i];
        if(o==1){
            int rk=get_rk(a[id].y,id);
            change(1,1,cnt,rk,val,a[id].y);
            a[id].x=val;
        }else{
            int ork=get_rk(a[id].y,id);
            change(1,1,cnt,ork,0,0);
            int nrk=get_rk(val,id);
            change(1,1,cnt,nrk,a[id].x,val);
            a[id].y=val;
        }cout<<mx[1]<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！