标签: Splay

[NOI2004]郁闷的出纳员 题解

[NOI2004]郁闷的出纳员 题解

题目地址:洛谷:【P1486】[NOI2004]郁闷的出纳员 – 洛谷、BZOJ:Problem 1503. — [NOI2004]郁闷的出纳员

题目描述

OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。
好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?
如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

题意简述

维护一个集合,四种操作:

  1. 插入一个数
  2. 集合全体加一个数
  3. 集合全体减一个数
  4. 查第$k$大数(即从大到小第$k$个)

如果全体减数以后某些元素小于了阈值,从集合中删去它们,并记录下整个过程中总共删了多少数,在最后输出。

输入输出格式

输入格式:
第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。
接下来的n行,每行表示一条命令。命令可以是以下四种之一:
名称 格式 作用
I命令 I_k 新建一个工资档案,初始工资为k。如果某员工的初始工资低于工资下界,他将立刻离开公司。
A命令 A_k 把每位员工的工资加上k
S命令 S_k 把每位员工的工资扣除k
F命令 F_k 查询第k多的工资
_(下划线)表示一个空格,I命令、A命令、S命令中的k是一个非负整数,F命令中的k是一个正整数。
在初始时,可以认为公司里一个员工也没有。

输出格式:
输出文件的行数为F命令的条数加一。
对于每条F命令,你的程序要输出一行,仅包含一个整数,为当前工资第k多的员工所拿的工资数,如果k大于目前员工的数目,则输出-1。
输出文件的最后一行包含一个整数,为离开公司的员工的总数。

输入输出样例

输入样例#1:

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

输出样例#1:

10
20
-1
2

说明

I命令的条数不超过100000
A命令和S命令的总条数不超过100
F命令的条数不超过100000
每次工资调整的调整量不超过1000
新员工的工资不超过100000

题解

显然可以用平衡树来维护,这里写的是Splay。
插入很常规。考虑在外面维护一个标记来记录集合内的总体变化值$delta$,然后在插入删除的时候用它来处理。减数删除的时候可以先向集合中插入一个$k-delta-1$,把这个节点转到根,然后把它和左子树都删掉,往删点数里加上这一堆数的个数-1即可。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline char readsingle() {
    char c;
    while(!isalpha(c = fgc())) {}
    return c;
}

const int MAXN = 500005;

struct Node {
    int ch[2], fa, siz, cnt, val;
} tr[MAXN];
int rt, tot, sta[MAXN], stop;

inline int newnode() {
    int p;
    if(stop) {
        p = sta[--stop];
    } else {
        p = ++tot;
    }
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int p) {
    sta[stop++] = p;
}

inline void update(int p) {
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].cnt;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
    if(!tr[p].fa) rt = p;
}

