评测记录：
时间用了1200ms，感觉应该是比较快的莫队了 莫队基本思路之前的题解已经讲过了，不再赘述 这里主要讲一下关于块大小的优化和奇偶性优化 一些细节上的卡常数就放在代码里讲了块大小优化
好吧，在写这个之前，我从机房巨佬空中得到了一个结论莫队的复杂度是
（S为块大小） 但实际上是
证明略 故我们可以适当的调大块的大小 由爆OJ得，本题块大小应当在
左右（不适用所有程序） 奇偶性优化
若上一块中的右端点坐标是递增的，则这块中右端点递减
若上一块中的右端点坐标是递减的，则这块中右端点递增 这样的话，原本在块转移时右端点的移动情况由
变为
故变得更优 例如样例 1 21 10011 10011 20
若使用奇偶性优化
1,2——>1,100——>11,100——>11,20 不使用 1,2——>1,100——>11,20——>11,100 效果可以说是很显著了#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#pragma GCC optimize("-ftree-pre")#pragma GCC optimize("-ftree-vrp")#pragma GCC optimize("-fpeephole2")#pragma GCC optimize("-ffast-math")#pragma GCC optimize("-fsched-spec")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("-falign-jumps")#pragma GCC optimize("-falign-loops")#pragma GCC optimize("-falign-labels")#pragma GCC optimize("-fdevirtualize")#pragma GCC optimize("-fcaller-saves")#pragma GCC optimize("-fcrossjumping")#pragma GCC optimize("-fthread-jumps")#pragma GCC optimize("-funroll-loops")#pragma GCC optimize("-fwhole-program")#pragma GCC optimize("-freorder-blocks")#pragma GCC optimize("-fschedule-insns")#pragma GCC optimize("inline-functions")#pragma GCC optimize("-ftree-tail-merge")#pragma GCC optimize("-fschedule-insns2")#pragma GCC optimize("-fstrict-aliasing")#pragma GCC optimize("-fstrict-overflow")#pragma GCC optimize("-falign-functions")#pragma GCC optimize("-fcse-skip-blocks")#pragma GCC optimize("-fcse-follow-jumps")#pragma GCC optimize("-fsched-interblock")#pragma GCC optimize("-fpartial-inlining")#pragma GCC optimize("no-stack-protector")#pragma GCC optimize("-freorder-functions")#pragma GCC optimize("-findirect-inlining")#pragma GCC optimize("-fhoist-adjacent-loads")#pragma GCC optimize("-frerun-cse-after-loop")#pragma GCC optimize("inline-small-functions")#pragma GCC optimize("-finline-small-functions")#pragma GCC optimize("-ftree-switch-conversion")#pragma GCC optimize("-foptimize-sibling-calls")#pragma GCC optimize("-fexpensive-optimizations")#pragma GCC optimize("-funsafe-loop-optimizations")#pragma GCC optimize("inline-functions-called-once")#pragma GCC optimize("-fdelete-null-pointer-checks")//看起来很有用但的确很有用的40行优化#include namespace IO{ const unsigned int Buffsize=1<<25,Output=1<<25; static char Ch[Buffsize],*St=Ch,*T=Ch; inline char getc() { return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++); } static char Out[Output],*nowps=Out; inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;} inline int read() { int x=0;static char ch;int f=1; for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1; for(;isdigit(ch);ch=getc())x=x*10+(ch^48); return x*f; } template inline void write(T x,char ch='\n') { if(!x)*nowps++=48; if(x<0)*nowps++='-',x=-x; static unsigned int sta[111],tp; for(tp=0;x;x/=10)sta[++tp]=x%10; for(;tp;*nowps++=sta[tp--]^48); *nowps++=ch; }}//IO（fread，fwite）优化，自行百度using namespace std;using namespace IO;int color[500009],ans[500009],p[1000001],divi;int blong[500009];struct lj{ int l,r,bel; }q[500009];inline bool rnk(lj a,lj b){ return blong[a.l]^blong[b.l]?blong[a.l] b.r);//奇偶性优化}int main (){ register int n,m,l,r=0,num=0; n=read(); for(register int *i=color+1,*ed=color+n+1;i!=ed;++i)//指针遍历数组更快，i++比++i慢 { *i=read(); } m=read(); divi=ceil(sqrt(m)*1.65);//块大小优化 for(register int *i=blong,*ed=blong+n+1,j=0,bfj=0;i!=ed;++i,++j)//同上上 { j=bfj+1; *i=*(i-1); if(j==divi) ++*i,j=0; bfj=j; } for(register lj *i=q+1,*ed=q+m+1;i!=ed;++i)//同上 { (*i).l=read(); (*i).r=read(); ((*i).bel)=i-q; } sort(q+1,q+m+1,rnk); l=1; for(register int i=1;i<=m;++i) { while(l>q[i].l) num+=!p[color[--l]]++; while(l q[i].r) num-=!--p[color[r--]]; ans[q[i].bel]=num; } for(register int *i=ans+1,*ed=ans+m+1;i!=ed;++i)//同上 { write(*i); } flush();} 突然发现树状数组跑得没我快ovo