题解：AT_abc389_f [ABC389F] Rated Range

cheng2010 · 2025-01-19 10:54:15 · 题解

前情提要：

思路

一个一个跳显然爆炸，要考虑优化。

对于每一次操作，只有值在 l \sim r 中的数会加一，其余不变，这启发我们需要一个动态查询在值 l \sim r 中的数据结构，平衡树呼之欲出。

具体的，维护一个 lazy 标记，在分裂合并时下传即可，记得最后要把标记全下传了。

时间：O(n \log n)。

看来平衡树还是 YYDS。

code

#include<bits/stdc++.h>
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
#define tp_rt treap.root
#define INF 2147483647
using namespace std;
const int N=1e6+7;
struct BST
{
    int lson,rson,val,rnd,siz,lazy;
}tree[N];
struct FHQ_Treap
{
    int cnt,root;
    inline void change(int x)
    {
        tree[x].siz=tree[ls(x)].siz+1+tree[rs(x)].siz;
    }
    inline void down(int p)
    {
        int x=tree[p].lazy;
        tree[p].lazy=0;
        if(ls(p))
        {
            tree[ls(p)].val+=x;
            tree[ls(p)].lazy+=x; 
        }
        if(rs(p))
        {
            tree[rs(p)].val+=x;
            tree[rs(p)].lazy+=x; 
        }
    }
    inline void split_val(int p,int &x,int &y,int key)
    {
        if(!p)
        {
            x=y=0;
            return;
        }
        down(p);
        if(tree[p].val<=key)
        {
            x=p;
            split_val(rs(p),rs(p),y,key);
            change(x);
        }
        else
        {
            y=p;
            split_val(ls(p),x,ls(p),key);
            change(y);
        }
    }
    inline int merge(int x,int y)
    {
        if(!x||!y)
            return x|y;
        down(x);
        down(y);
        if(tree[x].rnd<tree[y].rnd)
        {
            rs(x)=merge(rs(x),y);
            change(x);
            return x;
        }
        else
        {
            ls(y)=merge(x,ls(y));
            change(y);
            return y;
        }
    }
    inline int join(int x)
    {
        tree[++cnt].val=x;
        tree[cnt].siz=1;
        tree[cnt].rnd=rand();
        return cnt;
    }
    inline void ins(int &rt,int x)
    {
        int r1,r2;
        split_val(rt,r1,r2,x);
        rt=merge(merge(r1,join(x)),r2);
    }
    inline void update(int &rt,int l,int r)
    {
        int r1,r2,r3;
        split_val(rt,r2,r1,l-1);
        split_val(r1,r1,r3,r);
        tree[r1].val++;
        tree[r1].lazy++;
        rt=merge(r2,merge(r1,r3));
    }
    inline void down_all(int p)
    {
        down(p);
        if(ls(p))
            down_all(ls(p));
        if(rs(p))
            down_all(rs(p));
    }
}treap;
int n,q;
int l[N],r[N];
int main()
{
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&l[i],&r[i]);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x;
        scanf("%d",&x);
        treap.ins(tp_rt,x);
    }
    for(int i=1;i<=n;i++)
    {
        treap.update(tp_rt,l[i],r[i]);
    }
    treap.down_all(tp_rt);
    for(int i=1;i<=q;i++)
    {
        printf("%d\n",tree[i].val);
    }
}