POJ_2104_K-th Number_主席树

题意:给定一个长度为n的序列,m次询问区间第k小

分析:

主席树模板

主席树可以理解成为n棵权值线段树的前缀和

但我们不能建n棵线段树,只需要对于每个修改的结点新建一个点,剩下的儿子什么的连到上一棵树的儿子上

这样做到节约空间,实际上我们只需要开nlogn的空间

对于这道题就相当于对每个前缀建一棵树

查询的时候前缀和相减,在相减后的线段树上查询

代码简短思路清晰

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100050
int t[N*20],n,m,a[N],root[N],tot,ls[N*20],rs[N*20];
struct A
{
int num,id,v;
}d[N];
bool cmp1(const A &x,const A &y)
{
return x.num<y.num;
}
bool cmp2(const A &x,const A &y)
{
return x.id<y.id;
}
void insert(int x,int &y,int l,int r,int val)
{
y=++tot;
if(l==r){ t[y] = t[x] + 1; return ; }
int mid=l+r>>1;
if(val<=mid) rs[y]=rs[x],insert(ls[x],ls[y],l,mid,val);
else ls[y]=ls[x],insert(rs[x],rs[y],mid+1,r,val);
t[y]=t[ls[y]]+t[rs[y]];
}
int query(int x,int y,int l,int r,int k)
{
if(l==r)return a[l];
int sizls=t[ls[y]]-t[ls[x]],mid=l+r>>1;
if(k<=sizls) return query(ls[x],ls[y],l,mid,k);
else return query(rs[x],rs[y],mid+1,r,k-sizls);
}
int main()
{
scanf("%d%d",&n,&m);
int i,x,y,k,j;
for(i=1;i<=n;i++) scanf("%d",&d[i].num),d[i].id=i;
sort(d+1,d+n+1,cmp1);d[0].num=453753322;
for(i=1,j=0;i<=n;i++) { if(d[i].num!=d[i-1].num)j++;d[i].v=j;a[j]=d[i].num; }
sort(d+1,d+n+1,cmp2);
for(i=1;i<=n;i++) insert(root[i-1],root[i],1,n,d[i].v);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&k);
printf("%d\n",query(root[x-1],root[y],1,n,k));
}
}

最新文章

  1. Mysql中eft join、right join、inner join的区别
  2. 安装运行okvis
  3. 领域模型驱动设计(Domain Driven Design)入门概述
  4. javascript设计模式学习之七——迭代器模式
  5. hadoop源代码解读
  6. 使用函数的递归调用来解决Hanoi(汉诺)塔问题。
  7. SQL存储过程笔记
  8. JSP简单标签标签库开发
  9. 函数(swift)
  10. AWS 认证攻略(SA)
  11. Oracle 触发器 trigger
  12. 2019-04-28——Django学习
  13. Intel发6款全新9代i9/i7/i5 CPU:巅峰8核
  14. js 原型链和继承(转)
  15. Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko
  16. [Python] 04 - os &amp; sys module
  17. LeetCode--458--可怜的小猪
  18. vue.js用select实现省,市,提交后,默认显示省,市信息
  19. mysql中sql查询使用注意
  20. ACtiveMQ中间件-发布订阅模式

热门文章

  1. 《转》优化UITableViewCell高度计算的那些事
  2. Axis创建webservice客户端和服务端
  3. win7 64位专业版下的x64编译问题
  4. 二分查找算法的C++和PHP实现
  5. Ocelot中文文档-服务发现
  6. RDC去省赛玩前の日常训练 Chapter 1
  7. php中$_FILES应用实例
  8. Arduino初学
  9. AbstractQueuedSynchronizer原理及代码分析
  10. BootStrap 常用控件总结