P14447 [ICPC 2025 Xi'an R] Azalea Garden

ziyistudy · 2025-11-11 18:48:41 · 题解

此篇为 dmy 比赛复盘。

显然剩下最小可以转为击败最多。

把 a 最大的拿出来击败其他的肯定是最优的，不妨令为 i，如果可以击败 sum 个，则答案肯定为 sum 或 sum+1，即这个 i 也可以被打败，考虑以下情况：

• 令不能击败的 a_j 中的最大值为 A，如果有 b_i\leq A，答案为 sum+1。
• 再能击败中找出一个序列 k，其中 i 为 k 的最后一项，使得对于任意 i，b_{k_{i+1}}\leq a_{k_i}，即前者能击败后者，然后有 b_1\leq A，这样答案为 sum+1。 我们思考第三种情况，发现向这种环环紧扣的结构可以转换为若干区间，使得它们的并是一段连续的区间。具体地，把每组 a_i,b_i 转化为区间 [b_i,a_i]，若最后存在其中若干区间的并能完全覆盖 [A,b_i]，则答案可行。线段树维护即可。

具体地，将值离散化，值域线段树下标为防御值 b，维护区间中尽量长的并，即可以维护 l,r，如果 rs_l\leq ls_r，则左端点可以为 ls_l，否则取 r 最大值。特殊地，如果 ls_r\ge rs_r，则左端点直接为 ls_l，不用取 \min 原因是 rs_l 一定不小于 ls_l。然后我们可以在是指线段树统计，唯一特殊的地方是，当 a_i<b_i 时，我们在统计 a_i 不可以击败的会算上自己，而自己本来就不能被击败，故直接返回即可。

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head
const int N=4e5+5,M=2e6+5,INF=2e9;
int a[N],b[N];
int d[M],tot;
struct node{int v,x,y;}que[N];
#define mid ((l+r)>>1)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
multiset<int> S[M];
struct node1{int sum,mx,mn;};
struct Seg_tree
{
    node1 ans[M<<2];
    node1 merge(node1 l,node1 r)
    {
        node1 now;
        now.sum=l.sum+r.sum;
        if(l.mx>=r.mx) now.mx=l.mx,now.mn=l.mn;
        else now.mx=r.mx,now.mn=(l.mx>=r.mn?l.mn:r.mn);
        return now;
    }
    void push_up(int pos)
    {
        ans[pos]=merge(ans[ls(pos)],ans[rs(pos)]);   
    }
    void upd(int pos,int x)
    {
        ans[pos].mx=-INF,ans[pos].mn=INF,ans[pos].sum=S[x].size();
        if(S[x].size()) ans[pos].mx=*S[x].rbegin(),ans[pos].mn=x;
    }
    void build(int pos,int l,int r)
    {
        if(l==r){
            upd(pos,l);
            return ;
        }
        build(ls(pos),l,mid);
        build(rs(pos),mid+1,r);
        push_up(pos);
    }
    void modify(int pos,int l,int r,int x)
    {
        if(l==r) {upd(pos,l);return ;}
        if(x<=mid) modify(ls(pos),l,mid,x);
        else modify(rs(pos),mid+1,r,x);
        push_up(pos);
    }
    node1 query(int pos,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr) return ans[pos];
        if(qr<=mid) return query(ls(pos),l,mid,ql,qr);
        else if(ql>mid) return query(rs(pos),mid+1,r,ql,qr);
        return merge(query(ls(pos),l,mid,ql,qr),query(rs(pos),mid+1,r,ql,qr));
    }
}tree;
int work()
{
    int x=tree.ans[1].mx,y=tree.ans[1].mn;
    if(x==tot) return 1;
    node1 tmp=tree.query(1,1,tot,x+1,tot);
    if(x<y) return tmp.sum;
    if(y<=tmp.mx) return tmp.sum;
    return tmp.sum+1;
}
signed main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) {cin>>a[i]>>b[i];d[++tot]=a[i],d[++tot]=b[i];}
    for(int i=1;i<=q;i++) {cin>>que[i].v>>que[i].x>>que[i].y;d[++tot]=que[i].x,d[++tot]=que[i].y;}
    sort(d+1,d+tot+1);tot=unique(d+1,d+tot+1)-d-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(d+1,d+tot+1,a[i])-d,b[i]=lower_bound(d+1,d+tot+1,b[i])-d;
    for(int i=1;i<=q;i++) que[i].x=lower_bound(d+1,d+tot+1,que[i].x)-d,que[i].y=lower_bound(d+1,d+tot+1,que[i].y)-d;
    for(int i=1;i<=n;i++) S[b[i]].insert(a[i]);
    tree.build(1,1,tot);
    cout<<work()<<'\n';
    for(int i=1;i<=q;i++){
        S[b[que[i].v]].erase(S[b[que[i].v]].find(a[que[i].v]));
        tree.modify(1,1,tot,b[que[i].v]);
        a[que[i].v]=que[i].x,b[que[i].v]=que[i].y;
        S[b[que[i].v]].insert(a[que[i].v]);
        tree.modify(1,1,tot,b[que[i].v]);
        cout<<work()<<'\n';
    }
    for(int i=1;i<=n;i++) S[b[i]].clear();
    tot=0;
}