Original link :http://www.tyvj.cn/p/1730

Tree cover tree ...

as follows :

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define lc root<<1
#define rc root<<1|1
#define INF 0x3f3f3f3f
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)>(b)?(b):(a))
const int Max_N = ;
struct SBT *null;
struct SBT{
int v, s, c;
SBT *ch[];
SBT(int _v = ) : v(_v){
c = s = ;
ch[] = ch[] = null;
}
inline void push_up(){
s = ch[]->s + ch[]->s + c;
}
inline int cmp(int x) const{
return v == x ? - : x > v;
}
}stack[Max_N << ], *ptr[Max_N << ];
int sz = , sum = , arr[Max_N];
void init(){
null = &stack[sz++];
null->s = null->c = ;
}
inline void rotate(SBT* &x, int d){
SBT *k = x->ch[!d];
x->ch[!d] = k->ch[d];
k->ch[d] = x;
k->s = x->s;;
x->push_up();
x = k;
}
void Maintain(SBT* &x, int d){
if (x->ch[d] == null) return;
if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
rotate(x, !d);
} else if (x->ch[d]->ch[!d]->s > x->ch[d]->s){
rotate(x->ch[d], d), rotate(x, !d);
} else {
return;
}
Maintain(x, ), Maintain(x, );
}
void insert(SBT* &x, int v){
if (x == null){
x = &stack[sz++];
x->v = v;
x->ch[] = x->ch[] = null;
} else {
x->s++;
int d = x->cmp(v);
if (- == d){
x->c++;
return;
}
insert(x->ch[d], v);
x->push_up();
Maintain(x, d);
}
}
void del(SBT* &x, int v){
if (x == null) return;
int d = x->cmp(v);
x->s--;
if (- == d){
if (x->c > ){
x->c--;
} else if (x->ch[] == null || x->ch[] == null){
x = x->ch[] != null ? x->ch[] : x->ch[];
} else {
SBT *ret = x->ch[];
for (; ret->ch[] != null; ret = ret->ch[]);
del(x->ch[], x->v = ret->v);
}
} else {
del(x->ch[d], v);
}
if (x != null) x->push_up();
}
int sbt_rank(SBT *x, int v){
int t = , cur = ;
for (; x != null;){
t = x->ch[]->s;
if (v == x->v) return cur + t;
else if (v < x->v) x = x->ch[];
else cur += t + x->c, x = x->ch[];
}
return cur;
}
int sbt_pred(SBT *x, int v){
int t = -;
for (; x != null;){
if (x->v < v){
t = x->v;
x = x->ch[];
}
else x = x->ch[];
}
return t == - ? -INF : t;
}
int sbt_succ(SBT *x, int v){
int t = -;
for (; x != null;){
if (x->v > v){
t = x->v;
x = x->ch[];
}
else x = x->ch[];
}
return t == - ? INF : t;
}
void seg_built(int root, int l, int r){
ptr[root] = null;
for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
if (l == r) return;
int mid = (l + r) >> ;
seg_built(lc, l, mid);
seg_built(rc, mid + , r);
}
void seg_rank(int root, int l, int r, int x, int y, int v){
if (x > r || y < l) return;
if (x <= l && y >= r){
sum += sbt_rank(ptr[root], v);
return;
}
int mid = (l + r) >> ;
seg_rank(lc, l, mid, x, y, v);
seg_rank(rc, mid + , r, x, y, v);
}
void seg_modify(int root, int l, int r, int pos, int v){
if (pos > r || pos < l) return;
del(ptr[root], arr[pos]);
insert(ptr[root], v);
if (l == r) return;
int mid = (l + r) >> ;
seg_modify(lc, l, mid, pos, v);
seg_modify(rc, mid + , r, pos, v);
}
int seg_pred(int root, int l, int r, int x, int y, int v){
if (x > r || y < l) return -INF;
if (x <= l && y >= r) return sbt_pred(ptr[root], v);
int mid = (l + r) >> ;
int v1 = seg_pred(lc, l, mid, x, y, v);
int v2 = seg_pred(rc, mid + , r, x, y, v);
return _max(v1, v2);
}
int seg_succ(int root, int l, int r, int x, int y, int v){
if (x > r || y < l) return INF;
if (x <= l && y >= r) return sbt_succ(ptr[root], v);
int mid = (l + r) >> ;
int v1 = seg_succ(lc, l, mid, x, y, v);
int v2 = seg_succ(rc, mid + , r, x, y, v);
return _min(v1, v2);
}
void gogo(int n, int a, int b, int k){
int mid, l = , r = ;
while (l < r){
sum = ;
mid = (l + r) >> ;
seg_rank(, , n, a, b, mid);
if (sum < k) l = mid + ;
else r = mid;
}
printf("%d\n", l - );
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
init();
int i, n, m, a, b, c, d;
scanf("%d %d", &n, &m);
for (i = ; i <= n; i++) scanf("%d", &arr[i]);
seg_built(, , n);
while (m--){
scanf("%d", &a);
switch (a){
case :
sum = ;
scanf("%d %d %d", &b, &c, &d);
seg_rank(, , n, b, c, d);
printf("%d\n",sum);
break;
case :
scanf("%d %d %d", &b, &c, &d);
gogo(n, b, c, d);
break;
case :
scanf("%d %d", &b, &c);
seg_modify(, , n, b, c), arr[b] = c;
break;
case :
scanf("%d %d %d", &b, &c, &d);
printf("%d\n", seg_pred(, , n, b, c, d));
break;
case :
scanf("%d %d %d", &b, &c, &d);
printf("%d\n", seg_succ(, , n, b, c, d));
break;
}
}
return ;
}

