【XJTU 2020暑期集训】Day11 - 2019 杭电多校训练第2场

J - Just Skip The Problem

签到题。每一次询问最多只能获得一位的信息，有询问次数下界为 n，可构造询问：第 i 个询问为 y_i=000\dots010\dots000（只有第 i 位为1），显然可行，并且该询问方案的任意排列均可行，共 n! 个。现证明其它询问方案不能达到理论下界：当存在 y_i 与 y_j 在某一位上均为1时，若 x 在该位上位0，则这两个询问最多可获得一位的信息，因此达不到下界。所以答案为 n!，由于模数 p=10^6+3，所以当 n\ge p 时直接输出0，否则暴力计算即可。

K - Keen On Everything But Triangle

用主席树维护权值，对于每个询问，暴力查找可以构成三角形的最大的三个数。由于斐波那契数列的性质，最多暴力 \log n 次，每次复杂度为 O(n\log n)，所以总复杂度 O(n\log^2 n)。

Code

J - Just Skip The Problem

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MOD 1000003
#define int long long

using namespace std;

int n;

signed main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        if (n >= MOD) {
            cout << 0 << endl;
        } else {
            int ans = 1;
            for (int i = 2; i <= n; i++) {
                ans = ans * i % MOD;
            }
            cout << ans << endl;
        }
    }
}

K - Keen On Everything But Triangle

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 100005
#define MAX_T 4000005
#define int long long

using namespace std;

int n, q, tot;
int a[MAX_N];
int rt[MAX_N];
int L[MAX_T];
int R[MAX_T];
int sum[MAX_T];
vector<int> v;

int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void build(int o, int &k, int l, int r, int p) {
    k = ++tot;
    sum[k] = sum[o] + 1;
    if (l == r) {
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) {
        R[k] = R[o];
        build(L[o], L[k], l, m, p);
    } else {
        L[k] = L[o];
        build(R[o], R[k], m + 1, r, p);
    }
}

int getx(int o, int &k, int l, int r, int rk) {
    if (l == r) {
        return l;
    }
    int m = (l + r) >> 1, s = sum[L[k]] - sum[L[o]];
    if (rk <= s) {
        return getx(L[o], L[k], l, m, rk);
    }
    return getx(R[o], R[k], m + 1, r, rk - s);
}

signed main() {
    while (scanf("%lld%lld", &n, &q) != EOF) {
        v.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%lld", a + i);
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for (int i = 0; i <= tot; i++) {
            L[i] = R[i] = sum[i] = 0;
        }
        for (int i = 0; i <= n; i++) {
            rt[i] = 0;
        }
        tot = 0;
        int N = v.size();
        for (int i = 1; i <= n; i++) {
            build(rt[i - 1], rt[i], 1, N, getid(a[i]));
        }
        int l, r;
        while (q--) {
            scanf("%lld%lld", &l, &r);
            if (r - l + 1 < 3) {
                printf("-1\n");
            } else {
                int rk = r - l + 1;
                int a = getx(rt[l - 1], rt[r], 1, N, rk) - 1;
                int b = getx(rt[l - 1], rt[r], 1, N, rk - 1) - 1;
                int c = getx(rt[l - 1], rt[r], 1, N, rk - 2) - 1;
                while (rk > 3 && v[a] >= v[b] + v[c]) {
                    rk--, a = b, b = c;
                    c = getx(rt[l - 1], rt[r], 1, N, rk - 2) - 1;
                }
                if (v[a] < v[b] + v[c]) {
                    printf("%lld\n", v[a] + v[b] + v[c]);
                } else {
                    printf("-1\n");
                }
            }
        }
    }
}