欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[luogu1486][郁闷的出纳员]

程序员文章站 2022-03-26 13:57:45
思路 这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候,如果要删除的数比这棵子树的根大,那么就把根变成根的右孩子,这样就相当于删除了整棵左子树和根节点。然后重新维护一 ......

题目链接

思路

这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候,如果要删除的数比这棵子树的根大,那么就把根变成根的右孩子,这样就相当于删除了整棵左子树和根节点。然后重新维护一下siz,并且维护一下平衡性就行了。

竟然把rotate函数写错了。调了30min。又没正确理解

如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

这句话的含义,又调了30min。23333

代码

//每次修改操作之后都进行一次删除,并且更改删除函数
/*
* @author: wxyww
* @date:   2018-12-02 08:41:38
* @last modified time: 2018-12-02 10:02:49
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
#define ls tr[cur].ch[0]
#define rs tr[cur].ch[1]
typedef long long ll;
const int n = 100000 + 100,inf = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int ch[2],id,val,siz,cnt;
}tr[n];
int min;
void up(int cur) {
    tr[cur].siz = tr[ls].siz + tr[rs].siz + tr[cur].cnt;
}
void rotate(int &cur,int f) {
    int son = tr[cur].ch[f];
    tr[cur].ch[f] = tr[son].ch[f ^ 1];
    tr[son].ch[f ^ 1] = cur;
    up(cur);
    cur = son;
    up(cur);
}
int tot;
void insert(int &cur,int val) {
    if(!cur) {
        cur = ++tot;
        tr[cur].id = rand();
        tr[cur].val = val;
        tr[cur].siz = tr[cur].cnt = 1;
        return;
    }
    tr[cur].siz++;
    if(val == tr[cur].val) {tr[cur].cnt++;return;}
    int d = val > tr[cur].val;
    insert(tr[cur].ch[d],val);
    if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
    if(!cur) return;
    if(val <= tr[cur].val) del(ls,val);
    else {
        del(rs,val);
        cur = rs;
    }
    up(cur);
    if(tr[ls].id < tr[cur].id && ls) rotate(cur,0);
    if(tr[rs].id < tr[cur].id && rs) rotate(cur,1);
}
int kth(int cur,int now) {
    while(1) {
        if(now > tr[rs].siz + tr[cur].cnt) now -= tr[rs].siz + tr[cur].cnt,cur = ls;
        else if(now <= tr[rs].siz) cur = rs;
        else return tr[cur].val; 
    }
}
int main() {
    int rt = 0;
    int n = read(),change = 0,num = 0;
    min = read();
    char c;
    while(n--) {
        int x;
        scanf("\n%c %d",&c,&x);
        if(c == 'i') {
            x -= change;
            if(x >= min) num++,insert(rt,x);
        }
        if(c == 'a') min -= x,change += x;
        if(c == 's') {
            min += x;
            del(rt,min);
            change -= x;
        }
        if(c == 'f') {
            if(x > tr[rt].siz) puts("-1");
            else printf("%d\n",kth(rt,x) + change);
        }
    }
    cout<<num - tr[rt].siz<<endl;
    return 0;
}

一言

时间会把你欠下的对不起,变成还不起,又会把很多对不起,变成来不及。 ——乖,摸摸头