复杂度要证明吗？就是为什么优秀近一倍- -
by 神迹 @ 2019-03-26 22:30:21
```cpp
// luogu-judger-enable-o2
#pragma GCC optimize("Ofast")
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define vd void
#define il inline
#define re register
#define end exit(0)
#define FOR(i,a,b) for(re int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(re int i=(a);i>=(b);--i)
using namespace std;
const int N(1000007),INF(2147483647);
int n,l(1),r(0),num(0);
int a[N],cnt[N],ans[N],belong[N];
struct Node {
int l,r,id,block;
friend bool operator < (Node x,Node y) {
return (belong[x.l]^belong[y.l])?belong[x.l]>belong[y.l]:((belong[x.l]&1)?x.r<y.r:x.r>y.r);
}
}b[N];
namespace IO {
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,1<<17,stdin),pa==pb)?EOF:*pa++
char buf[1<<17],pbuf[1<<17],stack_IO[30],*pa(buf),*pb(buf),*pp(pbuf);
il int read() {
re int s(0),f(1);
re char ch(gc);
while(ch<'0'||ch>'9') ch=='-'?f=-1,ch=gc:ch=gc;
while(ch>='0'&&ch<='9') s=s*10+ch-48,ch=gc;
return f*s;
}
il vd write(re int x,re char c='\n') {
re int top_IO(0);
if(!x) *pp++=48;
while(x) stack_IO[top_IO++]=x%10+48,x/=10;
while(top_IO) *pp++=stack_IO[--top_IO];
*pp++=c;
}
} using namespace IO;
vd Main() {
n=read();
int size=ceil(sqrt(n)),block((double)n/size);
FOR(i,1,block) {
FOR(j,(i-1)*size+1,i*size) {
belong[j]=i;
}
}
FOR(i,1,n) a[i]=read();
int q(read());
FOR(i,1,q)
b[i].l=read(),b[i].r=read(),b[i].id=i;
sort(b+1,b+q+1);
FOR(i,1,q) {
int ql(b[i].l),qr(b[i].r);
while(l<ql) num-=!--cnt[a[l++]];
while(l>ql) num+=!cnt[a[--l]]++;
while(r<qr) num+=!cnt[a[++r]]++;
while(r>qr) num-=!--cnt[a[r--]];
ans[b[i].id]=num;
}
FOR(i,1,q)
printf("%d\n",ans[i]);
fwrite(pbuf,1,pp-pbuf,stdout);
}
int main() {
Main();
return (0);
}
```
这我代码你尽力理解吧，加油！！
by 神迹 @ 2019-03-26 22:42:20
@[神迹](/space/show?uid=124571) 请问 结构体 中 自定义 比较函数belong[x.l]^belong[y.l] 是什么意思？
不应该总是返回1吗？
by 张泰来 @ 2019-03-26 23:00:44
@[神迹](/space/show?uid=124571) 对不起，理解有误，请忽略我的第二个问题。
by 张泰来 @ 2019-03-26 23:03:01
@[神迹](/space/show?uid=124571) 谢谢！谢谢！AC了。
然而不开O2的确过不了。
by 张泰来 @ 2019-03-26 23:34:31
没事辛苦
by 神迹 @ 2019-03-27 01:05:58