题解 - Vijos

2

larryzhong LV 9 @ 2018-01-02 13:28:12

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

struct Splay {
    int tot, root, ch[maxn][2], fa[maxn], val[maxn], size[maxn], cnt[maxn];
    void maintain(int k) {
        size[k] = size[ch[k][0]] + size[ch[k][1]] + cnt[k];
    }
    bool get(int k) {
        return k == ch[fa[k]][1];
    }
    void clear(int k) {
        ch[k][0] = ch[k][1] = fa[k] = val[k] = size[k] = cnt[k] = 0;
    }
    void rotate(int k) {
        int old = fa[k], oldf = fa[old], chk = get(k);
        ch[old][chk] = ch[k][chk ^ 1];
        fa[ch[old][chk]] = old;
        ch[k][chk ^ 1] = old;
        fa[old] = k;
        fa[k] = oldf;
        if (oldf) {
            ch[oldf][ch[oldf][1] == old] = k;
        }
        maintain(old), maintain(k);
    }
    void splay(int k) {
        for (int f = fa[k]; f = fa[k]; rotate(k)) {
            if (fa[f]) {
                rotate(get(k) == get(f) ? f : k);
            }
        }
        root = k;
    }
    void insert(int k) {
        if (!root) {
            val[++tot] = k;
            cnt[tot]++;
            root = tot;
            maintain(root);
            return;
        }
        int cur = root, f = 0;
        while (1) {
            if (val[cur] == k) {
                cnt[cur]++;
                maintain(cur), maintain(f);
                splay(cur);
                break;
            }
            f = cur;
            cur = ch[cur][val[cur] < k];
            if (!cur) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;
                maintain(tot), maintain(f);
                splay(tot);
                break;
            }
        }
    }
    int rk(int k) {
        int res = 0, cur = root;
        while (1) {
            if (k < val[cur]) {
                cur = ch[cur][0];
            } else {
                res += size[ch[cur][0]];
                if (k == val[cur]) {
                    splay(cur);
                    return res + 1;
                }
                res += cnt[cur];
                cur = ch[cur][1];
            }
        }
    }
    int kth(int k) {
        int cur = root;
        while (1) {
            if (ch[cur][0] && k <= size[ch[cur][0]]) {
                cur = ch[cur][0];
            } else {
                k -= cnt[cur] + size[ch[cur][0]];
                if (k <= 0) {
                    return val[cur];
                }
                cur = ch[cur][1];
            }
        }
    }
    int get_prev() {
        int cur = ch[root][0];
        while (ch[cur][1]) {
            cur = ch[cur][1];
        }
        return cur;
    }
    void del(int k) {
        rk(k);
        if (cnt[root] > 1) {
            cnt[root]--;
            maintain(root);
            return;
        }
        if (!ch[root][0] && !ch[root][1]) {
            clear(root);
            root = 0;
            return;
        }
        if (!ch[root][0]) {
            int old = root;
            root = ch[root][1];
            fa[root] = 0;
            clear(old);
            return;
        }
        if (!ch[root][1]) {
            int old = root;
            root = ch[root][0];
            fa[root] = 0;
            clear(old);
            return;
        }
        int x = get_prev(), old = root;
        splay(x);
        fa[ch[old][1]] = x;
        ch[x][1] = ch[old][1];
        clear(old);
        maintain(root);
    }
} tree;

int main() {
    int n, mn, add = 0, cnt = 0;
    scanf("%d %d", &n, &mn);
    while (n--) {
        char op;
        int k, sz = tree.size[tree.root];
        scanf("\n%c %d", &op, &k);
        if (op == 'I') {
            if (k >= mn) {
                tree.insert(k - add);
            }
        } else if (op == 'A') {
            add += k;
        } else if (op == 'S') {
            add -= k;
            for (int i = 1; i <= sz; i++) {
                if (tree.kth(1) + add < mn) {
                    tree.del(tree.kth(1));
                    cnt++;
                } else {
                    break;
                }
            }
        } else {
            printf("%d\n", k > sz ? -1 : tree.kth(sz - k + 1) + add);
        }
    }
    printf("%d\n", cnt);
    return 0;
}

0

zhouruiyang LV 8 @ 2019-10-05 20:19:13

替罪羊树！！！

0

天神塞勒涅 LV 10 @ 2018-08-20 23:33:22

权值线段树裸题！！！
May the father of understanding guide U

0

linda_fcj LV 8 @ 2018-03-29 13:16:41

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e7+10;
int n,Min,tot; 
int root,tmp;
int val[maxn],si[maxn],ch[maxn][2],pri[maxn];

inline int read()
{
    int i=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar())
        if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar())
        i=(i<<3)+(i<<1)+(ch^48);
    return i*f;
}

inline int newnode(int x)
{
    val[++tot]=x;
    si[tot]=1;
    pri[tot]=rand();
    return tot;
}

inline void update(int p)
{
    si[p]=si[ch[p][0]]+si[ch[p][1]]+1;
}

inline void split(int rt,int x,int &a,int &b)
{
    if(rt==0)
    {
        a=b=0;
        return;
    }
    if(val[rt]<=x)
    {
        a=rt;
        split(ch[rt][1],x,ch[rt][1],b);
    }
    else
    {
        b=rt;
        split(ch[rt][0],x,a,ch[rt][0]);
    }
    update(rt);
}

inline int merge(int a,int b)
{
    if(!a || !b) return a^b;
    if(pri[a]<pri[b])
    {
        ch[a][1]=merge(ch[a][1],b);
        update(a);
        return a;
    }
    else
    {
        ch[b][0]=merge(a,ch[b][0]);
        update(b);
        return b;
    }
}


int kth(int rt,int k)
{
    int now=rt;
    while(1)
    {
        if(si[ch[now][0]]>=k)
            now=ch[now][0];
        else 
        {
            k-=si[ch[now][0]];
            if(k==1)return now;
            k--;
            now=ch[now][1];
        }
    }
}


int main()
{
    n=read(),Min=read();
    srand(n);
    int cnt=0;
    while(n--)
    {
        int k,a,b,u,v; 
        char op[4];
        scanf("%s",op);
        k=read();
        if(op[0]=='I')
        {
            if(k>=Min)
            {
                split(root,k-tmp,a,b);
                root=merge(merge(a,newnode(k-tmp)),b);
            }
        }
        else if(op[0]=='A')
            tmp+=k;
        else if(op[0]=='S')
        {
            tmp-=k;
            int vv=0;
            while(root && val[kth(root,1)]+tmp<Min)
            {
                vv=val[kth(root,1)];
                cnt++;
                split(root,vv-1,a,b);
                split(b,vv,u,v);
                b=merge(ch[u][0],ch[u][1]);
                root=merge(a,merge(b,v));
            }
        }
        else if(op[0]=='F')
        {
            if(root!=0 && si[root]>=k) 
                printf("%d\n",val[kth(root,si[root]-k+1)]+tmp);
            else
                printf("-1\n");
        }
    }
    printf("%d\n",cnt);
    return 0;
}

非旋转的Treap

0

WeiSama LV 8 @ 2017-02-02 20:05:18

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int maxnode = 100000 + 5;

