做法:先按左端点排序,分成 $\sqrt{m}$ 块,每块内部按右端点排序,然后暴力处理每块第一个询问,通过第一个询问的结果更新其余询问。
by CEFqwq @ 2024-03-27 19:19:44
@[爱肝大模拟的tlxjy](/user/482610) 总感觉你这个莫队不太正宗……
by Brilliant11001 @ 2024-03-27 19:39:09
@[Brilliant11001](/user/602372) 第一次学/kk
by CEFqwq @ 2024-03-27 19:45:43
@[爱肝大模拟的tlxjy](/user/482610)
哥们这道题不用回滚莫队思想吧?
by Aventurine_stone @ 2024-03-27 19:55:52
@[爱肝大模拟的tlxjy](/user/482610) 感觉你这个做法复杂了,我没有怎么看懂
by Brilliant11001 @ 2024-03-27 19:56:33
@[yangyuchen666](/user/1041101) 什么是回滚莫队
by CEFqwq @ 2024-03-27 19:57:09
@[爱肝大模拟的tlxjy](/user/482610) 普通的莫队是将整个序列分块,将所有询问离线下来,按照左端点为第一关键字、右端点为第二关键字排序。维护左右指针,对于每个询问,将左右指针移动至与当前查询区间对齐从而求出答案。
by Brilliant11001 @ 2024-03-27 20:01:32
@[爱肝大模拟的tlxjy](/user/482610)
普通的莫队不应该逐个块处理,应该排序后就集中处理。 比如:
```cpp
l=1;
for(int k=1;k<=m;k++)
{
while(r<q[k].r)
add(a[++r]);
while(r>q[k].r)
del(a[r--]);
while(l<q[k].l)
del(a[l++]);
while(l>q[k].l)
add(a[--l]);
ans1[q[k].idx]=sum-(r-l+1),ans2[q[k].idx]=1ll*(r-l+1)*(r-l);
l==r?ans2[q[k].idx]=1:1;
}
```
by Aventurine_stone @ 2024-03-27 20:02:16
@[爱肝大模拟的tlxjy](/user/482610)
add表示加上这个数,del表示减去这个数。
哥们你如果是自己推的莫队思路的话,你可以先去看看别人的博客。
by Aventurine_stone @ 2024-03-27 20:03:54
@[yangyuchen666](/user/1041101) 但是为什么我这样写会 WA 呢(
好像写法本身没太大问题?
by CEFqwq @ 2024-03-27 20:08:00