[BZOJ3236][Ahoi2013]作业（莫队+分块）

2019-11-08 01:29:20

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

和Gty的二逼妹子序列那道题是一样的，只不过多加了一问而已对权值分块，然后将区间离线之后莫队，每一次修改O(1) $O(1)$ ，查询O(n√) $O(/sqrt n)$

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1000005int n,m,block,t,ansum,ansval,ans[N][2];int a[N],num[N],L[N],R[N],cnt[N],sum[N],val[N];struct data{int l,r,x,y,id;}q[N];int cmp(data a,data b){ return num[a.l]<num[b.l]||(num[a.l]==num[b.l]&&num[a.r]<num[b.r]);}void modui(int l,int r,int f){ for (int i=l;i<=r;++i) { int last=cnt[a[i]]; sum[num[a[i]]]-=cnt[a[i]]; cnt[a[i]]+=f; sum[num[a[i]]]+=cnt[a[i]]; if (!last&&cnt[a[i]]) ++val[num[a[i]]]; else if (last&&!cnt[a[i]]) --val[num[a[i]]]; }}void query(int l,int r){ ansum=0,ansval=0; if (num[l]==num[r]) { for (int i=l;i<=r;++i) if (cnt[i]) ansum+=cnt[i],++ansval; return; } if (l==L[num[l]]) l=num[l]; else { for (int i=l;i<=R[num[l]];++i) if (cnt[i]) ansum+=cnt[i],++ansval; l=num[l]+1; } if (r==R[num[r]]) r=num[r]; else { for (int i=L[num[r]];i<=r;++i) if (cnt[i]) ansum+=cnt[i],++ansval; r=num[r]-1; } for (int i=l;i<=r;++i) ansum+=sum[i],ansval+=val[i];}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i]); for (int i=1;i<=m;++i) { scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].x,&q[i].y); q[i].x=max(q[i].x,1);q[i].y=min(q[i].y,n); q[i].id=i; } block=sqrt(n);t=(n-1)/block+1; for (int i=1;i<=n;++i) num[i]=(i-1)/block+1; L[1]=1,R[1]=block; for (int i=2;i<=n;++i) L[i]=L[i-1]+block,R[i]=R[i-1]+block;R[t]=n; sort(q+1,q+m+1,cmp); modui(q[1].l,q[1].r,1); query(q[1].x,q[1].y); ans[q[1].id][0]=ansum,ans[q[1].id][1]=ansval; for (int i=2;i<=m;++i) { if (q[i-1].l<q[i].l) modui(q[i-1].l,q[i].l-1,-1); else modui(q[i].l,q[i-1].l-1,1); if (q[i-1].r<q[i].r) modui(q[i-1].r+1,q[i].r,1); else modui(q[i].r+1,q[i-1].r,-1); query(q[i].x,q[i].y); ans[q[i].id][0]=ansum,ans[q[i].id][1]=ansval; } for (int i=1;i<=m;++i) PRintf("%d %d/n",ans[i][0],ans[i][1]);}

上一篇：Allow No 'Access-Control-Allow-Origin' header is present

下一篇：leetcode485

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注