模板题,以后要学splay,大概看一下treap就好了。

 #include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; const int maxn = 3e5+;
int num[maxn],st[maxn]; struct Treap{
int size;
int key,fix;
Treap *ch[]; Treap(int key)
{
size = ;
fix = rand();
this->key = key;
ch[] = ch[] = NULL;
}
int compare(int x) const
{
if(x == key) return -;
return x < key ? : ;
}
void Maintain()
{
size = ;
if(ch[] != NULL) size += ch[]->size;
if(ch[] != NULL) size += ch[]->size;
}
}; void Rotate(Treap* &t ,int d)
{
Treap *k = t->ch[d^];
t->ch[d^] = k->ch[d];
k->ch[d] = t;
t->Maintain();
k->Maintain();
t = k;
} void Insert(Treap* &t,int x)
{
if(t == NULL) t = new Treap(x);
else
{
int d = x < t->key ? : ;
Insert(t->ch[d],x);
if(t->ch[d]->fix > t->fix)
Rotate(t,d^);
}
t->Maintain();
} void Delete(Treap* &t,int x)
{
int d = t->compare(x);
if(d == -)
{
Treap *tmp = t;
if(t->ch[] == NULL)
{
t = t->ch[];
delete tmp;
tmp = NULL;
}
else if(t->ch[] == NULL)
{
t = t->ch[];
delete tmp;
tmp = NULL;
}
else
{
int k = t->ch[]->fix > t->ch[]->fix ? : ;
Rotate(t,k);
Delete(t->ch[k],x);
}
}
else Delete(t->ch[d],x);
if(t!=NULL) t->Maintain();
} bool Find(Treap *t,int x)
{
while(t != NULL)
{
int d = t->compare(x);
if(d == -) return true;
t = t->ch[d];
}
return false;
} int Kth(Treap *t,int k)
{
if(t == NULL || k <= || k > t->size)
return -;
if(t->ch[] == NULL && k == )
return t->key;
if(t->ch[] == NULL)
return Kth(t->ch[],k-);
if(t->ch[]->size >= k)
return Kth(t->ch[],k);
if(t->ch[]->size + == k)
return t->key;
return Kth(t->ch[],k--t->ch[]->size);
} int Rank(Treap *t,int x)
{
int r;
if(t->ch[] == NULL) r = ;
else r = t->ch[]->size;
if(x == t->key) return r+;
if(x < t->key)
return Rank(t->ch[],x);
return r++Rank(t->ch[],x);
} void DeleteTreap(Treap* &t)
{
if(t == NULL) return;
if(t->ch[] != NULL) DeleteTreap(t->ch[]);
if(t->ch[] != NULL) DeleteTreap(t->ch[]);
delete t;
t = NULL;
} int save[maxn];
int M,N; int main()
{
while(~scanf("%d%d",&M,&N))
{
for(int i=;i<=M;i++)
scanf("%d",&save[i]);
Treap *root = NULL;
int cnt = ;
for(int i=,x;i<=N;i++)
{
scanf("%d",&x);
for(int j = cnt;j <= x;j++)
Insert(root,save[j]);
cnt = x+;
printf("%d\n",Kth(root,i));
}
DeleteTreap(root);
}
}

最新文章

  1. 快速Android开发系列通信篇之EventBus
  2. Xcode工程使用CocoaPods管理第三方库新建工程时出现错误
  3. [linux] cp: omitting directory `XXX&#39;问题解决
  4. 《第一行代码--Android》阅读笔记之Activity
  5. 【PPT分享】五类常见的用户分析场景
  6. VS2015如何另存解决方案文件-修改解决方案sln文件的路径
  7. 怎么样CSDN Blog投机和增加流量?
  8. Linux基础(4)
  9. windows 下进程池的操作
  10. python爬虫基础应用----爬取校花网视频
  11. linux 网络套接字
  12. c++的虚继承
  13. Python中操作Redis
  14. Zookeeper简介与集群搭建【转】
  15. 本地Sql Server数据库传到服务器数据库
  16. Linux基础(五) Shell函数
  17. 16_python_面向对象
  18. 寂静之地百度云在线观看迅雷下载A Quiet Place高清BT下载
  19. JPA(六):映射关联关系------映射单向一对多的关联关系
  20. 20145104张家明 《Java程序设计》第四次实验设计

热门文章

  1. 多模块后带来的问题解决方法 - OSGI原形(.NET)
  2. 朱晔的互联网架构实践心得S1E10:数据的权衡和折腾【系列完】
  3. Faster R-CNN:详解目标检测的实现过程
  4. Centos7 下SVN迁移
  5. 设计模式——MVC MVP MVVM
  6. Atcoder F - LCS (DP-最长公共子序列,输出字符串)
  7. es6在网页中模块引入的方法
  8. 福州大学软件工程1816 | W班 第2次作业成绩排名
  9. Is-a
  10. Non-Volatile Register 非易失性寄存器 调用约定对应寄存器使用