头像

Clever_Jimmy




离线:5个月前


新鲜事 原文

Clever_Jimmy
7个月前
lyndon


活动打卡代码 AcWing 158. 项链

Clever_Jimmy
7个月前
#include <bits/stdc++.h>
#define LL long long

std::string A, B;
int n;

int solve(std::string S) {
    int i = 1, j = 2, k, ans;
    while(i <= n && j <= n) {
        for(k = 0; k < n && S[i + k] == S[j + k]; ++k);
        if(k == n)
            break;
        if(S[i + k] > S[j + k]) {
            i += k + 1;
            if(i == j)
                ++i;
        }
        else {
            j += k + 1;
            if(i == j)
                ++j;
        }
    }
    ans = std::min(i, j);
    return ans;
}

int32_t main() {
    std::cin >> A; n = A.size(); A = " " + A + A;
    std::cin >> B; B = " " + B + B;

    int pos1 = solve(A);
    int pos2 = solve(B);

    // std::cout << pos1 << ' ' << pos2 << std::endl;

    for(int i = pos1, j = pos2, len = 1; len <= n; ++i, ++j, ++len) {
        if(A[i] != B[j]) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i = pos1, len = 1; len <= n; ++i, ++len)
        std::cout << A[i];


    return 0;
}



Clever_Jimmy
2020-01-25 14:48

题目描述

给定一个序列 $A$,要求支持以下操作:

  1. $\text{ADD}(l, r, val)$

    将 $A[l \cdots r]$ 全部加上一个数 $val$;

  2. $\text{REVERSE}(l, r)$

    将 $A[l \cdots r]$ 逆序排布;

  3. $\text{REVOLVE}(l, r, T)$

    将 $A[l, r - T]$ 移至 $A[r - T + 1, r]$ 后面;

  4. $\text{INSERT}(x, val)$

    在 $A_x$ 后面插入 $val$;

  5. $\text{DELETE}(x)$

    删除 $A_x$ 这个元素;

  6. $\text{MIN}(l, r)$

    求 $\min\limits_{j = l}^rA_j$。

样例输入

7
9 8 7 1 1 1 9 
9
ADD 1 6 10
ADD 2 7 7
REVERSE 1 7
MIN 1 3
REVOLVE 1 6 5
DELETE 7
MIN 1 5
MIN 2 5
MIN 1 4

样例输出

16
18
18
18

思路

这一题,看到了序列翻转的操作,自然地可以想到用 $\text{Splay}$ 来解决。

定义1:一棵树根节点的右节点的左结点为这棵树的 重要点

定义2:一棵树通过最右下方的点为这棵树的 极值点

  1. $\text{ADD}(l, r, val)$ 操作

    我们先将 $[l, r]$ 这个区间 $\text{split}$ 出来,然后在这个区间上打上标记即可。

    注意标记的意义:这个点的权值已经被修改过,但是它的子树没有被修改。

  2. $\text{REVERSE}(l, r)$ 操作

    同 (1) 一样先将 $[l, r]$ 这个区间 $\text{split}$ 出来,然后在这个区间上打上标记。

  3. $\text{REVOLVE}(l, r, T)$ 操作

    容易想到的是,轮换 $r - l + 1$ 次是没有意义的。于是我们先将 $T$ 对 $r - l + 1$ 取模,再进行操作。

    1. 先将 $[l, r - T]$ 这个区间 $\text{split}$ 出来(得到 $f_1$)

      我们把它从 $\text{splay}$ 中删去。

      注意到此时我们应该将这个区间从 $root$ 的左儿子中取出。

    2. 再将 $[r - T + 1, r]$ 这个区间 $\text{split}$ 出来(得到 $f_3$)

      • 若 $f_3$ 为空,记 $f_4$ 为根节点的右儿子的右儿子。

        显然我们应如 $root-f_1-f_4$ 连接这三个点。

        我们先考虑将 $f_1$ 连接到 $root$ 上。

        然后记这棵树的极值点为 $f_5$,我们将 $f_5$ 伸展至根的右孩子。

        可以证明,此时 $f_5$ 无右孩子,于是我们可以将 $f_4$ 连接到 $f_5$ 上。

      • 若 $f_3$ 不为空,那么我们找到这棵树的极值点,将它伸展至重要点。

        可以证明,此时 $f_3$ 无右孩子,于是我们可以将 $f_1$ 连接到 $f_3$ 上。

    值得注意的是,这个操作带来的标记的上传以及下放是十分麻烦的。

  4. $\text{INSERT}(x, val)$ 操作

    我们将 $[x, x]$ 这个区间 $\text{split}$ 出来,设这个点为 $p$。

    将 $val$ 作为右孩子连接到 $p$ 上即可。

  5. $\text{DELETE}(x)$ 操作

    这个操作比较简单,直接将 $[x, x]$ 这个区间 $\text{split}$ 出来,并将其父亲的左孩子置为空即可。

  6. $\text{MIN}(l, r)$ 操作

    我们将 $[l, r]$ 这个区间 $\text{split}$ 出来,设这个点为 $p$。

    输出 $p$ 的子树中的最小值即可。

