Editorial for Giá trị lớn nhất 3
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; const fi=''; maxn=100010; oo=2000000000; var b:array[1..maxn,0..2] of longint; a,g,h:array[0..maxn*5] of longint; c,pos,re:array[0..maxn] of longint; n,m:longint; procedure init(node,l,r:longint); var mid:longint; begin if l=r then begin h[node]:=l; pos[l]:=node; a[node]:=c[l]; end else begin mid:=(l+r) shr 1; init(node shl 1,l,mid); init(node shl 1+1,mid+1,r); h[node]:=h[node shl 1]; a[node]:=max(a[node shl 1],a[node shl 1+1]); end; end; procedure rf; var i:longint; c:char; begin readln(m); n:=0; for i:=1 to m do begin readln(c,b[i,1],b[i,2]); if c='Q' then b[i,0]:=1 else inc(n); end; init(1,1,n); end; function find(node,l,r,val:longint):longint; var mid:longint; begin if l=r then find:=l else begin mid:=(l+r) shr 1; val:=val+g[node]; if h[node shl 1+1]<=val then find:=find(node shl 1+1,mid+1,r,val) else find:=find(node shl 1,l,mid,val); end; end; procedure incr(node,l,r,x,y:longint); var mid:longint; begin if (l=x) and (r=y) then begin g[node]:=g[node]+1; h[node]:=h[node]-1; end else begin mid:=(l+r) shr 1; if x<=mid then incr(node shl 1,l,mid,x,min(y,mid)); if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y); h[node]:=min(h[node shl 1],h[node shl 1+1])-g[node]; end; end; procedure update(x:longint); begin while x>1 do begin x:=x shr 1; h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x]; a[x]:=max(a[x shl 1],a[x shl 1+1]); end; end; procedure get(node,l,r,x,y:longint;var re:longint); var mid,t,u:longint; begin if (l=x) and (r=y) then re:=a[node] else begin mid:=(l+r) shr 1; t:=-oo; u:=-oo; if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t); if mid<y then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u); re:=max(t,u); end; end; procedure pr; var i,x,y,dem:longint; begin for i:=m downto 1 do if b[i,0]=0 then begin x:=find(1,1,n,b[i,2]); if x<n then incr(1,1,n,x+1,n); c[x]:=b[i,1]; h[pos[x]]:=oo; update(pos[x]); end; fillchar(g,sizeof(g),0); init(1,1,n); dem:=0; for i:=m downto 1 do if b[i,0]=0 then begin x:=find(1,1,n,b[i,2]); if x<n then incr(1,1,n,x+1,n); h[pos[x]]:=oo; a[pos[x]]:=-oo; update(pos[x]); end else begin dem:=dem+1; x:=find(1,1,n,b[i,1]); y:=find(1,1,n,b[i,2]); get(1,1,n,x,y,re[dem]); end; while dem>0 do begin writeln(re[dem]); dec(dem); end; end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include<iostream> #include<cstring> #include<cstdio> #include<set> using namespace std; const int N = 1e5+7; int bit1[2*N], m, n, st[4*N], bit2[2*N]; struct query { char type; int x, y; void read() { scanf(" %c%d%d", &type, &x, &y); } } q[N]; void updateBIT(int * bit, int i, int v) { for(; i <= n; i += i & -i) bit[i] += v; } int findBIT(int * bit, int v) { int res = n; for(int mask = n >> 1; mask != 0 && res >= 1; mask >>= 1) { int t = res - mask; if(v <= bit[t]) res = t; else v -= bit[t]; } return res; } int sumBIT(int * bit, int i) { int res = 0; for(; i != 0; i -= i & -i) res += bit[i]; return res; } void updateST(int k, int l, int r, int u, int v) { if(u < l || u > r || l > r) return; if(l == r) st[k] = max(st[k], v); else { updateST(2*k, l, (l+r)/2, u, v); updateST(2*k+1, (l+r)/2+1, r, u, v); st[k] = max(st[2*k], st[2*k+1]); } } int getST(int k, int l, int r, int u, int v) { if(v < l || r < u || l > r) return st[0]; if(u <= l && r <= v) return st[k]; return max(getST(2*k, l, (l+r)/2, u, v), getST(2*k+1, (l+r)/2+1, r, u, v)); } void enter() { scanf("%d", &m); for(int i = 1; i <= m; ++i) { q[i].read(); if(q[i].type == 'A') ++n; } } void standardizate() { while(n & (n-1)) n -= n & -n; n <<= 1; for(int i = 1; i <= n; ++i) updateBIT(bit2, i, 1); for(int i = m; i >= 1; --i) if(q[i].type == 'A') { int backup = q[i].y; q[i].y = findBIT(bit2, q[i].y); updateBIT(bit1, backup, 1); updateBIT(bit2, q[i].y, -1); } else { q[i].x = findBIT(bit2, q[i].x); q[i].y = findBIT(bit2, q[i].y); } } void solve() { memset(st, 0xc1, sizeof st); for(int i = 1; i <= m; ++i) { if(q[i].type == 'A') updateST(1, 1, n, q[i].y, q[i].x); else printf("%d\n", getST(1, 1, n, q[i].x, q[i].y)); } } int main() { enter(); standardizate(); solve(); return 0; }
Code mẫu của RR
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair using namespace std; //Buffer reading int INP,AM; #define BUFSIZE (1<<10) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ fread(BUF,1,BUFSIZE,stdin); \ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const double PI = acos(-1.0); const int oo = 1000111000; struct Node { Node *ch[2]; int p; int size; int key, maxVal; Node(int newKey) { ch[0] = ch[1] = NULL; size = 1; p = rand(); key = maxVal = newKey; } } *root; void print2(Node *p) { if (!p) return ; print2(p->ch[0]); printf("%d ", p->key); print2(p->ch[1]); } void print(Node *p) { if (!p) { puts("Bst (0): ."); return ; } printf("Bst (%d): ", p->size); print2(p); puts("."); } void update(Node *p) { if (p == NULL) return ; p->size = 1; p->maxVal = p->key; REP(b,2) if (p->ch[b]) { p->size += p->ch[b]->size; p->maxVal = max(p->maxVal, p->ch[b]->maxVal); } } Node *rotate(Node *t, int b) { Node *s = t->ch[1-b]; t->ch[1-b] = s->ch[b]; s->ch[b] = t; update(t); update(s); return s; } inline int getSize(Node *p) { return p ? p->size : 0; } Node *get(Node *p, int k) { if (!p) return p; if (k <= getSize(p->ch[0])) return get(p->ch[0], k); k -= getSize(p->ch[0])+1; if (!k) return p; return get(p->ch[1], k); } Node *insert(Node *p, int k, int x) { if (!p) return new Node(x); int b = !(k <= getSize(p->ch[0]) + 1); if (!b) p->ch[0] = insert(p->ch[0], k, x); else p->ch[1] = insert(p->ch[1], k - getSize(p->ch[0]) - 1, x); if (p->p > p->ch[b]->p) p = rotate(p, 1-b); update(p); return p; } Node *erase(Node *p, int k) { if (!p) return p; if (k == getSize(p->ch[0]) + 1) { if (!p->ch[0] && !p->ch[1]) return NULL; else if (!p->ch[0]) p = rotate(p, 0); else if (!p->ch[1]) p = rotate(p, 1); else p = rotate(p, p->ch[0]->p < p->ch[1]->p); p = erase(p, k); } else { if (k <= getSize(p->ch[0])) p->ch[0] = erase(p->ch[0], k); else p->ch[1] = erase(p->ch[1], k-getSize(p->ch[0])-1); } update(p); return p; } int getMax(Node *p, int l, int r, int u, int v) { if (!p || l > r) return -oo; if (v < l || r < u) return -oo; if (u <= l && r <= v) return p->maxVal; int mid = l + getSize(p->ch[0]); int res = -oo; if (u <= mid && mid <= v) res = p->key; return max(max(getMax(p->ch[0], l, mid-1, u, v), getMax(p->ch[1], mid+1, r, u, v)), res); } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int q, x, y; scanf("%d\n", &q); while (q--) { char c = getchar(); if (c == 'A') { scanf("%d %d\n", &x, &y); root = insert(root, y, x); } else { scanf("%d %d\n", &x, &y); printf("%d\n", getMax(root, 1, root->size, x, y)); } // print(root); } return 0; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <utility> #include <vector> #define MAX_LEVEL 17 using namespace std; int INF = (1 << 30) - 5,Q; struct node { int level,value; node* nextNode[MAX_LEVEL]; int width[MAX_LEVEL]; int maxValue[MAX_LEVEL]; node(int _L,int _V) { level = _L; value = _V; for (int i = 0; i <= level; i++) { width[i] = 1; nextNode[i] = NULL; maxValue[i] = value; } } }; int randomLevel() { int L = 0; while (rand() % 2 < 1 && L + 1 < MAX_LEVEL) L++; return L; } struct skipList { node* head; void init() { head = new node(MAX_LEVEL - 1,-INF); } void insert(int pos,int value) { node* A = head; node* link[MAX_LEVEL]; int tmp = 0; for (int i = head->level; i >= 0; i--) { while (tmp + A->width[i] < pos) { tmp += A->width[i]; A = A->nextNode[i]; } link[i] = A; } node* B = new node(randomLevel(),value); for (int i = 0; i <= B->level; i++) { B->nextNode[i] = link[i]->nextNode[i]; link[i]->nextNode[i] = B; } for (int i = B->level + 1; i <= head->level; i++) { link[i]->width[i]++; link[i]->maxValue[i] = max(link[i]->maxValue[i],value); } link[0]->width[0] = 1; link[0]->maxValue[0] = link[0]->value; for (int i = 1; i <= B->level; i++) { link[i]->width[i] = 0; link[i]->maxValue[i] = link[i]->maxValue[i - 1]; node* C = link[i]; while (C != B) { link[i]->width[i] += C->width[i - 1]; link[i]->maxValue[i] = max(link[i]->maxValue[i],C->maxValue[i - 1]); C = C->nextNode[i - 1]; } } B->width[0] = 1; B->maxValue[0] = value; for (int i = 1; i <= B->level; i++) { B->width[i] = 0; B->maxValue[i] = B->maxValue[i - 1]; node* C = B; while (C != B->nextNode[i]) { B->width[i] += C->width[i - 1]; B->maxValue[i] = max(B->maxValue[i],C->maxValue[i - 1]); C = C->nextNode[i - 1]; } } } int maximum(int x,int y) { node* A = head; int tmp = 0; for (int i = head->level; i >= 0; i--) while (tmp + A->width[i] <= x) { tmp += A->width[i]; A = A->nextNode[i]; } int ret = -INF; int gap = y - x + 1,i = 0; while (gap > 0) { while (i < A->level && A->width[i + 1] <= gap) i++; while (A->width[i] > gap) i--; ret = max(ret,A->maxValue[i]); gap -= A->width[i]; A = A->nextNode[i]; } return ret; } } S; int main() { scanf("%d\n", &Q); S.init(); while (Q--) { char arg; int x,y; while (1) { scanf("%c", &arg); if (arg == 'Q' || arg == 'A') break; } scanf("%d %d\n", &x, &y); if (arg == 'A') S.insert(y,x); else printf("%d\n", S.maximum(x,y)); } }
Code mẫu của skyvn97
#include<cstdio> const int INF=(int)2e9; struct node { int val,maxv,high,balance,nnode; node *parent,*left,*right; node(){} void print(void) const { printf("Node properties: %d|%d|%d|%d|%d\n",val,maxv,high,balance,nnode); // if (this->left==NULL) printf("Left null\n"); else printf("Left %d\n",this->left->val); // if (this->right==NULL) printf("Right null\n"); else printf("Right %d\n",this->right->val); } }; node *root; int max(const int &x,const int &y) { if (x>y) return (x); else return (y); } int max(int x,int y,int z) { return (max(max(x,y),z)); } void tree_init() { root=NULL; } void treeview(node *a,int l) { if (a==NULL) return; int i; for (i=1;i<=l;i=i+1) printf("\t"); printf("%d|%d|%d|%d|%d\n",a->val,a->maxv,a->high,a->balance,a->nnode); // system("Pause"); for (i=1;i<=l;i=i+1) printf("\t"); printf("Left\n"); treeview(a->left,l+1); for (i=1;i<=l;i=i+1) printf("\t"); printf("Right\n"); treeview(a->right,l+1); } void create(node *&p,const int &x) { if (p!=NULL) return; p=new node(); p->val=x; p->maxv=x; p->high=1; p->balance=0; p->nnode=1; p->parent=NULL; p->left=NULL; p->right=NULL; } void calculate(node *p) { if (p==NULL) return; // printf("Before %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode); int l,r; if (p->left==NULL) l=0; else l=p->left->high; if (p->right==NULL) r=0; else r=p->right->high; p->high=max(l,r)+1; p->balance=l-r; if (p->left==NULL) l=0; else l=p->left->nnode; if (p->right==NULL) r=0; else r=p->right->nnode; p->nnode=l+r+1; if (p->left==NULL) l=-INF; else l=p->left->maxv; if (p->right==NULL) r=-INF; else r=p->right->maxv; p->maxv=max(l,r,p->val); // printf("After %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode); } void link(node *a,node *b,int dir) { if (a==NULL) { root=b; if (root!=NULL) root->parent=NULL; return; } if (dir==1) a->left=b; else a->right=b; if (b!=NULL) b->parent=a; } void left_rotation(node *a) { //printf("Left rotate %d\n",a->val); node *b,*c; int dir=0; c=a->parent; if (c!=NULL) { if (c->left==a) dir=1; else dir=2; } b=a->right; link(a,b->left,2); link(b,a,1); link(c,b,dir); calculate(a); calculate(b); // a->print(); } void right_rotation(node *a) { //printf("Right rotate %d\n",a->val); node *b,*c; c=a->parent; int dir=0; if (c!=NULL) { if (c->left==a) dir=1; else dir=2; } b=a->left; link(a,b->right,1); link(b,a,2); link(c,b,dir); calculate(a); calculate(b); } void rebalance(node *a) { node *c; while (a!=NULL) { calculate(a); c=a->parent; //printf("rebalancing %d\n",a->val); if (a->balance==2) { if (a->left->balance==-1) left_rotation(a->left); right_rotation(a); } if (a->balance==-2) { if (a->right->balance==1) right_rotation(a->right); left_rotation(a); } a=c; } } void insert(const int &i,const int &x) { // printf("insert %d %d\n",i,x); node *p,*q; int rem=0; int nleft; int dir=0; p=root; q=NULL; while (p!=NULL) { q=p; if (p->left==NULL) nleft=0; else nleft=p->left->nnode; if (rem+nleft+1>=i) { p=p->left; dir=1; } else { rem+=nleft+1; p=p->right; dir=2; } } // if (q==NULL) printf("insert to root %d\n",dir); // else printf("insert to %d %d\n",q->val,dir); if (p==NULL) { create(p,x); if (root==NULL) root=p; else { link(q,p,dir); //treeview(root); rebalance(p); } } } int maxhigh(node *a,int l,int r,int u,int v) { // printf("Get max %d %d %d %d\n",l,r,u,v); // if (a!=NULL) a->print(); // else printf("NULL\n"); if (l>v) return (-INF); if (r<u) return (-INF); if (l>r) return (-INF); if (v<u) return (-INF); if (a==NULL) return (-INF); if (u<=l && r<=v) return (a->maxv); int nleft; if (a->left==NULL) nleft=0; else nleft=a->left->nnode; int left=maxhigh(a->left,l,l+nleft-1,u,v); int right=maxhigh(a->right,l+nleft+1,r,u,v); int mid; if (u<=l+nleft && l+nleft<=v) mid=a->val; else mid=-INF; return (max(left,mid,right)); } int n,q; int maxhigh(const int &u,const int &v) { // printf("Answering from %d to %d\n",u,v); return (maxhigh(root,1,n,u,v)); } void process(void) { n=0; tree_init(); char c; int i,x,y; scanf("%d",&q); for (i=1;i<=q;i=i+1) { scanf(" %c",&c); scanf("%d",&x); scanf("%d",&y); if (c=='A') { // printf("Insertion started\n"); insert(y,x); // treeview(root,0); // printf("\n"); n++; // printf("Insertion completed\n"); // system("pause"); } else printf("%d\n",maxhigh(x,y)); } } int main(void) { #ifndef ONLINE_JUDGE //freopen("tmp.txt","r",stdin); #endif process(); return 0; }
Code mẫu của khuc_tuan
#include <cstring> #include <cstdlib> #include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int BITMASK = 0xFFFFF; template <class E> struct Treap { struct Node { Node *L, *R, *P; E value; int total; int rank; E maxvalue; int c; Node(E value) : value(value), total(1), c(0) { this->rank = rand() & BITMASK; L = R = P = NULL; } void updateTotal() { total = 1 + (L == NULL ? 0 : L->total) + (R == NULL ? 0 : R->total); maxvalue = value; if(L != NULL) maxvalue = max(maxvalue, L->maxvalue); if(R != NULL) maxvalue = max(maxvalue, R->maxvalue); } }; Node *root; int count; Treap() { root = NULL; count = 0; } void rotateLeft(Node *node) { Node *a = node->R; Node *fa = node->P; node->R = a->L; a->L = node; if(node->R != NULL) node->R->P = node; node->P = a; a->P = fa; if(fa == NULL) root = a; else if(fa->L == node) fa->L = a; else fa->R = a; node->updateTotal(); a->updateTotal(); } void rotateRight(Node *node) { Node *a = node->L; Node *fa = node->P; node->L = a->R; a->R = node; if(node->L != NULL) node->L->P = node; node->P = a; a->P = fa; if(fa == NULL) root = a; else if(fa->L == node) fa->L = a; else fa->R = a; node->updateTotal(); a->updateTotal(); } void pushdown(Node *n) { while(n->L != NULL || n->R != NULL) { Node *p = n->L; if(p == NULL || (n->R != NULL && n->R->rank < p->rank)) p = n->R; if(p->rank < n->rank) { if(p == n->L) rotateRight(n); else rotateLeft(n); } else break; } } void pushup(Node *n) { while(n->P != NULL) { if(n->rank < n->P->rank) { if(n == n->P->L) rotateRight(n->P); else rotateLeft(n->P); } else break; } } void add(E value) { ++count; if(root == NULL) root = new Node(value); else { Node *p = root; while(true) { p->total++; bool lessoreq = !(p->value < value); if(lessoreq && p->L != NULL) p = p->L; else if(!lessoreq && p->R != NULL) p = p->R; else break; } bool lessoreq = !(p->value < value); if(lessoreq) { p->L = new Node(value); p->L->P = p; pushup(p->L); } else { p->R = new Node(value); p->R->P = p; pushup(p->R); } } } Node* find(E value) { Node *p = root; while(p != NULL) { bool less = value < p->value; bool gr = p->value < value; if(!less && !gr) return p; else if(less) p = p->L; else p = p->R; } return NULL; } bool contain(E value) { return find(value) != NULL; } void remove(E value) { Node *p = find(value); if(p != NULL) { --count; p->rank = 1<<30; pushdown(p); Node *fa = p->P; if(fa != NULL) if(p == fa->L) fa->L = NULL; else fa->R = NULL; if(fa == NULL) root = NULL; while(fa != NULL) { fa->total--; fa = fa->P; } } } Node* findK(int k) { Node *p = root; int onleft = 0; while(true) { int newonleft = onleft + (p->L == NULL ? 0 : p->L->total); if(newonleft == k) return p; else if(newonleft > k) p = p->L; else { onleft = newonleft + 1; p = p->R; } } } int toIndex(Node *n) { if(n == NULL) return count; int id = 0; if(n->L != NULL) id = n->L->total; while(n != NULL) { Node *p = n->P; if(p != NULL && p->R == n) id += (p->L == NULL ? 0 : p->L->total) + 1; n = p; } return id; } Node* upperBound(Node *root, E value) { if(root == NULL) return NULL; bool less = value < root->value; if(less) { Node *r = upperBound(root->L, value); if(r != NULL) return r; else return root; } else return upperBound(root->R, value); } Node* lowerBound(Node *root, E value) { if(root == NULL) return NULL; bool leoreq = !(root->value < value); if(leoreq) { Node *r = lowerBound(root->L, value); if(r != NULL) return r; else return root; } else return lowerBound(root->R, value); } pair<Treap,Treap> split(int m) { // first m elements -> 1 tree, remains -> 1 tree Treap left, right; if(m >= count) return make_pair(*this,Treap()); else if(m <= 0) return make_pair(Treap(),*this); else { Node *p = findK(m); p->rank = -1<<30; pushup(p); left.root = p->L; p->L->P = NULL; p->L = NULL; p->updateTotal(); right.root = p; left.count = (left.root == NULL ? 0 : left.root->total); right.count = (right.root == NULL ? 0 : right.root->total); p->rank = rand() & BITMASK; right.pushdown(p); return make_pair(left, right); } } Treap mergeWith(Treap tr) { if(tr.root == NULL) return *this; if(root == NULL) return tr; Node *p = tr.findK(0); p->rank = -1<<30; tr.pushup(p); p->L = root; root->P = p; p->updateTotal(); Treap res; res.root = p; res.count = p->total; p->rank = rand() & BITMASK; res.pushdown(p); return res; } }; Treap<int> tr; char buf[1000]; int n, sz; int main() { scanf("%d", &n); gets(buf); for(int i=0;i<n;++i) { gets(buf); int x, y; sscanf(buf+1, "%d%d", &x, &y); if(buf[0] == 'A') { if(sz == 0) tr.add(x); else { Treap<int>::Node *p = tr.findK((y == sz + 1) ? (sz - 1) : (y - 1)); p->rank = 1<<30; tr.pushdown(p); Treap<int>::Node *nn = new Treap<int>::Node(x); if(y == sz + 1) p -> R = nn, nn->P = p; else p -> L = nn, nn -> P = p; for(Treap<int>::Node *q=nn;q!=NULL;q=q->P) q->updateTotal(); p->rank = rand() & BITMASK; tr.pushup(p); tr.pushup(nn); } ++sz; } else { Treap<int>::Node *u = tr.findK(x - 1); Treap<int>::Node *v = tr.findK(y - 1); Treap<int>::Node *p, *fa; for(p=u;p!=NULL;p=p->P) p->c++; for(p=v;p!=NULL;p=p->P) p->c++; int res = u->value; if(u->c < 2 && u->R != NULL) res = max( res, u->R->maxvalue); p = u; while(p->c < 2) { fa = p->P; if(fa->L == p) { res = max( res, fa->value); if(fa->c < 2 && fa->R != NULL) res = max( res, fa->R->maxvalue); } p = fa; } res = max(res, v->value); if(v->c < 2 && v->L != NULL) res = max( res, v->L->maxvalue); p = v; while(p->c < 2) { fa = p->P; if(fa->R == p) { res = max( res, fa->value); if(fa->c < 2 && fa->L != NULL) res = max( res, fa->L->maxvalue); } p = fa; } for(p=u;p!=NULL;p=p->P) p->c--; for(p=v;p!=NULL;p=p->P) p->c--; printf("%d\n", res); } } return 0; }
Comments