int n, m, k, delta, ans;
char cmd[5];

struct Node {
Node *f, *ch[2];
int value, num, size;

int cmpv(int x) const {
if (x == value) return -1;
return x < value ? 0 : 1;
}

int cmps(int x) const {
int s = ch[1]->size + num;
if (x <= s && x > ch[1]->size) return -1;
return x > s ? 0 : 1;
}

void update() {
size = ch[0]->size + ch[1]->size + num;
}
} *null, *root, memory[maxnode];

stack<Node*> pool;

Node* NewNode(int value, Node *f) {
Node *t = pool.top(); pool.pop();
t->f = f, t->ch[0] = t->ch[1] = null;
t->value = value;
t->num = t->size = 1;
return t;
}

void Rotate(Node *x, bool d) {
Node *y = x->f;
y->ch[!d] = x->ch[d];
if (x->ch[d] != null) x->ch[d]->f = y;
x->f = y->f;
if (y->f != null)
if (y->f->ch[0] == y) y->f->ch[0] = x;
else y->f->ch[1] = x;
x->ch[d] = y, y->f = x, y->update();
if (y == root) root = x;
}

void Splay(Node *x, Node *f) {
while (x->f != f)
if (x->f->f == f)
if (x->f->ch[0] == x) Rotate(x, 1);
else Rotate(x, 0);
else {
Node *y = x->f, *z = y->f;
if (z->ch[0] == y)
if (y->ch[0] == x) Rotate(y, 1), Rotate(x, 1);
else Rotate(x, 0), Rotate(x, 1);
else
if (y->ch[1] == x) Rotate(y, 0), Rotate(x, 0);
else Rotate(x, 1), Rotate(x, 0);
}
x->update();
}

void Init() {
for (int i = 0; i < maxnode; i++) pool.push(memory + i);
null = NewNode(-1, null);
null->num = null->size = 0;
root = null;
}

void Insert(int v) {
Node *x = root, *y = null;
while (x != null) {
x->size++;
int d = x->cmpv(v);
if (d == -1) { x->num++; break; }
y = x, x = x->ch[d];
}
if (x == null) {
x = NewNode(v, y), y->ch[v > y->value] = x;
if (y == null) root = x;
}
Splay(x, null);
}

Node* Select(int v) {
Node *x = root, *y = root;
while (x != null) {
if (x->value + delta < m) y = x;
if (x->value + delta >= v) x = x->ch[0];
else x = x->ch[1];
}
Splay(y, null);
return y;
}

int Delete() {
Node *x = Select(m);
if (x->value + delta < m) {
root = x->ch[1];
root->f = null;
return x->ch[0]->size + x->num;
} else return 0;
}

int kth(Node *x, int k) {
if (x == null || k <= 0 || k > x->size) return -1;
int d = x->cmps(k);
if (d == -1) return x->value;
if (!d) return kth(x->ch[d], k - x->ch[1]->size - x->num);
else return kth(x->ch[d], k);
}

int main() {
Init();
scanf("%d%d", &n, &m);
while (n--) {
scanf("%s%d", cmd, &k);
switch (cmd[0]) {
case 'I':
if (k >= m) Insert(k - delta);
break;
case 'A':
delta += k;
break;
case 'S':
delta -= k;
ans += Delete();
break;
case 'F':
printf("%d\n", k <= root->size ? kth(root, k) + delta : -1);
break;
}
}
printf("%d\n", ans);
return 0;
}

0

ljt12138 LV 10 @ 2016-12-17 18:59:28

数据结构题第一次一遍AC留念.............

Treap，期望nlgn
S的时候重建就行了，有点像替罪羊树

#include <bits/stdc++.h>
using namespace std;

int key[100005], lc[100005], rc[100005], siz[100005], rk[100005];
int top = 0, root = 0;

inline int new_node(int k){ key[++top] = k; siz[top]=1; lc[top]=rc[top] = 0; rk[top] = rand(); return top; }
inline void update(int &r){ siz[r] = siz[lc[r]]+siz[rc[r]]+1; }
inline void lift_l(int &k){ int t = lc[k]; lc[k] = rc[t]; rc[t] = k; update(k); update(t); k = t;}
inline void lift_r(int &k){ int t = rc[k]; rc[k] = lc[t]; lc[t] = k; update(k); update(t); k = t;}
void push(int &nd, int k)
{
    if (!nd)
        nd = new_node(k);
    else if (key[nd] >= k) {
        push(rc[nd], k); update(nd); if (rk[rc[nd]] > rk[nd]) lift_r(nd);
    } else {
        push(lc[nd], k); update(nd); if (rk[lc[nd]] > rk[nd]) lift_l(nd);
    }
}

void pop(int &nd, int k)
{
    if (!nd) return;
    if (key[nd] > k) pop(rc[nd], k);
    else if (key[nd] < k) pop(lc[nd], k);
    else {
        while (lc[nd]) {lift_l(nd); siz[nd]--; nd = rc[nd];}
        while (rc[nd]) {lift_r(nd); siz[nd]--; nd = lc[nd];}
        nd = 0;
    }
}

int kth(int &nd, int k)
{
    if (siz[lc[nd]]+1 == k) return key[nd];
    else if (siz[lc[nd]]+1 > k) return kth(lc[nd], k);
    else return kth(rc[nd], k-siz[lc[nd]]-1);
}

int n, minn;
int delta = 0, cnt = 0;
char c;
int a;
vector<int> vec;

void travel(int nd, vector<int> &vec)
{
    if (nd) {
        travel(lc[nd], vec);
        if (key[nd]+delta >= minn) vec.push_back(nd);
        else cnt++;
        travel(rc[nd], vec);
    }
}

int rebuild(vector<int> &vec, int l, int r)
{
    if (l > r) return 0;
    int mid = (l+r)>>1;
    lc[vec[mid]] = rebuild(vec, l, mid-1);
    rc[vec[mid]] = rebuild(vec, mid+1, r);
    update(vec[mid]);
    return vec[mid];
}

int main()
{
    freopen("cashier.in", "r", stdin);
    freopen("cashier.out", "w", stdout);
    srand(time(0));
    cin >> n >> minn;
    for (int i = 1; i <= n; i++) {
        scanf("\n%c %d", &c, &a);
        switch(c) {
            case 'I': if (a >= minn) push(root, a-delta); break;
            case 'A': delta += a; break;
            case 'S': delta -= a; vec.clear(); travel(root, vec); root = rebuild(vec, 0, vec.size()-1); break;
            case 'F': if (a > siz[root]) puts("-1"); else printf("%d\n", kth(root, a)+delta); break;
        }
        //dfs(root);
    }
    cout << cnt << endl;
    return 0;
}

0

Mickeypeng LV 4 @ 2016-11-28 23:38:52