代码实现

#include <bits/stdc++.h>
#define LL long long
#define rgi register int
#define rgl register long long
#define il inline

const LL oo = 0x3f3f3f3f3f3f3f3fLL;
const int N = 2e6 + 10;

int n, m;
LL a[N];

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

struct SPLAYNODE {
    int fa, ch[2], siz, rev;
    LL val, min_val, add;
};

struct SPLAY {
    static const int MAXSIZE = N;
    int root, cntNode; SPLAYNODE t[MAXSIZE];

    int son(int p) { return p == t[t[p].fa].ch[1]; }
    int make(int f, int v) {
        t[++cntNode].fa = f;
        t[cntNode].val = t[cntNode].min_val = v;
        t[cntNode].siz = 1, t[cntNode].rev = t[cntNode].add = 0;
        return cntNode;
    }
    void connect(int p, int f, int o) {  t[p].fa = f, t[f].ch[o] = p; }
    void pushup(int p) {
        t[p].min_val = t[p].val;
        if(t[p].ch[0]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[0]].min_val);
        if(t[p].ch[1]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[1]].min_val);
        t[p].siz = t[t[p].ch[0]].siz + t[t[p].ch[1]].siz + 1;
    }
    void pushdown(int p) {
        if(t[p].rev) {
            std::swap(t[p].ch[0], t[p].ch[1]);
            t[t[p].ch[0]].rev ^= 1;
            t[t[p].ch[1]].rev ^= 1;
            t[p].rev = 0;
        }
        if(t[p].add) {
            SPLAYNODE &L = t[t[p].ch[0]], &R = t[t[p].ch[1]]; LL v = t[p].add;
            if(t[p].ch[0]) L.add += v, L.val += v, L.min_val += v;
            if(t[p].ch[1]) R.add += v, R.val += v, R.min_val += v;
            t[p].add = 0;
        }
    }

    void rotate(int p) {
        int f = t[p].fa, g = t[f].fa;
        int o1 = son(p), o2 = son(f);
        connect(t[p].ch[o1 ^ 1], f, o1);
        connect(f, p, o1 ^ 1);
        connect(p, g, o2);
        pushup(f), pushup(p);
    }
    void splay(int p, int tmp) {
        int tar = t[tmp].fa;
        while(t[p].fa != tar) {
            int f = t[p].fa, g = t[f].fa;
            if(g != tar) son(p) ^ son(f) ? rotate(p) : rotate(f);
            rotate(p);
        }
        if(tmp == root) root = p;
    }

    void build(int &p, int f, int l, int r) {
        if(l > r) return;
        p = ++cntNode;
        int mid = l + r >> 1;
        t[p].fa = f, t[p].val = t[p].min_val = a[mid], t[p].rev = t[p].add = 0;
        build(t[p].ch[0], p, l, mid - 1);
        build(t[p].ch[1], p, mid + 1, r);
        pushup(p);
    }
    int kth(int rk) {
        int p = root;
        while(1) {
            pushdown(p);
            if(t[t[p].ch[0]].siz >= rk) p = t[p].ch[0];
            else {
                rk -= t[t[p].ch[0]].siz + 1;
                if(!rk) return p;
                p = t[p].ch[1];
            }
        }
    }
    int split(int l, int r, int dir) { // dir = 1 ->make it to the right
        int nxt[2] = { kth(l), kth(r + 2) };
        splay(nxt[dir ^ 1], root);
        splay(nxt[dir], t[root].ch[dir]);
        return t[t[root].ch[dir]].ch[dir ^ 1];
    }
    void revolve(int l, int r, int d) {
        if(!d) return;
        int f1 = split(l, r - d, 0);
        int f2 = t[root].ch[0];
        pushdown(root), pushdown(f2);
        t[f2].ch[1] = 0;
        pushup(f2), pushup(root);
        int f3 = split(r - d + 1 - t[f1].siz, r - t[f1].siz, 1);
        if(!f3) {
            int f4 = t[t[root].ch[1]].ch[1];
            connect(f1, t[root].ch[1], 1);
            pushup(t[root].ch[1]), pushup(root);
            int f5 = root; pushdown(root);
            while(t[f5].ch[1]) f5 = t[f5].ch[1], pushdown(f5);
            splay(f5, t[root].ch[1]);
            pushdown(root), pushdown(f5);
            connect(f4, f5, 1);
            pushup(t[root].ch[1]), pushup(root);
        }
        else {
            pushdown(f3);
            while(t[f3].ch[1]) f3 = t[f3].ch[1], pushdown(f3);
            splay(f3, t[t[root].ch[1]].ch[0]);
            connect(f1, t[t[root].ch[1]].ch[0], 1);
            pushup(t[t[root].ch[1]].ch[0]), pushup(t[root].ch[1]), pushup(root);
        }
    }
} T;

