题目
传送门 to luogu
思路
首先它是个莫队的题。（为什么？我也不知道 😃）
但是 莫队只能处理两个变量 的询问（并且任意一个变量的移动对答案的影响可以快速计算，一般是
O
(
1
)
\mathcal O(1)
O(1) ）。所以只好把这个式子变换一下。记
f
(
m
,
x
)
=
∑
j
=
1
m
[
a
j
=
x
]
f(m,x)=\sum_{j=1}^{m}[a_j=x]
f(m,x)=∑j=1m[aj=x] ，则
=
∑
x
=
0
∞
g
e
t
(
l
1
,
r
1
,
x
)
⋅
g
e
t
(
l
2
,
r
2
,
x
)
=
[
f
(
r
1
,
x
)
−
f
(
l
1
−
1
,
x
)
]
⋅
[
f
(
r
2
,
x
)
−
f
(
l
2
−
1
,
x
)
]
=
f
(
r
1
,
x
)
⋅
f
(
r
2
,
x
)
+
⋯
\begin{aligned} &=\sum_{x=0}^{\infty}get(l_1,r_1,x)\cdot get(l_2,r_2,x)\\ &=[f(r_1,x)-f(l_1-1,x)]\cdot[f(r_2,x)-f(l_2-1,x)]\\ &=f(r_1,x)\cdot f(r_2,x)+\cdots \end{aligned}
=x=0∑∞get(l1,r1,x)⋅get(l2,r2,x)=[f(r1,x)−f(l1−1,x)]⋅[f(r2,x)−f(l2−1,x)]=f(r1,x)⋅f(r2,x)+⋯
我实在是不想打啦 全部打出来太长了。
反正这样就变成两个变量啦！
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std
;
const int MaxN
= 50000, SqrtN
= 230;
int n
, q
, a
[MaxN
];
struct Query
{
int l
, r
, id
; Query(){}
Query(int L
,int R
,int I
):l(L
),r(R
),id(I
){
if(l
< r
) swap(l
,r
);
}
bool operator<(const Query
&that
)const{
if(l
/SqrtN
!= that
.l
/SqrtN
)
return l
/SqrtN
< that
.l
/SqrtN
;
if((l
/SqrtN
)&1)
return r
> that
.r
;
return r
< that
.r
;
}
}query
[MaxN
<<2];
void init(){
scanf("%d",&n
);
for(int i
=0; i
<n
; ++i
)
scanf("%d",&a
[i
]);
scanf("%d",&q
);
for(int i
=0,l1
,r1
,l2
,r2
; i
<q
; ++i
){
scanf("%d %d %d %d",&l1
,&r1
,&l2
,&r2
);
l1
-= 2; l2
-= 2; -- r1
; -- r2
;
query
[i
<<2|0] = Query(r1
,r2
,i
<<1|1);
query
[i
<<2|1] = Query(r1
,l2
,i
<<1);
query
[i
<<2|2] = Query(l1
,r2
,i
<<1);
query
[i
<<2|3] = Query(l1
,l2
,i
<<1|1);
}
sort(query
,query
+(q
<<2));
}
long long ans
;
long long answer
[MaxN
]; int cnt
[MaxN
][2];
void add(int id
,int f
){
ans
+= cnt
[a
[id
]][f
^1];
++ cnt
[a
[id
]][f
];
}
void release(int id
,int f
){
ans
-= cnt
[a
[id
]][f
^1];
-- cnt
[a
[id
]][f
];
}
void Mo(){
int nowl
= -1, nowr
= -1;
for(int i
=0; i
<(q
<<2); ++i
){
while(nowr
< query
[i
].r
)
add(++ nowr
,1);
while(query
[i
].r
< nowr
)
release(nowr
--,1);
while(nowl
< query
[i
].l
)
add(++ nowl
,0);
while(query
[i
].l
< nowl
)
release(nowl
--,0);
answer
[query
[i
].id
>>1] += ((query
[i
].id
&1)*2-1)*ans
;
}
for(int i
=0; i
<q
; ++i
)
printf("%lld\n",answer
[i
]);
}
int main(){
init();
Mo();
return 0;
}
