[bzoj3065]带插入区间K小值 解题报告

2024-03-10 19:18
文章标签 报告 插入 区间 解题 小值 bzoj3065

本文主要是介绍[bzoj3065]带插入区间K小值 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

傻逼怎么做：
先用一个块链维护序列，做到 O(n√) 插入， O(1) 比较两个点在序列中位置的大小。时间复杂度是 O(nn√) 。
再用一个块链维护权值，每个块维护按位置排序的序列。查询的时候从小到大枚举每个块，先在块里二分统计块内在查询区间中的个数，然后如果发现答案在这个块里，就直接暴力找到第k小的是哪个。取块大小等于 O(nlog2n−−−−−−√) ，则时间复杂度是 O(qnlog2n−−−−−−√) 。
总的时间复杂度就是 O(nn√+qnlog2n−−−−−−√) ，然后不知道是我姿势不对还是什么情况。。写了9K。
鸟哥的做法：
用块链维护，每个块维护每种权值出现次数的前缀和、和对一块权值出现次数的前缀和。这样时间复杂度就是 O((n+q)n√) ，而且比我的做法好写很多。。
我的代码：

#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cassert>
#include<cstring>
#include<cmath>
const int N=7e4+5,A=7e4+5,Q=175000+5;
int n;char * cp=(char *)malloc(30000000);
void in(int &x){bool flag=0;while(*cp<'0'||*cp>'9')flag=*cp++=='-';for(x=0;*cp>='0'&&*cp<='9';)x=x*10+(*cp++^'0');if(flag)x=-x;
}
char * os=(char *)malloc(500000),* op=os;
void out(int x){if(x){out(x/10);*op++='0'+x%10;}
}int w[N];
int p_pos1[N],p_pos2[N];
int w_pos1[N],w_pos2[N];//只有插入 
const int S=200;
//const int S=200;
//S∈[200,300]
//N/S∈[233,350]
int ptot=1;
int p_block[1000+5][1000+5];
int p_num[1000+5],p_pos0[1000+5];
void p_out(){printf("-----out p:\n");for(int i=1;i<ptot;++i){printf("%d:",p_num[i]);for(int j=1;j<=p_block[p_num[i]][0];++j)printf("%d(%d,%d) ",p_block[p_num[i]][j],p_pos1[p_block[p_num[i]][j]],p_pos2[p_block[p_num[i]][j]]);puts("");}
}
void p_build(){for(int i=1;i<=n;++i){if(p_block[ptot][0]==S)++ptot;++p_block[ptot][0];p_block[ptot][p_block[ptot][0]]=i;p_pos1[i]=ptot,p_pos2[i]=p_block[ptot][0];}for(int i=ptot++;i;--i)p_num[i]=p_pos0[i]=i;
}
void p_insert(int x){int i=1,j;for(;x-p_block[p_num[i]][0]>0&&i+1<ptot;++i)x-=p_block[p_num[i]][0];int bi=p_num[i];for(j=++p_block[bi][0];j>x;--j){p_block[bi][j]=p_block[bi][j-1];p_pos2[p_block[bi][j]]=j;}p_block[bi][x]=n;p_pos1[n]=bi,p_pos2[n]=x;if(p_block[bi][0]==S<<1){p_block[bi][0]=S;memcpy(p_block[ptot]+1,p_block[bi]+S+1,sizeof(int)*S);p_block[ptot][0]=S;for(j=S;j;--j){p_pos1[p_block[ptot][j]]=ptot;p_pos2[p_block[ptot][j]]=j;}x=i;for(i=ptot-1;i>x;--i){p_num[i+1]=p_num[i];p_pos0[p_num[i]]=i+1;}p_num[x+1]=ptot;p_pos0[ptot]=x+1;++ptot;}
}
bool p_cmp(const int &a,const int &b){return p_pos1[a]!=p_pos1[b]?p_pos0[p_pos1[a]]<p_pos0[p_pos1[b]]:p_pos2[a]<p_pos2[b];
}//需要支持插入/删除 
const int B=500;
//const int B=1050;
//B∈[500,2000]
//N/B∈[35,140]
struct WS{int num,w;bool operator < (const WS & o)const{return w<o.w;}
}w_tmp[35000+5];
int w_q[2000+5],w_h,w_t;
int w_block[2000+5][2000+5],w_sorted[2000+5][2000+5];
int w_last[2000+5],w_next[2000+5],w_first;
void w_out(){printf("---out w\n");for(int i=w_first;i;i=w_next[i]){printf("w_block[%d]\n",i);printf("sorted by w:");for(int j=1;j<=w_block[i][0];++j)printf("%d ",w_block[i][j]);puts("");printf("sorted by p:");for(int j=1;j<=w_block[i][0];++j)printf("%d ",w_sorted[i][j]);puts("");}//for(int i=1;i<n;++i)printf("pos[%d]={%d,%d}\n",i,w_pos1[i],w_pos2[i]);
}
void w_build(){for(int i=1;i<=400;++i)w_q[i-1]=i;for(int i=1;i<=n;++i)w_tmp[i]=(WS){i,w[i]};sort(w_tmp+1,w_tmp+n+1);for(int i=1;i<=n;++i){if(w_block[w_q[w_h]][0]==B)++w_h;w_block[w_q[w_h]][++w_block[w_q[w_h]][0]]=w_tmp[i].num;w_pos1[w_tmp[i].num]=w_q[w_h],w_pos2[w_tmp[i].num]=w_block[w_q[w_h]][0];}w_first=1;for(int i=++w_h;i>1;--i){w_last[i]=i-1;w_next[i-1]=i;}for(int i=w_h;i;--i){memcpy(w_sorted[i]+1,w_block[i]+1,sizeof(int)*w_block[i][0]);sort(w_sorted[i]+1,w_sorted[i]+w_block[i][0]+1,p_cmp);}
}
void w_split(int i){if(w_block[i][0]>=B<<1){int j;w_block[w_q[w_h]][0]=w_block[i][0]-(w_block[i][0]>>1);memcpy(w_block[w_q[w_h]]+1,w_block[i]+1+(w_block[i][0]>>1),sizeof(int)*w_block[w_q[w_h]][0]);for(j=w_block[w_q[w_h]][0];j;--j){w_pos1[w_block[w_q[w_h]][j]]=w_q[w_h];w_pos2[w_block[w_q[w_h]][j]]=j;}w_sorted[w_q[w_h]][0]=w_sorted[i][0]=0;int tmp;for(j=1;j<=w_block[i][0];++j){tmp=w_pos1[w_sorted[i][j]];w_sorted[tmp][++w_sorted[tmp][0]]=w_sorted[i][j];}w_block[i][0]>>=1;w_next[w_q[w_h]]=w_next[i];w_last[w_q[w_h]]=i;w_last[w_next[i]]=w_q[w_h];w_next[i]=w_q[w_h];w_h=(w_h+1)%400;}
}
int tmp[2000+5];
void w_delete(int x){int i=w_pos1[x],j;for(j=w_pos2[x];j<w_block[i][0];++j){w_block[i][j]=w_block[i][j+1];w_pos2[w_block[i][j]]=j;}j=w_block[i][0];while(w_sorted[i][j]!=x)--j;for(;j<w_block[i][0];++j)w_sorted[i][j]=w_sorted[i][j+1];--w_block[i][0];if(w_block[i][0]){if(w_block[i][0]<B&&w_next[i]){memcpy(w_block[i]+w_block[i][0]+1,w_block[w_next[i]]+1,sizeof(int)*w_block[w_next[i]][0]);memcpy(w_block[w_next[i]]+1,w_block[i]+1,sizeof(int)*(w_block[i][0]+w_block[w_next[i]][0]));for(j=w_block[i][0];j;--j)w_pos1[w_block[i][j]]=w_next[i];for(j=w_block[w_next[i]][0]+w_block[i][0];j>w_block[i][0];--j)w_pos2[w_block[w_next[i]][j]]=j;int k=1,o=1;for(j=1;j<=w_block[i][0]&&k<=w_block[w_next[i]][0];)if(p_cmp(w_sorted[i][j],w_sorted[w_next[i]][k])){tmp[o++]=w_sorted[i][j++];}else{tmp[o++]=w_sorted[w_next[i]][k++];}memcpy(tmp+o,w_sorted[i]+j,sizeof(int)*(w_block[i][0]-j+1));memcpy(tmp+o,w_sorted[w_next[i]]+k,sizeof(int)*(w_block[w_next[i]][0]-k+1));w_block[w_next[i]][0]+=w_block[i][0];memcpy(w_sorted[w_next[i]]+1,tmp+1,sizeof(int)*w_block[w_next[i]][0]);w_next[w_last[i]]=w_next[i];w_last[w_next[i]]=w_last[i];if(i==w_first)w_first=w_next[i];w_q[w_t]=i;w_t=(w_t+1)%400;w_split(w_next[i]);}}else{w_next[w_last[i]]=w_next[i];w_last[w_next[i]]=w_last[i];if(i==w_first)w_first=w_next[i];w_q[w_t]=i;w_t=(w_t+1)%400;}
}
void w_insert(int x){int i=w_first,j;if(i==0){i=w_first=w_q[w_h];w_h=(w_h+1)%400;w_last[i]=w_next[i]=0;w_block[i][0]=1,w_block[i][1]=x;w_sorted[i][1]=x;w_pos1[x]=i,w_pos2[x]=1;}else{while(w_next[i]&&w[w_block[w_next[i]][1]]<w[x])i=w_next[i];for(j=++w_block[i][0];j>1&&w[w_block[i][j-1]]>=w[x];--j){w_block[i][j]=w_block[i][j-1];w_pos2[w_block[i][j]]=j;}w_block[i][j]=x;w_pos1[x]=i,w_pos2[x]=j;for(j=w_block[i][0];j>1&&p_cmp(x,w_sorted[i][j-1]);--j)w_sorted[i][j]=w_sorted[i][j-1];w_sorted[i][j]=x;w_split(i);}
}
int main(){freopen("bzoj_3065.in","r",stdin);freopen("bzoj_3065.out","w",stdout);fread(cp,1,30000000,stdin);int m;in(n);for(int i=1;i<=n;++i)in(w[i]);p_build();w_build();++n;//p_out(),w_out();int q;in(q);int x,y,k,val;int i,j;int lastans=0;int cnt;while(q--){while(*cp<'A'||*cp>'Z')++cp;//printf("-------------\n");switch(*cp++){case 'Q':in(x),in(y),in(k);//x^=lastans,y^=lastans,k^=lastans;for(i=1;x>p_block[p_num[i]][0];++i){x-=p_block[p_num[i]][0];y-=p_block[p_num[i]][0];}x=p_block[p_num[i]][x];for(;y>p_block[p_num[i]][0];++i)y-=p_block[p_num[i]][0];y=p_block[p_num[i]][y];//printf("Get range:[%d,%d]\n",x,y);for(i=w_first;;i=w_next[i]){cnt=upper_bound(w_sorted[i]+1,w_sorted[i]+w_block[i][0]+1,y,p_cmp)-lower_bound(w_sorted[i]+1,w_sorted[i]+w_block[i][0]+1,x,p_cmp);//printf("cnt(%d)=%d-%d\n",i,upper_bound(w_sorted[i]+1,w_sorted[i]+w_block[i][0]+1,y,p_cmp)-w_sorted[i],lower_bound(w_sorted[i]+1,w_sorted[i]+w_block[i][0]+1,x,p_cmp)-w_sorted[i]);if(k>cnt)k-=cnt;else{for(j=1;j<=w_block[i][0];++j)if(!p_cmp(w_block[i][j],x)&&!p_cmp(y,w_block[i][j])&&--k==0){lastans=w[w_block[i][j]];break;}break;}}if(lastans)out(lastans);else *op++='0';*op++='\n';//printf("%d\n",lastans);break;case 'M':in(x),in(val);//x^=lastans,val^=lastans;for(i=1;x>p_block[p_num[i]][0];++i)x-=p_block[p_num[i]][0];x=p_block[p_num[i]][x];w_delete(x);w[x]=val;w_insert(x);break;case 'I':in(x),in(val);//x^=lastans,val^=lastans;w[n]=val;p_insert(x);w_insert(n);++n;break;}//p_out(),w_out();}fwrite(os,1,op-os,stdout);
}

