The 2024 Sichuan Provincial Collegiate Programming Contest题解

G. Function Query

题意

给你一个数组 和 次询问(, )，每次询问给你两个数和，定义，找出下标 满足，不存在则输出。

input

5 6
3 5 1 2 4
0 2
1 1
2 3
3 2
4 2
5 8

output

2
3
2
1
4
-1

我们发现对于给定的 和 ， 只有大于0、小于0和等于0三种情况。而一旦 ，就只要选择 即可。因此下面讨论另外两种情况。

我们发现如果不存在 满足$ f(x) < 0x$都满足 ，显然答案是。 同理。反之，若两者都存在，那么我们肯定能找到一个分界点（因为只有 只有两种情况），使得 。现在的问题转换成我们怎么找到这个下标。

下标肯定不是盲目去找的，要想到找到某些具有特殊性质的下标。由于异或并不满足单调性，那么我们的特殊性质就很少了。我们应该想到需要找下标最小的点（最大也可以，下面以最小为例子），这样如果找到了满足 最小下标 ，肯定有 。但是又有新问题出现了：如果该怎么处理呢？因为只有大于或者小于两种情况，因此我们既找满足 的最小下标，也找 的最小下标，若答案存在， 和 之间必定有一个是，一个非。我们取大的那个输出即可。

那么我们怎么去找呢？看到二进制，我们可以想到逐位比较。用字典树记录 ，并且每个位置都记录最小的那个下标（即如果 与 具有部分相同的二进制前缀，那么该他们在字典树上有重合的位置。这些重合的位置上我只记录小的那个下标）。给定了 和 ，我们怎么找 呢？我们以找 为例，从高到低找到了第 位。我们要知道如果比到了第 位，那么前面的每个位置肯定都满足。 如果 这一位是，那么 这一位不得不是 。反之如果 的这一位是，那么如果存在 使得 这一位是 ，我们就取，然后让的这一位与 的这一位相同，继续往后找。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

struct Trie {
    vector<vector<int>> ch;
    vector<int> z;

    Trie(int n) {
        ch.resize((n + 1) << 4);
        z.resize((n + 1) << 4);
        for (int i = 0; i < ((n + 1) << 4); i++) {
            ch[i].resize(2);
        }
    }

    int idx = 0;

    void insert(int x, int id) {
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            int k = x >> j & 1;
            if (!ch[p][k]) {
                ch[p][k] = ++idx;
                z[idx] = id;
            }
            p = ch[p][k];
        }
    }

    int querym(int a, int b) {
        int ans = -1;
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            bool f = false, g = false;
            if (a >> j & 1) {
                f = true;
            }
            if (b >> j & 1) {
                g = true;
            }

            if (f && g) {
                if (ch[p][1]) {
                    int res = z[ch[p][1]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

            if (f && !g) {
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && g) {
                if (ch[p][0]) {
                    int res = z[ch[p][0]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && !g) {
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }
        }

        return ans;
    }

    int queryb(int a, int b) {
        int ans = -1;
        int p = 0;
        for (int j = 31; j >= 0; j--) {
            bool f = false, g = false;
            if (a >> j & 1) {
                f = true;
            }
            if (b >> j & 1) {
                g = true;
            }

            if (f && g) {
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

            if (f && !g) {
                if (ch[p][0]) {
                    int res = z[ch[p][0]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && g) {
                if (!ch[p][1]) {
                    return ans;
                }
                p = ch[p][1];
            }

            if (!f && !g) {
                if (ch[p][1]) {
                    int res = z[ch[p][1]];
                    if (ans == -1) {
                        ans = res;
                    }
                    else {
                        ans = min(ans, res);
                    }
                }
                if (!ch[p][0]) {
                    return ans;
                }
                p = ch[p][0];
            }

        }

        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    Trie tree(n + 1);
    map<int, int> mp;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        tree.insert(x, i);
        mp[x] = min(i, n - 1);
    }


    while (q--) {
        int a, b;
        cin >> a >> b;
        if (mp.contains(a ^ b)) {
            cout << mp[a ^ b] << endl;
            continue;
        }
        int ans = max(tree.queryb(a, b), tree.querym(a, b));
        if (ans <= 1) {
            ans = -1;
        }
        else {
            ans--;
        }

        cout << ans << endl;
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

A. Reverse Pairs Coloring

题意

给你一个长度为 () 的排列，以及一个的方格，对于所有满足 以及 的下标，给方格第 行第 列的方格染色， 求染色的联通块的个数。

input

9
5 9 1 8 2 6 4 7 3

output

5

可以对小数据画图分析。 比如题目所给样例，最后的方格是这样的：

xxxx.....
xxxx.xxx.
.........
.xxx.xx..
.........
..xx.....
..x......
..x......
.........

我们发现以下性质：
1. 对于第 行，染色个数不超过。因为需要找逆序对，而对于所有逆序对，都有。
2. 对于每个，它肯定不会作用到满足的下标 。因为逆序对是对于 的下标 ，而对于列的染色是 列。既然 在前面出现过了，就不会在后面形成逆序对。

于是我们可以模拟以下过程：
1. 对于每一个 ，先对这一行的前 个格子染色。
2. 对于每一个 ，将满足 的下标 中的第 列中染色的方块划去。

这样我们就模拟完了这个过程。但是目前还有一点问题，那就是怎么去记录每一行的染色情况呢？我们可以转换一下过程：只有一行。首先所有方格都染色。遍历到第 行时，对第 个删除。然后取前 个，就是目前的状态。
所以现在我们只需要维护一个数组了。由于是取前 个，我们可以考虑保存中数组连续位置左端点的位置。删除了第 个，如果是左端点，就将其删去；如果 被染色，那么第 个将成为新的左端点。注意到当 时是不会产生新的联通块的，因为此时 是 的前缀。当 ，只需要查找区间 的左端点个数就是新的联通块的个数。可以用树状数组保存左端点。时间复杂度。

code

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

template<class T>
struct BIT {
    vector<T> c;
    int ub;
    BIT() {}
    BIT(int ub_) {
        ub = ub_;
        init();
    }

    void init() {
        c.resize(ub + 1);
        c.assign(ub + 1, 0);
    }

    int lowbit(int x) {
        return x & -x;
    }

    void add(int pos, T val) {
        if (pos <= 0) return;
        while (pos <= ub) {
            c[pos] += val;
            pos += lowbit(pos);
        }
    }

    T query(int pos) {
        if (pos <= 0) return 0;
        T res = 0;
        while (pos) {
            res += c[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    T query(int l, int r) {
        return query(r) - query(l - 1); 
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<bool> vis(n + 2, true);
    vis[0] = vis[n + 1] = false;

    BIT<int> c(n);

    c.add(1, 1);

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        vis[x] = false;
        if (c.query(x, x)) {
            c.add(x, -1);
        }
        if (vis[x + 1]) {
            c.add(x + 1, 1);
        }
        if (a[i] < a[i - 1]) continue;
        ans += c.query(a[i - 1], a[i]);
    }


    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}