可以说是平衡树模板题吧
但是我非要用线段树做（手动笑脸）
其实也不难，工资范围是-20万到20万，全部加20万变为0到40万
加上懒惰标记就可以了
最后，记得用scanf printf 能AC，cin cout不取消关联6个点TLE，
```C++
#include <iostream>
#include <fstream>
using namespace std;
const int maxn=200000;
int totnum=0;
struct node
{
node* l;
node* r;
int delay;
int data;
node(node* ll,node*rr)
{
delay=0;
data=0;
l=ll;
r=rr;
}
};
node* nil=new node(NULL,NULL);
node* root=new node(nil,nil);

void init(node* cur,int l,int r)
{
if(l==r)
return;
cur->l=new node(nil,nil);
cur->r=new node(nil,nil);
int mid=(l+r)/2;
init(cur->l,l,mid);
init(cur->r,mid+1,r);
}
void del(int l,int r,int curl,int curr,node* cur)
{
if(cur->delay==1)
return;
if((curl==l)&&(r==curr))
{
cur->delay=1;
totnum+=cur->data;
cur->data=0;
return;
}
int mid=(curl+curr)/2;
if(r<=mid)
del(l,r,curl,mid,cur->l);
else if(l>mid)
del(l,r,mid+1,curr,cur->r);
else
{
del(l,mid,curl,mid,cur->l);
del(mid+1,r,mid+1,curr,cur->r);
}
cur->data=cur->l->data+cur->r->data;
}
void add(int x,int curl,int curr,node* cur)
{
if(cur->delay==1)
{
cur->data=0;
cur->delay=0;
cur->l->delay=1;
cur->l->data=0;
cur->r->delay=1;
cur->r->data=0;
}
cur->data+=1;
if(curl==curr)
return;
int mid=(curl+curr)/2;
if(x<=mid)
add(x,curl,mid,cur->l);
else
add(x,mid+1,curr,cur->r);
}
int findk(int x,int curl,int curr,node* cur)
{
//cout<<curl<<" "<<curr<<" "<<cur->data<<endl;;
if(x>cur->data)
return -1;
if(curl==curr)
return curl;
int mid=(curl+curr)/2;
if(cur->r->data>=x)
return findk(x,mid+1,curr,cur->r);
else
return findk(x-cur->r->data,curl,mid,cur->l);
}
int main()
{
init(root,0,2*maxn);
char op;
char ignore;
int lazy=0;
int n,m,k;
scanf("%d%d",&n,&m);
scanf("%c",&ignore);
for(int i=0;i<n;i++)
{
scanf("%c%c%d",&op,&ignore,&k);
scanf("%c",&ignore);
//cout<<op<<k;
if(op=='I')
{
if(k<m)
continue;
add(k+maxn-lazy,0,2*maxn,root);
}
else if(op=='A')
{
lazy+=k;
}
else if(op=='S')
{
lazy-=k;
del(0,m+maxn-lazy-1,0,2*maxn,root);
}
else if(op=='F')
{
int ans=findk(k,0,2*maxn,root);
if(ans==-1)
printf("-1\n");
else printf("%d\n",ans-maxn+lazy);
}
}
printf("%d\n",totnum);
}
```

0

zxu22 LV 10 @ 2016-10-10 19:27:31

那么多Splay的题解了，刚好我不会splay，离线线段树居然也能写出来，就是可能效率有点低，也有可能是cin的问题。
离线线段树代码贴上去
```C++
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

long long n, minkey;
char ord[300300];
long long q[300300],a[100300];
long long tot = 0;
long long tree[600600] = { 0 };

void add(long long l, long long r, long long num, long long tar) //加入的位置是tar
{
if (tar<1 || tar>tot) return;
if (tree[num] == 0)
{
tree[num * 2] = 0;
tree[num * 2 + 1] = 0;
}
tree[num]++;
if (l == r) return;
long long mid = (l + r) / 2;
if (tar <= mid) add(l, mid, num * 2, tar);
else if (tar > mid) add(mid + 1, r, num * 2 + 1, tar); //这种代码我就没这样写过
}

long long del(long long l, long long r, long long num, long long tar) //tar是第几个元素
{
if (tar == 0)return 0;
if (tree[num] == 0){ tree[num * 2] = tree[num * 2 + 1] = 0; return 0; }
long long back = 0;
long long mid = (l + r) / 2;
if (l == r) //会死循环吗？我也不懂，特判一下
{
back = tree[num];
tree[num] = 0;
return back;
}
if (tar <= mid)
{
back += del(l, mid, num * 2, tar);
}
else
{
back += tree[num * 2];
tree[num * 2] = 0;
back += del(mid + 1, r, num * 2 + 1, tar);
}
tree[num] -= back;
return back; //删除了back个元素
} //这个是减工资的时候用
/*我就没这样写过线段树！我也不懂自己在写什么了。*/

long long found(long long l, long long r, long long num, long long k) //找k小元素出来
{
if (l == r) return a[l]; //得到的元素还要加上base才能完整
long long mid = (l + r) / 2;
if (k > tree[num] || k < 1) return -23333333;
if (k <= tree[num * 2]) return found(l, mid, num * 2, k);
if (k > tree[num * 2]) return found(mid + 1, r, num * 2 + 1, k - tree[num * 2]); //这个效率是lg(n)吧？
}
/*简直作死，不过要勇于尝试……*/

long long binary_search(long long num)
{
long long l=0, r=tot;
while (l < r)
{
long long mid = (l + r + 1) / 2;
if (a[mid] <= num) l = mid;
else r = mid - 1;
}
return l;
} //二分查找，写到混乱的代码，不愧noi

int main()
{
ios::sync_with_stdio(false);
cin >> n >> minkey;
long long away = 0;
long long base = 0; //代表涨工资的量
for (long long i = 1; i <= n; i++)
{
cin >> ord[i] >> q[i];
if (ord[i] == 'I')
a[++tot] = q[i] - base;
else if (ord[i] == 'S') base -= q[i];
else if (ord[i] == 'A') base += q[i];
// F 忽略掉
}
sort(a + 1, a + tot + 1); //以上为离线处理
a[0] = -99999999;
base = 0; //init
for (long long i = 1; i <= n; i++) //这里是正式操作了
{
if (ord[i] == 'I') //加入一个人
{
long long num = q[i] - base;
if (q[i] >= minkey)
{
long long tar = binary_search(num);
add(1, tot, 1, tar);
}
// else away++;
}
else if (ord[i] == 'S') //降工资啊，要裁员
{
base -= q[i];
long long num = minkey - base - 1; //比这个低的，或者等于的(减了1)都要裁员~
long long tar = binary_search(num);
away += del(1, tot, 1, tar); //删除tar，以及比他小的元素
}
else if (ord[i] == 'A') base += q[i]; //涨工资也不会加人
else if (ord[i] == 'F') //找第k大了！
{
long long ans =found(1, tot, 1, tree[1] - q[i] + 1);
if (ans!=-23333333)
cout << ans + base << endl;
else cout << -1 << endl;
}
}
cout << away << endl;

return 0;
}
```

0

