@[Sellaris](/user/567739) 答案好像都是对的。就是慢。有大佬能让我请教一下为什么吗？
by Sellaris @ 2022-03-06 11:41:50
@[Sellaris](/user/567739) 奇偶排序
by happybob @ 2022-03-06 11:41:55
@[Sellaris](/user/567739)
```cpp
///测试讨论区
//#pragma once
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#define _USE_MINGW_ANSI_STDIO 1
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define ll long long
using namespace std;
//using namespace __gnu_pbds;
const int maxn=1e6+10;
//__gnu_pbds::tree <ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> TREE ;
inline int read(){
register int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
return ret*f; //x=(x<<1)+(x<<3)+(ch^48);
}
int n,m,a[maxn];
int s,cur;
int ans[maxn],num[maxn];
struct query{
int l,r,bel,id;
}q[maxn];
inline bool cmp(query a,query b){
if(a.bel==b.bel) { return (a.bel&1?a.r<b.r:a.r>b.r); } // here
return (a.bel<b.bel) ;
}
inline void add(int p){
num[p]++;
if(num[p]==1) cur++;
}
inline void del(int p){
num[p]--;
if(num[p]==0) cur--;
}
signed main(){
//std::ios::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);
//freopen(in.txt,r,stdin);freopen(out.txt,w,stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
m=read();s=sqrt(n);
for(int i=1;i<=m;i++){
q[i].l=read();
q[i].r=read();
q[i].bel=(q[i].l-1)/s+1; // here
q[i].id=i;
}
std::sort(q+1,q+1+m,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l<q[i].l) del(a[l++]);
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(r>q[i].r) del(a[r--]);
ans[q[i].id]=cur;
}
for(int i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}
```
by happybob @ 2022-03-06 11:45:17
@[happybob](/user/332914)
可是大佬您看这个。
by Sellaris @ 2022-03-06 11:46:03
[link](https://www.spoj.com/status/ns=29216098)
并没有奇偶排序但效率比我快了5倍以上
by Sellaris @ 2022-03-06 11:46:13
@[Sellaris](/user/567739) 这个啥
by happybob @ 2022-03-06 11:46:23
@[Sellaris](/user/567739)
真正问题在于：
```cpp
q[i].bel=(q[i].r-1)/s+1;
```
这句话应该对 $l$ 分块而不是 $r$。
by happybob @ 2022-03-06 11:47:19
@[Sellaris](/user/567739) 所以猜测是自己哪里有问题，但实在是看不出来。理论上代码效率一样阿。
by Sellaris @ 2022-03-06 11:47:40
@[happybob](/user/332914) 好的谢谢您。理解了。
by Sellaris @ 2022-03-06 11:48:03