站长之家是什么,网站建设验收表,新媒体营销的方式,南通关键词优化软件I love counting HDU - 6964
题意#xff1a;
一个数组c#xff0c;给你了(l,r)一个范围#xff0c;问这个范围内满足ci ^ a b数量的有多少#xff1f;
题解#xff1a;
我第一反应是莫队#xff0c;直接莫队得到结果#xff0c;但是发现样例不对#xff0c;再…I love counting HDU - 6964
题意
一个数组c给你了(l,r)一个范围问这个范围内满足ci ^ a b数量的有多少
题解
我第一反应是莫队直接莫队得到结果但是发现样例不对再调了半天后我突然想明白对于每个询问a和b是不一样的也就是说莫队是通过询问来调整区间大小上一次询问满足情况的答案不一定适用于下一个询问所以每次都要重新询问所以就不是简单的莫队 方法一 不能直接莫队那我们就改改用莫队分块来做我们用莫队维护每次询问的每个块内元素种类以及每个元素本身的数量 然后我们开始单独分析式子c ^ a b 对于等号情况我们单独考虑先只考虑小于号 对于第j位 如果b是1a是1那么c是1一定小于b 如果b是1a是0那么c是0一定小于b 如果b是0a是1那么c只能是1才有可能小于b 如果b是0a是0那么c只能是0才有可能小于b 我们统计一定小于的情况不断向后找小于的情况。用分块来计算小于的情况比如c的第三位是1例如0100那么从0100到0111都是满足题意的我们用一个前缀和来计算这个区间。前缀和内是用分块之前我们已经统计了每个块的大小还有每个元素的数量。 最后还有c ^ a b的情况这简单c a ^ b看是否存在这个c就完事了 相当于莫队都预处理好给后面直接用 方法二 刚才我分析第j位的那些步骤不正是字典树的步骤所以这个题也可以用字典树来做用树状数组维护前缀和 具体做法 用vector存每个右端点所对应的当前询问对应的lab用vis数组记录当前值是否出现过用树状数组维护前缀答案就是cal(i)-cal(l-1) 这里树状数组的作用单纯就是算区间和
代码
莫队分块
#includeiostream
#includecstring
#includealgorithm
#includecstdio
#includecmath
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 ps;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;
}
字典树线段树
#includeiostream
#includecstring
#includecstdio
#includealgorithm
#includevectorusing 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];
vectornode 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 ressum[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;
}
