AtCoder Beginner Contest 431

T0mle · 2025-11-09 10:33:29 · 个人记录

顺序：GABCDEF。

G

将 f(l,r) 分成三部分：字典序小于原来，等于原来，大于原来。

小于的大于是逆序对和正序对，fenwick 数数。

将询问离线下来排序。

对于 x 不大于逆序对个数的询问，字典序小于原来。

这部分 f(l,r) 的顺序是：l 最小的前提下，a_r 最小，然后 r 最大。

线段树随便算一算。但是我的代码要求集合第 k 大，set advance 假了，并且不会用平板电视，只能再写个动态开点线段树了。

其余两部分同理。

5.2k，fwk+2smt。

40min

::::info[代码过长放在这里吧]

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005;
// const int V = ;
// const int mod = ;
typedef unsigned us;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vl;
template <class T> using pq = priority_queue <T>;
template <class T> using pqg = priority_queue <T, vector <T>, greater <T> >;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repr(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define perr(i, a, b) for (int i = (a); i > (b); --i)

#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back

template <class T1, class T2> inline void ckmn(T1 &a, T2 b) { (a > b) && (a = b, 0); }
template <class T1, class T2> inline void ckmx(T1 &a, T2 b) { (a < b) && (a = b, 0); }

namespace IO {
    // char buf[1 << 23], *p1 = buf, *p2 = buf;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
    template <class T> void rd(T &a, unsigned c = 0) {
        while (c = getchar(), c < 48 || c > 57);
        for (a = 0; c >= 48 && c <= 57; c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
    }
    template <class T> void wrt(T x) { if (x > 9) wrt(x / 10); putchar(x % 10 ^ 48); }
} using IO::rd; using IO::wrt;

int n, q, a[N];
pii ans[N];
struct Ques { int x, id; } qu[N];
map <int, int> mp;

struct shit {
    int ls, rs, ct;
    #define ll(p) Tr[p].ls
    #define rr(p) Tr[p].rs
    #define cct(p) Tr[p].ct
} Tr[N * 200];
#define MM (L + R >> 1)
int tot;
void pushpu(int p) { cct(p) = cct(ll(p)) + cct(rr(p)); }
inline void sb(int p, int x, int k, int L, int R) {
    if (L == R) { cct(p) += k; return; }
    if (x <= MM) {
        if (!ll(p)) ll(p) = ++tot;
        sb(ll(p), x, k, L, MM);
    } else {
        if (!rr(p)) rr(p) = ++tot;
        sb(rr(p), x, k, MM + 1, R);
    }
    pushpu(p);
}
int shabi1(int p, int x, int L, int R) {
    if (L == R) return L;
    if (cct(ll(p)) >= x) return shabi1(ll(p), x, L, MM);
    return shabi1(rr(p), x - cct(ll(p)), MM + 1, R);
}

struct Seg {
    int l, r, ct;
    int rt;
    #define l(p) tr[p].l
    #define r(p) tr[p].r
    #define ct(p) tr[p].ct
    #define rt(p) tr[p].rt
} tr[N << 2];
#define M (l(p) + r(p) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)

inline void pushup(int p) {
    ct(p) = ct(ls) + ct(rs);
}
void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) { rt(p) = ++tot, ct(p) = 0; return; }
    build(ls, l, M), build(rs, M + 1, r);
    pushup(p);
}
void mod1(int p, int x, int k) {
    if (l(p) == r(p)) {
        sb(rt(p), k, 1, 1, n);
        ct(p) = cct(rt(p));
        return;
    }
    mod1(x <= M ? ls : rs, x, k), pushup(p);
}
void mod2(int p, int x, int k) {
    if (l(p) == r(p)) {
        sb(rt(p), k, -1, 1, n);
        ct(p) = cct(rt(p));
        return;
    }
    mod2(x <= M ? ls : rs, x, k), pushup(p);
}
int qrk(int p, int x) {
    if (l(p) == r(p)) {
        return shabi1(rt(p), ct(p) - x + 1, 1, n);
    }
    if (ct(ls) >= x) return qrk(ls, x);
    return qrk(rs, x - ct(ls));
}
int qry(int p, int l, int r) {
    if (l > r || l > r(p) || r < l(p)) return 0;
    if (l <= l(p) && r >= r(p)) return ct(p);
    if (r <= M) return qry(ls, l, r);
    if (l > M)  return qry(rs, l, r);
    return qry(ls, l, r) + qry(rs, l, r);
}
int qrk2(int p, int x, int l, int r) {
    if (l(p) == r(p)) {
        return shabi1(rt(p), x, 1, n);
    }
    int c = qry(ls, l, r);
    // cout << l(p) << "  " << r(p) << "  " << c << endl;
    if (c >= x) return qrk2(ls, x, l, r);
    return qrk2(rs, x - c, l, r);
}

struct BIT {
    int a[N];
    #define LB(k) ((k) & -(k))
    void clr() { memset(a, 0, sizeof(a)); }
    void add(int x, int k) { for (; x < N; x += LB(x)) a[x] += k; }
    int qry(int x) { int R = 0; for (; x; x -= LB(x)) R += a[x]; return R; }
} fwk;

bool cmp(Ques a, Ques b) { return a.x < b.x; }
int ivct() {
    int R = 0;
    per(i, n, 1) {
        R += fwk.qry(a[i] - 1);
        fwk.add(a[i], 1);
    }
    return R;
}
int nivct() {
    fwk.clr();
    int R = 0;
    rep(i, 1, n) {
        R += fwk.qry(a[i] - 1);
        fwk.add(a[i], 1);
    }
    return R;
}
void solve() {
    rd(n), rd(q);
    rep(i, 1, n) rd(a[i]);
    rep(i, 1, q) rd(qu[i].x), qu[i].id = i;
    sort(qu + 1, qu + q + 1, cmp);
    int A = ivct(), C = nivct();
    int B = n * (n - 1) / 2 - A - C;
    int now = 0;
    build(1, 1, n);
    rep(i, 1, n) mod1(1, a[i], i);
    int j = 1;
    rep(i, 1, n) {
        mod2(1, a[i], i);
        int cc = qry(1, 1, a[i] - 1);
        while (j <= q && now + cc >= qu[j].x) {
            ans[qu[j].id] = {i, qrk(1, qu[j].x - now)};
            j++;
        }
        now += cc;
    }
    pii sm;
    rep(i, 1, n) {
        if (mp[a[i]]) sm = {mp[a[i]], i};
        mp[a[i]] = i;
    }
    while (j <= q && A + B >= qu[j].x) {
        ans[qu[j].id] = sm;
        j++;
    }
    now = A + B;
    build(1, 1, n);
    per(i, n, 1) {
        int cc = qry(1, a[i] + 1, n);
        while (j <= q && now + cc >= qu[j].x) {
            ans[qu[j].id] = {i, qrk2(1, qu[j].x - now, a[i] + 1, n)};
            j++;
        }
        now += cc;
        mod1(1, a[i], i);
    }
    rep(i, 1, q) wrt(ans[i].fi), putchar(32), wrt(ans[i].se), putchar(10);
}
signed main() {
    int T = 1;
    if (0) rd(T);
    while (T--) solve();
}

::::

A