题目大意
给你一个数列,让你求两个区间内各个数出现次数的乘积的和。
分析
数据范围告诉我们可以用莫队过。
我并不知道什么曼哈顿什么乱七八糟的东西,但是我们可以用容斥原理将这个式子展开来。
\[\sum^{\infty}_{0}get(l_1,r_1,x)\times get(l_2,r2,x)\]
上述式子是题目给出的式子。
我们都知道乘法具有交换律和分配律。
将式子展开成以下的性质
\[\sum^{\infty}_{x=0} get(0,r_1,x) \times get(0,r_2,x)-\sum^{\infty}_{x=0}get(0,l_1-1,x)\times get(0,r_2,x)-\sum^{\infty}_{x=0}get(0,r_1,x)\times get(0,l_2-1,x)+\sum^{\infty}_{x=0}get(0,l_1-1,x)\times get(0,l_2-1,x)\]
将询问拆成四个部分,最终一起解决,就可以了。
代码
#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define N 50005
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
struct Rec_Qus {
int l, r, id, blo, opt;
}q[N << 2];
int Dl[N], Dr[N], a[N];
ll res, ans[N];
int n, m, tot, block;
bool cmp(Rec_Qus A, Rec_Qus B) {
return (A.blo == B.blo)? (A.r < B.r): (A.blo < B.blo);
}
void AddL(int x) { res += Dr[a[x]]; ++ Dl[a[x]]; }
void AddR(int x) { res += Dl[a[x]]; ++ Dr[a[x]]; }
void DecL(int x) { res -= Dr[a[x]]; -- Dl[a[x]]; }
void DecR(int x) { res -= Dl[a[x]]; -- Dr[a[x]]; }
int main() {
ms(Dl, 0); ms(Dr, 0);
read(n); block = sqrt(n);
for (int i = 1; i <= n; i ++) read(a[i]);
read(m);
tot = 0;
for (int i = 1; i <= m; i ++) {
int l1, r1, l2, r2;
read(l1); read(r1); read(l2); read(r2);
q[++ tot] = (Rec_Qus) {l1 - 1, l2 - 1, i, (l1 - 2) / block + 1, 1};
q[++ tot] = (Rec_Qus) {r1, r2, i, (r1 - 1) / block + 1, 1};
q[++ tot] = (Rec_Qus) {l1 - 1, r2, i, (l1 - 2) / block + 1, -1};
q[++ tot] = (Rec_Qus) {r1, l2 - 1, i, (r1 - 1) / block + 1, -1};
}
sort(q + 1, q + 1 + tot, cmp);
int l = 0, r = 0;
for (int i = 1; i <= tot; i ++) {
while (r < q[i].r) AddR(++ r);
while (l > q[i].l) DecL(l --);
while (r > q[i].r) DecR(r --);
while (l < q[i].l) AddL(++ l);
ans[q[i].id] += q[i].opt * res;
}
for (int i = 1; i <= m; i ++) printf("%lld\n", ans[i]);
return 0;
}