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

https://ac.nowcoder.com/acm/contest/5388/C

• 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];

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() {
for(int i = 1; i <= n; ++i) {
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--) {