树套树 动态第K小

又手敲了一遍 对树套树有了一些理解：

1.动态第K大只支持单点修改，区间修改对外层线段树无法更新其父亲节点

2.线段树套权值线段树还是权值线段树套线段树  具体看题目要求，一般来说外层线段树  是要求区间修改的，动态第K大+区间加就无法转化为这类问题 所以不能处理

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=2e6+5;
int rt[maxn*2],ls[maxn*20],rs[maxn*20],sum[maxn*20];
int n,tot,sz,cnt,a[maxn],b[maxn*2],c[maxn];
int V1[maxn],V2[maxn],c1,c2;
struct node
{
	int l,r,k,flag;
}q[maxn];
void update(int &o,int l,int r,int k,int value)
{
	if(!o)o=++cnt;
	sum[o]+=value;
	if(l==r)return;
	int m=(l+r)/2;
	if(k<=m)update(ls[o],l,m,k,value);
	else update(rs[o],m+1,r,k,value); 
}
void modify(int pos,int value)
{
	int k=lower_bound(b+1,b+1+sz,a[pos])-b;
	for(int i=pos;i<=n;i+=(i&-i))
	update(rt[i],1,sz,k,value);
}
int query(int l,int r,int k)
{
	if(l==r)return l;
	int m=(l+r)/2,res=0;
	for(int i=1;i<=c1;i++)res+=sum[ls[V1[i]]];
	for(int i=1;i<=c2;i++)res-=sum[ls[V2[i]]];
	if(k<=res)
	{
		for(int i=1;i<=c1;i++)V1[i]=ls[V1[i]];
		for(int i=1;i<=c2;i++)V2[i]=ls[V2[i]];
		return query(l,m,k);
	}
	else
	{
		for(int i=1;i<=c1;i++)V1[i]=rs[V1[i]];
		for(int i=1;i<=c2;i++)V2[i]=rs[V2[i]];
		return query(m+1,r,k-res);		
	}
}
int get(int l,int r,int k)
{
	c1=c2=0;
	for(int i=r;i;i-=(i&-i))
	V1[++c1]=rt[i];
	for(int i=l-1;i;i-=(i&-i))
	V2[++c2]=rt[i];
	return query(1,sz,k);
}
int main()
{
	int m,l,r,k;
	char s[2];
	tot=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]),b[++tot]=a[i];
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		if(s[0]=='C')
		{
			scanf("%d%d",&q[i].l,&q[i].k);
			q[i].flag=1,b[++tot]=q[i].k;
		}
		else
		{
			scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
			q[i].flag=2;
		}	
	}
	sort(b+1,b+1+tot);
	sz=unique(b+1,b+1+tot)-(b+1);
	for(int i=1;i<=n;i++)
	modify(i,1);
	for(int i=1;i<=m;i++)
	{
		if(q[i].flag==1)
		{
			modify(q[i].l,-1);
			a[q[i].l]=q[i].k;
			modify(q[i].l,1);
		}
		else
		printf("%dn",b[get(q[i].l,q[i].r,q[i].k)]);
	}
}

最后

以上就是靓丽期待为你收集整理的树套树 动态第K小的全部内容，希望文章能够帮你解决树套树 动态第K小所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。