71 条题解

  • 2
    @ 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
    @ 2019-10-05 20:19:13

    替罪羊树!!!

  • 0
    @ 2018-08-20 23:33:22

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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;
    }

  • 0
    @ 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;
    }

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

      ...666

    • @ 2016-03-23 13:19:51

      手动高清重置害怕⊙△⊙

  • 0
    @ 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
    @ 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
    @ 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
    @ 2015-10-15 22:36:23

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

  • 0
    @ 2015-08-16 11:26:42

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

  • 0
    @ 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
    @ 2014-03-16 21:13:25
    1. 这题不知怎么弄得,我splay的写法,在用例2和用例3上T了一天,差点放弃了。
    2. 评测结果
    3. 编译成功
    4. 测试数据 #0: Accepted, time = 171 ms, mem = 3052 KiB, score = 10
    5. 测试数据 #1: Accepted, time = 0 ms, mem = 2784 KiB, score = 10
    6. 测试数据 #2: Accepted, time = 0 ms, mem = 2776 KiB, score = 10
    7. 测试数据 #3: Accepted, time = 0 ms, mem = 2780 KiB, score = 10
    8. 测试数据 #4: Accepted, time = 31 ms, mem = 2916 KiB, score = 10
    9. 测试数据 #5: Accepted, time = 39 ms, mem = 2784 KiB, score = 10
    10. 测试数据 #6: Accepted, time = 46 ms, mem = 2972 KiB, score = 10
    11. 测试数据 #7: Accepted, time = 78 ms, mem = 2784 KiB, score = 10
    12. 测试数据 #8: Accepted, time = 156 ms, mem = 2784 KiB, score = 10
    13. 测试数据 #9: Accepted, time = 218 ms, mem = 4132 KiB, score = 10
    14. Accepted, time = 739 ms, mem = 4132 KiB, score = 100
    15. #include<cstdio>
    16. #include<algorithm>
    17. using namespace std;
    18. const int maxn=100005;
    19. class SplayTree {
    20. private:
    21. int sz[maxn],ch[maxn][2],pre[maxn],val[maxn],num[maxn],NOW;
    22. public:
    23. int leave,root,ext;
    24. inline void Rotate(int x,int f) {
    25. int y=pre[x];
    26. ch[y][!f]=ch[x][f];
    27. pre[ch[x][f]]=y;
    28. pre[x]=pre[y];
    29. if(pre[x]) ch[pre[y]][ch[pre[y]][1]==y]=x;
    30. ch[x][f]=y;
    31. pre[y]=x;
    32. push_up(y);
    33. }
    34. inline void Splay(int x,int goal) {
    35. while(pre[x]!=goal) {
    36. if(pre[pre[x]]==goal) {
    37. Rotate(x,ch[pre[x]][0]==x);
    38. }
    39. else {
    40. int y=pre[x],z=pre[y];
    41. int f=(ch[z][0]==y);
    42. if(ch[y][f]==x) {
    43. Rotate(x,!f),Rotate(x,f);
    44. }
    45. else {
    46. Rotate(y,f),Rotate(x,f);
    47. }
    48. }
    49. }
    50. push_up(x);
    51. if(goal==0) root=x;
    52. }
    53. inline void RotateTo(int k,int goal) {//把第k位的数转到goal下边
    54. int x=root;
    55. while(k<=sz[ch[x][0]]||k>sz[ch[x][0]]+num[x]) {
    56. if(k<=sz[ch[x][0]]) x=ch[x][0];
    57. else {
    58. k-=(sz[ch[x][0]]+num[x]);
    59. x=ch[x][1];
    60. }
    61. }
    62. Splay(x,goal);
    63. }
    64. inline void del(int x) {
    65. leave+=sz[x];
    66. ext-=sz[x];
    67. int fa=pre[x];
    68. ch[fa][ch[fa][1]==x]=0;
    69. pre[x]=0;
    70. push_up(root);
    71. }
    72. inline void push_up(int x) {
    73. sz[x]=num[x]+sz[ch[x][0]]+sz[ch[x][1]];
    74. }
    75. inline void init() {
    76. ch[0][0]=ch[0][1]=pre[0]=sz[0]=num[0]=NOW=leave=ext=root=0;
    77. val[0]=-0x3f3f3f3f;
    78. }
    79. inline void NewNode(int &x,int c,int fa) {
    80. ext++;
    81. x=++NOW;
    82. ch[x][0]=ch[x][1]=0;
    83. pre[x]=fa;
    84. num[x]=sz[x]=1;
    85. val[x]=c;
    86. }
    87. inline void insert(int k,int &p,int f) {
    88. if(p==0) {
    89. NewNode(p,k,f);
    90. Splay(p,0);
    91. return;
    92. }
    93. if(val[p]==k) {
    94. num[p]++;
    95. sz[p]++;
    96. ext++;
    97. Splay(p,0);
    98. return;
    99. }
    100. if(val[p]<k) insert(k,ch[p][1],p);
    101. else insert(k,ch[p][0],p);
    102. push_up(p);
    103. }
    104. inline int getrank(int v) {//返回小于v里面最大的那个数的rank
    105. int rank=0,p=root;
    106. while(p!=0) {
    107. if(val[p]==v) {
    108. rank+=sz[ch[p][0]];
    109. break;
    110. }
    111. if(val[p]<v) {
    112. rank+=sz[ch[p][0]]+num[p];
    113. p=ch[p][1];
    114. }
    115. else p=ch[p][0];
    116. }
    117. return rank;
    118. }
    119. inline void judge(int v) {
    120. int rank=getrank(v)+1;
    121. if(rank>ext) {
    122. root=0;
    123. leave+=ext;
    124. ext=0;
    125. }
    126. else {
    127. RotateTo(rank,0);
    128. del(ch[root][0]);
    129. }
    130. }
    131. inline void query(int k,int chg) {
    132. RotateTo(ext+1-k,0);
    133. printf("%d\n",val[root]+chg);
    134. }
    135. }spt;

    136. int main() {
    137. int n,low,k,tlow;
    138. char c[10];
    139. scanf("%d%d",&n,&low);
    140. tlow=low;
    141. spt.init();
    142. while(n--) {
    143. scanf("%s%d",c,&k);
    144. if(c[0]=='I') {
    145. if(k>=low) spt.insert(k+tlow-low,spt.root,0);
    146. }
    147. else if(c[0]=='A') tlow-=k;
    148. else if(c[0]=='S') {
    149. tlow+=k;
    150. spt.judge(tlow);
    151. }
    152. else if(c[0]=='F') {
    153. if(k>spt.ext) puts("-1");
    154. else spt.query(k,low-tlow);
    155. }
    156. }
    157. printf("%d\n",spt.leave);
    158. return 0;
    159. }

  • 0
    @ 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
    @ 2013-04-20 18:44:17

    一道splay的水题

信息

ID
1507
难度
7
分类
数据结构 | 平衡树 点击显示
标签
递交数
2541
已通过
409
通过率
16%
被复制
4
上传者