int main() {
    n = read();
    for(rgi i = 1; i <= n; ++i) a[i + 1] = read();
    T.t[0].min_val = a[0] = a[n + 2] = oo;
    T.build(T.root, 0, 1, n + 2);
    m = read();
    for(rgi i = 1; i <= m; ++i) {
        std::string opt; std::cin >> opt;
        if(opt == "ADD") {
            int l = read(), r = read(), v = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].add += v;
            T.t[p].val += v;
            T.t[p].min_val += v;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "REVERSE") {
            int l = read(), r = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].rev ^= 1;
        }
        if(opt == "REVOLVE") {
            int l = read(), r = read(), d = read();
            d %= r - l + 1;
            T.revolve(l, r, d);
        }
        if(opt == "INSERT") {
            int x = read(), v = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.pushdown(p);
            T.t[p].ch[1] = T.make(p, v);
            T.pushup(p), T.pushup(f), T.pushup(g);
        }
        if(opt == "DELETE") {
            int x = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[f].ch[0] = 0;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "MIN") {
            int l = read(), r = read();
            int p = T.split(l, r, 1);
            printf("%lld\n", T.t[p].min_val);
        }
    }
    return 0;
}

有任何疑问请在评论区留言,也可 QQ 私聊。

QQ : 506503360



活动打卡代码 AcWing 266. 超级备忘录

Clever_Jimmy
2020-01-25 14:11
#include <bits/stdc++.h>
#define LL long long
#define rgi register int
#define rgl register long long
#define il inline

const LL oo = 0x3f3f3f3f3f3f3f3fLL;
const int N = 2e6 + 10;

#define JUDGE 0
#define DEBUG 0

int n, m;
LL a[N];

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

struct SPLAYNODE {
    int fa, ch[2], siz, rev;
    LL val, min_val, add;
};

struct SPLAY {
    static const int MAXSIZE = N;
    int root, cntNode; SPLAYNODE t[MAXSIZE];

