一直都说学莫队,直到现在才学,训练的时候就跪了 T_T,其实挺简单的感觉。其实训练的时候也看懂了,一知半解,就想着先敲。(其实这样是不好的,应该弄懂再敲,以后要养成这个习惯)
前缀异或也很快想出来,结果没弄好边界,也是对前缀异或和莫队的不熟练。
CF 的E题,给定区间中有多少子区间个数异或等于k
容易想到的是预处理前缀异或值,求解区间[L, R]的贡献,相当于在前缀异或值[L – 1, R]中任取两个数,异或值等于k
知道区间[L, R]的贡献,可以O(1)知道[L – 1, R]和[L, R + 1]的贡献,就可以用莫队了
把询问分块,每块大小sqrtn,然后块内按右端点排序,然后two pointer维护即可。
因为块内的大小是sqrtn,然后每次移动只会移动sqrtn的大小。复杂度是nsqrtn
两题都是莫队的一个应用,离线查询区间
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = + ;
struct Query {
int L, R, id;
}node[maxn];
int a[maxn];
int n, m, k, magic;
bool cmp(struct Query a, struct Query b) {
if (a.L/magic != b.L/magic) return a.L/magic < b.L/magic;
else return a.R < b.R;
}
LL ans[maxn];
LL num[maxn];
void calc() {
LL temp = ;
int L = , R = ;
num[] = ;
for (int i = ; i <= m; ++i) {
while (R < node[i].R) {
++R;
temp += num[a[R] ^ k];
num[a[R]]++;
}
while (R > node[i].R) { // differ sqrt
num[a[R]]--;
temp -= num[a[R] ^ k];
--R;
}
while (L < node[i].L) {
num[a[L - ]]--;
temp -= num[a[L - ] ^ k];
++L;
}
while (L > node[i].L) {
--L;
temp += num[a[L - ] ^ k];
num[a[L - ]]++;
}
ans[node[i].id] = temp;
}
}
void work() {
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= n; ++i) {
scanf("%d", a + i);
a[i] ^= a[i - ];
// printf("%d ", a[i]);
}
magic = (int)sqrt(n);
for (int i = ; i <= m; ++i) {
scanf("%d%d", &node[i].L, &node[i].R);
node[i].id = i;
}
sort(node + , node + + m, cmp);
calc();
for (int i = ; i <= m; ++i) {
cout << ans[i] << endl;
}
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 5e5 + ;
struct Query {
int L, R, id;
LL a, b;
void init() {
if (a != ) {
LL t = __gcd(a, b);
a /= t, b /= t;
} else b = ;
}
}node[maxn], ans[maxn];
int n, m, magic;
int a[maxn];
LL num[maxn];
bool cmp(struct Query a, struct Query b) {
if (a.L/magic != b.L/magic) return a.L/magic < b.L/magic;
else return a.R < b.R;
}
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
scanf("%d", a + i);
}
for (int i = ; i <= m; ++i) {
scanf("%d%d", &node[i].L, &node[i].R);
node[i].id = i;
}
magic = sqrt(n);
sort(node + , node + + m, cmp);
int L = , R = ;
LL res = ;
for (int i = ; i <= m; ++i) {
while (R < node[i].R) {
++R;
res -= num[a[R]] * num[a[R]] - num[a[R]];
num[a[R]]++;
res += num[a[R]] * num[a[R]] - num[a[R]];
}
while (R > node[i].R) { //不同块之间才会出现
res -= num[a[R]] * num[a[R]] - num[a[R]];
num[a[R]]--;
res += num[a[R]] * num[a[R]] - num[a[R]];
R--;
}
while (L < node[i].L) { //每个块之间只是按照R排序的
res -= num[a[L]] * num[a[L]] - num[a[L]];
num[a[L]]--;
res += num[a[L]] * num[a[L]] - num[a[L]];
L++;
}
while (L > node[i].L) {
--L;
res -= num[a[L]] * num[a[L]] - num[a[L]];
num[a[L]]++;
res += num[a[L]] * num[a[L]] - num[a[L]];
}
ans[node[i].id].a = res, ans[node[i].id].b = 1LL * (node[i].R - node[i].L + ) * (node[i].R - node[i].L);
}
for (int i = ; i <= m; ++i) {
ans[i].init();
printf("%lld/%lld\n", ans[i].a, ans[i].b);
}
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}