POJ_2104_K-th Number_主席树

时间:2022-10-13 10:50:35

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));
}
}

POJ_2104_K-th Number_主席树的更多相关文章

  1. bzoj3207--Hash&plus;主席树

    题目大意: 给定一个n个数的序列和m个询问(n,m<=100000)和k,每个询问包含k+2个数字:l,r,b[1],b[2]...b[k],要求输出b[1]~b[k]在[l,r]中是否出现. ...

  2. bzoj1901--树状数组套主席树

    树状数组套主席树模板题... 题目大意: 给定一个含有n个数的序列a[1],a[2],a[3]--a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]--a[ ...

  3. BZOJ 3626&colon; &lbrack;LNOI2014&rsqb;LCA &lbrack;树链剖分 离线&vert;主席树&rsqb;

    3626: [LNOI2014]LCA Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2050  Solved: 817[Submit][Status ...

  4. BZOJ 1146&colon; &lbrack;CTSC2008&rsqb;网络管理Network &lbrack;树上带修改主席树&rsqb;

    1146: [CTSC2008]网络管理Network Time Limit: 50 Sec  Memory Limit: 162 MBSubmit: 3522  Solved: 1041[Submi ...

  5. BZOJ 2588&colon; Spoj 10628&period; Count on a tree &lbrack;树上主席树&rsqb;

    2588: Spoj 10628. Count on a tree Time Limit: 12 Sec  Memory Limit: 128 MBSubmit: 5217  Solved: 1233 ...

  6. BZOJ 1901&colon; Zju2112 Dynamic Rankings&lbrack;带修改的主席树&rsqb;【学习笔记】

    1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 7143  Solved: 2968[Su ...

  7. &lbrack;bzoj3932&rsqb;&lbrack;CQOI2015&rsqb;&lbrack;任务查询系统&rsqb; (主席树)

    Description 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的 任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si ...

  8. &lbrack;bzoj2588&rsqb;&lbrack;count on a tree&rsqb; &lpar;主席树&plus;lca&rpar;

    Description 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权.其中lastans是上一个询问的答案,初始 ...

  9. &lbrack;bzoj2653&rsqb;&lbrack;middle&rsqb; &lpar;二分 &plus; 主席树&rpar;

    Description 一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整. 给你一个长度为n的序列s. 回答Q个这样的询问:s的左端点在[a,b ...

随机推荐

  1. python 输出十六进制中文乱码

    代码中红色字体为解决方案: #-*-coding:utf-8-* import csv filename='C:\Users\yaru\Desktop\Senti_Value(1).csv' data ...

  2. selenium处理极验滑动验证码

    要爬取一个网站遇到了极验的验证码,这周都在想着怎么破解这个,网上搜了好多知乎上看到有人问了这问题https://www.zhihu.com/question/28833985,我按照这思路去大概实现了 ...

  3. Windows 环境下基于 Redis 的 Celery 任务调度模块的实现

    搭建环境: Windows-x64 10 Celery 3.1.23 Celery-with-redis 3.0 Redis-win32-win64 2.4.5   实现步骤: 1.安装 Redis ...

  4. MySQL索引和锁

    索引和锁可以让查询锁定更少的行.如果你的查询从不访问那些不需要访问的行,那么就会锁定更少的行,从两个方面来看这对性能都有好处.首先,虽然innodb的行锁效率很高,内存使用也很少,但是锁定行的时候仍然 ...

  5. Django&lpar;二)如何在IIS中部署django项目

    环境配置 windows7 Django 2.0 python 3.6 wfastcgi 3.0 关键步骤 打开CGI功能 控制面板/程序和功能/打开或关闭windwos功能,如图: 安装wfastc ...

  6. SQL Pretty Printer for SSMS 很不错的SQL格式化插件

    写SQL语句或者脚本时,看到凌乱的格式就头大了,于是决心找一款SQL语句格式化的工具. 功夫不负有心人还真的被我找到一款很好用,很方便的SQL Server插件:SQL Pretty Printer ...

  7. Hdu 5072 Coprime(容斥&plus;同色三角形)

    原题链接 题意选出三个数,要求两两互质或是两两不互质.求有多少组这样的三个数. 分析 同色三角形n个点 每两个点连一条边(可以为红色或者黑色),求形成的三条边颜色相同的三角形的个数反面考虑这个问题,只 ...

  8. python 小练习 5

    Py从小喜欢奇特的东西,而且天生对数字特别敏感,一次偶然的机会,他发现了一个有趣的四位数2992, 这个数,它的十进制数表示,其四位数字之和为2+9+9+2=22,它的十六进制数BB0,其四位数字之和 ...

  9. 使用swagger 生成 Flask RESTful API

    使用swagger 生成 Flask RESTful API http://www.voidcn.com/article/p-rcvzjvpf-e.html swagger官网 https://swa ...

  10. 易错java知识点总结&lpar;持续更新)

    1. 2.java转义字符的理解 参考知乎大神:http://www.zhihu.com/question/29232624 正向和逆向处理转义字符 正向:把两个字符 \ n 识别为一个转义字符 ne ...