首页 > 其他分享 >区间 kth

区间 kth

时间：2022-09-01 11:57:07浏览次数：84  
标签：ch int 复杂度 re kth 区间 inf include

众所周知，区间 kth 有很多种求法。

本文中的时间复杂度和分数均以实现 P3834 为准。

为了更好地贴合现实，本文代码将更加符合学此算法时的实际情况。

一、排序

通过选择 / 冒泡 / 插入排序，将区间排序后输出 k 小值。

时间复杂度 \(O(mn^2)\)

实际得分：50 分

用时：7.81s

#include<cstdio>
using namespace std;
int n,m,l,r,k;
int a[200007],s[200007];
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",&l,&r,&k);
		for(int i=l;i<=r;i++)
			s[i-l+1]=a[i];
		for(int i=r-l+1;i>0;i--)
			for(int j=1;j<i;j++)
				if(s[j]>s[j+1])
					{int t=s[j];s[j]=s[j+1];s[j+1]=t;}
		printf("%d\n",s[k]);
	}
	return 0;
}

二、sort

作为 C 党，有必要了解 STL。

通过 sort 将排序的时间复杂度降下来（当然也可以自己写）

时间复杂度 \(O(mn\log n)\)

实际得分：50 分

用时：6.49s

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,l,r,k;
int a[200007],s[200007];
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",&l,&r,&k);
		for(int i=l;i<=r;i++)
			s[i-l+1]=a[i];
		sort(s+1,s+r-l+2);
		printf("%d\n",s[k]);
	}
	return 0;
}

三、分治

sort 的思想是二分，但我们要找的 kth 只可能出现在二分中的其中一个部分，那么就没有必要对两个部分都递归，而可以只对其中一部分递归。

时间复杂度 \(O(m(\dfrac n2+\dfrac n4+\dfrac n8+\cdots))=O(mn)\)

实际得分：50 分

用时：6.44s

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,l,r,k;
int a[200007],s[200007];
void _sort(int l,int r,int k)
{
	int i=l,j=r,v=s[l];
	while(i<=j)
	{
		while(s[i]<v)i++;
		while(s[j]>v)j--;
		if(i<=j)swap(s[i],s[j]),i++,j--;
	}
	if(k<=j)_sort(l,j,k);
	else if(i<=k)_sort(i,r,k);
	else return;
}
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",&l,&r,&k);
		for(int i=l;i<=r;i++)
			s[i-l+1]=a[i];
		_sort(1,r-l+1,k);
		printf("%d\n",s[k]);
	}
	return 0;
}

四、nth_element

为了避免重复造轮子，STL 中已经收录了 \(O(n)\) 求 k 小值的函数 nth_element（虽然还是重复造轮子了）。

时间复杂度 \(O(mn)\)

实际得分：50 分

用时：6.43s

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,l,r,k;
int a[200007],s[200007];
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",&l,&r,&k);
		for(int i=l;i<=r;i++)
			s[i-l+1]=a[i];
		nth_element(s+1,s+k,s+r-l+2);
		printf("%d\n",s[k]);
	}
	return 0;
}

五、值域映射

一种思想叫做从值域考虑，把区间里的数在值域上进行一个映射，然后倒着扫，扫到一个数就 \(k\leftarrow k-1\)，\(k=0\) 的时候输出。

时间复杂度 \(O(mn)\)

实际得分：50 分

用时：6.42s

#include<cstdio>
#include<algorithm>
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=2e5+7;
int n,m;
int a[inf],bok[inf],T[inf];
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		bok[i]=a[i]=re();
	sort(bok+1,bok+n+1);
	int num=unique(bok+1,bok+n+1)-bok-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(bok+1,bok+num+1,a[i])-bok;
	for(int i=1;i<=m;i++)
	{
		int l=re(),r=re(),k=re();
		for(int j=l;j<=r;j++)
			T[a[j]]++;
		for(int j=1;j<=num;j++)
		{
			k-=T[j];
			if(k<=0)
			{
				wr(bok[j]),putchar('\n');
				break;
			}
		}
		for(int j=l;j<=r;j++)
			T[a[j]]--;
	}
	return 0;
}

六、归并树

用线段树套 vector，在 \(O(n\log n)\) 的时间里建立归并树。

查询时二分答案，每次二分一个 mid，求区间内有多少数小于 mid，即在线段树的对应节点里的 vector 中再二分。

