Submission #1229548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229548		hashdfdfh	Secret (JOI14_secret)	C++20	100 / 100	341 ms	4436 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e3 + 5;

// 保持原始数组
int arr[MAX_N];

// log2(MAXN)
const int LOG = 10;

int mask[MAX_N]; // 记录每个位置的区间信息
int dat[LOG][MAX_N]; // 存储预处理的最小值数据

// X X X X   X X X X          	3 * 2 = 6
// X X  X X  X X  X X			1 * 4 = 4
// X  X  X  X  X  X  X  X		0 * 8 = 0

// (n / 2 - 1) * 2		n - 2
// (n / 4 - 1) * 4		n - 4
// (n / 8 - 1) * 8     n - 8

// nlgn - (2 + 4 + 8 + ... + 2 ^ i)	2 ^ i <= n的最大值
// nlgn - (2 ^ (i + 1) - 2) = nlgn - 2 ^ (i + 1) + 2 
// nlgn - 2 * n + 2（不会超过8000）
// 8 * 3 - (2 + 4 + 8) = 10

void preprocess(int L, int R, int level) {
    // 区间只有1个元素，不用计算
    if (L == R) {
        return;
    }

    // 找到区间中间索引
    int mid = (L + R) / 2;

    // 预处理求dat（i到mid的最小值）
    // 从mid向左计算
    dat[level][mid] = arr[mid];
    for (int i = mid - 1; i >= L; i--) {
        dat[level][i] = Secret(arr[i], dat[level][i + 1]);
    }

    // 预处理求right（mid+1到r的最小值）
    // 从mid+1向右计算
    dat[level][mid + 1] = arr[mid + 1];
    for (int i = mid + 2; i <= R; i++) {
        dat[level][i] = Secret(dat[level][i - 1], arr[i]);
    }

    // 更新右半部分的mask标记
    for (int i = mid + 1; i <= R; i++) {
        mask[i] ^= (1 << level);
    }

    // 递归处理左右子区间
    preprocess(L, mid, level + 1);
    preprocess(mid + 1, R, level + 1);
}

// 末尾连续0的个数
int count_trailing_zeros(int x) {
    // 特殊处理0的情况
    if (x == 0) {
        return 32;
    }

    int count = 0;

    // 检查最低位是否为0
    while ((x & 1) == 0) {
        count++;
        // 右移一位
        x >>= 1;
    }
    return count;
}

void Init(int N, int A[]) {
    for (int i = 0; i < N; ++i) {
        arr[i] = A[i];
    }
    preprocess(0, N - 1, 0);
}

int Query(int L, int R) {
    // 只有一个元素
    if (L == R) {
        return arr[L];
    }

    // 计算mask的差异位数，确定查询层级
    // __builtin_ctz
    // diff_bits就是L和R，第一次被划分到两个区域的层级
    int diff_bits = count_trailing_zeros(mask[L] ^ mask[R]);
    return Secret(dat[diff_bits][L], dat[diff_bits][R]);
}

• Subtask 1: 100 / 100