HDU6704 补
2019山东省赛 E 补
// 区间操作 灵活应用
静态区间第k小
普通权值线段树可以查询整体的第k小问题
而主席树就是利用这一点保存每个时刻的权值线段树,这样当查询区间第k值时就能通过相减得到这个区间的权值线段树 就相当于这个区间求整体第k值
故主席树能查询区间第k值(__)
利用重复信息保存插入每个数时的 权值线段树
那么当求l~r的区间 时 只需要 将插入第r个数时的权值线段树T【root【r】】 减去T【root【l-1】】(其中的细节要好好理解)那么我们得到的其实就是L ~ R的权值线段树了 直接按步即可
主席树要注意内存 一般开正常大小25倍
代码参考qsc🙅
其中重点理解的应该还是怎么建立这个主席树的问题
当我们把所有数离散化后
如果在X位置插入一个数,那么我们对于新的主席树需要添加的边其实就是 从叶子X到根部ROOT的那一条链上面的点添加新边就可以了
原理其实挺好理解,难度应该在对于代码的理解与实现方面上(这应该也是所有数据结构的共同点)
巧妙的离散化(❓❓)不太重要记住就好 垃圾离散化1.28 只能使你的代码整洁一些,不建议使用
其中ROOT【i】代表的是第i个权值线段树 头结点的编号
代码中 update,query 中的参数X和Y其实都是一个节点的编号(困扰好久😞)
编号 编号 编号!!!
T[y].L即为左子树的编号 T【T【y】.L】.sum即为左子树的数字数量
其他类推
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define warn printf("!!**!!\n")
using namespace std;
typedef long long L;
typedef pair<int,int>pii;
const int maxn=1e6;
const int mod=1e9+7;
const int oo=1e9;
const int N=100005;
int n,m,cnt,root[maxn*40+10],a[maxn*40+10],x,y,k;
struct node
{
int l,r,sum;
} T[maxn*25+10];
vector<int>v;
int getid(int x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void update(int l,int r,int &x,int y,int pos)
{
T[++cnt]=T[y],T[cnt].sum++,x=cnt;
if(l==r)
return;
int mid=l+r>>1;
if(mid>=pos)
update(l,mid,T[x].l,T[y].l,pos);
else
update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
if(l==r)
return l;
int mid=l+r>>1;
///编号 编号!!!
int sum=T[T[y].l].sum-T[T[x].l].sum;
if(sum>=k)
return query(l,mid,T[x].l,T[y].l,k);
else
return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
cnt=0,v.clear();
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),v.push_back(a[i]);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1; i<=n; i++)
update(1,n,root[i],root[i-1],getid(a[i]));
for(int i=1; i<=m; i++)
{
scanf("%d %d %d",&x,&y,&k);
printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
}
}
}