「Luogu P5268」[SNOI2017]一个简单的询问

给定一个长度为$n$的序列$a$和$q$组询问,对于每组询问,给定$l_1,r_1,l_2,r_2$,求

其中,$\operatorname{get}(l,r,x)$表示在区间$[l,r]$中,数字$x$出现的次数。

注意:答案有可能超过$\texttt{int}$的最大值。

$\texttt{Data Range:}n,q\leq 5\times 10^4,1\leq a_i\leq n,1\leq l_1\leq r_1\leq n,1\leq l_2\leq r_2\leq n$

链接

Luogu P5268

BZOJ 5016

题解

文化课选手$\texttt{Karry5307}$终于更博了qwq!

首先,显然会有

右边的和式是可以拆成前缀和的形式的,就暴力拆一下,于是有

我们定义一个$\operatorname{g}(r,x)=\operatorname{get}(1,r,x)$,拆一下式子,有

展开一下里面的括号

拆成四个询问维护一下就好了

这里说说转移。

首先考虑从$\sum\limits_{x=0}^{\infty}\operatorname{g}(l,x)\operatorname{g}(r,x)$转移到$\sum\limits_{x=0}^{\infty}\operatorname{g}(l+1,x)\operatorname{g}(r,x)$会发生什么。

为了接下来好懂,这里开两个数组,$cntl$和$cntr$。$cntl_i$指$a_1\sim a_l$中$i$的出现次数,$cntr_i$,相应的为$a_1\sim a_r$中$i$的出现次数。

不难发现

这个的话,把求和符号展开一下就行了。

所以说,这样的转移应该是$++cntl_{a_{l+1}},res+=cntr_{a_{l+1}}$的。

剩下三种情况在这里就不详细解释了,推的方法也是这个样子的。

于是就可以完结撒花了qwq!

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=5e4+51;
struct Query{
ll l,r,ord,sign;
inline bool operator <(const Query &rhs)const;
};
Query qry[MAXN<<2];
ll cnt,qcnt,qtot,blockSize,l,r,lx,rx,ptrl,ptrr;
li ress;
ll num[MAXN],cntl[MAXN<<2],cntr[MAXN<<2];
li res[MAXN<<2];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline bool Query::operator <(const Query &rhs)const
{
return (r/blockSize)==(rhs.r/blockSize)?l<rhs.l:r<rhs.r;
}
inline void add(ll cur,ll op)
{
op?++cntr[num[cur]]:++cntl[num[cur]];
ress+=op?cntl[num[cur]]:cntr[num[cur]];
}
inline void del(ll cur,ll op)
{
ress-=op?cntl[num[cur]]:cntr[num[cur]];
op?cntr[num[cur]]--:cntl[num[cur]]--;
}
int main()
{
blockSize=sqrt((cnt=read()));
for(register int i=1;i<=cnt;i++)
{
num[i]=read();
}
qcnt=read();
for(register int i=0;i<qcnt;i++)
{
l=read(),r=read(),lx=read(),rx=read();
qry[++qtot]=(Query){r,rx,i,1};
qry[++qtot]=(Query){l-1,rx,i,-1};
qry[++qtot]=(Query){r,lx-1,i,-1};
qry[++qtot]=(Query){l-1,lx-1,i,1};
}
for(register int i=1;i<=qtot;i++)
{
if(qry[i].l<qry[i].r)
{
swap(qry[i].l,qry[i].r);
}
}
sort(qry+1,qry+qtot+1);
for(register int i=1;i<=qtot;i++)
{
while(ptrl<qry[i].l)
{
add(++ptrl,0);
}
while(ptrl>qry[i].l)
{
del(ptrl--,0);
}
while(ptrr<qry[i].r)
{
add(++ptrr,1);
}
while(ptrr>qry[i].r)
{
del(ptrr--,1);
}
res[qry[i].ord]+=qry[i].sign*ress;
}
for(register int i=0;i<qcnt;i++)
{
printf("%lld\n",res[i]);
}
}