    int son(int p) { return p == t[t[p].fa].ch[1]; }
    int make(int f, int v) {
        t[++cntNode].fa = f;
        t[cntNode].val = t[cntNode].min_val = v;
        t[cntNode].siz = 1, t[cntNode].rev = t[cntNode].add = 0;
        return cntNode;
    }
    void connect(int p, int f, int o) {  t[p].fa = f, t[f].ch[o] = p; }
    void pushup(int p) {
        t[p].min_val = t[p].val;
        if(t[p].ch[0]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[0]].min_val);
        if(t[p].ch[1]) t[p].min_val = std::min(t[p].min_val, t[t[p].ch[1]].min_val);
        t[p].siz = t[t[p].ch[0]].siz + t[t[p].ch[1]].siz + 1;
    }
    void pushdown(int p) {
        if(t[p].rev) {
            std::swap(t[p].ch[0], t[p].ch[1]);
            t[t[p].ch[0]].rev ^= 1;
            t[t[p].ch[1]].rev ^= 1;
            t[p].rev = 0;
        }
        if(t[p].add) {
            SPLAYNODE &L = t[t[p].ch[0]], &R = t[t[p].ch[1]]; LL v = t[p].add;
            if(t[p].ch[0]) L.add += v, L.val += v, L.min_val += v;
            if(t[p].ch[1]) R.add += v, R.val += v, R.min_val += v;
            t[p].add = 0;
        }
    }

    void rotate(int p) {
        int f = t[p].fa, g = t[f].fa;
        int o1 = son(p), o2 = son(f);
        connect(t[p].ch[o1 ^ 1], f, o1);
        connect(f, p, o1 ^ 1);
        connect(p, g, o2);
        pushup(f), pushup(p);
    }
    void splay(int p, int tmp) {
        int tar = t[tmp].fa;
        while(t[p].fa != tar) {
            int f = t[p].fa, g = t[f].fa;
            if(g != tar) son(p) ^ son(f) ? rotate(p) : rotate(f);
            rotate(p);
        }
        if(tmp == root) root = p;
    }

    void build(int &p, int f, int l, int r) {
        if(l > r) return;
        p = ++cntNode;
        int mid = l + r >> 1;
        t[p].fa = f, t[p].val = t[p].min_val = a[mid], t[p].rev = t[p].add = 0;
        build(t[p].ch[0], p, l, mid - 1);
        build(t[p].ch[1], p, mid + 1, r);
        pushup(p);
    }
    int kth(int rk) {
        int p = root;
        while(1) {
            pushdown(p);
            if(t[t[p].ch[0]].siz >= rk) p = t[p].ch[0];
            else {
                rk -= t[t[p].ch[0]].siz + 1;
                if(!rk) return p;
                p = t[p].ch[1];
            }
        }
    }
    int split(int l, int r, int dir) { // dir = 1 ->make it to the right
        int nxt[2] = { kth(l), kth(r + 2) };
        splay(nxt[dir ^ 1], root);
        splay(nxt[dir], t[root].ch[dir]);
        return t[t[root].ch[dir]].ch[dir ^ 1];
    }
    void revolve(int l, int r, int d) {
        if(!d) return;
        int f1 = split(l, r - d, 0);
        int f2 = t[root].ch[0];
        pushdown(root), pushdown(f2);
        t[f2].ch[1] = 0;
        pushup(f2), pushup(root);
        int f3 = split(r - d + 1 - t[f1].siz, r - t[f1].siz, 1);
        if(!f3) {
            int f4 = t[t[root].ch[1]].ch[1];
            connect(f1, t[root].ch[1], 1); pushup(t[root].ch[1]), pushup(root);
            int f5 = root; pushdown(root);
            while(t[f5].ch[1]) f5 = t[f5].ch[1], pushdown(f5);
            splay(f5, t[root].ch[1]);
            pushdown(root), pushdown(f5);
            connect(f4, f5, 1);
            pushup(t[root].ch[1]), pushup(root);
        }
        else {
            pushdown(f3);
            while(t[f3].ch[1]) f3 = t[f3].ch[1], pushdown(f3);
            splay(f3, t[t[root].ch[1]].ch[0]);
            connect(f1, t[t[root].ch[1]].ch[0], 1);
            pushup(t[t[root].ch[1]].ch[0]), pushup(t[root].ch[1]), pushup(root);
        }
    }
} T;

int main() {
#if JUDGE
    freopen("memory.in", "r", stdin);
    freopen("my.out", "w", stdout);
#endif
    n = read();
    for(rgi i = 1; i <= n; ++i) a[i + 1] = read();
    T.t[0].min_val = a[0] = a[n + 2] = oo;
    T.build(T.root, 0, 1, n + 2);
    m = read();
    for(rgi i = 1; i <= m; ++i) {
        std::string opt; std::cin >> opt;
        if(opt == "ADD") {
            int l = read(), r = read(), v = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].add += v;
            T.t[p].val += v;
            T.t[p].min_val += v;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "REVERSE") {
            int l = read(), r = read();
            int p = T.split(l, r, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[p].rev ^= 1;
        }
        if(opt == "REVOLVE") {
            int l = read(), r = read(), d = read();
            d %= r - l + 1;
            T.revolve(l, r, d);
        }
        if(opt == "INSERT") {
            int x = read(), v = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.pushdown(p);
            T.t[p].ch[1] = T.make(p, v);
            T.pushup(p), T.pushup(f), T.pushup(g);
        }
        if(opt == "DELETE") {
            int x = read();
            int p = T.split(x, x, 1), f = T.t[p].fa, g = T.t[f].fa;
            T.t[f].ch[0] = 0;
            T.pushup(f), T.pushup(g);
        }
        if(opt == "MIN") {
            int l = read(), r = read();
            int p = T.split(l, r, 1);
            printf("%lld\n", T.t[p].min_val);
        }
//      debug();
    }
    return 0;
}
/*
7
9 8 7 1 1 1 9 
9
ADD 1 6 10
ADD 2 7 7
REVERSE 1 7
MIN 1 3
REVOLVE 1 6 5
DELETE 7
MIN 1 5
MIN 2 5
MIN 1 4

*/