inline void splay(int p, int tar) {
    for(int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
        if(tr[fa].fa != tar) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline int queryk(int k) {
    int p = rt;
    for(;;) {
        if(tr[tr[p].ch[1]].siz >= k) {
            p = tr[p].ch[1];
        } else if(tr[tr[p].ch[1]].siz + tr[p].cnt >= k) {
            return tr[p].val;
        } else {
            k -= tr[tr[p].ch[1]].siz + tr[p].cnt;
            p = tr[p].ch[0];
        }
    }
}

inline int insert(int v) {
    if(!rt) {
        rt = ++tot;
        tr[rt].val = v;
        tr[rt].siz = 1;
        tr[rt].cnt = 1;
        return rt;
    }
    int p = rt, fa = 0;
    while(p) {
        fa = p;
        if(tr[p].val > v) p = tr[p].ch[0];
        else if(tr[p].val == v) {
            tr[p].cnt++; splay(p, 0); return p;
        } else p = tr[p].ch[1];
    }
    p = ++tot;
    tr[p].val = v;
    tr[p].siz = 1;
    tr[p].cnt = 1;
    tr[p].fa = fa;
    if(tr[fa].val > v) tr[fa].ch[0] = p;
    else tr[fa].ch[1] = p;
    splay(p, 0);
    return p;
}

int n, mn, del, ltot;

int main() {
    n = readint(); mn = readint();
    while(n--) {
        char op = readsingle();
        int k = readint();
        if(op == 'I') {
            if(k >= mn) insert(k - del);
        } else if(op == 'A') {
            del += k;
        } else if(op == 'S') {
            del -= k;
            int p = insert(mn - 1 - del);
            tr[tr[p].ch[1]].fa = 0; rt = tr[p].ch[1];
            ltot += tr[tr[p].ch[0]].siz + tr[p].cnt - 1;
        } else {
            if(k > tr[rt].siz) puts("-1");
            else printf("%d\n", queryk(k) + del);
        }
    }
    printf("%d", ltot);
    return 0;
}
[SCOI2014]方伯伯的OJ 题解

[SCOI2014]方伯伯的OJ 题解

题目地址:洛谷:【P3285】[SCOI2014]方伯伯的OJ – 洛谷、BZOJ:Problem 3595. — [Scoi2014]方伯伯的Oj

题目描述

方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。
方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

1.操作格式为1 x y,意味着将编号为x的用户编号改为y,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时,1是一个当前不在排名中的编号。
2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为x用户的排名。
3.操作格式为3 x,意味着将编号为x的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为x用户的排名。
4.操作格式为4 k,意味着查询当前排名为k的用户编号,执行完该操作后需要输出当前操作用户的编号。

但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:

  • 1 x+a y+a
  • 2 x+a
  • 3 x+a
  • 4 k+a

其中a为上一次操作得到的输出,一开始a=0。
例如:上一次操作得到的输出是5这一次操作的输入为:1 13 15因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10现在你截获了方伯伯的所有操作,希望你能给出结果。

输入输出格式

输入格式:
输入的第1行包含2个用空格分隔的整数n和m,表示初始用户数和操作数。此后有m行,每行是一个询问,询问格式如上所示。

输出格式:
输出包含m行。每行包含一个整数,其中第i行的整数表示第i个操作的输出。

输入输出样例

输入样例#1:

10 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

输出样例#1:

2
2
2
4
3
5
5
7
8
11

说明

对于 100% 的数据,1 <= n <= 10^8,1 <= m <= 10^5
输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 <= y <= 2 * 10^8,并且y 没有出现在队列中。
对于所有操作 4,保证 1 <= k <= n。

题解

处理编号与splay节点编号之间的对应关系,我们可以考虑使用map。
第一位和最后一位的处理方法类似[ZJOI2006]书架 题解 | KSkun’s Blog
改编号的操作,只需要把原来的编号从map中删去再加入新的编号即可。
但是这个n的数据范围有点吓人呀,我们考虑用一个节点表示一段连续区间,等到用到这个区间中某个值的时候再把它割成[l, i-1]、[i, i]、[i+1, r]三段,这样的话每次操作前要先割区间,然后继续。map存的也不再是编号-splay节点的关系了,而是区间左端点-splay节点,这样我们每次找到小于等于要处理编号的节点即可。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <map>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005, INF = 1e9;

std::map<int, int> spn;

struct Node {
    int fa, ch[2], l, r, siz;
} tr[MAXN];
int rt, tot;

inline void update(int p) {
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].r - tr[p].l + 1;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[fa].fa = p; tr[p].ch[!t] = fa;
    update(fa);
    if(!tr[p].fa) rt = p;
}

inline void splay(int p, int tar) {
    for(int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
        if(tr[fa].fa != tar) rotate(isleft(p) == isleft(fa) ? fa : p);
    }
    update(p);
}

inline int queryn(int p, int rk) {
    if(rk <= tr[tr[p].ch[0]].siz) {
        return queryn(tr[p].ch[0], rk);
    }
    rk -= tr[tr[p].ch[0]].siz;
    if(rk <= tr[p].r - tr[p].l + 1) {
        splay(p, 0);
        return tr[p].l + rk - 1;
    }
    rk -= tr[p].r - tr[p].l + 1;
    return queryn(tr[p].ch[1], rk);
}

inline int querypre() {
    int p = tr[rt].ch[0];
    while(tr[p].ch[1]) p = tr[p].ch[1];
    return p;
}

inline int querynxt() {
    int p = tr[rt].ch[1];
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int p, int id) {
    if(tr[p].l < id) {
        int q = ++tot;
        tr[q].ch[0] = tr[p].ch[0];
        tr[tr[q].ch[0]].fa = q;
        tr[p].ch[0] = q;
        tr[q].l = tr[p].l; tr[q].r = id - 1;
        tr[q].fa = p;
        update(q);
        spn[tr[q].l] = q;
    }
    if(tr[p].r > id) {
        int q = ++tot;
        tr[q].ch[1] = tr[p].ch[1];
        tr[tr[q].ch[1]].fa = q;
        tr[p].ch[1] = q;
        tr[q].l = id + 1; tr[q].r = tr[p].r;
        tr[q].fa = p;
        update(q);
        spn[tr[q].l] = q;
    }
    tr[p].l = tr[p].r = id;
    update(p);
    spn[id] = p;
}

inline int top(int p) {
    splay(p, 0);
    int res = tr[tr[p].ch[0]].siz + 1;
    if(!tr[p].ch[0]) return res;
    if(!tr[p].ch[1]) {
        std::swap(tr[p].ch[0], tr[p].ch[1]);
        return res;
    }
    int q = querynxt();
    split(q, tr[q].l);
    splay(q, p);
    tr[q].ch[0] = tr[p].ch[0];
    tr[tr[q].ch[0]].fa = q;
    tr[p].ch[0] = 0;
    update(p); update(q);
    return res;
}

inline int bottom(int p) {
    splay(p, 0);
    int res = tr[tr[p].ch[0]].siz + 1;
    if(!tr[p].ch[1]) return res;
    if(!tr[p].ch[0]) {
        std::swap(tr[p].ch[0], tr[p].ch[1]);
        return res;
    }
    int q = querypre();
    split(q, tr[q].r);
    splay(q, p);
    tr[q].ch[1] = tr[p].ch[1];
    tr[tr[q].ch[1]].fa = q;
    tr[p].ch[1] = 0;
    update(p); update(q);
    return res;
}

int n, m, op, x, y, ans;

int main() {
    n = readint(); m = readint();
    tot = 1;
    tr[1].l = 1; tr[1].r = n; update(1); spn[1] = 1; rt = 1;
    while(m--) {
        op = readint(); x = readint() - ans; if(op == 1) y = readint() - ans;
        int p;
        if(op != 4) {
            std::map<int, int>::iterator it = --spn.upper_bound(x);
            p = it->second;
            split(p, x);
        }
        if(op == 1) {
            splay(p, 0);
            ans = tr[tr[p].ch[0]].siz + 1;
            spn.erase(tr[p].l);
            tr[p].l = tr[p].r = y; spn[y] = p;
        } else if(op == 2) {
            ans = top(p);
        } else if(op == 3) {
            ans = bottom(p);
        } else {
            ans = queryn(rt, x);
        }
        printf("%d\n", ans);
    }
    return 0;
}
[SPOJ-QTREE7]Query on a tree VII 题解

[SPOJ-QTREE7]Query on a tree VII 题解

题目地址:洛谷:【SP16580】QTREE7 – Query on a tree VII – 洛谷、SPOJ:SPOJ.com – Problem QTREE7

题目描述

You are given a tree (an acyclic undirected connected graph) with n nodes. The tree nodes are numbered from 1 to n. Each node has a color, white or black, and a weight. We will ask you to perfrom some instructions of the following form:

  • 0 u: ask for the maximum weight among the nodes which are connected to u, two nodes are connected if all the node on the path from u to v (inclusive u and v) have a same color.
  • 1 u: toggle the color of u(that is, from black to white, or from white to black).
  • 2 u w: change the weight of u to w.

给一个带点权的树,点有黑白两种颜色。操作:1.询问到u路径上颜色都一样的点中点权的最大值2.改变颜色3.改变点权

输入输出格式

输入格式:
The first line contains a number n denoted how many nodes in the tree(1 ≤ n ≤ 10^5). The next n-1 lines, each line has two numbers (u, v) describe a edge of the tree(1 ≤ u, v ≤ n). The next 2 lines, each line contains n number, the first line is the initial color of each node(0 or 1), and the second line is the initial weight, let’s say Wi, of each node(|Wi| ≤ 10^9). The next line contains a number m denoted how many operations we are going to process(1 ≤ m ≤ 105). The next m lines, each line describe a operation (t, u) as we mentioned above(0 ≤ t ≤ 2, 1 ≤ u ≤ n, |w| ≤ 10^9).

输出格式:
For each query operation, output the corresponding result.

输入输出样例

输入样例#1:

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
0 1
1 1
0 1

输出样例#1:

1
5

输入样例#2:

7
1 2
1 3
2 4
2 5
3 6
3 7
0 0 0 0 0 0 0
1 2 3 4 5 6 7
4
0 1
1 1
0 2
0 3

输出样例#2:

7
5
7

题解

参考资料:【Qtree】Query on a tree系列LCT解法 – CSDN博客
可以从QTREE6的代码改过来。QTREE6见:[SPOJ-QTREE6]Query on a tree VI 题解 | KSkun’s Blog
实际上和QTREE6的区别就在于要维护的值变成了若干最大值。那么我们考虑Splay子树直接算,轻边子树用一个set维护,这样方便在access的时候增删元素。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <set>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], ecnt, fa[MAXN], col[MAXN];

