莫队入门 | P1972 HH的项链

Xeqwq · 2022-05-04 20:31:34 · 个人记录

博客食用更佳
前置知识：分块。

莫队

OI-wiki
由莫涛~~神仙老爷~~发明的算法。这是一种离线分治算法，即先收集到所有的询问，然后自己通过排序来处理回答询问的顺序。
模板题：
SP3267 D-query
P1972 HH的项链
内容完全一样，不过第二题在2021年被lxl加了数据卡了莫队，~~各种乱搞优化似乎都过不了了~~。

问题描述：

现有共有 n 项的数组 a ，对它进行 m 次询问，每次询问 l,r 之间有多少个不同的数。
数据规模：1 \le n,m,a_i \le 10^6

方法：

1.暴力，时间复杂度 O(nm) ， TLE 安排。

2.莫队
开个桶，记录每个数在当前区间（不是目标区间）的出现次数，变量 now 记录当前区间内出现的不同的数的种数。
我们每次不用求出冗余的部分，可以从上次询问开始。对询问排序的方法我们后续讨论。

int l=0,r=-1;//避免莫队玄学bug，一般习惯这样起手
void add(int p)//当前区间加上这个位置的值
{
    if(!cnt[a[p]]) now++;
    cnt[a[p]]++;
}
void del(int p)//当前区间减去这个位置的值
{
    if(cnt[a[p]]==1) now--;
    cnt[a[p]]--;
}
struct Node
{
    int l,r,id;
    //l和r是查询范围，id是查询序号，这样在排序、计算之后合起来回答的时候可以知道哪个结果是第几次查询的。
}q[Maxn];//询问
for(int i=1;i<=m;i++)//main函数中的部分
{
    while(q[i].r>r) add(++r);//当前右边界边向目标右边界右移
    while(q[i].r<r) del(r--);//当前右边界边向目标右边界左移
    while(q[i].l>l) del(l++);//当前左边界边向目标左边界右移
    while(q[i].l<l) add(--l);//当前左边界边向目标左边界左移
    ans[q[i].id]=now;
}

这也是最基本的莫队模板。

3.我们再来优化。
想想之前的方法哪里有疏漏？
顺序。如果给的询问是这样的：

1 2
999999 1000000
3 4
999997 999998
......

死因：反复拉扯。所以我们必须要排序。
如果按照左端点排序，右边反复拉扯还是可以把复杂度打回 O(n^2) ，右端点同理。
找到了一种合理一些的排序方法：分块后，按照左端点所在块递增排序，左端在同块的时候右端递增。这样的话就不会因为左边一小点差距然后被拉来拉去，可以放过左端点一小点的差距，在每次都微调一下，右端点放开跑也不会折返太多。

bool operator<(Node n1,Node n2)
{
    return (k[n1.l]^k[n2.l])?k[n1.l]<k[n2.l]:n1.r<n2.r;
}

另外，在明白了莫队的基本原理之后，也可以试试这种排序方法：

bool operator<(Node n1,Node n2)
{
    return (k[n1.l]^k[n2.l])?k[n1.l]<k[n2.l]:((k[n1.l]&1)?n1.r < n2.r : n1.r > n2.r);
}

左端点在奇数块的时候右端递增排序，左端点在偶数块的时候右端点递减排序。这样可以在左端点换块的时候右端点换向，来回的时候都可以计算区间结果，不用右端点无谓地回来再向右来浪费时间。

开桶。开桶导致时间复杂度很高，因为我们要频繁地改 cnt 。
有没有方法能优化这一步：有。
摒弃桶的方法，预处理记录每一个位置的前一个和后一个和它数一样的位置。不用每次移动的时候记录和判断cnt的数量，我们可以用这种方法（以左端点向右从 l 移动到 l+1 为例，右端点及其它方向同理）：
记 l 位置的值为 col ，下一个 col 在坐标为 nxt 的位置。
若 nxt \le r ，则说明在 [l,r] 之内还有 col 这个值。
反之若 nxt > r ，则说明在 [l,r] 之内没有 col 这个值，同时 now-- 。
参考代码：（为了调掉玄学 bug ，我~~冒着被大家喷的风险~~做了0打头处理）

memset(last,0xff,sizeof(last));
for(int i=0;i<n;i++)
{
    pre[i]=last[a[i]];
    last[a[i]]=i;
    if(pre[i]>=0) nxt[pre[i]]=i;
    nxt[i]=n;
}//预处理部分
//脑袋转不过来的可以打开excel表格，对着样例模拟数据
//我打了半个小时，我比较蒻

for(int i=1;i<=m;i++)
{
    while(l<q[i].l) now-=(r<nxt[l++]);
    while(l>q[i].l) now+=(r<nxt[--l]);
    while(r<q[i].r) now+=(l>pre[++r]);
    while(r>q[i].r) now-=(l>pre[r--]);
    ans[q[i].id]=now;
}//相应地，后面的挪左右指针也做了处理

再带上 register inline IO优化 之类的基础优化操作，我将之前总用时26s调到了8.30s,那些卡莫队的数据最大的点我也就 686ms ，顺利 AC 。
AC记录

祝你好运qwq~。

莫队入门 | P1972 HH的项链

莫队

问题描述：

方法：

End