首页 > 其他分享 >P1486 [NOI2004] 郁闷的出纳员

P1486 [NOI2004] 郁闷的出纳员

时间:2025-01-21 20:10:14浏览次数:1  
标签:P1486 int tr 出纳员 fa NOI2004 key rc now

P1486 [NOI2004] 郁闷的出纳员

题目翻译:

维护一个可重数集,共有 \(n\) 次操作,和一个最小限制 \(min\),共有四种操作:

  • \(I\) \(k\) 给集合添加 \(k\) 若 \(k<min\) 则直接删除(不算入删除个数)
  • \(A\) \(k\) 将集合中的所有元素加上 \(k\)
  • \(S\) \(k\) 将所有元素减少 \(k\) 并将所有值小于 \(min\) 的删除
  • \(F\) \(k\) 输出集合中元素从大到小的第 \(k\) 名的值,若 \(k\) 大于当前元素的值,则输出 \(-1\)

最后还要输出总共删除了多少元素

思路:

对于求第 \(k\) 大的数和随时可以插入等操作,很容易想到用平衡树来维护。由于可能会有重复的数,我们可以给每个节点都维护一个 \(cnt\) 用来储存该节点数的个数。

  • 对于插入操作就与普通的插入没有区别,只要特判一下,看是否有一样的,有就直接给该节点加一。并且要特判一下是否小于 \(min\),若小于则直接跳过。
void ins(int key){
    if(key<mi)return;
    int now=rt,f=0;
    while(now && tr[now].key!=key){
        f=now;
        now=tr[now].s[key>tr[now].key];
    }
    if(now){
        tr[now].cnt++;
        splay(now); 
        return;
    }
    now=newnode(key);
    fa(now)=f;
    if(f)tr[f].s[key>tr[f].key]=now;
    splay(now);
}
  • 对于给所有加上 \(k\)我们可以暴力的给所有节点都加上 \(k\),不管是否已经删除或者有没有用,应为删除的节点已经没有与树有连边,所以无法访问,自然没有影响,时间复杂度为 \(O(n)\)
for(int i=1;i<=idx;i++){
    tr[i].key+=k;
}
  • 对于对所有节点减去 \(k\),我们也可以全部减去,但为了删点,我们可以先找到最接近且 \(\geq k+min\) 的点,将他给 \(splay\) 到根节点,这样所有减去 \(k\) 会小于 \(min\) 的节点都会在根节点的左子树,这样只需要给 \(ans\) 加上子树大小,然后断开连接即可。最后给所有节点减去 \(k\).
void find(int key){
    int now=rt;
    while(key!=tr[now].key && tr[now].s[key>tr[now].key]){
        now=tr[now].s[key>tr[now].key];
    }
    splay(now);
}
int nxt(int key){
    find(key);
    if(tr[rt].key>=key)return rt;
    int now=rc(rt);
    while(lc(now))now=lc(now);
    return now;
}
void del2(int x){
    int now=nxt(x+mi);
    splay(now);
    ans+=tr[lc(now)].siz;
    lc(now)=0;
    pushup(now);
    for(int i=1;i<=idx;i++){
        tr[i].key-=x;
    }
}
  • 查找第 \(k\) 大的数。与普通查找没有什么区别但要注意的是,由于为了防止树中没有符合要求的节点,所以会先加入一个极大值,所以找的时候要找第 \(k+1\) 大的数。其次,由于有重复的数,所以在转移时还会要算上 \(cnt\)值
int kth(int rk){
    int now=rt;
    if(rk>=tr[now].siz)return -1;
    rk++;
    while(true){
        int sz=tr[rc(now)].siz;
        if(sz>=rk && rc(now)){
            now=rc(now);
        }
        else if(rk>tr[rc(now)].siz+tr[now].cnt){
            rk-=sz+tr[now].cnt;
            now=lc(now);
        }
        else{
            return tr[now].key;
        }
    }
}

完整代码:

