赞同
而且并不支持在题面中告知做法的行为
by Heartbeat666 @ 2018-01-26 23:53:23
这个好像是专门加强用来卡莫队的，好像前几天还在征求数据
by ViXbob @ 2018-01-27 00:01:23
这个你要问毒瘤lxl了
他（她）让我加强的数据……
@[noip](/space/show?uid=3296)
然后练习莫队还有别的题目啊，比如SDOI2009的某题
by chen_zhe @ 2018-01-27 08:56:17
修理了一下数据，开了两个subtask
一个subtask是莫队肯定能过的，有100分
还有一个subtask是必须用BIT的，有100分
模仿了一下导弹拦截
by chen_zhe @ 2018-01-27 09:09:11
所以没人写线段树的嘛...
by mengbierr @ 2018-01-27 09:22:08
@[mengbierr](/space/show?uid=35873) 题解里面有一个主席树的
by chen_zhe @ 2018-01-27 09:54:51
@[chen_zhe](/space/show?uid=8457) 毒瘤CZ，那道题也被你加强数据，莫队也过不掉了
by sxyugao @ 2018-05-11 14:22:18
是不是可以考虑在题目上写一下和bzoj范围不一样...
($10^6 \to 2 \times 10^6$)
by 宽嫂 @ 2018-05-22 09:47:31
这个数据加强还害得BIT RE了
166分程序：（求教）
```
#include <bits/stdc++.h>
#define N 2000500
#define M 2000500
#define C 2000500
#define lowbit(x) (x & (-x))
using namespace std;
int n,c,q;
int col[N],Head[C],Next[N] = {0,0},Next2[N];
struct Q{
int l,r,note;
bool operator < (const Q cq) const{
return l < cq.l;
}
}a[M];
int ans[N],ll;
int d[N];
inline void Add(int x){
++d[x];
while (x <= n) x += lowbit(x),++d[x];
}
inline void Dev(int x){
--d[x];
while (x <= n) x += lowbit(x),--d[x];
}
inline int Ask(int x){
int tot = d[x];
while (x > 0) x -= lowbit(x),tot += d[x];
return tot;
}
int main(){
memset(d,0,sizeof(d));
memset(Head,0,sizeof(Head));
scanf("%d%d%d",&n,&c,&q);
for (int i = 1; i <= n; ++i) scanf("%d",&col[i]);
for (int i = 1; i <= q; ++i){
scanf("%d%d",&a[i].l,&a[i].r);
a[i].note = i;
}
sort(a+1,a+q+1);
for (int i = n; i >= 1; --i){
Next[i] = Head[ col[i] ];
Head[ col[i] ] = i;
Next2[i] = Next[ Next[i] ];
}
for (int i = 1; i <= n; ++i)
if (i == Next[ Head[ col[i] ] ]) Add(i);
ll = 0;
for (int i = 1; i <= q; ++i){
while (ll < a[i].l){
if (Next[ll]) Dev(Next[ll]);
if (Next2[ll]) Add(Next2[ll]);
++ll;
}
ans[ a[i].note ] = Ask(a[i].r) - Ask(a[i].l-1);
}
for (int i = 1; i <= q; ++i) printf("%d\n",ans[i]);
return 0;
}
```
by s_r_f @ 2018-06-02 22:13:57
然而莫队加上各种优化有133分
```cpp
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 2000005
using namespace std;
int n,m,c,a[maxn],sum[maxn],bl,cl=1,cr,query[maxn],ans;
char pbuf[10000010],*p=pbuf;
struct abc{
int L,R,id,p;
inline bool operator <(const abc &b)const{return p^b.p? L<b.L:p&1? R>b.R:R<b.R;}
}s[maxn];
inline char gt()
{
static char buf[10000010],*A=buf,*B=buf;
return A==B&&(B=(A=buf)+fread(buf,1,10000000,stdin),A==B)? EOF:*A++;
}
inline int read(int &ret)
{
ret=0;char ch=gt();
while (ch<'0'||ch>'9') ch=gt();
while (ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+(ch^48),ch=gt();
return ret;
}
inline void write(int &x)
{
static int stack_[35];int top=0;
if (!x) stack_[++top]=0;
while (x) stack_[++top]=x%10,x/=10;
while (top) *p++=stack_[top--]^48;
}
int main()
{
freopen("4113.in","r",stdin);
freopen("4113.out","w",stdout);
read(n);read(c);read(m);bl=sqrt(n);
for (int i=1;i<=n;++i) read(a[i]);
for (int i=1;i<=m;++i)
read(s[i].L),read(s[i].R),s[i].id=i,s[i].p=s[i].L/bl;
sort(s+1,s+m+1);
for (int i=1;i<=m;++i)
{
while (cl<s[i].L){if (--sum[a[cl++]]==1) --ans;}
while (cl>s[i].L){if (++sum[a[--cl]]==2) ++ans;}
while (cr<s[i].R){if (++sum[a[++cr]]==2) ++ans;}
while (cr>s[i].R){if (--sum[a[cr--]]==1) --ans;}
query[s[i].id]=ans;
}
for (int i=1;i<=m;++i) write(query[i]),*p++='\n';
fwrite(pbuf,1,p-pbuf,stdout);
return 0;
}
```
by everdream @ 2018-07-25 22:01:26