fork download
copy 
  1. #include <cstdio>
  2. #include <ctime>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7. #define rep(i, n) for(int i = 0; i < (int)n; i++)
  8. #define INF (1 << 30)
  9. #define mp make_pair
  10.  
  11. int n, q;
  12. vector<int> p;
  13.  
  14. struct node_t{
  15.     int val;
  16.     node_t *lch, *rch;
  17.     int pri;
  18.     int cnt;
  19.     int mini;
  20.     node_t(int v) : val(v), cnt(1), mini(v){
  21.     pri = rand() % INF;
  22. 	rch = lch = NULL;
  23.     }
  24. };
  25.  
  26. int sol_count(node_t *t){ return !t ? 0 : t->cnt; }
  27. int sol_mini(node_t *t){ return !t ? INF : t->mini; }
  28.  
  29. node_t *update(node_t *t){
  30.     t->cnt = sol_count(t->lch) + sol_count(t->rch) + 1;
  31.     t->mini = min(min(sol_mini(t->lch), sol_mini(t->rch)), t->val);
  32.     return t;
  33. }
  34.  
  35. node_t *merge(node_t *l, node_t * r) {
  36.     if (!l || !r) return !l ? r : l;
  37.     if (l->pri > r->pri){
  38. 	l->rch = merge(l->rch, r);
  39. 	return update(l);
  40.     } else {
  41. 	r->lch = merge(l, r->lch);
  42. 	return update(r);
  43.     }
  44. }
  45.  
  46. pair<node_t*, node_t*> split(node_t *t, int pos) {
  47.     if (!t) return mp((node_t*)NULL, (node_t*)NULL); 
  48.     if (pos <= sol_count(t->lch)) {
  49. 	pair<node_t*, node_t*> s = split(t->lch, pos); 
  50. 	t->lch = s.second; 
  51. 	return mp(s.first, update(t)); 
  52.     } else {
  53. 	pair<node_t*, node_t*> s = split(t->rch, pos - sol_count(t->lch) - 1);
  54. 	t->rch = s.first;
  55. 	return mp(update(t), s.second); 
  56.     }
  57. }
  58.  
  59. node_t *insert(node_t *t, int pos, node_t *n) {
  60.     pair<node_t*, node_t*> s = split(t, pos - 1);
  61.     return merge(merge(s.first, n), s.second);
  62. }
  63.  
  64. node_t *remove(node_t *t, int pos) {
  65.     pair<node_t*, node_t*> s;
  66.     s = split(t, pos - 1);
  67.     return merge(s.first, split(s.second, 1).second);
  68. }
  69.  
  70. int minimum(node_t *t, int l, int r) {
  71.     int tmp;
  72.     pair<node_t*, node_t*> res1, res2;
  73.     res1 = split(t, l - 1);
  74.     res2 = split(res1.second, r - l + 1);
  75.     tmp = sol_mini(res2.first);
  76.     t = merge(res1.first, merge(res2.first, res2.second));
  77.     return tmp;
  78. }
  79.  
  80. inline void output(node_t* v, int x, int y) { if(v != NULL && v->val >= x && v->val <= y) printf("%d\n", v->val); }
  81.  
  82. node_t* find_split_node(node_t* r, int x, int y) {
  83.     node_t* v = r;
  84.     while (v != NULL && !(v->lch == NULL && v->rch == NULL) && (v->val >= y || x > v->val)) {
  85. 	output(v, x, y);
  86. 	if(y <= v->val) v = v->lch;
  87. 	else v = v->rch;
  88.     }
  89.     return v;
  90. }
  91.  
  92. void repo(node_t* r) {
  93.     if(r == NULL) return ;
  94.     if(r->lch != NULL) repo(r->lch);
  95.     printf("%d\n", r->val);
  96.     if(r->rch != NULL) repo(r->rch);
  97. }
  98.  
  99. void query(node_t *r, int x, int y) {
  100.     node_t* vs = find_split_node(r, x, y);
  101.     if(vs == NULL) return ;
  102.     output(vs, x, y);
  103.  
  104.     if(vs->lch != NULL || vs->rch != NULL) {
  105. 	node_t* v = vs->lch;
  106. 	while(v != NULL && !(v->lch == NULL && v->rch == NULL)) {
  107. 	    output(v, x, y);
  108. 	    if(x <= v->val) {
  109. 		repo(v->rch);
  110. 		v = v->lch;
  111. 	    } else v = v->rch;
  112. 	}
  113. 	output(v, x, y);
  114.  
  115. 	v = vs->rch;
  116. 	while(v != NULL && !(v->lch == NULL && v->rch == NULL)) {
  117. 	    output(v, x, y);
  118. 	    if(y <= v->val) v = v->lch;
  119. 	    else {
  120. 		repo(v->lch);
  121. 		v = v->rch;
  122. 	    }
  123. 	}
  124. 	output(v, x, y);
  125.     }
  126. }
  127.  
  128. int main(){
  129.     scanf("%d %d", &n, &q);
  130.     srand((unsigned int) time(NULL));
  131.     p.resize(n);
  132.     rep(i, n) scanf("%d", &p[i]);
  133.     sort(p.begin(), p.end());
  134.     node_t root(p[0]);
  135.     node_t* u = &root;
  136.     for(int i = 1; i < n; ++i) u = insert(u, i + 1, new node_t(p[i]));
  137.  
  138.     while(q--) {
  139. 	puts("");
  140. 	int a, b;
  141. 	scanf("%d %d", &a, &b);
  142. 	if(a > b) swap(a, b);
  143. 	query(u, a, b);
  144.     }
  145.     return 0;
  146. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SiVLfM
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!