繁体版 企业网站,外包公司做网站图片哪里整的,网页设计图片大小如何调整,什么是网站维护中正题
评测记录#xff1a;https://www.luogu.org/recordnew/lists?uid52918pidP3834 题意
给定一个长度为n的序列#xff0c;有m个询问#xff0c;求一个区间内的第k小的树。 解题思路
我们先思考用线段树快速询问第k小的树 我们可以用权值线段树来处理第k小的树https://www.luogu.org/recordnew/lists?uid52918pidP3834 题意
给定一个长度为n的序列有m个询问求一个区间内的第k小的树。 解题思路
我们先思考用线段树快速询问第k小的树 我们可以用权值线段树来处理第k小的树先将数组离散化排序加去重然后下标[l...r][l...r][l...r]表示在离散化序列内l∼rl∼rl\sim r中的数出现过多少次然后因为已经离散化了所以我们可以直接根据两个子节点返回的值来进行向下寻找。 我们开始考虑区间问题。区间问题就是只算上这个区间内的数的线段树我们可以使用前缀和。建立n个线段树表示1∼x1∼x1\sim x这个区间然后每次查询就是用第rrr棵线段树减去·第l#x2212;1" role="presentation">l−1l−1l-1棵线段树就好了。 但是这么一算其实时间复杂度和空间复杂度还不如暴力那就直接暴力吧。这么一想我们会发现其实每次修改都只修改一条链那么我们为什么不每次只增加一条链呢 那么我们开始今天的正题可持久化线段树主席树。 直接给出结构 上面的数是区间范围下面的是值。绿色为新增加的点 我们每次只修改一条链然后没有修改的那一部分和原来的节点相连每次询问不同版本时只需要从不同版本的根节点开始访问就可以了。而这样我们就需要动态开点了。 代码
#includecstdio
#includealgorithm
#define MN 200010
using namespace std;
struct tnode{int w,l,r,ls,rs;
}t[MN5];
int n,m,x,y,k,a[MN],b[MN],root[MN],num,q,w;
int build(int l,int r)//建立一棵空树
{int knum;t[k].ll,t[k].rr;if (lr) return k;int mid(lr)1;t[k].lsbuild(l,mid);t[k].rsbuild(mid1,r);//左右分区return k;//返回编号
}
int addt(int k,int z)//建立一条新链
{int nbnum;t[nb]t[k];t[nb].w;//动态开点if (t[k].lzt[k].rz) return nb;//到达节点int mid(t[k].lt[k].r)1;if (zmid) t[nb].lsaddt(t[k].ls,z);else t[nb].rsaddt(t[k].rs,z);//建立下一个节点return nb;
}
int query(int k1,int k2,int k)//前缀和询问区间
{if (t[k1].lt[k1].r) return t[k1].l;wt[t[k2].ls].w-t[t[k1].ls].w;//计算左子树在这个区间内的数字数量if (kw) return query(t[k1].ls,t[k2].ls,k);else return query(t[k1].rs,t[k2].rs,k-w);//向下询问
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,a[i]),b[i]a[i];sort(b1,b1n);//排序离散化1int qunique(b1,b1n)-b-1;//去重离散化root[0]build(1,q);//建立空树for (int i1;in;i){int telower_bound(b1,b1q,a[i])-b;//二分寻找原来的位置root[i]addt(root[i-1],te);//建立一条链}for (int i1;im;i){scanf(%d%d%d,x,y,k);printf(%d\n,b[query(root[x-1],root[y],k)]);//询问区间}
}
