2019南京网络赛F 树状数组+主席树

题目链接

大意：输出每个i为开头情况下的满足字典序最大的长度。

思路：每个i的答案显然是在[pos-k,pos+k]中取一个最大的且不超过i的答案+1，那么，我们可以用树状数组预处理出每个i在区间内小于他的个数，然后用主席树直接差区间第x小即可。
树状数组的操作细节为，把区间拆成左右两部分，然后求前缀小于i的值，两个剪一下就是区间了。

细节见代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e5 + 11;
int tt, n, k, pos[N];
struct uzi {
    int sum, l, r;
} T[N * 40];
int now, a[N], b[N], t[N];
void update(int l, int r, int &x, int y, int pos) {
    T[++now] = T[y]; T[now].sum++; x = now;
    if (l == r)return ;
    int mid = l + r >> 1;
    if (mid >= pos)update(l, mid, T[x].l, T[y].l, pos);
    else update(mid + 1, r, T[x].r, T[y].r, pos);
}
int get(int l, int r, int x, int y, int k) {
    if (l == r)return l;
    int sum = T[T[y].l].sum - T[T[x].l].sum;
    int mid = l + r >> 1;
    if (sum >= k)return get(l, mid, T[x].l, T[y].l, k);
    else return get(mid + 1, r, T[x].r, T[y].r, k - sum);
}
int ans[N];
struct uz{
    int l, i, s;
    bool operator <(const uz &t)const {
        return l < t.l;
    }
} p[N << 2];
int La[N], Ra[N], G[N];
void add(int p) {
    for (int i = p; i <= n; i += (i & -i))G[i]++;
}
int query(int p) {
    int A = 0;
    for (int i = p; i; i -= (i & -i))A += G[i];
   return A;
}
int main() {
    for (scanf("%d", &tt) ; tt; tt--) {
        scanf("%d%d", &n, &k); now = 0;
        int gogo = 0;
        memset(G, 0, sizeof G);
        for (int i = 1; i <= n; i++)scanf("%d", &a[i]), pos[a[i]] = i, update(1, n, t[i], t[i - 1], a[i]), ans[i] = 0;
        ans[1] = 1;
        for (int i = 1; i <= n; i++) {
            int l = pos[i] - k;
            int r = pos[i] + k;
            l = max(l, 1);
            r = min(r, n);
            p[++gogo] = {l - 1, i, 1};
            p[++gogo] = {r, i, 2};
        }
        sort(p + 1, p + 1 + gogo);
        int l = 0;
        for (int i = 1; i <= gogo; i++) {
            while (l < p[i].l) {
                add(a[++l]);
            }
            int now = query(p[i].i - 1);
            if (p[i].s == 1)La[p[i].i] = now;
            else Ra[p[i].i] = now;
        }
        for (int i = 2; i <= n; i++) {
            int l = pos[i] - k;
            int r = pos[i] + k;
            l = max(l, 1);
            r = min(r, n);
            int L = 1, R = r - l + 1, res = 0;
            int need = Ra[i] - La[i];
            if (need)res = get(1, n, t[l - 1], t[r], need);
            else res = 0;
            ans[i] = ans[res] + 1;
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", ans[i], (i == n ? '\n' : ' ') );
        }
    }
    return 0;
}