AC日记——Little Elephant and Array codeforces 221d

221D - Little Elephant and Array

思路：

　　莫队；

代码：

#include 
#include 
#include 
#include 
#include using namespace std;#define maxn 100005struct QueryType {int l,r,id;
};
struct QueryType qu[maxn];int n,m,ai[maxn],bi[maxn],ans[maxn],ci[maxn],num[maxn];
int size,now,bel[maxn],blo;inline void in(int &now)
{char Cget=getchar();now=0;while(Cget>'9'||Cget<'0') Cget=getchar();while(Cget>='0'&&Cget<='9'){now=now*10+Cget-'0';Cget=getchar();}
}bool cmp(QueryType aa,QueryType bb)
{if(bel[aa.l]==bel[bb.l]){if(bel[aa.r]==bel[bb.r]){if(aa.l==bb.l) return aa.r<bb.r;else return aa.l<bb.l;}else return bel[aa.r]<bel[bb.r];}else return bel[aa.l]<bel[bb.l];
}inline void updata(int x,int dis)
{if(num[ai[x]]==ci[x]) now--;num[ai[x]]+=dis;if(num[ai[x]]==ci[x]) now++;
}int main()
{in(n),in(m);for(int i=1;i<=n;i++) in(ai[i]),bi[i]=ai[i],ci[i]=ai[i];sort(bi+1,bi+n+1),size=unique(bi+1,bi+n+1)-bi-1;for(int i=1;i<=n;i++) ai[i]=lower_bound(bi+1,bi+size+1,ai[i])-bi;blo=sqrt(n);for(int i=1;i<=n;i++) bel[i]=(i+1)/blo;for(int i=1;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i;sort(qu+1,qu+m+1,cmp);int l=1,r=0;for(int no=1;no<=m;no++){int ll=qu[no].l,rr=qu[no].r;if(lfor(int i=l;i1);else for(int i=l-1;i>=ll;i--) updata(i,1);if(rfor(int i=r+1;i<=rr;i++) updata(i,1);else for(int i=r;i>rr;i--) updata(i,-1);l=ll,r=rr,ans[qu[no].id]=now;}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6838527.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！