poj 2761 Feed the dogs (treap树)

时间:2022-09-08 10:04:23
 /*************************************************************
题目: Feed the dogs(poj 2761)
链接: http://poj.org/problem?id=2761
题意: 给一个数列,在给一些区间,求这些区间第k小的值,这些
区间没有包含关系,也就是说如果La>Lb那么Ra>Rb;
算法: treap树
思路: 由于这些区间没有包含关系,把这些区间排序后从左边
开始计算,每计算一个区间把前面多余数删除,这样每
个点只要插入和删除一次就可以了。
**************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std; const int mx=;
struct S
{
int l, r;
int di,k;
};
S s[mx];
int a[mx];
int ans[mx];
int n,m;
bool com(S a,S b)
{
if (a.l==b.l) return a.r<b.r;
return a.l<b.l;
} typedef struct Node ///节点的结构体
{
Node *l,*r;
int val,pri; ///节点的值和优先级
int sz; ///节点子树的节点数
Node(int x) ///初始化节点
{
l=r=NULL;
val=x;
pri=rand();
sz=;
}
}Node;
Node *root; int Tsize(Node *T) ///计算子树的叶子节点
{
if (T==NULL) return ;
return T->sz;
}
Node *L_rotate(Node *T) ///右节点的优先级大于当前节点的优先级,进行左旋转
{
Node *A=T->r; ///A表示有节点
T->r=A->l;
A->l=T;
A->sz-T->sz; ///交换后A变成当前节点,所以它的子树的节点数等于原来节点的节点数
T->sz=Tsize(T->l)+Tsize(T->r)+;
return A;
}
Node *R_rotate(Node *T) ///左节点的优先级大于当前节点的优先级,进行右旋转
{
Node *A=T->l;
T->l=A->r;
A->r=T;
A->sz=T->sz;
T->sz=Tsize(T->l)+Tsize(T->r)+;
return A;
} void inser(Node *&T,int val) ///插入函数,和二叉排序树差不多
{
if (T==NULL)
{
T=new Node(val);
return ;
}
if (T->val>=val)
{
inser(T->l,val);
if ((T->l->pri)<(T->pri)) T=R_rotate(T); ///优先级比较,并旋转
}
else
{
inser(T->r,val);
if ((T->r->pri)<(T->pri)) T=L_rotate(T);
}
T->sz=Tsize(T->l)+Tsize(T->r)+;
} void Delete(Node *&T,int val) ///删除函数
{
if (T->val>val) Delete(T->l,val);
else if (T->val<val) Delete(T->r,val);
else
{
if (T->l==NULL&&T->r==NULL) T=NULL; ///左右节点都为空
else if (T->r==NULL) T=T->l; ///右节点为空
else if(T->l==NULL) T=T->r; ///左节点为空
else ///左右都不空
{
if (T->l->pri<T->r->pri) ///左节点优先级小于右边
{ ///右旋转,并向右子树删除
T=R_rotate(T); ///应为有旋转后,要删除的节点到有子树去了
Delete(T->r,val);
}
else
{
T=L_rotate(T);
Delete(T->l,val);
}
}
}
if (T!=NULL)
{
T->sz=Tsize(T->l)+Tsize(T->r)+;
}
} int Find(Node *T,int k) ///查找第k小的树
{
int temp=Tsize(T->l)+; ///temp小于等于T->val数的个数
if (temp==k) return T->val;
if (temp>k) return Find(T->l,k);
return Find(T->r,k-temp);
} void solve()
{
sort(s+,s+m+,com);
s[].l=-;
s[].r=-;
for (int i=;i<=m;i++)
{
for (int j=s[i-].l;j<=min(s[i-].r,s[i].l-);j++)
Delete(root,a[j]); ///删除比要计算区间多的数
for (int j=max(s[i-].r+,s[i].l);j<=s[i].r;j++)
inser(root,a[j]); ///插入该区间剩下的数
ans[s[i].di]=Find(root,s[i].k);
}
for (int j=s[m].l;j<=s[m].r;j++) Delete(root,a[j]);
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=m;i++)
{
int l,r;
scanf("%d%d%d",&l,&r,&s[i].k);
s[i].l=min(l,r);
s[i].r=max(l,r);
s[i].di=i;
}
root=NULL;
solve();
for (int i=;i<=m;i++) printf("%d\n",ans[i]);
}

poj 2761 Feed the dogs (treap树)的更多相关文章

  1. POJ 2761 Feed the dogs(平衡树or划分树or主席树)

    Description Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs ...

  2. POJ 2761 Feed the dogs (主席树)(K-th 值)

                                                                Feed the dogs Time Limit: 6000MS   Memor ...

  3. POJ 2761 Feed the dogs

    主席树,区间第$k$大. #pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio&gt ...

  4. POJ 题目2761 Feed the dogs(主席树&vert;&vert;划分树)

    Feed the dogs Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 16860   Accepted: 5273 De ...

  5. &lbrack;POJ2761&rsqb; Feed the dogs &lpar;Treap&rpar;

    题目链接:http://poj.org/problem?id=2761 题目大意:给你n个数,m次查询,m次查询分别是a,b,k,查询下表从a到b的第k小元素是哪个.这m个区间不会互相包含. Trea ...

  6. 划分树---Feed the dogs

    POJ  2761 Description Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to fee ...

  7. poj 2761 主席树的应用&lpar;查询区间第k小值&rpar;

    Feed the dogs Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 22084   Accepted: 7033 De ...

  8. 【POJ2761】【区间第k大】Feed the dogs&lpar;吐槽&rpar;

    Description Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs ...

  9. Poj2761-Feed the dogs&lpar;伸展树求名次&rpar;

    Description Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs ...

随机推荐

  1. &lbrack;ACM&rsqb; 1007 -球球方格

    与兔子方格类似,不过一秒走一格: 输入 代码 #include<iostream> using namespace std; int main(void) { int test_count ...

  2. SaltStack安装篇

    一.基础介绍1.简介 salt 是一个基础平台管理工具 salt是一个配置管理系统,能够维护预定于状态的远程节点 salt是一个分布式远程执行系统,用来在远程节点上执行命令和查询数据 2.salt的核 ...

  3. javascript开发 ios和android app的简单介绍

    先看几个名词解释: nodejs ionic,Cordova,phoneGap,anjularjs react-native,reactjs nodeJs 的介绍参见这里,写的很好http://www ...

  4. XmlBeanFactory的Bean加载

    如何使用这些bean,bean加载的探索: MyTestBean bean=(MyTestBean) bf.getBean("myTestBean"); AbstractBeanF ...

  5. PHP计划任务&colon;如何使用Linux的Crontab执行PHP脚本

    我们的PHP程序有时候需要定时执行,我们可以使用ignore_user_abort函数或是在页面放置js让用户帮我们实现.但这两种方法都不太可靠,不稳定.我们可以借助Linux的Crontab工具来稳 ...

  6. push以及pop,shift,unshift

    压入数组:往数组后面加:push         arr.push()返回值为添加后数组的长度 往数组前面加:unshift     arr.unshift()返回值为添加后数组的长度 拿出数组:拿掉 ...

  7. ForEach 循环

    在C 标签里面 有个foreach 标签,这个标签是专门来做循环的标签: <c:forEach items="${wekList}"  var="list&quot ...

  8. delphi 7里怎么隐藏PageControl控件的tabsheet标签

    Tabsheet1.tabvisible := False;

  9. Android Studio 小技巧

    请参照http://blog.csdn.net/jdsjlzx/article/details/50689047 个人认为较有用: 30

  10. 关于cp命令的编写

    关于cp命令的编写 娄老师在课上详细的讲了命令who的编写过程~对此,我很有启发!于是想亲自动手试试~ 有什么不足的地方请大家提出来! Learning by doing ~ 做中学,真的只有自己动手 ...