inline void addedge(int u, int v, int w) {
    gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}

struct LCT {
    struct LCTNode {
        int ch[2], fa, val, mx;
        std::multiset<int> s;
        bool rev;
    } lct[MAXN];

    inline bool isleft(int p) {
        return lct[lct[p].fa].ch[0] == p;
    }

    inline bool isroot(int p) {
        register int fa = lct[p].fa;
        return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
    }

    inline void update(int p) {
        register int ls = lct[p].ch[0], rs = lct[p].ch[1];
        lct[p].mx = lct[p].val;
        if(!lct[p].s.empty()) lct[p].mx = std::max(lct[p].mx, *--lct[p].s.end());
        if(ls) lct[p].mx = std::max(lct[p].mx, lct[ls].mx);
        if(rs) lct[p].mx = std::max(lct[p].mx, lct[rs].mx);
    }

    inline void reverse(int p) {
        std::swap(lct[p].ch[0], lct[p].ch[1]);
        lct[p].rev ^= 1;
    }

    inline void pushdown(int p) {
        register int ls = lct[p].ch[0], rs = lct[p].ch[1];
        if(lct[p].rev) {
            if(ls) reverse(ls);
            if(rs) reverse(rs);
            lct[p].rev ^= 1;
        }
    }

    int sta[MAXN], stop;

