题解 [牛客IOI周赛16-提高组 C] 最小鸽

• 最小鸽

题目描述

给定一个序列，每次询问包含一个位置的最小区间，满足这个区间元素的或（or）大于这个区间元素的最大值。

正解

在线肯定不太可行，想离线做法。

对于每一个数作为区间的最大值（不一定唯一），求它对这个区间产生的影响。

然后这个位置作为最大值的区间要合法的话，需要包含一个数二进制位与它不同。

其实就对每个位置，预处理出两个左端点，两个右端点。（作为最大值的左右端点，和遇到第一个数二进制位与它不同的左右端点）

然后合法不合法就和容易判断了，更新答案用线段树简单维护即可。

可能之后会补充判断是否合法，以及线段树更新区间的细节吧。

时间复杂度 。

补充

• upd : 如何统计答案

先规定一些东西

设 表示 : 满足位置在 ， 为最大值，最小的 。

设 表示 : 满足位置在 ， 为最大值，最大的 。

设 表示 : 往左边走第一个遇到的点与之二进制位不同。

设 表示 : 往右边走第一个遇到的点与之二进制位不同。

分类讨论计算贡献

这里只讨论 对答案的影响，因为 的讨论与之类似。

若 则其可以对 的区间产生影响，否则不行。

对于 的位置，让它的答案对 取 。

对于 的位置，区间 是合法的，我们对这种 求出一个最左端的 。（让区间对 取 ）

对于 的位置，区间 是合法的，我们对这种 求出一个最右端的 。（让区间对 取 ）

代码

#include <bits/stdc++.h>
#define N 300005
#define inf 1000000005

using namespace std;

int n, m;
int a[N], l[N], r[N], L[N], R[N];
int ans[N];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

void getNear(int b) {
    int las = -1;
    for(int i = 1; i <= n; ++i) {
        if(a[i] >> b & 1) {
            las = i;
        } else {
            l[i] = max(l[i], las);
        }
    }
    las = n + 2;
    for(int i = n; i >= 1; --i) {
        if(a[i] >> b & 1) {
            las = i;
        } else {
            r[i] = min(r[i], las);
        }
    }
}

int ll, rr, cv;

struct SMT {
#define lch(x) (x << 1)
#define rch(x) (x << 1 | 1)
    int val[N << 2];
    void build(int u, int l, int r) {
        val[u] = -inf;
        if(l == r) return void();
        int mid = l + r >> 1;
        build(lch(u), l, mid);
        build(rch(u), mid + 1, r);
    }
    void modify(int u, int l, int r) {
        if(ll <= l && r <= rr) return val[u] = max(val[u], cv), void();
        int mid = l + r >> 1;
        if(ll <= mid) modify(lch(u), l, mid);
        if(mid < rr) modify(rch(u), mid + 1, r);    
    }
    int query(int u, int l, int r) {
        if(l == r) return val[u];
        int mid = l + r >> 1;
        if(ll <= mid) return max(val[u], query(lch(u), l, mid));
        else return max(val[u], query(rch(u), mid + 1, r));
    }
}lT, rT, lenT;

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        l[i] = -1, r[i] = n + 2;
    }

    for(int i = 0; i < 30; ++i) getNear(i);

    a[0] = inf, a[n + 1] = inf;
    for(int i = 1; i <= n; ++i) {
        L[i] = i - 1;
        while(a[i] >= a[L[i]])
            L[i] = L[L[i]];
    }
    for(int i = n; i >= 1; --i) {
        R[i] = i + 1;
        while(a[i] >= a[R[i]])
            R[i] = R[R[i]];
    }

    lT.build(1, 1, n);     // 取正
    rT.build(1, 1, n);     // 取负
    lenT.build(1, 1, n); // 取负
    for(int i = 1; i <= n; ++i) {
        ++L[i], --R[i];
        if(L[i] <= l[i]) {
            ll = l[i], rr = i, cv = -(rr - ll + 1);
            lenT.modify(1, 1, n);
            ll = L[i], rr = l[i] - 1, cv = -i;
            if(ll <= rr) rT.modify(1, 1, n);
            ll = i + 1, rr = R[i], cv = l[i];
            if(ll <= rr) lT.modify(1, 1, n);
        }
        if(r[i] <= R[i]) {
            ll = i, rr = r[i], cv = -(rr - ll + 1);
            lenT.modify(1, 1, n);
            ll = r[i] + 1, rr = R[i], cv = i;
            if(ll <= rr) lT.modify(1, 1, n);
            ll = L[i], rr = i - 1, cv = -r[i];
            if(ll <= rr) rT.modify(1, 1, n);
        }
    }

    int ml, mr, mlen;
    for(int i = 1; i <= n; ++i) {
        ll = i, rr = i;
        ans[i] = inf;
        ml = lT.query(1, 1, n);
        mr = -rT.query(1, 1, n);
        mlen = -lenT.query(1, 1, n);
        ans[i] = min(ans[i], i - ml + 1);
        ans[i] = min(ans[i], mr - i + 1);
        ans[i] = min(ans[i], mlen);
        if(ans[i] >= n) ans[i] = -1;
    }

    int x;
    while(m--) {
        x = read();
        printf("%d\n", ans[x]);
    }
    return 0;
}