#include<bits/stdc++.h>
#define lc(x) tr[(x)].s[0]
#define rc(x) tr[(x)].s[1]
#define fa(x) tr[(x)].fa
using namespace std;
const int N=3e5+10;
struct tree{
    int s[2],fa,siz,key,cnt;
    tree(){s[0]=s[1]=fa=siz=cnt=key=0;}
}tr[N];
int idx,rt,mi,ans;
void pushup(int x){
    tr[x].siz=tr[lc(x)].siz+tr[rc(x)].siz+tr[x].cnt;
}
void clear(int x){
    lc(x)=rc(x)=fa(x)=tr[x].siz=tr[x].key=tr[x].cnt=0;
}
int newnode(int key){
    tr[++idx].key=key;
    tr[idx].siz=1;
    tr[idx].cnt=1;
    return idx;
}
int get(int x){
    return x==rc(fa(x));
}
void rotate(int x){
    int y=fa(x),z=fa(y),c=get(x);
    if(tr[x].s[c^1])fa(tr[x].s[c^1])=y;
    tr[y].s[c]=tr[x].s[c^1];
    tr[x].s[c^1]=y;
    fa(y)=x;
    fa(x)=z;
    if(z)tr[z].s[y==rc(z)]=x;
    pushup(y);
    pushup(x);
}
void splay(int x){
    for(int f=fa(x);f=fa(x),f;rotate(x)){
        if(fa(f))rotate(get(x)==get(f)?f:x);
    }
    rt=x;
}
void ins(int key){
    if(key<mi)return;
    int now=rt,f=0;
    while(now && tr[now].key!=key){
        f=now;
        now=tr[now].s[key>tr[now].key];
    }
    if(now){
        tr[now].cnt++;
        splay(now); 
        return;
    }
    now=newnode(key);
    fa(now)=f;
    if(f)tr[f].s[key>tr[f].key]=now;
    splay(now);
}
int kth(int rk){
    int now=rt;
    if(rk>=tr[now].siz)return -1;
    rk++;
    while(true){
        int sz=tr[rc(now)].siz;
        if(sz>=rk && rc(now)){
            now=rc(now);
        }
        else if(rk>tr[rc(now)].siz+tr[now].cnt){
            rk-=sz+tr[now].cnt;
            now=lc(now);
        }
        else{
            return tr[now].key;
        }
    }
}
void find(int key){
    int now=rt;
    while(key!=tr[now].key && tr[now].s[key>tr[now].key]){
        now=tr[now].s[key>tr[now].key];
    }
    splay(now);
}
int nxt(int key){
    find(key);
    if(tr[rt].key>=key)return rt;
    int now=rc(rt);
    while(lc(now))now=lc(now);
    return now;
}
void del2(int x){
    int now=nxt(x+mi);
    splay(now);
    ans+=tr[lc(now)].siz;
    lc(now)=0;
    pushup(now);
    for(int i=1;i<=idx;i++){
        tr[i].key-=x;
    }
}
int main(){
    int n;
    scanf("%d%d",&n,&mi);
    ins(1547483647);
    for(int i=1;i<=n;i++){
        char op;
        int k;
        cin>>op>>k;
        if(op=='I'){
            ins(k);
        }
        if(op=='A'){
            for(int i=1;i<=idx;i++){
                tr[i].key+=k;
            }
        }
        if(op=='S'){
            del2(k);
        }
        if(op=='F'){
            printf("%d\n",kth(k));
        }
    }
    printf("%d\n",ans);
}

平衡树讲解

标签:P1486,int,tr,出纳员,fa,NOI2004,key,rc,now
From: https://www.cnblogs.com/XichenOC/p/18684363

