旋转卡壳
2018-08-02 16:32:06
本篇题解发布者也是刚学的主席树,水平又low,还是第一次发题解
加上是先在代码上写了注释才写的题解,所以整个文章可能会有点重复啰嗦,有基础的可以直接看代码 在看的过程中有什么操作不懂可以结合代码看
如果有什么不对的地方还请大家多多包涵……
前置要求: 线段树 离散化 前缀和
可能比较好的观看体验: https://www.luogu.org/blog/0-1s/solution-p3834 (至少我看着还行)
看到题目 我们首先考虑个0分写法 对每个[l,r]sort一遍求出答案
然后觉得不行 考虑数据结构 有一段数组 还有区间询问 那就看看线段树
题目是求第k小 所以线段树维护的是[l,r]内数的出现次数
看数据范围 2*10^5个数 数的范围是±10^9 因此用离散化
开个x[200010]就是线段树维护的数组 x[i]存第i小的数 再开个线段树的数组存区间内数的出现次数 大概是这样子 ……完了 我好像不会线段树了......
再看题目 发现这样子做的话每个询问需要用[l,r]区间内的数的个数来建立一棵线段树 最多就有2*10^5棵线段树 时间空间都爆了 好了 GG
我们换个思路看 具体是什么思路我也不懂
先从简单入手 先求[1,r]的第k小
对于[1,i]树与[1,i+1]树 后者只是多了a[i+1]的插入所带来的影响
如图：
我们随便编一个数据 预处理如图(图丑 轻喷)
对于每一个新的线段树 我们可以在旧的线段树的基础上通过 增加新的节点 来构建这颗树 节省了大量的空间
我们可以用一个T[i]记录(1~i)线段树的根节点(容易看出根节点是一定是不同的)
这样算完了之后 我们就可以通过T[i]来询问(1~i)线段树
新的问题出现了 那如何解决区间问题呢 我们能求[1,i]的第k小(线段树的基本应用) 但是如何求[l,r]的第k小呢
想一下
[1,l]线段树是由插入 a[1]到a[l]的影响 构成的
[1,r]线段树是由插入 a[1]到a[r]的影响 构成的是不是有点前缀和的感觉
那么
[l,r]线段树是由插入 a[l]到a[r]的影响 构成的就等于
a[1]到a[r]的影响减去a[1]到a[l-1]的影响所以
[l,r]线段树 = [1,r]线段树 - [1,l-1]线段树是不是感觉很有道理
那具体怎么减呢
在线段树上 每个节点的值是这个节点所代表的区间内数字出现的次数 那么只要在(r)线段树的每一个节点上减去(l-1)线段树上的相同位置的节点的值 就行了
样例有点简单 但就是这个样子
下面在给出题面样例的模拟过程
预处理
更新插入的数带来的新线段树
根据上面的方法来得到询问需要的线段树 然后就询问就完事了
下面给出代码 注释可能有点啰嗦 凑合着看吧……(代码旁边的字符是无聊瞎写的 无视即可)
#include <bits/stdc++.h>
#define MAX 200010
using namespace std;
int nodeNum;
//所有节点的数量 //.............8888......... //
int L[MAX<<5],R[MAX<<5],sum[MAX<<5]; //..............;888........ //
//L[i]表示编号为i的节点的左儿子的编号 //...........888..888....... //
//sum[i]表示编号为i的节点所代表的区间内数字出现的次数 //........888888..;....88... //
int a[MAX],Hash[MAX]; //.......888.888.......888.. //
//a[i]为原数组 Hash[i]为排序后数组 //.......888.888.......!888 //
int T[MAX]; //.......88$.888........888. //
//T[i]为插入i个点后的树的根节点编号 //......888..888.....888.... //
//...........888.....888.... //
int read() //...........8888888888o.... //
{ //............&8888888...... //
int ans=0,flag=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {ans=(ans<<3)+(ans<<1)+ch-'0';ch=getchar();}
return ans*flag;
}
int build(int l,int r) //建一个空树(所有sum[i]都为0)
{
int num=++nodeNum; //num为当前节点编号
if(l!=r)
{
int m=(l+r)>>1;
L[num]=build(l,m);
R[num]=build(m+1,r);
}
return num; //返回当前节点的编号
}
int update(int pre,int l,int r,int x) //pre为旧树该位置节点的编号
{
int num=++nodeNum; //新建节点的编号
L[num]=L[pre];R[num]=R[pre];sum[num]=sum[pre]+1;
//该节点左右儿子初始化为旧树该位置节点的左右儿子
//因为插入的a[i](或Hash[x])在该节点所代表的区间中 所以sum++
if(l!=r)
{
int m=(l+r)>>1;
if(x<=m) L[num]=update(L[pre],l,m,x);
//x出现在左子树 因此右子树保持与旧树相同 修改左子树
else R[num]=update(R[pre],m+1,r,x);
}
return num;
}
int query(int u,int v,int l,int r,int k) //第k小
{
if(l==r) return Hash[l]; //找到第k小 l是节点编号 所以答案是Hash[l]
int m=(l+r)>>1;
int num=sum[L[v]]-sum[L[u]];
//用第一次模拟 这样比较容易看得懂 此时u=l-1 v=r
//则num= (1~r)树的左节点数字出现的次数 - (1~(l-1))树的左节点数字出现的次数
//即num等于([l,r])树左儿子数字出现的次数
if(num>=k) return query(L[u],L[v],l,m,k);
//当 左儿子数字出现的次数大于等于k 时 意味着 第k小的数字在左子树处
else return query(R[u],R[v],m+1,r,k-num);
//否则去右子树处找第k-num小的数字
}
int main()
{
int n=read(),m=read();
for(int i=1;i<=n;i++) {a[i]=read();Hash[i]=a[i];}
sort(Hash+1,Hash+1+n);
int size=unique(Hash+1,Hash+1+n)-Hash-1;
//size为线段树维护的数组的大小==Hash数组中不重复的数字的个数
T[0]=build(1,size); //初始化 建立一颗空树 并把该树的根节点的编号赋值给T[0]
for(int i=1;i<=n;i++)
{
int x=lower_bound(Hash+1,Hash+1+size,a[i])-Hash;
//在Hash的 [1,size+1)--->[1,size] 中二分查找第一个
// 大于等于(在这里可以看成等于) a[i]的Hash[x]
T[i]=update(T[i-1],1,size,x);
//更新a[i]带来的影响
//并将新树的根节点的编号赋值给T[i]
}
while(m--)
{
int l=read(),r=read(),k=read();
printf("%d\n",query(T[l-1],T[r],1,size,k)); //因为a[l]有影响 所以是T[l-1]
}
return 0;
}