题解 [牛客IOI周赛16-提高组 C] 最小鸽
最小鸽
https://ac.nowcoder.com/acm/contest/5388/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; }