2017清华计算机夏令营机试题目,2017 ECNU计算机系暑期夏令营机考 eoj3307. 送分题...

唔，晚上数学题写累了去eoj翻了翻前几年夏令营的机试题，大概这题算最难吧，就写了下

时间给的够宽，莫队暴力就好了(数据要离散化处理).

#include

using namespace std;

const int maxn=5e5+5;

typedef long long ll;

int Times[maxn],ans[maxn];

int sz,now,cnt=1;

struct Ques

{

int l,r,id;

}q[maxn];

struct edge

{

int c,id;

}color[maxn],col[maxn];

int read()

{

int now=0;char c=getchar();

while(c'9')c=getchar();

while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();

return now;

}

bool cmp(Ques a,Ques b)

{

if(a.l/sz==b.l/sz) return a.r

return a.l/sz

}

bool cmp1(edge a,edge b)

{

return a.c

}

bool cmp2(edge a,edge b)

{

return a.id

}

inline void Add(int p)

{

p=col[p].id;

// cout<

++Times[p];

if(Times[p]==2) ++now;

else if(Times[p]==3) --now;

}

inline void Subd(int p)

{

p=col[p].id;

--Times[p];

if(Times[p]==1) --now;

else if(Times[p]==2) ++now;

}

int main()

{

int n=read(),m=read();

sz=sqrt(n);

for(int i=1;i<=n;i++) color[i].c=read(),color[i].id=i;

for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;

sort(q+1,q+1+m,cmp);

sort(color+1,color+1+n,cmp1);

int pre=color[1].c;

for(int i=1;i<=n;i++)

{

if(color[i].c==pre) col[color[i].id].id=cnt;

else cnt++,pre=color[i].c,col[color[i].id].id=cnt;

}

sort(color+1,color+1+n,cmp2);

for(int i=1,l=1,r=0;i<=m;i++)

{

int ln=q[i].l,rn=q[i].r;

while(l>ln) Add(color[--l].id);

while(l

while(r

while(r>rn) Subd(color[r--].id);

ans[q[i].id]=now;

}

for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

}