目录
题目概述
原题参考：E. Iva & Pav
给出长度为n的数组和m次询问，每次询问包括一个左区间l和一个整数k，要求给出最大的右区间的值使得al & al+1 &... & ar >= k
思路想法
其实对二进制的几种运算随意看一下，可以发现：随着长度的增加，按位与的结果是保持单调不增，按位或则是保持单调不减，因此，对于一个区间[lt, rt]，它的元素的按位与是有单调性的，单调性就可以想着一个二分答案，我们可以先对数组进行预处理，记录每一次数组到之后的一个区间的按位与的值，然后对于每一次询问，可以使用一个极大值按位与，进行二分答案
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
int n, m, a[N], st[N][27];
int query(int lt, int res) {
ll cmp = (1ll << 34) - 1;
for(int i=20; i>=0; i--) {
if((cmp&st[lt][i]) >= res) {
cmp &= st[lt][i];
lt += (1<<i);
}
}
if((cmp&a[lt]) < res) lt --;
return lt;
}
void solve() {
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a[i];
st[i][0] = a[i];
}
for(int j=1; j<=20; j++) {
for(int i=1; i+(1<<j)-1<=n; i++)
st[i][j] = (st[i][j-1] & st[i+(1<<(j-1))][j-1]);
}
cin >> m;
while(m --) {
int res, lt;
cin >> lt >> res;
if(a[lt] < res) cout << -1 << " ";
else cout << query(lt, res) << " ";
}
for(int i=1; i<=n; i++) {
for(int j=0; j<=20; j++) a[i] = 0, st[i][j] = 0;
}
cout << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
做题反思
这个还真是老题中的老题（对我而言），很早之前就挂在我的主页那里，一直没有解决，看到之前写的暴力有点想笑，有意思。今天突然想把他尝试解决，打开看了一下题目，想到了区间的几种操作和二分，开开心心写完。呸，其实调了一会bug，原因是其中的一个按位与和大于的优先级的问题
标签：const,Iva,Pav,int,st,lt,按位,define From： https://www.cnblogs.com/notalking569/p/18049268