E. Iva Pav(线段树 + 二分)

传送门

题意

一个长度为n的数组a,给定一些询问，每次询问从下标x开始的区间，其区间&的和大于等于k的最大下标是多少

题目有很多种解法，比如(st表 + 二分，-----)

本次以线段树 + 二分为例(赛时写的这个,没往别的方向想)，可以作为线段树的练习题

pushdown操作没有用，可以删掉

解题思路：给定x,找出x~n的区间最大与。首先需要知道的是，与操作，越与越小，所以如果区间只有下标x自己的时候都没有超过k的话，那么无论怎么与都是不超过k的，所以在二分开始的时候判断-1的情况，然后用线段树查询区间与，降低复杂度。总复杂度为O(q * logn * logn)，5s足够了

#include using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";struct SegmentTree {const int n;struct Node {int l, r;i64 sum, add;};std::vector<Node> tr;SegmentTree(int n) : n(n), tr(4 << std::__lg(n)) {}SegmentTree(std::vector<i64> init) : SegmentTree(init.size() - 1) {std::function<void(int, int, int)> build = [&](int u, int l, int r) {tr[u].l = l, tr[u].r = r;if(l == r) tr[u].sum = init[l];else {int mid = l + r >> 1;build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);pushup(u);}};build(1, 1, n);}void pushup(int u) {tr[u].sum = tr[u << 1].sum & tr[u << 1 | 1].sum; }void pushdown(int u) {if(tr[u].add) {tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;tr[u << 1].add += tr[u].add;tr[u << 1 | 1].add += tr[u].add;tr[u].add = 0;}}void modify(int u, int l, int r, i64 k) {if(tr[u].l >= l && tr[u].r <= r){tr[u].sum += (tr[u].r - tr[u].l + 1) * k;tr[u].add += k;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r, k);if(r > mid) modify(u << 1 | 1, l, r, k);pushup(u);}}i64 query(int u, int l, int r) {if(tr[u].l > r || tr[u].r < l) return (1 << 31) - 1;if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;return (query(u << 1, l, r) & query(u << 1 | 1, l, r));}
};
//SegmentTree seg(w);  void solve() {int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i ++) {std::cin >> a[i];}SegmentTree seg(a);int q;std::cin >> q;while (q -- ) {int x, k;std::cin >> x >> k;if (a[x] < k) {std::cout << "-1 ";continue;}int l = x,r = n;auto check = [&](int mid) {int t = seg.query(1,x,mid);if (t >= k) {return true;}return false;};while (l < r) {int mid = l + r + 1>> 1;if (check(mid)) {l = mid;} else {r = mid - 1;}}if (seg.query(1,x,l) >= k) {std::cout << l << " ";}}std::cout << "\n";
}       signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr); int T = 1;std::cin >> T;while (T -- ) {solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！