相关文章

  • Luogu P2292 HNOI2004 L 语言 题解 [ 紫 ] [ AC 自动机 ] [ 状压 dp ]
    L语言:很好的一道状压dp题。思路看到这题,首先可以想到一个很暴力的dp,设\(dp_i\)表示考虑到第\(i\)位能否被理解,暴力匹配字符串转移即可。第一个优化也很显然,暴力匹配字符串换成AC自动机即可。但是时间复杂度变成了\(O(m|T||S|)\)的,显然会被卡。状压与位运算优化......
  • P1486
    偷懒的新方法#include<cstdio>#include<iostream>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>usingnamespace__gnu_pbds;usingnamespacestd;structnode{intv,id;node(inta,intb){......
  • [题解]P2292 [HNOI2004] L 语言
    P2292[HNOI2004]L语言注:下文中,\(s[l\simr]\)表示截取字符串\(s\)的第\(l\)个字符到第\(r\)个字符。文字描述的字符串下标从\(1\)开始,但代码实现从\(0\)开始。我们建出AC自动机后,有一个比较暴力的思路。我么用\(f[i]\)表示待查找字符串\(t\)的长度为\(i\)前缀是否满足......
  • P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance
    思路:注意到点对数量有\(N^2\)个,考虑丢掉一些无用的点对。对于点对\((x_1,y_1),(x_2,y_2)\),满足\(x_1\lex_2<y_2\ley_1\),即区间\([x_2,y_2]\)被\([x_1,y_1]\)包含,此时满足若询问到了\([x_1,y_1]\),则一定会询问到\([x_2,y_2]\)。若满足\(\operatorname{dis}(x_1......
  • P9058 [Ynoi2004] rpmtdq
    前言开个巨坑,可能以后会三四天一更?分析路径考虑点分治,以下的\(dis\)皆为确定根节点的。以下点对\((i,j)\)都钦定\(dis_i\ledis_j\)注意到很多点对对答案是无用的,条件为若点对\((i,j)\)存在\(k\in[l+1,r-1]\),满足\(dis_i>=dis_k\or\dis_j\gedis_k\),则点对\((i,j)......
  • P2286 [HNOI2004] 宠物收养场 题解
    P2286[HNOI2004]宠物收养场set做法题链\(_{洛谷}\)\(_{题库}\)思路一眼查找前驱后继的题。注意到一句话:那么用set就没有什么阻碍了,方便又快捷。题意很简单,若宠物多则查找与人需求最接近的上下两个值,人多则找与宠物最接近的上下两个人的值。出题人很善良,把选人和选宠物......
  • [lnsyoj284/luoguP2286/HNOI2004]宠物收养场
    题意原题链接每个宠物和领养人有一个对应的特点值\(a\),当领养人过多时,若添加一个特点值为\(a_p\)的宠物,则查询收养店中特点值最接近\(a_p\),为\(a_q\)的领养人(\(<a_p\)的值优先),将答案累加\(|a_q-a_p|\),然后删除该领养人,否则在收养店中添加一个领养人。反之亦然。求最终的答案\(......
  • P9058 [Ynoi2004] rpmtdq 题解
    Description给定一棵有边权的无根树,需要回答一些询问。定义\(\texttt{dist(i,j)}\)代表树上点\(i\)和点\(j\)之间的距离。对于每一组询问,会给出\(l,r\),你需要输出\(\min(\texttt{dist(i,j)})\)其中\(l\leqi<j\leqr\)。\(n\leq2\times10^5\),\(q\leq10^6\),\(1\l......
  • P2285 [HNOI2004] 打鼹鼠
    题目:链接:https://www.luogu.com.cn/problem/P2285这题感觉如果想不到递推关系可能会很麻烦,因为我之前想到的关系就是用dp存:包含三个维度:times,x,y,即dp[times][x][y]来存,然后递推。但是如果把dp看作是以p结尾的抓到的耗子数量时就会方便很多同时要注意,每次到一个点的时候先立为1......
  • 洛谷 P9058 [Ynoi2004] rpmtdq
    洛谷传送门类比P9062[Ynoi2002]AdaptiveHsearch&Lsearch处理区间最近点对的思路,尝试只保留可能有贡献的点对。处理树上路径容易想到点分治。设点\(u\)到分治中心的距离为\(a_u\)。我们有\(\text{dis}(u,v)\lea_u+a_v\)。考虑一个点对\((u,v)\)什么时候一定没......