本文主要是介绍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]);
}
这篇关于2017清华计算机夏令营机试题目,2017 ECNU计算机系暑期夏令营机考 eoj3307. 送分题...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!