活动打卡代码 AcWing 255. 第K个数

Clever_Jimmy
2019-12-22 07:21
#include <bits/stdc++.h>
#define rgi register int

const int N = 1e5 + 10;

int n, m, cntNode, tot;
int a[N], root[N], num[N], rev[N];

struct segNode {
    int lc, rc, dat;
} t[N * 40];

void Build(int &p, int l, int r) {
    if(!p) p = ++cntNode;
    if(l == r) return;
    int mid = l + r >> 1;
    Build(t[p].lc, l, mid);
    Build(t[p].rc, mid + 1, r);
}

void Insert(int &p, int pre, int L, int R, int val) {
    p = ++cntNode;
    t[p].lc = t[pre].lc, t[p].rc = t[pre].rc, t[p].dat = t[pre].dat + 1;
    if(L == R) return;
    int mid = L + R >> 1;
    if(val <= mid) Insert(t[p].lc, t[pre].lc, L, mid, val);
    else Insert(t[p].rc, t[pre].rc, mid + 1, R, val);
}

int Query(int p, int pre, int L, int R, int val) {
    if(L == R) return L;
    int mid = L + R >> 1, delta = t[t[p].lc].dat - t[t[pre].lc].dat;
    if(val <= delta) return Query(t[p].lc, t[pre].lc, L, mid, val);
    else return Query(t[p].rc, t[pre].rc, mid + 1, R, val - delta);
}

int main() {
    scanf("%d %d", &n, &m);
    Build(root[0], 1, n);
    for(rgi i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        num[++tot] = a[i];
    } std::sort(num + 1, num + tot + 1);
    tot = std::unique(num + 1, num + tot + 1) - (num + 1);
    for(rgi i = 1; i <= n; ++i) {
        int pos = std::lower_bound(num + 1, num + tot + 1, a[i]) - (num + 1) + 1;
        rev[pos] = a[i];
        a[i] = pos; Insert(root[i], root[i - 1], 1, n, a[i]);
    }
    for(rgi i = 1; i <= m; ++i) {
        int l, r, k; scanf("%d %d %d", &l, &r, &k);
        printf("%d\n", rev[Query(root[r], root[l - 1], 1, n, k)]);
    }
    return 0;
}
/*
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

*/



Clever_Jimmy
2019-12-22 06:58
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register long long
#define il inline

#define DEBUG 0

const int oo = 0x3f3f3f3f;
const int N = 5e5 + 10;

int n, m;
ll a[N], b[N];

struct segNode {
    int lc, rc;
    ll dat;
} t[N << 2];

struct BIT {
    ll c[N];
    void add(int x, ll val) { for(; x < N; x += x & -x) c[x] += val;}
    ll query(int x) { ll res = 0; for(; x; x -= x & -x) res += c[x]; return res;}
} T;

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b);}
void Pushup(int p) { t[p].dat = gcd(t[p << 1].dat, t[p << 1 | 1].dat);}

void Build(int p, int l, int r) {
    t[p].lc = l, t[p].rc = r;
    if(l == r) {
        t[p].dat = b[l];
        return;
    }
    int mid = l + r >> 1;
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    Pushup(p);
}

void Modify(int p, int x, ll val) {
    if(t[p].lc == t[p].rc) {
        t[p].dat += val;
        return;
    }
    int mid = t[p].lc + t[p].rc >> 1;
    if(x <= mid) Modify(p << 1, x, val);
    else Modify(p << 1 | 1, x, val);
    Pushup(p);
}