846047746 LV 7 @ 2016-04-19 11:30:01

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<string>
char c[1];
int v[100001],s[100001],f[100001],l[100001],r[100001],n,m,root,sum,len,u,k,ans,ss;
void zig(int x)
{
int t=f[x];
l[t]=r[x];
if(l[t]) f[l[t]]=t;
int ff=f[x]=f[t];
if(ff)
if(t==l[ff]) l[ff]=x;
else r[ff]=x;
r[x]=t;f[t]=x;
s[t]=s[l[t]]+s[r[t]]+1;
s[x]=s[l[x]]+s[r[x]]+1;
}
void zag(int x)
{
int t=f[x];
r[t]=l[x];
if(r[t]) f[r[t]]=t;
int ff=f[x]=f[t];
if(ff)
if(t==l[ff]) l[ff]=x;
else r[ff]=x;
l[x]=t;f[t]=x;
s[t]=s[l[t]]+s[r[t]]+1;
s[x]=s[l[x]]+s[r[x]]+1;
}
void splay(int x)
{
while(f[x])
{
int t=f[x];
if(!f[t])
{
if(x==l[t]) zig(x);
else zag(x);
break;
}
if(x==l[t])
if(t==l[f[t]])
{zig(t);zig(x);}
else
{zig(x);zag(x);}
else
if(t==r[f[t]])
{zag(t);zag(x);}
else
{zag(x);zig(x);}
}
}
void insert(int x)
{
int t=root;
while(true)
{
++s[t];
if(v[x]<=v[t])
if(l[t]) t=l[t];
else {l[t]=x;f[x]=t;break;}
else
if(r[t]) t=r[t];
else {r[t]=x;f[x]=t;break;}
}
splay(x);
root=x;
}
void del()
{
int t=root,p=0;
while(true)
if(m<=v[t])
if(l[t]) t=l[t];
else break;
else
if(r[t]) p=t,t=r[t];
else {p=t;break;}
if(!p) return;
splay(p);
ss+=s[l[p]]+1;
len-=s[l[p]]+1;
root=r[p];
f[root]=0;
}
void find(int x)
{
int t=root;
if(x>s[t])
{ans=-1;return;}
while(true)
if(x==s[r[t]]+1)
{ans=v[t]+sum;break;}
else
if(x<=s[r[t]]) t=r[t];
else x-=s[r[t]]+1,t=l[t];
}
int main()
{
scanf("%d%d",&n,&m);
while(n--)
{
scanf("%s%d",&c,&k);
if(c[0]=='I')
{
v[++u]=k-sum;
if(v[u]<m)
{--u;continue;}
s[u]=1;
if(++len==1)
{root=u;continue;}
insert(u);
}
else
if(c[0]=='A')
m-=k,sum+=k;
else
if(c[0]=='S')
m+=k,sum-=k,del();
else
find(k),printf("%d\n",ans);
}
printf("%d\n",ss);
return 0;
}

0

Onlynagesha LV 9 @ 2016-03-23 21:29:32

测试数据 #0: Accepted, time = 93 ms, mem = 6820 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 548 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 960 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 1732 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 2520 KiB, score = 10

测试数据 #6: Accepted, time = 46 ms, mem = 3296 KiB, score = 10

测试数据 #7: Accepted, time = 46 ms, mem = 2908 KiB, score = 10

测试数据 #8: Accepted, time = 78 ms, mem = 5648 KiB, score = 10

测试数据 #9: Accepted, time = 78 ms, mem = 7604 KiB, score = 10

Accepted, time = 387 ms, mem = 7604 KiB, score = 100

#include <cstdio>
#include <cstring>
#include <algorithm>

int main()
{
int n,min;
int employed=0;
scanf("%d%d",&n,&min);
int _min=min;
LesserSbt<int> sbt(n<<1);
while(n--)
{
char cmd;
int x;
do cmd=getchar(); while(cmd==' ' || cmd=='\n');
switch(cmd)
{
case 'I':
scanf("%d",&x);
if(x>=min)
{
++employed;
sbt.insert(x+_min-min);
}
break;
case 'A':
scanf("%d",&x);
_min-=x;
break;
case 'S':
scanf("%d",&x);
_min+=x;
sbt.eraseLess(_min);
break;
case 'F':
scanf("%d",&x);
int _ans=sbt.kthGreater(x);
printf("%d\n",_ans==-1 ? -1 : _ans+min-_min);
break;
}
}
printf("%d",employed-sbt.size());
return 0;
}

ljt12138 @ 2016-12-17 19:06:34

sbt好快...

0

1263659722 LV 10 @ 2016-02-19 10:46:56

splay tree

#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define LOCAL
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
#define N 1000010

//#include <tr1/unordered_set>
//#include <tr1/unordered_map>
//#include <array>

using namespace std;

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define REP_C(i, n) for (int n____=n,i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=b,i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=a,i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<n;++i)
#define FOR_N(i, a, b) for (i=a;i<b;++i)
#define DWN_N(i, b, a) for (i=b-1;i>=a;--i)
#define REP_1_C(i, n) for (int n____=n,i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=b,i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=a,i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=n;++i)
#define FOR_1_N(i, a, b) for (i=a;i<=b;++i)
#define DWN_1_N(i, b, a) for (i=b;i>=a;--i)
#define REP_C_N(i, n) for (int n____=(i=0,n);i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,a);i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,n);i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=a,b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,a);i>=a____;--i)

#define ECH(it, A) for (typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)
#define rECH(it, A) for (typeof((A).rbegin()) it=(A).rbegin(); it != (A).rend(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)
#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())
#define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int((A).size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define Ts *this
#define rTs return Ts
#define fi first
#define se second
#define re real()
#define im imag()

#define Rush for(int ____T=RD(); ____T--;)
#define Display(A, n, m) { \
REP(i, n){ \
REP(j, m-1) cout << A[i][j] << " "; \
cout << A[i][m-1] << endl; \
} \
}
#define Display_1(A, n, m) { \
REP_1(i, n){ \
REP_1(j, m-1) cout << A[i][j] << " "; \
cout << A[i][m] << endl; \
} \
}

typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

template<class T> inline T& RD(T &);
template<class T> inline void OT(const T &);
//inline int RD(){int x; return RD(x);}
inline LL RD(){LL x; return RD(x);}
inline DB& RF(DB &);
inline DB RF(){DB x; return RF(x);}
inline char* RS(char *s);
inline char& RC(char &c);
inline char RC();
inline char& RC(char &c){scanf(" %c", &c); return c;}
inline char RC(){char c; return RC(c);}
//inline char& RC(char &c){c = getchar(); return c;}
//inline char RC(){return getchar();}

template<class T> inline T& RDD(T &);
inline LL RDD(){LL x; return RDD(x);}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}
template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}
template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}
template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}
template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}
inline char& RC(char &a, char &b){RC(a), RC(b); return a;}
inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}
inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}
inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}
inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}
inline void RS(char *s1, char *s2){RS(s1), RS(s2);}
inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}
template<class T0,class T1>inline T0& RDD(T0&a, T1&b){RDD(a),RDD(b); return a;}
template<class T0,class T1,class T2>inline T1& RDD(T0&a, T1&b, T2&c){RDD(a),RDD(b),RDD(c); return a;}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void CLR(T &A){A.clear();}

template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}
template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(stack<T> &S){while (!S.empty()) S.pop();}
template<class T> inline void CLR(queue<T> &Q){while (!Q.empty()) Q.pop();}

