HDU - 6873 Game

传送门：HDU - 6873

思路分析

通过观察发现，只有两列的值会变化，可以把操作看成一整块平移，用fhq_treap维护

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a, b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror = 0;

    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }

    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }

    template<class T>
    inline bool read(T &x) {
        bool sign = 0;
        char ch = nc();
        x = 0;
        for (; blank(ch); ch = nc());
        if (IOerror)return false;
        if (ch == '-')sign = 1, ch = nc();
        for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
        if (sign)x = -x;
        return true;
    }

    template<class T, class... U>
    bool read(T &h, U &... t) {
        return read(h) && read(t...);
    }

#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
#define int long long
namespace fhq_treap {
#define ls(x) tree[x].l
#define rs(x) tree[x].r

    struct node {
        int l, r, val, key, siz, mi, sum;

        void clear() {
            l = r = val = key = siz = sum = 0;
            mi = INF;
        }
    } tree[N];

    int root, cnt;
    vector<int> tmp;

    void init(int maxn) {
        tmp.clear();
        root = cnt = 0;
        for (int i = 0; i <= maxn; i++) tree[i].clear();
        tree[0].mi = INF;
    }

    int newnode(int val) {
        tree[++cnt].val = val;
        tree[cnt].key = rng();
        tree[cnt].siz = 1;
        tree[cnt].sum = val;
        tree[cnt].mi = val;
        return cnt;
    }

    void pp(int x) {
        tree[x].siz = tree[ls(x)].siz + tree[rs(x)].siz + 1;
        tree[x].sum = tree[ls(x)].sum + tree[rs(x)].sum + tree[x].val;
        tree[x].mi = min(tree[x].val,min(tree[ls(x)].mi,tree[rs(x)].mi));
    }

    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tree[x].key > tree[y].key) {
            rs(x) = merge(rs(x), y);
            pp(x);
            return x;
        } else {
            ls(y) = merge(x, ls(y));
            pp(y);
            return y;
        }
    }


    void split_siz(int now, int ksiz, int &x, int &y) {
        if (!now) x = y = 0;
        else {
            if (tree[ls(now)].siz < ksiz) {
                x = now;
                split_siz(rs(now), ksiz - tree[ls(now)].siz - 1, rs(x), y);
            } else {
                y = now;
                split_siz(ls(now), ksiz, x, ls(y));
            }
            pp(now);
        }
    }

    void split_min(int now, int kmi, int &x, int &y) {
        if (!now) x = y = 0;
        else {
            if (tree[rs(now)].mi < kmi || tree[now].val < kmi) {
                x = now;
                split_min(rs(now), kmi, rs(x), y);
            } else {
                y = now;
                split_min(ls(now), kmi, x, ls(y));
            }
            pp(now);
        }
    }

    int kth_siz(int k) {
        int x = root;
        while (x) {
            if (tree[ls(x)].siz + 1 == k) break;
            else if (tree[ls(x)].siz >= k) x = ls(x);
            else {
                k -= tree[ls(x)].siz + 1;
                x = rs(x);
            }
        }
        return tree[x].val;
    }

    void dfs(int x) {
        if (!x) return;
        dfs(ls(x));
        tmp.pb(tree[x].val);
        dfs(rs(x));
    }

#undef ls
#undef rs
};
using namespace fhq_treap;

int a[N];

int move(int x, int y) {
    if (kth_siz(x) < y) return 0;
    int L, R;
    split_siz(root, x, L, R);
    if (tree[L].mi >= y) {
        root = merge(L, R);
        return 0;
    }

    int l, r;
    split_min(L, y, l, r);
    int ans = tree[r].sum - tree[r].siz * (y - 1);

    int l1, l2, r1, r2;
    split_siz(l, tree[l].siz - 1, l1, l2);
    split_siz(r, 1, r1, r2);
    tree[l2].val += tree[r1].val - (y - 1);
    tree[l2].sum = tree[l2].mi = tree[l2].val;
    tree[r1].sum = tree[r1].val = tree[r1].mi = y - 1;
    root = merge(merge(merge(l1, l2), merge(r2, r1)),R);
    return ans;

}


signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int T;
    read(T);
    while (T--) {
        int n, m;
        read(n,m);
        init(n);
        for (int i = 1; i <= n; i++) {
            read(a[i]);
            root = merge(root, newnode(a[i]));
        }
        while (m--) {
            int op, x, y;
            read(op);
            if (op == 1) {
                read(x,y);
                printf("%lld\n", move(x, y));
            } else {
                read(x);
                printf("%lld\n", kth_siz(x));
            }
        }
        dfs(root);
        for (int i = 0; i < n; i++) printf("%lld%c", tmp[i], i == n - 1 ? '\n' : ' ');
    }


    return 0;
}