总结：
①一定要生成极限数据测试！
②注意发掘题目的性质——既然权值是静态的，而位置是动态的，那么我们为什么要用块链维护权值呢？
③块链其实可以在每个块维护 O(n) 的信息，因为它最多只会产生 O(n√) 个块。如果要删除的话也没关系，我们在删除的时候其实并不需要把比较小的块合并，因为即使不那样也只会有 O(n√) 个块。

这篇关于[bzoj3065]带插入区间K小值 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/795247。

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
hdu 1754 I Hate It（线段树，单点更新，区间最值）

hdu 1754 I Hate It（线段树，单点更新，区间最值）

题意是求一个线段中的最大数。 线段树的模板题，试用了一下交大的模板。效率有点略低。 代码： #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
hdu4267区间统计

hdu4267区间统计

题意：给一些数，有两种操作，一种是在[a,b] 区间内，对（i - a）% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import
阅读更多...
hdu4417区间统计

hdu4417区间统计

给你一个数列{An}，然后有m次查询，每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead
阅读更多...
hdu3333区间统计

hdu3333区间统计

题目大意：求一个区间内不重复数字的和，例如1 1 1 3，区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...
Python：豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】

Python：豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】

**爬取豆瓣电影信息，分析近年电影行业的发展情况** 本文是完整的数据分析展现，代码有完整版，包含豆瓣电影爬取的具体方式【附带爬虫豆瓣，数据处理过程，数据分析，可视化，以及完整PPT报告】   最近MBA在学习《商业数据分析》，大实训作业给了数据要进行数据分析，所以先拿豆瓣电影练练手，网络上爬取豆瓣电影TOP250较多，但对于豆瓣电影全数据的爬取教程很少，所以我自己做一版。 目
阅读更多...
开题报告中的研究方法设计：AI能帮你做什么？

开题报告中的研究方法设计：AI能帮你做什么？

AIPaperGPT，论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗？研究方法部分是不是已经让你头疼到抓狂？ 别急，这可是大多数人都会遇到的难题！尤其是研究方法设计这一块，选定性还是定量，怎么搞才能符合老师的要求？ 每次到这儿，头脑一片空白。 好消息是，现在AI工具火得一塌糊涂，比如ChatGPT，居然能帮你在研究方法这块儿上出点主意。是不
阅读更多...
【干货分享】基于SSM的体育场管理系统的开题报告（附源码下载地址）

【干货分享】基于SSM的体育场管理系统的开题报告（附源码下载地址）

中秋送好礼 中秋佳节将至，祝福大家中秋快乐，阖家幸福。本期免费分享毕业设计作品：《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心，体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而，传统的体育场管理方式存在诸多问题，如资源分配不均、预约流程繁琐、数据统计不准确等，严重影响了体育场的使用效率和用户体验。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2