ll Query(int p, int l, int r) {
    if(l <= t[p].lc && t[p].rc <= r) return t[p].dat;
    int mid = t[p].lc + t[p].rc >> 1; ll res = 0;
    if(l <= mid) res = gcd(res, Query(p << 1, l, r));
    if(mid < r) res = gcd(res, Query(p << 1 | 1, l, r));
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for(rgi i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
        b[i] = a[i] - a[i - 1];
        T.add(i, b[i]);
    }
    Build(1, 1, n + 1);
    for(rgi i = 1; i <= m; ++i) {
        char cmd[5]; scanf("%s", cmd);
        int l = read(), r = read();
        if(cmd[0] == 'C') {
            ll d; scanf("%lld", &d);
            T.add(l, d), T.add(r + 1, -d);
            Modify(1, l, d), Modify(1, r + 1, -d);
        }
        else {
#if DEBUG
            printf("Array:");
            for(rgi i = 1; i <= n; ++i) printf("%d ", T.query(i));
            puts("");
            printf("T.query(l) : %d\n", T.query(l));
            printf("Query(1, l + 1, r) : %d\n", Query(1, l + 1, r));
#endif
            printf("%lld\n", std::abs(gcd(T.query(l), Query(1, l + 1, r))));
        }
    }
    return 0;
}
/*
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4

*/



Clever_Jimmy
2019-12-21 14:19
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <cctype>
#define rgi register int
#define rgl register long long
#define il inline
#define ll long long

using namespace std;

const int oo = 0x3f3f3f3fll;
const int N = 5e5 + 10;

int n, m, a[N];

struct segNode {
    int lc, rc;
    ll sum, pre, suf, dat;
} t[N << 2];

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

void Pushup(int p) {
    t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    t[p].dat = std::max(std::max(t[p << 1].dat, t[p << 1 | 1].dat), t[p << 1].suf + t[p << 1 | 1].pre);
    t[p].pre = std::max(t[p << 1].pre, t[p << 1].sum + t[p << 1 | 1].pre);
    t[p].suf = std::max(t[p << 1 | 1].suf, t[p << 1].suf + t[p << 1 | 1].sum);
}

void Build(int p, int l, int r) {
    t[p].lc = l, t[p].rc = r;
    if(l == r) {
        t[p].dat = t[p].pre = t[p].suf = t[p].sum = a[l];
        return;
    }
    int mid = l + r >> 1;
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    Pushup(p);
}

void Modify(int p, int x, ll val) {
    if(t[p].lc == t[p].rc) {
        t[p].dat = t[p].pre = t[p].suf = t[p].sum = val;
        return;
    }
    int mid = t[p].lc + t[p].rc >> 1;
    if(x <= mid) Modify(p << 1, x, val);
    else Modify(p << 1 | 1, x, val);
    Pushup(p);
}

segNode Query(int p, int l, int r) {
    if(l <= t[p].lc && t[p].rc <= r) return t[p];
    int mid = t[p].lc + t[p].rc >> 1;
    segNode L, R, res; bool Lflag(0), Rflag(0);
    L.dat = L.pre = L.suf = L.sum = -oo;
    R.dat = R.pre = R.suf = R.sum = -oo;
    res.dat = res.pre = res.suf = res.sum = -oo;
    if(l <= mid) {Lflag = 1, L = Query(p << 1, l, r);}
    if(mid < r) {Rflag = 1, R = Query(p << 1 | 1, l, r);}
    if(Lflag && Rflag) {
        res.dat = std::max(L.suf + Rflag * R.pre, std::max(L.dat, R.dat));
        res.pre = std::max(L.pre, L.sum + R.pre);
        res.suf = std::max(R.suf, L.suf + R.sum);
        res.sum = L.sum + R.sum;
    }
    if(!Lflag && Rflag) {
        res.dat = R.dat;
        res.pre = R.pre;
        res.suf = R.suf;
        res.sum = R.sum;
    }
    if(Lflag && !Rflag) {
        res.dat = L.dat;
        res.pre = L.pre;
        res.suf = L.suf;
        res.sum = L.sum;
    }
    return res;
}

int main() {
//  freopen("test.in", "r", stdin);
//  freopen("test.out", "w", stdout);
    n = read(), m = read();
    for(rgi i = 1; i <= n; ++i) a[i] = read();
    Build(1, 1, n);
    for(rgi i = 1; i <= m; ++i) {
        int opt = read(), x = read(), y = read();
        if(opt == 1) {
            if(x > y) std::swap(x, y);
            printf("%lld\n", Query(1, x, y).dat);
        }
        else Modify(1, x, y);
    }
    return 0;
}
/*
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

*/


