@[yaodiguoan](/user/1023793) 这道题莫队好像过不了了
by highkj @ 2024-04-26 15:01:23
好吧，我放弃了，$\mathcal O(n\sqrt{n})$ 的莫队过了简直就是一个奇迹！（（（
by lcfollower @ 2024-04-26 16:47:02
@[zjhs005](/user/1296826) 如果。
by lcfollower @ 2024-04-26 16:47:17
@[highkj](/user/381053) 但我看到有人用莫队过了啊，而且思路跟我差不多
by danlao @ 2024-04-26 17:36:32
@[yaodiguoan](/user/1023793) 你把扩大区间写前面，缩小的写后面（具体原因见OI-WIKI），在所有函数前十inline，实测44pte。
by lcfollower @ 2024-04-27 09:59:39
加上register。
by lcfollower @ 2024-04-27 10:00:09
@[danlao](/user/1023793) <https://www.luogu.com.cn/record/146121164>
```cpp
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
#include <cstdio>
#include <cctype>
namespace io
{
constexpr int BUFSIZE = 21 << 20;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
inline void init()
{
it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
}
inline char getch()
{
// if (is == it)
// it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
return /* (is == it) ? EOF : */*is++;
}
inline int getint()
{
int res = 0;
char ch = getch();
while (!(isdigit(ch))/* and ch != EOF */)
ch = getch();
while (isdigit(ch))
res = res * 10 + (ch - '0'), ch = getch();
return res;
}
inline void flush()
{
fwrite(obuf, 1, os - obuf, stdout);
os = obuf;
}
inline void putch(char ch)
{
*os++ = ch;
// if (os == ot)
// flush();
}
inline void putint(int res)
{
char q[10];
int top;
top = 0;
while (res)
q[top++] = res % 10 + '0', res /= 10;
while (top--)
putch(q[top]);
}
}
constexpr int N=1145141,A=1145141,M=1145141;
int n,m;
int a[N];
int S,bel[N];
struct query
{
int l,r,id;
};
query q[M];
int ans[M];
int /* cnt[A], */bt=0;
int lst[A],pre[N],nxt[N];
void mt()
{
S=int(ceil(n*pow(m,-0.5)));// S=sqrt(n)
for(int i=1;i<=n;i++)bel[i]=(i-1)/S+1;
sort(q+1,q+m+1,
[](const query &x,const query &y)-> bool
{
return ((bel[x.l]!=bel[y.l])?
bel[x.l]<bel[y.l]:
((bel[x.l]&1)?
x.r<y.r:
x.r>y.r));
});
for(int i=1;i<=n;i++)pre[i]=lst[a[i]],lst[a[i]]=i;
fill(lst,lst+A,0x3f3f3f3f);
for(int i=n;i;i--)nxt[i]=lst[a[i]],lst[a[i]]=i;
for(int i=1,l=1,r=0;i<=m;i++)
{
#define q q[i]
// if(abs(q.l-l)+abs(q.r-r)>(r-l+1)+(q.r-q.l+1))
// {
// while(l<=r)bt-=(!--cnt[a[r--]]);//clr
// r=(l=q.l)-1;
// }
while(q.l<l)bt+=(nxt[--l]>r);
while(r<q.r)bt+=(pre[++r]<l);
while(l<q.l)bt-=(nxt[l++]>r);
while(q.r<r)bt-=(pre[r--]<l);
// while (L > Opt[i].L) Sum += (Suf[--L] > R);
// while (R < Opt[i].R) Sum += (Pre[++R] < L);
// while (L < Opt[i].L) Sum -= (Suf[L++] > R);
// while (R > Opt[i].R) Sum -= (Pre[R--] < L);
ans[q.id]=bt;
#undef q
}
}
int main()
{
io::init();
n=io::getint();
for(int i=1;i<=n;i++)
{
a[i]=io::getint();
}
m=io::getint();
for(int i=1;i<=m;i++)
{
q[i].l=io::getint(),q[i].r=io::getint();
q[i].id=i;
}
mt();
for(int i=1;i<=m;i++)
{
// printf("%d\n",ans[i]);
io::putint(ans[i]);
io::putch('\n');
}
io::flush();
return 0;
}
```
by Po7ed @ 2024-05-01 21:27:58
参考别人代码打的，不开快读也可过
by Po7ed @ 2024-05-01 21:29:34