template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}
template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline bool EPT(T &a){return a.empty();}
template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}
template<class T, class C> inline T& SRT(T &A, C cmp){sort(ALL(A), cmp); return A;}
template<class T> inline T& RVS(T &A){reverse(ALL(A)); return A;}
template<class T> inline T& UNQQ(T &A){A.resize(unique(ALL(A))-A.begin());return A;}
template<class T> inline T& UNQ(T &A){SRT(A);return UNQQ(A);}
template<class T, class C> inline T& UNQ(T &A, C cmp){SRT(A, cmp);return UNQQ(A);}

//}

/** Constant List .. **/ //{

const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

//}

/** Add On .. **/ //{
// <<= '0. Nichi Joo ., //{

template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;}
template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;}
template <class T, class C> inline bool checkUpd(T& a, const T b, C c){return c(b,a) ? a = b, 1 : 0;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}
template<class T> inline T min(T a, T b, T c, T d, T e){return min(min(min(a,b),min(c,d)),e);}
template<class T> inline T max(T a, T b, T c, T d, T e){return max(max(max(a,b),max(c,d)),e);}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}
template<class T> T abs(T x){return x>0?x:-x;}
inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

inline DB cos(DB a, DB b, DB c){return (sqr(a)+sqr(b)-sqr(c))/(2*a*b);}
inline DB cot(DB x){return 1./tan(x);};
inline DB sec(DB x){return 1./cos(x);};
inline DB csc(DB x){return 1./sin(x);};

//}
// <<= '1. Bitwise Operation ., //{
namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}
inline bool _1(LL x, int i){return bool(x&1LL<<i);}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){
x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);
return x;
}

inline LL reverse_bits(LL x){
x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);
x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);
return x;
}

template<class T> inline bool odd(T x){return x&1;}
template<class T> inline bool even(T x){return !odd(x);}
template<class T> inline T low_bit(T x) {return x & -x;}
template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}
template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}
template<class T> inline int cover_idx(T x){int p = 0; while (_1(p) < x ) ++p; return p;}

inline int clz(int x){return __builtin_clz(x);}
inline int clz(LL x){return __builtin_clzll(x);}
inline int ctz(int x){return __builtin_ctz(x);}
inline int ctz(LL x){return __builtin_ctzll(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}
inline int lg2(LL x){return !x ? -1 : 63 - clz(x);}
inline int low_idx(int x){return !x ? -1 : ctz(x);}
inline int low_idx(LL x){return !x ? -1 : ctz(x);}
inline int high_idx(int x){return lg2(x);}
inline int high_idx(LL x){return lg2(x);}
inline int parity(int x){return __builtin_parity(x);}
inline int parity(LL x){return __builtin_parityll(x);}
inline int count_bits(int x){return __builtin_popcount(x);}
inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}
using namespace std;
typedef long long LL;
int a[N],u[N];
int n,m,w[N],cnt,rt,t1,t2,tag[N],rev[N],sz[N],fa[N],c[N][2],delta,leave;
void pushup(int x)
{
int lson=c[x][0],rson=c[x][1];
sz[x]=sz[lson]+sz[rson]+1;
}
/*
void rot(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
if(y!=k)c[z][c[z][l]==y]=x;
else k=x;
fa[x]=z;
fa[y]=x;
fa[c[x][r]]=y;
pushup(y);
pushup(x);
}
*/
void rot(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
if(y!=k)c[z][c[z][1]==y]=x;
else k=x;
fa[x]=z,fa[y]=x,fa[c[x][r]]=y;
c[y][l]=c[x][r],c[x][r]=y;
pushup(y);
pushup(x);
}

void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x],z=fa[y];
if(y!=k)
{
if((c[z][0]==y)^(c[y][0]==x))rot(x,k);
else rot(x,k);
}
rot(x,k);
}
}
void ins(int k)
{
if(!rt)
{
rt=++cnt;
w[cnt]=k,sz[cnt]=1;
return;
}
int p=rt,z;
while(p>0)
{
z=p;
sz[p]++;
if(w[p]>k)
{
p=c[p][0];
}
else
p=c[p][1];
}
if(w[z]>k)
c[z][0]=++cnt;
else
c[z][1]=++cnt;
w[cnt]=k,sz[cnt]=1,fa[cnt]=z;
splay(cnt,rt);

}
int find(int x,int rk)
{
int l=c[x][0],r=c[x][1];
if(sz[l]+1==rk)return x;
if(sz[l]>=rk)return find(l,rk);
return find(r,rk-sz[l]-1);
}/*
queue<int>q;
void rec(int x)
{
if(!x)return;
int l=c[x][0],r=c[x][1];
rec(l);
rec(r);
q.push(x);
fa[x]=c[x][0]=c[x][1]=0;
tag[x]=rev[x]=0;
}
int split(int k,int tot)
{
int x=find(rt,k),y=find(rt,k+tot+1);
splay(x,rt);splay(y,c[x][1]);
return c[y][0];
}
void erase(int k,int tot)
{
int x=split(k,tot),y=fa[x];
rec(x);
c[y][0]=0;
pushup(y);
pushup(fa[y]);
}*/
/*
int del(int &x,int f)
{
if(!x)
{
return 0;
}
int k,ls=c[x][0],rs=c[x][1],l=c[f][1]==x;
if(w[x]+delta<m)
{
k=del(rs,x)+sz[ls]+1;
sz[rs]=sz[x]-k;
sz[ls]=sz[x]=w[ls]=w[x]=0;
x=rs,fa[x]=f,c[f][l]=x;
}
else
{
k=del(ls,x);
sz[x]-=k;
}
return k;
}*//*
int query(int x,int k)
{
if(!k)return 0;
int lson=c[k][0],rson=c[k][1];
if(sz[lson+1]==x)return k;
else if(sz[lson]>=k)return query(x,lson);
return query(k-sz[lson]-1,rson);
}*/
int del(int &x,int f)
{
if(!x)
{
return 0;
}
int k,ls=c[x][0],rs=c[x][1],l=c[f][1]==x;
if(w[x]+delta<m)
{
k=del(rs,x)+sz[ls]+1;
sz[rs]=sz[x]-k;
sz[ls]=sz[x]=w[ls]=w[x]=0;
x=rs,fa[x]=f,c[f][l]=x;
}
else
{
k=del(ls,x);
sz[x]-=k;
}
return k;
}
int findpos(int x,int k)
{
if(!x)return 0;
int ls=c[x][0],rs=c[x][1];
if(sz[ls]+1==k)
return x;
else if(sz[ls]>=k)
{
return findpos(ls,k);
}
return findpos(rs,k-sz[ls]-1);
}
int main()
{
scanf("%d%d",&n,&m);
char ch;
int k;
getchar();
for(int i=1;i<=n;i++)
{
ch=getchar();
while(ch != 'I' && ch != 'A' && ch != 'S' && ch != 'F')
ch = getchar();
scanf("%d",&k);
if(ch=='I')
{
if(k<m)
{
continue;
}
ins(k-delta);
}
else if(ch=='A')
{
delta+=k;
}
else if(ch=='S')
{
delta-=k;
leave+=del(rt,0);
}
else if(ch=='F')
{
//if(k>n||k<1)printf("-1\n");
printf("%d\n",sz[rt]>=k?w[findpos(rt,sz[rt]-k+1)]+delta:-1);
}

}
printf("%d\n",leave);
return 0;
}

