LibreOJ 2254.「SNOI2017」一个简单的询问

好久没写过莫队了,今天回来练练手。
其实这题我早就想写了,但是因为鸽子属性咕了很久……
闲来无事,没想到十分钟左右就写完了(

f(i,x)=get(1,i,x)f(i,x) = \text{get}(1,i,x)

那么有

那么我们把每个询问 (l1,r1,l2,r2)(l_1,r_1,l_2,r_2) 都拆成 (r1,r2)(r1,l21)(l11,r2)+(l11,l21)(r_1,r_2) - (r_1,l_2 - 1) - (l_1 - 1,r_2) + (l_1 - 1,l_2 - 1) 的形式。
就能得到 4Q4Q 个只跟两个位置有关的询问。
然后发现询问里面有乘,没法用数据结构维护这个东东。
考虑上莫队。

当然和一般的莫队不同,稍微注意一下就好了。
只要理解了莫队应该都很容易写出来。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5e4;
const int Q = 5e4;
int n,q,a[N + 5],block,pos[N + 5];
int cnt[2][N + 5];
long long cur,ans[Q + 5];
inline void add(int x,int op)
{
cur -= (long long)cnt[0][a[x]] * cnt[1][a[x]];
++cnt[op][a[x]];
cur += (long long)cnt[0][a[x]] * cnt[1][a[x]];
}
inline void del(int x,int op)
{
cur -= (long long)cnt[0][a[x]] * cnt[1][a[x]];
--cnt[op][a[x]];
cur += (long long)cnt[0][a[x]] * cnt[1][a[x]];
}
struct s_query
{
int l,r,id,w;
inline bool operator<(const s_query &o) const
{
return pos[l] < pos[o.l] || (pos[l] == pos[o.l] && r < o.r);
}
} qry[(Q << 2) + 10];
int main()
{
scanf("%d",&n);
block = pow(n,2.0 / 3);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
scanf("%d",&q);
int l1,r1,l2,r2;
for(register int i = 1;i <= q;++i)
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
qry[(i - 1) * 4 + 1] = (s_query){r1,r2,i,1};
qry[(i - 1) * 4 + 2] = (s_query){r1,l2 - 1,i,-1};
qry[(i - 1) * 4 + 3] = (s_query){l1 - 1,r2,i,-1};
qry[i * 4] = (s_query){l1 - 1,l2 - 1,i,1};
}
sort(qry + 1,qry + 4 * q + 1);
for(register int i = 1,l = 0,r = 0;i <= q * 4;++i)
{
while(l < qry[i].l)
add(++l,0);
while(r < qry[i].r)
add(++r,1);
while(l > qry[i].l)
del(l--,0);
while(r > qry[i].r)
del(r--,1);
ans[qry[i].id] += cur * qry[i].w;
}
for(register int i = 1;i <= q;++i)
printf("%lld\n",ans[i]);
}

arknights