数据加强了，不吸氧跑得慢的莫队可以T10个点(
by _stellar @ 2019-04-06 10:46:49
@[MrWangnacl](/space/show?uid=83906) 这题我加了奇偶优化的莫队不吸氧全部T掉
by Andrew82 @ 2019-04-06 11:01:54
```cpp
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define ll long long
template<typename T>void read(T &x){
x=0;char r=getchar();T neg=1;
while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();}
x*=neg;
}
int n,m,k;
const int maxn=50000+10;
int c[maxn];
int a[maxn];
int block;
struct question{
int l;int r;int block;int order;
}Q[maxn];
int res[maxn];
inline bool cmp(question a,question b){
if((a.block==b.block))return a.r<b.r;
else return a.l<b.l;
}
void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void ins(register int pos,register int &_sigma){
_sigma+=2*c[a[pos]]+1;
++c[a[pos]];
}
inline void del(register int pos,register int &_sigma){
_sigma-=2*c[a[pos]]-1;
--c[a[pos]];
}
inline void mo(){
clean(c,0);
register int l=1,r=1;
++c[a[l]];
register int sigma=c[a[l]]*c[a[l]];
loop(i,1,m){
while(l<Q[i].l)del(l++,sigma);
while(l>Q[i].l)ins(--l,sigma);
while(r>Q[i].r)del(r--,sigma);
while(r<Q[i].r)ins(++r,sigma);
res[Q[i].order]=sigma;
}
loop(i,1,m)write(res[i]),printf("\n");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain.txt","r",stdin);
freopen("dataout.txt","w",stdout);
#endif
read(n);read(m);read(k);
clean(res,0);clean(a,0);
block=sqrt(n);
loop(i,1,n){
read(a[i]);
}
loop(i,1,m){
read(Q[i].l);
read(Q[i].r);
Q[i].order=i;
Q[i].block=i/block+1;
}
sort(Q+1,Q+1+m,cmp);
mo();
return 0;
}
```
by Andrew82 @ 2019-04-06 11:02:51
@[Andrew82](/space/show?uid=109378)
这不是奇偶优化啊..
不应该是这样的吗
```
return (l/block)^(a.l/block) ? l < a.l : (((l/block)&1) ? r < a.r : r > a.r);
```
还有分块大小最好改成$\texttt{n/sqrt(m*2/3)}$会快一点
by _stellar @ 2019-04-06 11:12:58
@[MrWangnacl](/space/show?uid=83906) 哦，我发错代码了，但是我现在发现问题并不在此处，是我手残。。。。
```
Q[i].block=i/block+1;
```
by Andrew82 @ 2019-04-06 11:17:39
@[Andrew82](/space/show?uid=109378) 
by _stellar @ 2019-04-06 11:22:53
？我的莫队轻松过
by Suuon_Kanderu @ 2020-05-20 20:44:54
@[Andrew82](/user/109378)
草我发现我的也错在这
by Piwry @ 2020-05-25 15:03:13