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

发表于 |
字数统计: 934 | 阅读时长 ≈ 5

给定一个长度为$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]);
    }
}