I love counting HDU - 6964

題意：

一個數組c，給你了(l,r)一個范圍，問這個范圍內滿足ci ^ a < b數量的有多少？

題解：

我第一反應是莫隊，直接莫隊得到結果，但是發現樣例不對，再調了半天后我突然想明白，對于每個詢問a和b是不一樣的，也就是說莫隊是通過詢問來調整區間大小，上一次詢問滿足情況的答案不一定適用于下一個詢問，所以每次都要重新詢問，所以就不是簡單的莫隊
方法一：
不能直接莫隊，那我們就改改，用莫隊+分塊來做，我們用莫隊維護每次詢問的每個塊內元素種類，以及每個元素本身的數量
然后我們開始單獨分析式子c ^ a <= b
對于等號情況我們單獨考慮，先只考慮小于號
對于第j位
如果b是1，a是1，那么c是1，一定小于b
如果b是1，a是0，那么c是0，一定小于b
如果b是0，a是1，那么c只能是1才有可能小于b
如果b是0，a是0，那么c只能是0才有可能小于b
我們統計一定小于的情況，不斷向后找小于的情況。用分塊來計算小于的情況，比如c的第三位是1，例如0100，那么從0100到0111都是滿足題意的，我們用一個前綴和來計算這個區間。前綴和內是用分塊，之前我們已經統計了每個塊的大小，還有每個元素的數量。
最后還有c ^ a =b的情況，這簡單c = a ^ b，看是否存在這個c就完事了
相當于莫隊都預處理好，給后面直接用
方法二：
剛才我分析第j位的那些步驟，不正是字典樹的步驟，所以這個題也可以用字典樹來做，用樹狀數組維護前綴和
具體做法：
用vector存每個右端點所對應的當前詢問對應的l，a，b，用vis數組記錄當前值是否出現過，用樹狀數組維護前綴，答案就是cal(i)-cal(l-1)
這里樹狀數組的作用單純就是算區間和

代碼：

莫隊+分塊

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int N = 100010; int n, m, a[N], k, cnt[N], sum[N], c[2*N], ans[N];//c要開2N，因為2個1e5的數異或值可以大于1e5 // sum[i]表示塊內數的種類，c[i]表示每個i這個數的種類 struct query {int l, r, a, b, id;bool operator<(const query &b) const {if (l / k == b.l / k)return r < b.r;return l < b.l;} } q[N]; void add(int x) {if (++cnt[x] == 1)sum[x / k]++, c[x]++; } void sub(int x) {if (--cnt[x] == 0)sum[x / k]--, c[x]--; } int ask(int x) {int res = 0;for (int i = x / k * k; i <= x; i++)res += c[i];for (int i = 0; i < x / k; i++)res += sum[i];return res; } int main() {scanf("%d", &n);k = sqrt(n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b);q[i].id = i;}sort(q, q + m);int l = 1, r = 0;for (int i = 0; i < m; i++) {while (l > q[i].l)add(a[--l]);while (l < q[i].l)sub(a[l++]);while (r < q[i].r)add(a[++r]);while (r > q[i].r)sub(a[r--]);int s = 0;int a = q[i].a, b = q[i].b;for (int j = 19; j >= 0; j--) {int p=s;if (b >> j & 1) {if (a >> j & 1)p |= 1 << j;else s |= 1 << j;ans[q[i].id] += ask(p + (1 << j) - 1) - ask(p - 1);//第j位是1的答案數量 } else {if (a >> j & 1)s |= 1 << j;}}ans[q[i].id] += c[q[i].a ^ q[i].b];}for (int i = 0; i < m; i++)printf("%d\n", ans[i]);return 0; }

字典樹+線段樹

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector>using namespace std; const int N = 1e5 + 10; int tr[400 * N][2], rt[N], sum[400 * N], ans[N], pre[N], idx; int n, a[N], m; struct node {int l, a, b, id; } q[N]; vector<node> v[N];void insert(int &now, int x, int val) {if (!now)now = ++idx;int u = now;for (int i = 17; ~i; i--) {int p = val >> i & 1;if (!tr[u][p])tr[u][p] = ++idx;u = tr[u][p];sum[u] += x;} }void add(int pos, int x, int val) {for (int i = pos; i <= n; i += (i & -i))insert(rt[i], x, val); }int query(int u, int a, int b) {int res = 0;for (int i = 17; ~i; i--) {int p1 = a >> i & 1;int p2 = b >> i & 1;if (p2) {if (p1)res += sum[tr[u][1]], u = tr[u][0];else res += sum[tr[u][0]], u = tr[u][1];} else {if (p1)u = tr[u][1];else u = tr[u][0];}if(!u)break;}return res+sum[u]; }int ask(int p, int a, int b) {int res = 0;for (int i = p; i; i -= (i & -i))res += query(rt[i], a, b);return res; }int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);scanf("%d", &m);for (int i = 0; i < m; i++) {int l, r, a, b;scanf("%d%d%d%d", &l, &r, &a, &b);v[r].push_back({l, a, b, i});}for (int i = 1; i <= n; i++) {if (pre[a[i]])add(pre[a[i]], -1, a[i]);add(i, 1, a[i]);pre[a[i]] = i;for (auto j:v[i])ans[j.id] = ask(i, j.a, j.b) - ask(j.l - 1, j.a, j.b);}for (int i = 0; i < m; i++)printf("%d\n", ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的I love counting HDU - 6964的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。