    inline void pushto(int p) {
        stop = 0;
        while(!isroot(p)) {
            sta[stop++] = p;
            p = lct[p].fa;
        }
        pushdown(p);
        while(stop) {
            pushdown(sta[--stop]);
        }
    }

    inline void rotate(int p) {
        register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
        lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
        lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
        lct[p].ch[!t] = fa; lct[fa].fa = p;
        update(fa);
    }

    inline void splay(int p) {
        pushto(p);
        for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
            if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
        }
        update(p);
    }

    inline void access(int p) {
        for(register int q = 0; p; q = p, p = lct[p].fa) {
            splay(p);
            if(lct[p].ch[1]) lct[p].s.insert(lct[lct[p].ch[1]].mx);
            if(q) lct[p].s.erase(lct[p].s.find(lct[q].mx));
            lct[p].ch[1] = q;
            update(p);
        }
    }

    inline void makert(int p) {
        access(p);
        splay(p);
        reverse(p);
    }

    inline int findrt(int p) {
        access(p);
        splay(p);
        while(lct[p].ch[0]) p = lct[p].ch[0];
        return p;
    }

    inline void link(int u) {
        access(fa[u]);
        splay(fa[u]);
        splay(u);
        lct[fa[u]].ch[1] = u;
        lct[u].fa = fa[u];
        update(fa[u]);
    }

    inline void cut(int u) {
        access(u);
        splay(u);
        lct[u].ch[0] = lct[lct[u].ch[0]].fa = 0;
        update(u);
    }

    inline void modify(int u, int w) {
        access(u);
        splay(u);
        lct[u].val = w;
        update(u);
    }

    inline int query(int u) {
        int c = col[u];
        u = findrt(u);
        splay(u);
        return col[u] == c ? lct[u].mx : lct[lct[u].ch[1]].mx;
    }
} L[2];

inline void dfs(int u, int f) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(v == f) continue;
        fa[v] = L[col[v]].lct[v].fa = u;
        dfs(v, u);
        L[col[v]].lct[u].s.insert(L[col[v]].lct[v].mx);
    }
    L[0].update(u); L[1].update(u);
}

int n, q, ut, vt, op;

int main() {
    memset(head, -1, sizeof(head));
    n = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt, 1);
        addedge(vt, ut, 1);
    }
    for(int i = 1; i <= n; i++) {
        col[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        L[0].lct[i].val = L[1].lct[i].val = readint();
    }
    dfs(1, 0);
    q = readint();
    while(q--) {
        op = readint(); ut = readint();
        if(op == 0) {
            printf("%d\n", L[col[ut]].query(ut));
        } else if(op == 1) {
            if(fa[ut]) {
                L[col[ut]].cut(ut);
                L[col[ut] ^ 1].link(ut);
            }
            col[ut] ^= 1;
        } else {
            vt = readint();
            L[0].modify(ut, vt);
            L[1].modify(ut, vt);
        }
    }
    return 0;
}