是
by Mars_Dingdang @ 2024-01-05 18:41:35
是的
by 114514zll @ 2024-01-10 19:31:57
能用树状数组为啥要莫队
by wudi306 @ 2024-01-28 13:51:55
@[hytallenxu](/user/726098) https://www.luogu.com.cn/discuss/684955
by Po7ed @ 2024-02-04 17:24:26
@[hytallenxu](/user/726098) 不是的，可以预处理前缀和后缀位置来判断是否多了/少了一种颜色，这样空间访问连续，加上奇偶排序常数大大减小。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9,M=1e6+9,S=1e6+9;
int n,m,len;
int a[N],ans[M],cnt[S];
int pre[N],nxt[N],last[N];
inline int get(int x){return x/len;}
struct query{
int id,l,r;
bool operator<(const query &t)const{
int i=get(l),j=get(t.l);
return i==j?(i&1?r<t.r:r>t.r):i<j;
}
}nd[M];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
cin>>m;
len=max(1.0,sqrt(1.0*n*n/m));
for(int i=0; i<m; i++)
cin>>nd[i].l>>nd[i].r,nd[i].id=i;
sort(nd,nd+m);
for(int i=1; i<=n; i++)
{
pre[i]=last[a[i]];
if(pre[i])nxt[pre[i]]=i;
nxt[i]=n+1,last[a[i]]=i;
}
for(int k=0,i=0,j=-1,res=0; k<m; k++)
{
while(i<nd[k].l)res-=(j<nxt[i++]);
while(i>nd[k].l)res+=(j<nxt[--i]);
while(j<nd[k].r)res+=(i>pre[++j]);
while(j>nd[k].r)res-=(i>pre[j--]);
ans[nd[k].id]=res;
}
for(int i=0; i<m; i++)
cout<<ans[i]<<'\n';
return 0;
}
```
by XHY20180718 @ 2024-02-14 21:51:28