简要题解

· · 个人记录

前四道题均为洛谷原题，大家自行查阅题解即可。

还原排列

观察 s_i 是由 j < i 且 p_j < p_i 贡献得到的，且贡献是 p_j。

不妨倒着考虑。

考虑 s_n 是如何得到的，一定是一段连续 1 \sim k_1 的和，然后我们就可以求出 p_n，接着考虑 s_{n - 1}，这时有两种情况：

考虑维护一个线段树，线段树存的是 1 \sim n 是否存在，初始时 1 \sim n 均存在，即对一个 1 \sim n 的排列建树。

我们计算 p_n 时，可以通过二分 + 线段树查询的方式来计算。具体来说，二分一个 mid，线段树计算 1 \sim mid 的和，再跟 s_n 进行判断。

计算出 p_n 后，在线段树上删除 p_n，即令线段树上 p_n 位置为 0。然后接着计算 p_{n-1}，我们同样使用二分 + 线段树查询区间和即可。

这样复杂度是两个 \log 的，使用线段树上二分可以做到一个 \log。

std：（暂时只有线段树上二分版）

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ls rt << 1
#define rs rt << 1 | 1
#define ll long long

using namespace std;

const ll N = 1e6 + 10;
ll n;
ll s[N], p[N];
ll t[N << 2];

inline ll read(){
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

inline void pushup(ll rt){
    t[rt] = t[ls] + t[rs];
}

void build(ll l, ll r, ll rt){
    if(l == r){
        t[rt] = l;
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

ll query(ll k, ll l, ll r, ll rt){
    if(l == r)
        return l;
    ll mid = (l + r) >> 1;
    if(k <= t[ls]) return query(k, l, mid, ls);
    else return query(k - t[ls], mid + 1, r, rs);
}

void remove(ll pos, ll l, ll r, ll rt){
    if(l == r){
        t[rt] = 0ll;
        return;
    }
    ll mid = (l + r) >> 1;
    if(pos <= mid) remove(pos, l, mid, ls);
    else remove(pos, mid + 1, r, rs);
    pushup(rt);
}

signed main(){
    n = read();
    for(ll i = 1; i <= n; i++)
        s[i] = read();
    build(1, n, 1);
    for(ll i = n; i >= 1; i--){
        p[i] = query(s[i] + 1, 1, n, 1);
        remove(p[i], 1, n, 1);
    }
    for(ll i = 1; i < n; i++)
        printf("%lld ", p[i]);
    printf("%lld\n", p[n]);
    return 0;
}

数列编辑器

的确是平衡树板子题，但是这里不讲平衡树。

考虑维护分别对光标前的数和光标后的数维护树状数组，那么事情就变得简单多了。

假设光标前树状数组为 t_1，光标后树状数组为 t_2。

插入：在 t_1 后插入 x。

删除：在 t_1 后插入 -(qry(siz) - qry(siz - 1))

左移：把 t_1 末尾元素删除，插入到 t_2 末尾。

右移：同理。

查询：分三种情况，全在 t_1；一半在 t_1，一半在 t_2；全在 t_2。

修改：判断在哪棵树上改哪棵即可。

std：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e5 + 10;
int n;

struct Tree{
    int id, c[N];

    inline void add(int x, int y){
        for(; x <= n; x += x & (-x)) c[x] += y;
    }

    inline void del(){
        add(id, qry(id - 1) - qry(id)), id--;
    }

    inline int qry(int x){
        int res = 0;
        for(; x; x -= x & (-x)) res += c[x];
        return res;
    }

}t1, t2;
char op[5];

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> op;
        if(op[0] == 'I'){
            int x; cin >> x;
            t1.add(++t1.id, x);
        }else if(op[0] == 'D') t1.del();
        else if(op[0] == 'L'){
            if(t1.id == 0) continue;
            int v = t1.qry(t1.id) - t1.qry(t1.id - 1);
            t1.del(), t2.add(++t2.id, v);
        }else if(op[0] == 'R'){
            if(t2.id == 0) continue;
            int v = t2.qry(t2.id) - t2.qry(t2.id - 1);
            t2.del(), t1.add(++t1.id, v);
        }else if(op[0] == 'Q'){
            int l, r; cin >> l >> r;
            if(t1.id >= r) cout << t1.qry(r) - t1.qry(l - 1) << endl;
            else if(t1.id < l) cout << t2.qry(t2.id - (l - t1.id) + 1) - t2.qry(t2.id - (r - t1.id)) << endl;
            else cout << (t1.qry(t1.id) - t1.qry(l - 1)) + (t2.qry(t2.id) - t2.qry(t2.id - (r - t1.id))) << endl;
        }else{
            int p, v; cin >> p >> v;
            if(t1.id >= p) t1.add(p, v - (t1.qry(p) - t1.qry(p - 1)));
            else{
                p = t2.id - (p - t1.id) + 1;
                t2.add(p, v - (t2.qry(p) - t2.qry(p - 1)));
            }
        }
    }
    return 0;
}