活动打卡代码 AcWing 265. 营业额统计

Clever_Jimmy
2019-12-21 11:36
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register long long
#define il inline

const int oo = 0x3f3f3f3f;
const double alpha = 0.86;

int n, ans;

struct Node {
    Node *l, *r;
    int val, tot, siz;
    /*
    * tot -> total num
    * siz -> valid num
    */
    bool del;
    bool bad() {
        return (l -> tot > tot * alpha) ||
               (r -> tot > tot * alpha);
    }
    void push() {
        tot = l -> tot + r -> siz + 1;
        siz = l -> siz + r -> siz + !del;
    }
    Node() {val = -oo, tot = siz = 0;}
} *root, *null, **BadTag;

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

void Dfs(Node *p, std::vector <Node *> &keys);
Node *Build(std::vector <Node *> &keys, int l, int r);
void Rebuild(Node *&p);
void Ins(Node *&p, int x);
void Insert(Node *&p, int x);
void Remove(Node *p, int x);
int GetRank(Node *p, int x);
int kth(Node *p, int x);

int main() {
    n = read(); root = null = new Node;
    ans = read(); Insert(root, ans);
    for(rgi i = 2; i <= n; ++i) {
        int x = read();
        int pre = kth(root, GetRank(root, x) - 1);
        int nxt = kth(root, GetRank(root, x));
//      printf("ans:%d\n", std::min(std::abs(pre - x), std::abs(nxt - x)));
        ans += std::min(std::abs(pre - x), std::abs(nxt - x));
        Insert(root, x);
    } printf("%d", ans);
    return 0;
}

void Dfs(Node *p, std::vector <Node *> &keys) {
    if(p == null) return;
    Dfs(p -> l, keys);
    if(!p -> del) keys.push_back(p);
    Dfs(p -> r, keys);
    if(p -> del) delete p;
}

Node *Build(std::vector <Node *> &keys, int l, int r) {
    if(l >= r) return null;
    int mid = l + r >> 1;
    Node *p = keys[mid];
    p -> l = Build(keys, l, mid);
    p -> r = Build(keys, mid + 1, r);
    p -> push();
    return p;
}

void Rebuild(Node *&p) {
    std::vector <Node *> vec;
    Dfs(p, vec);
    p = Build(vec, 0, vec.size());
}

void Ins(Node *&p, int x) {
    if(p == null) {
        p = new Node;
        p -> l = p -> r = null;
        p -> tot = p -> siz = 1;
        p -> del = 0;
        p -> val = x;
        return;
    }
    ++p -> tot;
    ++p -> siz;
    if(x >= p -> val) Ins(p -> r, x);
    else Ins(p -> l, x);
    if(p -> bad()) BadTag = &p;
    else if(BadTag != &null)
        p -> tot -= (*BadTag) -> tot - (*BadTag) -> siz;
}

void Insert(Node *&p, int x) {
    BadTag = &null;
    Ins(p, x);
    if(BadTag != &null) Rebuild(*BadTag);
}

void Remove(Node *p, int x) {
    if(!p -> del && p -> l -> siz + 1 == x) {
        p -> del = 1;
        --p -> siz;
        return;
    }
    --p -> siz;
    if(x <= p -> l -> siz + !p -> del) Remove(p -> l, x);
    else Remove(p -> r, x - p -> l -> siz - !p -> del);
}

int GetRank(Node *p, int x) {
    int res(1);
    while(p != null) {
        if(x <= p -> val) p = p -> l;
        else {
            res += p -> l -> siz + !p -> del;
            p = p -> r;
        }
    } return res;
}

int kth(Node *p, int x) {
    while(p != null) {
        if(!p -> del && p -> l -> siz + 1 == x)
            return p -> val;
        if(x <= p -> l -> siz + !p -> del) p = p -> l;
        else {
            x -= p -> l -> siz + !p -> del;
            p = p -> r;
        }
    }
}


活动打卡代码 AcWing 253. 普通平衡树

Clever_Jimmy
2019-12-16 13:00
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register ll
#define il inline

const double alpha = 0.86;

int n;