Antman @ 2016-02-19 10:48:02

...666
Onlynagesha @ 2016-03-23 13:19:51

手动高清重置害怕⊙△⊙

0

wang_yanheng LV 10 @ 2016-01-27 22:40:35

Splay 190 lines 1200ms (total)
讲一下做法：
使用Splay Tree维护工资。由于一种工资可能有多人，故需要新建一个域cnt，记录该种工资的人数。
又因为需要查询第k大值，还需要维护一个域size（表示以该节点为根的子树大小）。查询时，设当前节点为 x 。
若 k<=x.r.size，则进入 x.r 查询 k 大值；若 x.r.size< k<=x.cnt+x.r.size，则返回x.key；否则，进入 x.l 查询第 k-x.r.size-x.cnt 大值。

关于size和cnt的维护，其实只有两处：
1) 插入时将路径上的所有 size++，并把目标节点的 cnt++
2) 旋转时更新移位的两个节点的size

最后开一个全局变量 delta，用于记录工资增减。注意处理好即可。

贴一段代码

int getKMax(int k){
node *p = top->l;
if(k > getSize(p))
return -1;

while(p != NULL){
if(k <= getSize(p->r)){ //in left tree
p = p->r;
}else if(k <= getSize(p->r) + p->cnt){
return p->key;
}else{ //in right tree
k -= getSize(p->r) + p->cnt;
p = p->l;
}
}
return -1; //error
}

0

2859198007 LV 8 @ 2016-01-15 19:10:20

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL maxn=100010;
char s[5];
LL root,tot,N,MIN,sum,delta;
LL key[maxn],lc[maxn],rc[maxn],siz[maxn];
void r_rotate(LL &rt){
LL k=lc[rt];
lc[rt]=rc[k];
rc[k]=rt;
siz[k]=siz[rt];
siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1;
rt=k;
}
void l_rotate(LL &rt){
LL k=rc[rt];
rc[rt]=lc[k];
lc[k]=rt;
siz[k]=siz[rt];
siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1;
rt=k;
}
void Maintain(LL &rt,bool flag){
if(flag==false){
if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt);
else if(siz[rc[lc[rt]]]>siz[rc[rt]]){
l_rotate(lc[rt]);
r_rotate(rt);
}
else return ;
}
else{
if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt);
else if(siz[lc[rc[rt]]]>siz[lc[rt]]){
r_rotate(rc[rt]);
l_rotate(rt);
}
else return ;
}
Maintain(lc[rt],0); Maintain(rc[rt],1);
Maintain(rt,1); Maintain(rt,0);
}
void insert(LL &rt,LL v){
if(rt==0){
rt=++tot;
siz[rt]=1;
lc[rt]=rc[rt]=0;
key[rt]=v;
return ;
}
siz[rt]++;
if(v<=key[rt]) insert(lc[rt],v);
else insert(rc[rt],v);
Maintain(rt,1); Maintain(rt,0);
}
LL Delete(LL &rt,LL v){
LL ans;
siz[rt]--;
if(v==key[rt]||(v<key[rt]&&lc[rt]==0)||(v>key[rt]&&rc[rt]==0)){
ans=key[rt];
if(lc[rt]==0||rc[rt]==0) rt=lc[rt]+rc[rt];
else key[rt]=Delete(lc[rt],key[rt]+1);
return ans;
}
else if(v<key[rt]) ans=Delete(lc[rt],v);
else ans=Delete(rc[rt],v);
return ans;
}
LL select(LL &rt,LL k){
if(k==siz[lc[rt]]+1) return key[rt];
if(k<=siz[lc[rt]]) return select(lc[rt],k);
else return select(rc[rt],k-1-siz[lc[rt]]);
}
bool find(LL &rt,LL v){
if(rt==0) return false;
else if(v==key[rt]) return true;
else if(v<key[rt]) return find(lc[rt],v);
else if(v>key[rt]) return find(rc[rt],v);
}
LL pred(LL &rt,LL v){
if(rt==0) return v;
if(v<=key[rt]) return pred(lc[rt],v);
else{
LL ans=pred(rc[rt],v);
if(ans==v) return key[rt];
return ans;
}
}
void Clear(){
for(;;){
LL k=pred(root,MIN);
if(find(root,k)==true&&k<MIN) Delete(root,k),sum++;
else break;
}
}
int main(){
scanf("%lld%lld",&N,&MIN);
for(LL i=1,tmp;i<=N;i++){
scanf("%s%lld",s,&tmp);
if(s[0]=='I'){
if(tmp-delta<MIN){
continue;
}
insert(root,tmp-delta);
}
else if(s[0]=='A'){//增加工资
MIN-=tmp;//要求标准下降
delta+=tmp;
Clear();
}
else if(s[0]=='S'){//减少工资
MIN+=tmp;//要求标准上升
delta-=tmp;
Clear();
}
else{
if(siz[root]<tmp) puts("-1");
else printf("%lld\n",select(root,siz[root]-tmp+1)+delta);
}
}
printf("%lld\n",sum);
return 0;
}

0

TenderRun LV 10 @ 2015-12-10 14:01:21

###需要注意的是即来即走的人不计数！！！

评测状态 Accepted
题目 P1507 郁闷的出纳员
递交时间 2015-12-10 13:58:08
代码语言 C++
评测机 VijosEx
消耗时间 2133 ms
消耗内存 3412 KiB
评测时间 2015-12-10 13:58:13
评测结果
编译成功

