首页 > 代码库 > BZOJ 3809Gty的二逼妹子序列 解题报告+data marker
BZOJ 3809Gty的二逼妹子序列 解题报告+data marker
--BZOJ
http://www.lydsy.com/JudgeOnline/problem.php?id=3809
考虑对l,r跑莫队，对一组维护美丽度出现次数的桶修改，
然后把桶序列用分块维护查询
然后是吐槽：
内存28M，哦，这个题居然卡内存。。。。。
卡内存！！！
然后我就为本校的权限号贡献了三次MLE......
代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using std::sort; 5 struct ss{ 6 int l,r,a,b,num; 7 }x[1000010]; 8 int n,m,cut; 9 int tong[100005];10 int id[100005];11 int mark[400];12 int a[100005];13 int ans[1000010];14 bool cmp(ss a,ss b){15 if(id[a.l]==id[b.l])16 return a.r<b.r;17 return id[a.l]<id[b.l];18 }19 inline void in(int &ans)20 {21 ans=0;bool p=false;char ch=getchar();22 while((ch>‘9‘ || ch<‘0‘)&&ch!=‘-‘) ch=getchar();23 if(ch==‘-‘) p=true,ch=getchar();24 while(ch<=‘9‘&&ch>=‘0‘) ans=ans*10+ch-‘0‘,ch=getchar();25 if(p) ans=-ans;26 }27 void modui();28 int fin_brick(int l,int r);29 int main()30 {31 int i,j,k;32 in(n),in(m);33 cut=(int)sqrt(n);34 if(cut*cut<n)cut++;35 for(i=1;i<=n;i++)36 in(a[i]);37 for(i=1;i<=m;i++)38 in(x[i].l),in(x[i].r),in(x[i].a),in(x[i].b),x[i].num=i;39 for(i=1;i<=n;i++)40 id[i]=i/cut;41 sort(x+1,x+m+1,cmp);42 modui();43 for(i=1;i<=m;i++)44 printf("%d\n",ans[i]);45 return 0;46 }47 void modui(){48 int l_p=x[1].l,r_p=x[1].l-1,i;49 for(i=1;i<=m;i++){50 while(r_p<x[i].r){51 r_p++;52 if(!tong[a[r_p]])53 mark[a[r_p]/cut]++;54 tong[a[r_p]]++;55 }56 while(r_p>x[i].r){57 tong[a[r_p]]--;58 if(!tong[a[r_p]])59 mark[a[r_p]/cut]--;60 r_p--;61 }62 while(l_p>x[i].l){63 l_p--;64 if(!tong[a[l_p]])65 mark[a[l_p]/cut]++;66 tong[a[l_p]]++;67 }68 while(l_p<x[i].l){69 tong[a[l_p]]--;70 if(!tong[a[l_p]])71 mark[a[l_p]/cut]--;72 l_p++;73 }74 ans[x[i].num]=fin_brick(x[i].a,x[i].b);75 }76 }77 int fin_brick(int l,int r){78 int b_l=l/cut,b_r=r/cut,ll=l%cut,rr=r%cut;79 int i,j,ans=0;80 if(b_l==b_r){81 for(i=l;i<=r;i++)82 if(tong[i])83 ans++;84 return ans;85 }86 for(i=ll,j=l;i<=cut-1;i++,j++)87 if(tong[j])88 ans++;89 for(i=rr,j=r;i>=0;i--,j--)90 if(tong[j])91 ans++;92 b_l++;b_r--;93 for(i=b_l;i<=b_r;i++)94 ans+=mark[i];95 return ans;96 }
#include<cstdio>#include<cstdlib>#include<ctime>using namespace std;int main(){ srand(time(0)); int n=100000,m=1000000; int i; printf("%d %d\n",n,m); for(i=1;i<=n;i++) printf("%d ",rand()%n+1); printf("\n"); for(i=1;i<=m;i++){ int l=rand()%n+1,a=rand()%n+1; int r=l+rand()%(n-l+1),b=a+rand()%(n-a+1); printf("%d %d %d %d\n",l,r,a,b); }}
祝AC
BZOJ 3809Gty的二逼妹子序列 解题报告+data marker
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。