首页 > 代码库 > 【BZOJ3110】【Zjoi2013】K大数查询 树套树 权值线段树套区间线段树
【BZOJ3110】【Zjoi2013】K大数查询 树套树 权值线段树套区间线段树
#include <stdio.h>
int main()
{
puts("转载请注明出处谢谢");
puts("http://blog.csdn.net/vmurder/article/details/43020009");
}
题解：
外层权值线段树，内层区间线段树可解。
权值都是1~n，就不用离散化了。
我写了标记永久化。
其它心得神马的：
天生对树形数据结构无爱。
第一次写树套树，终于知道是怎么回事了。
（只针对本题）
就是外层每个点都表示了一段权值，
而它同时还是一颗线段树，
线段树里面记录了这段权值的出现区间、次数等等。
然后每次插入的时候
都是暴力地把该权值所在的
所有外层线段树节点
这些内层线段树的对应区间
权值+1（当然毕竟是线段树，肯定是各种lazy啊什么的保证logn）
外层线段树的非叶节点根本不是从它的子节点推状态过来的。。
反正他其实不是太神奇，是一种很暴力的东西。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 50500
#define M 5005000
using namespace std;
int root[N<<2],sum[M],son[M][2],lazy[M],cnt;
int n,m;
inline int query(int note,int L,int R,int l,int r)
{
if(!note)return 0;
if(L==l&&r==R)return sum[note];
int mid=L+R>>1,ans=lazy[note]*(r-l+1);
if(r<=mid)return query(son[note][0],L,mid,l,r)+ans;
else if(l>mid)return query(son[note][1],mid+1,R,l,r)+ans;
else return query(son[note][0],L,mid,l,mid)+query(son[note][1],mid+1,R,mid+1,r)+ans;
}
inline int QUERY(int l,int r,int k)
{
int ans=0,L=1,R=n,mid,temp,note=1;
do{
mid=L+R>>1,temp=query(root[note<<1|1],1,n,l,r);
if(temp>=k)L=mid+1,note=note<<1|1;
else R=mid,note<<=1,k-=temp;
}while(L<R);
return L;
}
inline void pushup(int x,int l,int r)
{
sum[x]=sum[son[x][0]]+sum[son[x][1]]+lazy[x]*(r-l+1);
}
inline void add(int ¬e,int L,int R,int l,int r)
{
if(!note)note=++cnt;
if(L==l&&r==R)
{
sum[note]+=r-l+1;
lazy[note]++;
return ;
}
int mid=L+R>>1;
if(r<=mid)add(son[note][0],L,mid,l,r);
else if(l>mid) add(son[note][1],mid+1,R,l,r);
else add(son[note][0],L,mid,l,mid),add(son[note][1],mid+1,R,mid+1,r);
pushup(note,L,R);
}
inline void ADD(int l,int r,int x)
{
int L=1,R=n,note=1;
while(L<R)
{
int mid=L+R>>1;
add(root[note],1,n,l,r);
if(x<=mid)R=mid,note<<=1;
else L=mid+1,note=note<<1|1;
}
add(root[note],1,n,l,r);
}
int main()
{
freopen("test.in","r",stdin);
int opt,l,r,k;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d%d",&opt,&l,&r,&k);
if(opt==1)ADD(l,r,k);
else printf("%d\n",QUERY(l,r,k));
}
return 0;
}
【BZOJ3110】【Zjoi2013】K大数查询 树套树 权值线段树套区间线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。