foo.cpp: In function 'int find_kth(int)':
foo.cpp:62:6: warning: unused variable 'ret' [-Wunused-variable]
int ret=0,p=root;
^
foo.cpp: In function 'int main()':
foo.cpp:117:8: warning: unused variable 'ans' [-Wunused-variable]
int ans;
^
测试数据 #0: Accepted, time = 468 ms, mem = 3404 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3404 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 3412 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 3412 KiB, score = 10
测试数据 #4: Accepted, time = 93 ms, mem = 3412 KiB, score = 10
测试数据 #5: Accepted, time = 171 ms, mem = 3404 KiB, score = 10
测试数据 #6: Accepted, time = 202 ms, mem = 3404 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 3404 KiB, score = 10
测试数据 #8: Accepted, time = 405 ms, mem = 3412 KiB, score = 10
测试数据 #9: Accepted, time = 608 ms, mem = 3412 KiB, score = 10
Accepted, time = 2133 ms, mem = 3412 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=214748300;
int n,m,mim,a,b,dta=0;
int cnt,root,ch[200005][2],fa[200005],sz[100005],key[100005];
void rotate(int x)
{ int y=fa[x],g=fa[y],c=ch[y][1]==x;
fa[y]=x;fa[x]=g;fa[ch[x][c^1]]=y;
ch[y][c]=ch[x][c^1];ch[x][c^1]=y;
sz[x]=sz[y];sz[y]=sz[ch[y][0]]+sz[ch[y][1]]+1;
if(g)ch[g][ch[g][1]==y]=x;
}
void splay(int x,int g=0)
{ for(int y;(y=fa[x])!=g;rotate(x))
if(fa[y]!=g)rotate((x==ch[y][1])==(ch[fa[y]][1]==y)?y:x);
if(g==0)root=x;
}
void add(int x)
{ int p=root;
if(!p)
{ p=++cnt;
root=p;
sz[p]=1;
key[p]=x;
return;
}
int pre;
while(p)
{ pre=p;
sz[p]++;
p=ch[p][key[p]<=x];
}
p=++cnt;
fa[p]=pre;
ch[pre][key[pre]<=x]=p;
sz[p]=1;
key[p]=x;
splay(p);
}
int find_pos(int x)
{
int p=root,pos=0,maxn=-INF;
for(;p;)
{
if(key[p]>=x){
p=ch[p][0];
}
else{
if(maxn<=key[p]){
pos=p;
maxn=key[p];
}
p=ch[p][1];
}
}
return pos;
}
int find_kth(int k)
{
int ret=0,p=root;
while(p)
{ if(sz[ch[p][0]]+1>k)p=ch[p][0];
else if(sz[ch[p][0]]+1<k){
k-=sz[ch[p][0]]+1;
p=ch[p][1];
}
else {
k=0;
break;
}
}
if(k!=0)return 0;
return p;
}
void zxbl(int p)
{ if(!p)return;
zxbl(ch[p][0]);
printf("<%d >",key[p]+mim);
zxbl(ch[p][1]);
}
int main()
{

scanf("%d%d",&m,&mim);
int tot=0;
char op[10];
for(;m--;)
{

//zxbl(root);
//printf("\n");
//printf("dta:%d\n",dta);
scanf("%s",op);
if(op[0]=='I')
{ scanf("%d",&a);
if(a>=mim)
{add(a-mim+dta);n++;}
}
else if(op[0]=='S')
{ scanf("%d",&a);
dta+=a;
int p=find_pos(dta);
if(p==0)continue;
splay(p);
tot+=sz[ch[p][0]]+1;
n-=sz[ch[p][0]]+1;

root=ch[p][1];
fa[ch[p][1]]=0;
}
else if(op[0]=='A')
{ scanf("%d",&a);
dta-=a;
}
else if(op[0]=='F')
{ scanf("%d",&a);
int ans;
if(a>n||a<1)printf("-1\n");
else printf("%d\n",key[find_kth(n-a+1)]-dta+mim);
}
}
printf("%d\n",tot);
return 0;
}

0

qq790189732 LV 8 @ 2015-10-15 22:36:23

为什么我用treap用了5s多，是不是我RP不行。。。

0

孖作多情、 LV 9 @ 2015-08-16 11:26:42

主要是“如果某员工的初始工资低于工资下界，他将立刻离开公司”不计入总数，错了N次才发现。
因为“I命令的条数不超过 100000”，所以数组开到100000就可以了，没必要*2；
至于什么用write而不加ln，纯属扯淡。
相同大小的点应该放在右儿子处。
删除点的时候直接把左子树砍了。
我用的是SBT，但不知为什么很慢，上了2000+MS。

0

huanghongxun LV 10 @ 2014-07-17 16:20:46

SBT挺慢不知道为啥
删除的时候小于限定值直接删掉整个子树就好了

Block Code

#include <cstdio>
long n, mi, g;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define s(x) tree[x].s
#define key(x) tree[x].key
int root = 0, cnt = 0, rm = 0;
struct Node {
int l, r, s; long key;
Node() { l = r = s = 0; }
} tree[100005];
inline void r_rotate(int &t) {
int k = l(t); l(t) = r(k); r(k) = t; s(k) = s(t);
s(t) = s(l(t)) + s(r(t)) + 1; t = k;
}
inline void l_rotate(int &t) {
int k = r(t); r(t) = l(k); l(k) = t; s(k) = s(t);
s(t) = s(l(t)) + s(r(t)) + 1; t = k;
}
void maintain(int &t, bool flag) {
if(!flag) {
if(s(l(l(t))) > s(r(t))) r_rotate(t);
else if(s(r(l(t))) > s(r(t))) {
l_rotate(l(t)); r_rotate(t);
}
else return;
} else {
if(s(r(r(t))) > s(l(t))) l_rotate(t);
else if(s(l(r(t))) > s(l(t))) {
r_rotate(r(t)); l_rotate(t);
}
else return;
}
maintain(l(t),false);
maintain(r(t),true);
maintain(t,false);
maintain(t,true);
}
void insert(int &t, long v) {
if(t == 0) {
key(t = ++cnt) = v;
s(t) = 1;
} else {
s(t)++;
if(v < key(t)) insert(l(t), v);
else insert(r(t), v);
}
maintain(t, v >= key(t));
}
void remove(int &t, long v) {
if(t == 0) return;
if(key(t) < v) {
rm += s(l(t)) + 1;
remove(t = r(t), v);
} else {
remove(l(t), v);
s(t) = s(l(t)) + s(r(t)) + 1;
}
maintain(t, true);
maintain(t, false);
}
int search(int t, int k) {
if(s(r(t))+1 == k)
return key(t);
else if(s(r(t))+1<k)
return search(l(t),k-s(r(t))-1);
else
return search(r(t),k);
}
int main() {
scanf("%d%d", &n, &mi);
char t[5]; long j;
while(n--) {
scanf("%s%d", t, &j);
switch(t[0]) {
case 'I': if(j >= mi) insert(root, j-g); break;
case 'A': g += j; break;
case 'S': g -= j; remove(root, mi-g); break;
case 'F':
if(s(root) < j) puts("-1");
else printf("%d\n", search(root, j)+g);
break;
}
}
printf("%d", rm);
return 0;
}

0

lx865712528 LV 6 @ 2014-03-16 21:13:25