时间复杂度 \(O(m\log^3n)\)

实际得分：80 分（稍稍卡常）

用时：5.84s

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
inline int re()
{
    int s=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')
        s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s;
}
inline void wr(int s)
{
    if(s>9)wr(s/10);
    putchar(s%10+48);
}
const int inf=2e5+7;
int n,m,num,a[inf],bok[inf];
struct Seg_Tree{
    int le,ri;
    vector<int>h;
}T[inf<<2];
inline void build(int i,int l,int r)
{
    T[i].le=l,T[i].ri=r;
    if(l==r)
    {
        T[i].h.push_back(a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    vector<int>::iterator lc=T[i<<1].h.begin(),rc=T[i<<1|1].h.begin();
    while(lc!=T[i<<1].h.end()&&rc!=T[i<<1|1].h.end())
    {
        if(*lc<*rc)T[i].h.push_back(*lc),lc++;
        else T[i].h.push_back(*rc),rc++;
    }
    while(lc!=T[i<<1].h.end())
        T[i].h.push_back(*lc),lc++;
    while(rc!=T[i<<1|1].h.end())
        T[i].h.push_back(*rc),rc++;
}
inline int judge(int i,int l,int r,int k)
{
    if(l<=T[i].le&&T[i].ri<=r)
        return lower_bound(T[i].h.begin(),T[i].h.end(),k)-T[i].h.begin();
    int mid=(T[i].le+T[i].ri)>>1,ans=0;
    if(l<=mid)ans+=judge(i<<1,l,r,k);
    if(mid<r)ans+=judge(i<<1|1,l,r,k);
    return ans;
}
inline int ask(int x,int y,int k)
{
    int l=1,r=num;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        int ls=judge(1,x,y,mid);
        if(ls<k)l=mid;
        else if(ls>=k)r=mid-1;
    }
    return bok[l];
}
int main()
{
    n=re();m=re();
    for(register int i=1;i<=n;i++)
        bok[i]=a[i]=re();
    sort(bok+1,bok+n+1);
    num=unique(bok+1,bok+n+1)-bok-1;
    for(register int i=1;i<=n;i++)
        a[i]=lower_bound(bok+1,bok+num+1,a[i])-bok;
    build(1,1,n);
    for(register int i=1;i<=m;i++)
    {
        int l=re(),r=re(),k=re();
        wr(ask(l,r,k)),putchar('\n');
    }
    return 0;
}

七、主席树

发明者的原话是：“对于原序列的每一个前缀 \([1\sim i]\) 建出一棵线段树维护值域上每个数出现的次数，则其树是可减的。”

其实就是前缀和。

权值线段树储存的是值域上数的个数。对于版本 R 的权值线段树减去版本 L-1 的权值线段树，就得到了维护 [L,R] 的权值线段树。

实际得分：100 分

用时：537ms

#include<cstdio>
#include<algorithm>
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=2e5+7;
int n,m,num,a[inf],bok[inf];
struct Seg_Tree{
	int lson,rson;
	int sum;
	#define lc(i) T[i].lson
	#define rc(i) T[i].rson
}T[inf<<5];
int rot[inf],cnt;
void insert(int j,int &i,int l,int r,int k)
{
	i=++cnt;T[i]=T[j];
	if(l==r){T[i].sum++;return;}
	int mid=(l+r)>>1;
	if(k<=mid)insert(lc(j),lc(i),l,mid,k);
	else insert(rc(j),rc(i),mid+1,r,k);
	T[i].sum=T[lc(i)].sum+T[rc(i)].sum;
}
int ask(int i,int j,int l,int r,int k)
{
	if(l==r)return l;
	int mid=(l+r)>>1,sum=T[lc(j)].sum-T[lc(i)].sum;
	if(k<=sum)return ask(lc(i),lc(j),l,mid,k);
	return ask(rc(i),rc(j),mid+1,r,k-sum);
}
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		bok[i]=a[i]=re();
	sort(bok+1,bok+n+1);
	num=unique(bok+1,bok+n+1)-bok-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(bok+1,bok+num+1,a[i])-bok;
	for(int i=1;i<=n;i++)
		insert(rot[i-1],rot[i],1,num,a[i]);
	for(int i=1;i<=m;i++)
	{
		int l=re(),r=re(),k=re();
		wr(bok[ask(rot[l-1],rot[r],1,num,k)]),putchar('\n');
	}
	return 0;
}