bzoj 3196/tyvj p1730 More articles on the binary balance tree

  1. bzoj 3196 Tyvj 1730 Two forces balance tree ( The line tree sets the rank tree )

    3196: Tyvj 1730 Two forces balance tree Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1807  Solved: 772[Submit][Stat ...

  2. BZOJ 3196: Tyvj 1730 Two forces balance tree ( Tree cover tree )

    There should be many ways to solve this problem .... I used a line segment tree treap.... -------------------------------------------------------------------- ...

  3. bzoj 3196/ Tyvj 1730 Two forces balance tree ( Balance tree of line segment tree cover )

    3196: Tyvj 1730 Two forces balance tree Time Limit: 10 Sec  Memory Limit: 128 MB[Submit][Status][Discuss] Description ...

  4. bzoj 3196: Tyvj 1730 Two forces balance tree

    #include<cstdio> #include<ctime> #include<cstdlib> #include<iostream> #defin ...

  5. BZOJ 3196 Tyvj 1730 Two forces balance tree Tree cover tree Line segment tree treap

    http://www.lydsy.com/JudgeOnline/problem.php?id=3196 http://hzwer.com/2734.html Line segment tree sleeve treap, Seems to be splay It's fine too ...

  6. BZOJ 3196 Tyvj 1730 Two forces balance tree —— Tree array sets the chairman tree

    [ Topic analysis ] It's said that it's tree to tree .( Fog ) Write tree array set chairman tree , And then Rank1 了 .23333 Single point modification , Interval query +k Large number query = Tree array sets the chairman tree . [ Code ] #include <cstdio> ...

  7. BZOJ 3196 Tyvj 1730 Two forces balance tree : Line segment tree sleeve splay

    Portal The question Give you a length of $ n $ An orderly sequence of numbers $ a $ , Conduct $ m $ operations , There are several operations : Inquire about $ k $ In the interval $ [l,r] $ Internal ranking Query range $ [l,r] $ Inside row ...

  8. BZOJ - 3196 Tyvj 1730 Two forces balance tree ( Line segment tree sleeve treap)

    Topic link Interval segment treetop treap, Spatial complexity $O(nlogn)$, The time complexity is in addition to the query interval k Big is $O(log^3n)$ All but $O(log^2n)$ Of . ( It is said that the segment tree sets the segment tree . Tree array nested segment tree can also pass ?) ...

  9. bzoj 3196 Tyvj 1730 Two forces balance tree 【 Line segment tree set splay】

    Rounding is violence . For each interval of the line tree, open a tree sorted by weight splay For the second operation , Two minutes , Each query mid Ranking , Complexity $ O(nlog(n)^{3}) $ The rest of the operation is $ O(nlog( ...

Random recommendation

  1. Use a new one blog Slightly ..

    Before csdn This is too laggy. .. Just write a long one blog I'm stuck .. Turn around here , It's better .. primary blog Address Ah, why is the domain called darklove Well .. This was created a long time ago .. In short, it's a and clearl ...

  2. heartbeat install

    wget ftp://mirror.switch.ch/pool/1/mirror/scientificlinux/6rolling/i386/os/Packages/epel-release-6-5 ...

  3. 01TCP/IP Basics

    ISO/OSI Reference model : OSI(open system interconnection) The open systems interconnection model is made up of ISO(International Organization for Standardiz ...

  4. Xiaohei's soul ballad (HDU2155: greedy +dfs+ Wonderful solution )

    subject : Click here The meaning of the title is the same as that of the so-called hero 100 There is one meaning …… stay T It can go down to the ground in seconds , That's all right. ( There is also a board between the board can not exceed H high ). Contact this topic in the training match last night , I was greedy at that time +dfs, Just like I thought ...

  5. [TYVJ] P1026 Ploughing robot

    Ploughing robot background Background USACO OCT 09 2ND   describe Description Farmer John In order to liberate myself from the endless plowing work , So he bought a new robot to help him plow ...

  6. cpp( Chapter vii. )

    1.c++ Provides 3 Kind of said c— Style string method : A character array , String constant , String pointer . The character array is not necessarily a string , With a null character '\0' To end an array of characters when the string . 2. When the function parameter is an array , Although it reduces the time and memory, it makes ...

  7. Agent Job agent perform SSIS Package

    Abstract : In the use of Agent Job when , function SSIS Bag Run as account number , There has to be SSIS in connection manager Connection permission of . If there is no connection permission , You can use create proxy account number , And ensure proxy zhang ...

  8. Find a way to write , similar callback&amp;&amp;callback()

    And callback&&callback() different approaches but equally satisfactory results return data && { title: `To-do (${data.length})`, componen ...

  9. Spring Cloud Current limiting ideas and solutions

    from : http://blog.csdn.net/zl1zl2zl3/article/details/78683855 In high concurrency applications , Current limiting is often an unavoidable topic . This paper discusses in detail in Spring Clo ...

  10. Detailed exploration TextRange object -- Search and select ( Reprint )

    TextRange Objects are dynamic HTML(DHTML) Advanced features of , It can be used to accomplish many text related tasks , For example, searching and selecting text . Text range allows you to select characters . Words and sentences are picked from the document .TextRange object ...