这题不知怎么弄得，我splay的写法，在用例2和用例3上T了一天，差点放弃了。
评测结果
编译成功
测试数据 #0: Accepted, time = 171 ms, mem = 3052 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2784 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2780 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 2916 KiB, score = 10
测试数据 #5: Accepted, time = 39 ms, mem = 2784 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 2972 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 2784 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 2784 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 4132 KiB, score = 10
Accepted, time = 739 ms, mem = 4132 KiB, score = 100
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
class SplayTree {
private:
int sz[maxn],ch[maxn][2],pre[maxn],val[maxn],num[maxn],NOW;
public:
int leave,root,ext;
inline void Rotate(int x,int f) {
int y=pre[x];
ch[y][!f]=ch[x][f];
pre[ch[x][f]]=y;
pre[x]=pre[y];
if(pre[x]) ch[pre[y]][ch[pre[y]][1]==y]=x;
ch[x][f]=y;
pre[y]=x;
push_up(y);
}
inline void Splay(int x,int goal) {
while(pre[x]!=goal) {
if(pre[pre[x]]==goal) {
Rotate(x,ch[pre[x]][0]==x);
}
else {
int y=pre[x],z=pre[y];
int f=(ch[z][0]==y);
if(ch[y][f]==x) {
Rotate(x,!f),Rotate(x,f);
}
else {
Rotate(y,f),Rotate(x,f);
}
}
}
push_up(x);
if(goal==0) root=x;
}
inline void RotateTo(int k,int goal) {//把第k位的数转到goal下边
int x=root;
while(k<=sz[ch[x][0]]||k>sz[ch[x][0]]+num[x]) {
if(k<=sz[ch[x][0]]) x=ch[x][0];
else {
k-=(sz[ch[x][0]]+num[x]);
x=ch[x][1];
}
}
Splay(x,goal);
}
inline void del(int x) {
leave+=sz[x];
ext-=sz[x];
int fa=pre[x];
ch[fa][ch[fa][1]==x]=0;
pre[x]=0;
push_up(root);
}
inline void push_up(int x) {
sz[x]=num[x]+sz[ch[x][0]]+sz[ch[x][1]];
}
inline void init() {
ch[0][0]=ch[0][1]=pre[0]=sz[0]=num[0]=NOW=leave=ext=root=0;
val[0]=-0x3f3f3f3f;
}
inline void NewNode(int &x,int c,int fa) {
ext++;
x=++NOW;
ch[x][0]=ch[x][1]=0;
pre[x]=fa;
num[x]=sz[x]=1;
val[x]=c;
}
inline void insert(int k,int &p,int f) {
if(p==0) {
NewNode(p,k,f);
Splay(p,0);
return;
}
if(val[p]==k) {
num[p]++;
sz[p]++;
ext++;
Splay(p,0);
return;
}
if(val[p]<k) insert(k,ch[p][1],p);
else insert(k,ch[p][0],p);
push_up(p);
}
inline int getrank(int v) {//返回小于v里面最大的那个数的rank
int rank=0,p=root;
while(p!=0) {
if(val[p]==v) {
rank+=sz[ch[p][0]];
break;
}
if(val[p]<v) {
rank+=sz[ch[p][0]]+num[p];
p=ch[p][1];
}
else p=ch[p][0];
}
return rank;
}
inline void judge(int v) {
int rank=getrank(v)+1;
if(rank>ext) {
root=0;
leave+=ext;
ext=0;
}
else {
RotateTo(rank,0);
del(ch[root][0]);
}
}
inline void query(int k,int chg) {
RotateTo(ext+1-k,0);
printf("%d\n",val[root]+chg);
}
}spt;
int main() {
int n,low,k,tlow;
char c[10];
scanf("%d%d",&n,&low);
tlow=low;
spt.init();
while(n--) {
scanf("%s%d",c,&k);
if(c[0]=='I') {
if(k>=low) spt.insert(k+tlow-low,spt.root,0);
}
else if(c[0]=='A') tlow-=k;
else if(c[0]=='S') {
tlow+=k;
spt.judge(tlow);
}
else if(c[0]=='F') {
if(k>spt.ext) puts("-1");
else spt.query(k,low-tlow);
}
}
printf("%d\n",spt.leave);
return 0;
}

0

绿色的云 LV 10 @ 2013-08-04 15:52:47

SBT水过~
测试数据 #0: Accepted, time = 343 ms, mem = 4148 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 460 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 456 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 920 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 1344 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 1868 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 2740 KiB, score = 10
测试数据 #7: Accepted, time = 93 ms, mem = 2780 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 4180 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 5068 KiB, score = 10
Accepted, time = 1042 ms, mem = 5068 KiB, score = 100
略慢啊555
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXA 101

int suff[MAXA];
int n,minc;

struct node {
node *left_child,*right_child;
int r,s,key;
};

node *bank,*roof;
int z=0;
int ans=0;

int left_ratote(node* &t){
node *k=(*t).right_child;
(*t).right_child=(*k).left_child;
(t).s=((t).left_child).s+((*t).right_child).s+1;
(*k).left_child=t;
(*k).s=(t).s+((*k).right_child).s+1;
t=k;
return 0;
}

int right_ratote(node* &t){
node *k=(*t).left_child;
(*t).left_child=(*k).right_child;
(t).s=((t).left_child).s+((*t).right_child).s+1;
(*k).right_child=t;
(*k).s=(t).s+((*k).left_child).s+1;
t=k;
return 0;
}

int maintain(node* &t){
if ((((t).left_child).left_child).s>((*t).right_child).s){
right_ratote(t);
maintain((t).right_child);
maintain(t);
return 0;
}
if (((*(t).left_child).right_child).s>((*t).right_child).s){
left_ratote((*t).left_child);
right_ratote(t);
maintain((*t).left_child);
maintain((t).right_child);
maintain(t);
return 0;
}
if (((*(t).right_child).right_child).s>((*t).left_child).s){
left_ratote(t);
maintain((t).left_child);
maintain(t);
return 0;
}
if (((*(t).right_child).left_child).s>((*t).left_child).s){
right_ratote((*t).right_child);
left_ratote(t);
maintain((*t).left_child);
maintain((*t).right_child);
maintain(t);
return 0;
}
return 0;
}

int INSERT(int x,node* &t){
if (t==bank){
t=new(node);
(*t).s=1;
(*t).key=x;
(*t).r=z;
(*t).left_child=(*t).right_child=bank;
return 0;
}
(*t).s++;
if (x<((*t).key+suff[z]-suff[(*t).r])){
INSERT(x,(*t).left_child);
} else INSERT(x,(*t).right_child);
maintain(t);
return 0;
}

int DELETE(node* &t){
if (t==bank){
return 0;
}
if ((*t).key+suff[z]-suff[(t).r]<minc){
ans+=(((*t).left_child).s+1);
t=(*t).right_child;
DELETE(t);
} else DELETE((*t).left_child);
if (t!=bank){
(t).s=((t).left_child).s+((*t).right_child).s+1;
maintain(t);
}
return 0;
}

int getrank(int x,node t){
if (x-1==((*t).right_child).s){
return (*t).key+suff[z]-suff[(t).r];
}
if (x-1<((*t).right_child).s){
return getrank(x,(t).right_child);
}
return getrank(x-((*t).right_child).s-1,(*t).left_child);
}

int main(){
bank=new(node);
(*bank).s=0;
roof=(*bank).left_child=(*bank).right_child=bank;
scanf("%d%d",&n,&minc);
suff[z]=0;
while (n--){
char c[1];
int k;
scanf("%s%d",&c,&k);
switch (c[0]){
case 'I':
if (k<minc){
break;
}
INSERT(k,roof);
break;
case 'A':
z++;
suff[z]=suff[z-1]+k;
break;
case 'S':
z++;
suff[z]=suff[z-1]-k;
DELETE(roof);
break;
case 'F':
if (k>(*roof).s){
printf("-1\n");
break;
}
printf("%d\n",getrank(k,roof));
break;
}
}
printf("%d\n",ans);
return 0;
}

0

jackchen LV 8 @ 2013-04-20 18:44:17

一道splay的水题

题解

71 条题解

Block Code

郁闷的出纳员

信息

状态

开发

支持

题解

71 条题解

Block Code

郁闷的出纳员

信息

状态

开发

支持

还没有账户？

登录