八、线段树套平衡树

九、分块

十、整体二分

十一、莫队

十二、值域分块

十三、划分树

维护一个节点里面有多少数被划分到左边，有多少数被划分到右边，然后在线段树上查询。

由于稳定排序，在父节点的相对位置与在子节点中的相对位置相同。

时间复杂度 \(O(n\log n)\)

实际得分：100 分

用时：419ms

#include<cstdio>
#include<algorithm>
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=2e5+7;
int n,m,bok[inf];
struct Seg_Tree{
	int a[inf],sum[inf];
}T[20];
void build(int dep,int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1,k=bok[mid];
	int sum=0,cnt=mid-l+1;
	for(int i=l;i<=r;i++)
		if(T[dep].a[i]<k)cnt--;
	int il=l-1,ir=mid;
	for(int i=l;i<=r;i++)
	{
		int now=T[dep].a[i];
		if(now<k)sum++,T[dep+1].a[++il]=now;
		else if(now==k&&cnt)
		{
			sum++,cnt--;
			T[dep+1].a[++il]=now;
		}
		else T[dep+1].a[++ir]=now;
		T[dep].sum[i]=sum;
	}
	build(dep+1,l,mid);
	build(dep+1,mid+1,r);
}
int ask(int dep,int l,int r,int x,int y,int k)
{
	if(l==r)return T[dep].a[l];
	int mid=(l+r)>>1;
	int s1=0,s2=T[dep].sum[y];
	if(x^l)s1=T[dep].sum[x-1];
	if(k<=s2-s1)return ask(dep+1,l,mid,l+s1,l+s2-1,k);
	return ask(dep+1,mid+1,r,x-s1+mid-l+1,y-s2+mid-l+1,k-s2+s1);
}
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		T[1].a[i]=bok[i]=re();
	sort(bok+1,bok+n+1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int l=re(),r=re(),k=re();
		wr(ask(1,1,n,l,r,k)),putchar('\n');
	}
	return 0;
}

十四、根号平衡

参考文章

标签：ch,int,复杂度,re,kth,区间,inf,include
From： https://www.cnblogs.com/adm-1223/p/16638552.html

相关文章

  • ac802 区间和
    注意>>的运算顺序在加减之后#include<bits/stdc++.h>usingnamespacestd;constintN=300010;//intn,m;inta[N];//坐标插入的值in......
  • 涉及区间的查询
    1.找出一系列连续的值问题：判断哪些行表示一系列连续的项目。即某一行项目开始时间和前一行的项目结束时间是一致的。示例表：  解决方案：利用窗函数......
  • 15.区间覆盖问题(贪心)
    题目描述：设x1,x2,……,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?对于给定的实直线上的n个点和闭区间的长度k，设......
  • [算法]区间归并
    问题分析有的时候,会遇到给定一系列的区间,求交集or并集,或者合并的题.这些题的解题方式比较通用个,做一个总结.会用到集合和归并排序的相关知识.两个区间的关系有六种......
  • 区间问题----多次区间修改，少次单点询问的差分
    《定义》对于原数列：a1a2a3.....aiaj........an-1an这个数列的差分为ca[j]=aj-ai这个数列的前缀和为he[j]=aj+ai+..+a2+a1 我们可以惊奇的发现差分的前缀和==原......
  • 区间计数相关题目 907,828
    907. SumofSubarrayMinimumsMediumGivenanarrayofintegersarr,findthesumof min(b),where b rangesoverevery(contiguous)subarrayof arr.......
  • 求区间第k小数 数据范围小的时候（100） 考虑dp
    华为云挑战赛1001求前n个区间分成m段的第(len-0.05*len)个小数#include<bits/stdc++.h>usingnamespacestd;voidread(int&x){ charc=0;x=0; while(!isdigit(c))......
  • 2022牛客多校 补赛 C Cmostp（区间结尾本质不同子串）
    多次询问求一个串的结尾在\([l,r]\)之间的本质不同子串个数。此题是求一个区间的不同元素的问题，使用扫描线的方法解决，即每次加入一个元素就将这个位置\(+1\)，这个元素上一......
  • 632. 最小区间
     难度困难370收藏分享切换为英文接收动态反馈你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。......
  • 56. 合并区间
    56.合并区间以数组intervals表示若干个区间的集合，其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99