struct Node {
    Node *l, *r;
    int tot, siz, val;
    /*
    * tot -> total num
    * siz -> valid num
    */
    bool del;
    bool bad() {
        return (l -> tot > alpha * tot) ||
               (r -> tot > alpha * tot);
    }
    void push() {
        tot = l -> tot + r -> tot + 1;
        siz = l -> siz + r -> siz + !del;
    }
} *null, *root, **BadTag;

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

void Dfs(Node *&p, std::vector <Node *> &keys) {
    if(p == null) return;
    Dfs(p -> l, keys);
    if(!p -> del) keys.push_back(p);
    Dfs(p -> r, keys);
    if(p -> del) delete p; // 1
}

Node *Build(std::vector <Node *> &keys, int l, int r) {
    if(l >= r) return null;
    int mid = l + r >> 1;
    Node *p = keys[mid];
    p -> l = Build(keys, l, mid);
    p -> r = Build(keys, mid + 1, r); // 2
    p -> push();
    return p;
}

void Rebuild(Node *&p) {
    std::vector <Node *> vec;
    Dfs(p, vec);
    p = Build(vec, 0, vec.size());
}

void Ins(Node *&p, int x) {
    if(p == null) {
        p = new Node;
        p -> l = p -> r = null;
        p -> tot = p -> siz = 1;
        p -> val = x;
        p -> del = 0;
        return;
    }
    ++p -> siz;
    ++p -> tot;
    if(x >= p -> val) Ins(p -> r, x);
    else Ins(p -> l, x);
    if(p -> bad()) BadTag = &p;
    else if(BadTag != &null)
        p -> tot -= (*BadTag) -> tot - (*BadTag) -> siz; // 3
}

void Insert(Node *&p, int x) {
    BadTag = &null;
    Ins(p, x);
    if(BadTag != &null) Rebuild(*BadTag);
}

void Remove(Node *p, int x) {
    if(!p -> del && p -> l -> siz + 1 == x) {
        --p -> siz;
        p -> del = 1;
        return;
    }
    --p -> siz;
    if(x <= p -> l -> siz + !p -> del) Remove(p -> l, x);
    else Remove(p -> r, x - p -> l -> siz - !p -> del);
}

int GetRank(Node *p, int x) {
    int res(1);
    while(p != null) {
        if(p -> val >= x) p = p -> l; // 4
        else {
            res += p -> l -> siz + !p -> del;
            p = p -> r;
        }
    } return res;
}

int kth(Node *p, int x) {
    while(p != null) {
        if(!p -> del && p -> l -> siz + 1 == x) // 5
            return p -> val;
        if(p -> l -> siz >= x) p = p -> l;
        else {
            x -= p -> l -> siz + !p -> del;
            p = p -> r;
        }
    }
}

int main() {
    n = read();
    root = null = new Node;
    for(rgi i = 1; i <= n; ++i) {
        int opt = read(), x = read();
        switch(opt) {
            case 1: Insert(root, x); break;
            case 2: Remove(root, GetRank(root, x)); break;
            case 3: printf("%d\n", GetRank(root, x)); break;
            case 4: printf("%d\n", kth(root, x)); break;
            case 5: printf("%d\n", kth(root, GetRank(root, x) - 1)); break;
            case 6: printf("%d\n", kth(root, GetRank(root, x + 1))); break;
        }
    }
    return 0;
}



活动打卡代码 AcWing 112. 雷达设备

Clever_Jimmy
2019-10-25 13:53
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register ll
#define il inline

const int oo = 0x3f3f3f3f;
const int N = 1000 + 10;

int n, d, ans; double pos = -oo;

struct inv {
    double l, r;
    bool operator < (const struct inv &rhs) const {
        return l < rhs.l;
    }
} t[N];

il int read() {
    rgi x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch))  x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

int main() {
    n = read(), d = read();
    for(rgi i = 1; i <= n; ++i) {
        int x = read(), y = read();
        if(y > d) {
            puts("-1");
            return 0;
        }
        t[i].l = (double)(x - sqrt(d * d - y * y));
        t[i].r = (double)(x + sqrt(d * d - y * y));
    }

    std::sort(t + 1, t + n + 1);

    for(rgi i = 1; i <= n; ++i) {
        if(t[i].l > pos)    pos = t[i].r, ans++;
        else    pos = std::min(pos, t[i].r);
    }

    printf("%d ", ans);
    return 0;
}