Untitled
unknown
plain_text
a year ago
3.2 kB
6
Indexable
#include<iostream> #include <bits/stdc++.h> #define ll long long #define ld long double #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int N = 3e5 + 6, mod = 1e9 + 7; int orTree[N << 2]; vector<pair<int, int>> basisTree[N << 2]; vector<pair<int,int>> mergeBasis(vector<pair<int,int>> a, vector<pair<int,int>> b) { vector<pair<int, int >> ret; for(auto p : a) { int val = p.second; for(auto x : ret) val = min(val, val ^ x.first); if(val) ret.push_back({val,p.second}); } for(auto p : b) { int val = p.second; for(auto x : ret) val = min(val, val ^ x.first); if(val) ret.push_back({val,p.second}); } return ret; } int a[N], n, q; void build(int node, int s, int e) { basisTree[node].clear(); if(s==e) { orTree[node] = a[s]; basisTree[node] = {{a[s], a[s]}}; return; } int md = (s + e) >> 1; build(node<<1,s,md); build(node<<1|1,md+1,e); orTree[node] = orTree[node << 1] | orTree[node << 1 | 1]; basisTree[node] = mergeBasis(basisTree[node << 1], basisTree[node << 1 | 1]); } void update(int node, int s, int e, int index, int val) { if(s==e) { orTree[node] = val; basisTree[node] = {{val, val}}; return; } int md = (s + e) >> 1; if(index <= md) update(node<<1,s,md,index,val); else update(node<<1|1,md+1,e,index,val); orTree[node] = orTree[node << 1] | orTree[node << 1 | 1]; basisTree[node] = mergeBasis(basisTree[node << 1], basisTree[node << 1 | 1]); } void pruneTree(int node, int s, int e, int l, int r, int val) { if(r < s || e < l) return; if((orTree[node] & val) == orTree[node])return; if(s==e) { orTree[node] &= val; basisTree[node] = {{orTree[node], orTree[node]}}; return; } int md = (s + e) >> 1; pruneTree(node<<1,s,md,l,r,val); pruneTree(node<<1|1,md+1,e,l,r,val); orTree[node] = orTree[node << 1] | orTree[node << 1 | 1]; basisTree[node] = mergeBasis(basisTree[node << 1], basisTree[node << 1 | 1]); } vector<pair<int, int>> query(int node, int s, int e, int l, int r) { if(l<=s&&e<=r) return basisTree[node]; int md = (s + e) >> 1; if(r <= md) return query(node<<1,s,md,l,r); else if(l > md) return query(node<<1|1,md+1,e,l,r); return mergeBasis(query(node<<1,s,md,l,r), query(node<<1|1,md+1,e,l,r)); } void doWork() { cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i]; build(1,1,n); while (q--) { int tp,l,r; cin >> tp >> l >> r; if(tp==1) { int x; cin >> x; pruneTree(1,1,n,l,r,x); } else if(tp==2) { update(1,1,n,l,r); } else { auto p = query(1,1,n,l,r); int ans = 0; for(auto x : p)ans = max(ans, x.first ^ ans); cout << ans << '\n'; } } } int main() { IO int t = 1; cin >> t; // return 0; for (int i = 1; i <= t; i++) { // cout << "Case #" << i << ": "; doWork(); } } // 6 4 3 1 2
Editor is loading...
Leave a Comment