@[b612](/space/show?uid=138280) 随便过啊...调调块的大小
by xhhkwy @ 2019-01-05 11:00:41
> @[b612](/space/show?uid=138280) 有啊,卡常
by arfa @ 2019-01-05 11:00:48
@[b612](/space/show?uid=138280) 或者吸氧+奇偶优化
by xhhkwy @ 2019-01-05 11:01:24
@[xhhkwy](/space/show?uid=96592) 块的大小怎样才是最优？~~试过吸氧和优先队列，都过不了。蒟蒻不会奇偶优化~~
by lxy__ @ 2019-01-05 11:09:24
@[xhhkwy](/space/show?uid=96592) 没事了~~（卡常通过~~
by lxy__ @ 2019-01-05 11:18:15
@[arfa](/space/show?uid=77760) %%%
by lxy__ @ 2019-01-05 11:18:20
@[b612](/space/show?uid=138280)
```c
// luogu-judger-enable-o2
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#define SIZE 500100
#define rint register int
#define ll long long
namespace IO{
const int BS=(1<<23)+5; int Top=0;
char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
void flush(){fwrite(OT,1,OS-OT,stdout),OS=OT;}
void Putchar(char c){*OS++ =c;if(OS==fin)flush();}
void write(int x){
if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-');
while(x) SS[++Top]=x%10,x/=10;
while(Top) Putchar(SS[Top]+'0'),--Top;
}
int read(){
int nm=0,fh=1; char cw=Getchar();
for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
} using namespace IO;
struct mxr
{
int l,r,id;
int ans;
}e[SIZE];
int n,m,blo,ans;
int v[SIZE],bl[SIZE],cnt[SIZE<<1];
inline bool cmp(mxr a,mxr b){return bl[a.l]==bl[b.l] ? (bl[b.l]&1) ? a.r<b.r : a.r>b.r : a.l<b.l;}
inline bool recmp(mxr a,mxr b){return a.id<b.id;}
int main()
{
n=read();blo=800;
for(rint i=1;i<=n;++i) v[i]=read(),bl[i]=i/blo;
m=read();
for(rint i=1;i<=m;++i)
{
e[i].l=read(),e[i].r=read();
e[i].id=i;
}
std::sort(e+1,e+m+1,cmp);
rint l=1,r=0;
for(rint i=1;i<=m;++i)
{
while(l<e[i].l) ans-=(--cnt[v[l]]==0),++l;
while(l>e[i].l) --l,ans+=(++cnt[v[l]]==1);
while(r>e[i].r) ans-=(--cnt[v[r]]==0),--r;
while(r<e[i].r) ++r,ans+=(++cnt[v[r]]==1);
e[i].ans=ans;
}
std::sort(e+1,e+m+1,recmp);
for(rint i=1;i<=m;i++) printf("%d\n",e[i].ans);
return 0;
}
```
大概就是这样
by mxr已死 @ 2019-01-05 11:20:07
```c
inline bool cmp(mxr a,mxr b){return bl[a.l]==bl[b.l] ? (bl[b.l]&1) ? a.r<b.r : a.r>b.r : a.l<b.l;}
```
这是奇偶优化
by mxr已死 @ 2019-01-05 11:21:06
@[xhhkwy](/space/show?uid=96592) 这个题块大小能怎么调啊
by a2956331800 @ 2019-01-05 11:22:10
@[mxrmxr](/space/show?uid=86478) 谢谢
by lxy__ @ 2019-01-05 11:24:57