深圳11区将实行居家办公,seo顾问服务 品达优化,苏州做网站哪家好,做网站平台的公司今天学习了一下主席树#xff08;名字这么强的嘛#xff09; 虽然直接理解起来不容易#xff0c;但是这种解决问题的思想其实并不陌生。 我们可以首先来看维护整个区间第K大的线段树 我们将[l,r]区间内数字的多少用线段树进行维护#xff0c;这样的话为了求取区间第k大名字这么强的嘛 虽然直接理解起来不容易但是这种解决问题的思想其实并不陌生。 我们可以首先来看维护整个区间第K大的线段树 我们将[l,r]区间内数字的多少用线段树进行维护这样的话为了求取区间第k大我们先看左区间有多少个数字如果左区间就有多于K的数字或者等于K个我们直接去左区间找如果左区间没有K个我们就去右区间找找右区间第K-左区间数字个数大的数
void query(int k,int l,int r,int k)
{if(lr) return l;int mid(lr)1;if(tree[k1].numk) query(k1,l,mid,k);else query(k1|1,mid1,r,k);
}但是我们要求解的问题没有这么简单我们需要很方便的求任意区间第K大比较容易想到的方法是给每个区间建立一个线段树然后找哪个查哪个然而这样的时空复杂度显然是不允许的。 我们可以来看另一个问题就是我们想要很方便地查询任意区间和我们的第一想法是不是也是将任意区间和计算出来然后输出呢同样不允许的情况下我们引入了前缀和计算从[1…i]的和然后[l,r]的和就是sum[r]-sum[l-1] 同样的对于我们想要很方便的求取区间第K大问题我们也引入前缀和的思想我们保存从1…n的所有维护[1…i]区间内任意区间数字个数的线段树就像上面那样然后想要求解的是[l,r]那么[l,r]区间内任意区间数字个数就是tree[ root[r] ].num-tree[ root[l-1] ].num然后就能像上面一样求解问题啦 然而我们需要保存1…n所有维护[1…i]区间内任意区间数字个数的线段树也是很不容易做到的但是在每一次更新的时候多加入一个数字我们只会修改从这个数字到根节点的不超过logn个节点其他的节点都是相同的那么我们不妨就直接用没有改变的节点再重新申请需要修改的节点。因为一个儿子可能被多个父亲使用所以这个时候的父亲和儿子节点已经不满足2n和2n1的关系我们就需要每个节点保存他的左儿子和右儿子的指针这里我们用数组下标模拟指针同时我们还需要一个root数组保存每个线段树的根节点的指针 对于区间[1…i]的线段树他的根节点一开始是和前面一个元素的根节点是相同的左儿子和右儿子以及区间数字的个数也是相同的然后我们加入一个新元素a[i]如果a[i]在左区间就建立一个新的左儿子节点这个左儿子一开始也和之前的左儿子相同我们再更新这个左儿子直到更新到叶子节点右儿子同理 代码如下
struct node
{int l,r,cnt;
}tree[MAXN];void insert(int x,int num,int l,int r)
{tree[t]tree[x]; tree[t].cnt; xt; //t指向当前可分配空间的数组的下标相当于新节点的指针if(lr) return;int mid(lr)1;if(nummid) insert(tree[x].l,num,l,mid);else insert(tree[x].r,num,mid1,r);
}
查询的话和最上面的代码类似
int query(int i,int j,int k,int l,int r)
{if(lr) return l;int tmptree[tree[j].l].cnt-tree[tree[i].l].cnt;//左区间的元素个数int mid(lr)1;if(ktmp){return query(tree[i].l,tree[j].l,k,l,mid);}else{return query(tree[i].r,tree[j].r,k-tmp,mid1,r);}
}因为我们需要维护数据范围大小的区间这可能是做不到的[-1e-9~1e9]都做不到。因此我们需要进行离散化 离散化代码
scanf(%d%d,N,M);for(int i1;iN;i){scanf(%d,a[i]);b[i]a[i];}sort(b1,bN1); //排序nunique(b1,b1N)-b-1;//去重后指向不包含重复元素的末尾的后一个元素后面都是与前面重复的n就是不重复元素的个数t0;for(int i1;iN;i){a[i]lower_bound(b1,b1n,a[i])-b; //a[i]重新赋值为在b[i]的次序离散化}完整代码哦对了还要注意开空间在网上听大佬说得开n*40的空间巨恐怖
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includequeue
#includevector
#includeset
#includestring
#includecmath
#includeclimitsusing namespace std;const int MAXN2000010;
int a[MAXN],b[MAXN],root[MAXN];
int N,M,n,t;
struct node
{int l,r,cnt;
}tree[MAXN];void insert(int x,int num,int l,int r)
{tree[t]tree[x]; tree[t].cnt; xt;if(lr) return;int mid(lr)1;if(nummid) insert(tree[x].l,num,l,mid);else insert(tree[x].r,num,mid1,r);
}int query(int i,int j,int k,int l,int r)
{if(lr) return l;int tmptree[tree[j].l].cnt-tree[tree[i].l].cnt;int mid(lr)1;if(ktmp){return query(tree[i].l,tree[j].l,k,l,mid);}else{return query(tree[i].r,tree[j].r,k-tmp,mid1,r);}
}int main()
{int T,u,v,k;scanf(%d,T);while(T--){scanf(%d%d,N,M);for(int i1;iN;i){scanf(%d,a[i]);b[i]a[i];}sort(b1,bN1);nunique(b1,b1N)-b-1;t0;for(int i1;iN;i){a[i]lower_bound(b1,b1n,a[i])-b;}root[0]tree[0].ltree[0].rtree[0].cnt0;for(int i1;iN;i){root[i]root[i-1];insert(root[i],a[i],1,n);}for(int i0;iM;i){scanf(%d%d%d,u,v,k);printf(%d\n,b[query(root[u-1],root[v],k,1,n)]);}}return 0;
}
