Untitled
unknown
plain_text
23 days ago
4.4 kB
1
Indexable
Never
#include<bits/stdc++.h> using namespace std; #define int long long struct Trie { static const int B = 31; // The number of bits we are considering, adjust based on your data type. struct node { node* nxt[2]; // Pointers to child nodes int sz; // The size/count of elements in the subtrie rooted at this node node() { nxt[0] = nxt[1] = nullptr; sz = 0; } }*root; Trie() { root = new node(); } void insert(int val) { node* cur = root; cur->sz++; for (int i = B - 1; i >= 0; i--) { int b = (val >> i) & 1; if (cur->nxt[b] == nullptr) cur->nxt[b] = new node(); cur = cur->nxt[b]; cur->sz++; } } void erase(int val) { node* cur = root; cur->sz--; for (int i = B - 1; i >= 0; i--) { int b = (val >> i) & 1; cur = cur->nxt[b]; cur->sz--; } } int query(int x, int k) { // Number of values such that val ^ x < k node* cur = root; int ans = 0; for (int i = B - 1; i >= 0; i--) { if (cur == nullptr) break; int b1 = (x >> i) & 1; int b2 = (k >> i) & 1; if (b2 == 1) { if (cur->nxt[b1]) ans += cur->nxt[b1]->sz; cur = cur->nxt[!b1]; } else cur = cur->nxt[b1]; } return ans; } int get_max(int x) { // Returns maximum of val ^ x node* cur = root; int ans = 0; for (int i = B - 1; i >= 0; i--) { int k = (x >> i) & 1; if (cur->nxt[!k]) { cur = cur->nxt[!k]; ans = (ans << 1) | 1; } else { cur = cur->nxt[k]; ans <<= 1; } } return ans; } int get_min(int x) { // Returns minimum of val ^ x node* cur = root; int ans = 0; for (int i = B - 1; i >= 0; i--) { int k = (x >> i) & 1; if (cur->nxt[k] && cur->nxt[k]->sz) { cur = cur->nxt[k]; ans <<= 1; } else { cur = cur->nxt[!k]; ans = (ans << 1) | 1; } } return ans; } void del(node* cur) { for (int i = 0; i < 2; i++) if (cur->nxt[i]) del(cur->nxt[i]); delete(cur); } }; int cntSmaller(Trie::node* root, int N, int K) { int cntPairs = 0; for (int i = 30; i >= 0 && root; i--) { bool x = N & (1 << i); bool y = K & (1 << i); if (y) { if (root->nxt[x]) { cntPairs += root->nxt[x]->sz; } root = root->nxt[1 - x]; } else { root = root->nxt[x]; } } return cntPairs; } typedef long long ll; const int N=1e4+5; const int Qu=2e5+5; const int SQ=100; struct Query{ int l,r,q_idx,blk_idx; Query(){} Query(int _l,int _r,int _q_idx) { l=_l,r=_r,q_idx=_q_idx,blk_idx=_l/SQ; } bool operator<(const Query&Q)const{ if(blk_idx!=Q.blk_idx) { return blk_idx<Q.blk_idx; } return r<Q.r; } }; ll n,q,k,arr[N],res=0,ans[Qu];Query qu[Qu]; Trie t; map<int,int>frq; ll calc(int idx) { return arr[idx]*frq[arr[idx]]*frq[arr[idx]]; } long long output=0; void add(int idx) { frq[arr[idx]]++; output+= cntSmaller(t.root,arr[idx],k); t.insert(arr[idx]); } void remove(int idx) { frq[arr[idx]]--; t.erase(arr[idx]); output-= cntSmaller(t.root,arr[idx],k); } void MO_process() { sort(qu,qu+q); int l=1,r=0; for(int i=0;i<q;i++) { while(l>qu[i].l) add(--l); while(r<qu[i].r) add(++r); while(l<qu[i].l) remove(l++); while(r>qu[i].r) remove(r--); ans[qu[i].q_idx]=output; } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t; cin>>t; while(t--) { cin >> n >> k >> q; for (int i = 0; i < n; i++) { cin >> arr[i]; } for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; qu[i] = Query(--l, --r, i); } MO_process(); for (int i = 0; i < q; i++) { cout << ans[i] << ' '; } cout << '\n'; } return 0; }
Leave a Comment