Topic: POJ2104
Using tree, chairman of problem solving, almost the same code, but a code to AC, a code RE?
AC code:

 
# include & lt; Iostream> 
# include & lt; Cstdio> 
# include & lt; Cstring> 
# include & lt; Algorithm> 
Using namespace STD. 
Const int maxn=100001; 
Struct Node {
Int the ls, rs; 
Int CNT. 
} the tr [20] maxn *; 
Int cur, rt (maxn); 
Void init () {
Cur=0; 
} 
The inline void push_up (int o {
Tr [o] CNT=tr ls [tr [o]] CNT + tr [tr [o] rs] CNT. 
} 
Int the build (int int l, r) {
Int k=cur++; 
If (l==r) {
Tr [k]. CNT=0; 
The return of k; 
} 
Int mid=(l + r) & gt;> 1; 
Tr [k]. Ls=build (l, mid); 
Tr [k]. Rs=build (mids + 1, r); 
Push_up (k); 
The return of k; 
} 
Int the update (int o, int l, int r, int pos, int val) {
Int k=cur++; 
Tr=tr [k] [o]; 
If (l==pos& & R=={pos) 
Tr [k]. CNT +=val; 
The return of k; 
} 
Int mid=(l + r) & gt;> 1; 
If (pos<=mid) tr [k]. Ls=update (tr [o]. Ls, l, mid, pos, val); 
The else tr [k]. Rs=update (tr [o] rs, mid + 1, r, pos, val); 
Push_up (k); 
The return of k; 
} 
Int query (int l, int r, int o, int v, int KTH) {
If (l==r) return the l; 
Int mid=(l + r) & gt;> 1; 
Int res=tr ls [tr [v]] - tr CNT ls [tr [o]] CNT. 
If (kth<=res) return query (l, mid, tr [o]. Ls, tr [v]. Ls, KTH); 
The else return query (mids + 1, r, tr [o] rs, tr [v]. Rs, KTH - res); 
} 
Int b [maxn]; 
Int sortb [maxn]; 
Int main () 
{
Int n, m; 
Int T; 
//the scanf (" % d ", & amp; T); 
//while (T -) {
While (~ the scanf (" % d % d ", & amp; N, & amp; M)) {
init(); 
For (int I=1; I<=n; I++) {
The scanf (" % d ", & amp; B [I]); 
Sortb [I] [I]=b; 
} 
Sort (sortb sortb + 1, + 1 + n); 
Int CNT=1; 
For (int I=2; I<=n; I++) {
If (sortb [I]!=sortb [CNT]) {
Sortb [+ + CNT]=sortb [I]; 
} 
} 
Rt [0]=build (1, CNT); 
For (int I=1; I<=n; I++) {
Int p=lower_bound (sortb + 1, sortb + CNT + 1, b [I]) - sortb; 
Rt [I]=update (rt] [I - 1, 1, CNT, p, 1); 
} 
for (int i=0; IInt a, b, k; 
The scanf (" % d % d % d ", & amp; A, & amp; B, & amp; K); 
Int independence idx=query (1, CNT, rt (a - 1), rt [b], k); 
Printf (" % d \ n ", sortb [independence idx]); 
} 
} 
return 0; 
} 

RE code:

 
# include & lt; Stdio. H> 
# include & lt; String. H> 
# include & lt; Algorithm> 
# include & lt; Math. H> 
# include & lt; Iostream> 
Using namespace STD. 
Const int MAXN=100001; 
Struct Node {
Int l, r; 
Int CNT. 
Tree * MAXN [20]}; 
Int cur;//note down the number of node 
Int root [MAXN];//save every time the location of the updated 
Int a [MAXN], b [MAXN]; 
Void init () {
Cur=0; 
} 
Void PushUp (int) node {
Tree [node] CNT=tree [tree [node]. L] CNT + tree [tree [r]. Node r]. CNT. 
} 
Int the build (int int l, r) {
Int k=cur++; 
If (l==r) {
Tree [k]. CNT=0; 
The return of k; 
} 
Int mid=(l + r)/2; 
Tree [k]. L=build (l, mid); 
Tree [k]. R=build (mids + 1, r); 
PushUp (k); 
The return of k; 
} 
Int the update (int node, int l, int r, int x, int v) {
Int k=cur++; 
Tree [k]=tree (node); 
If (l==x & amp; & R=={x) 
Tree [k]. CNT +=v; 
The return of k; 
} 
Int mid=(l + r)/2; 
If (mid>=x) 
Tree [k]. L=update (tree) [r]. The node l, l, mid, x, v); 
The else 
Tree [k]. R=update (tree) [r]. Node r, mid + 1, r, x, v); 
PushUp (k); 
The return of k; 
} 
Int query (int node1, int 2, int l, int r, int k) {//node1 said the previous version, 2 said after a version 
If (l==r) 
Return the l; 
Int mid=(l + r)/2; 
Tree [2]. Int res=tree [l]. CNT - tree [tree [node1]. L] CNT. 
If (res>=k) 
Return the query (tree [node1]. L, tree [2]. L, l, mid, k); 
Return the query (tree) [r]. Node1 r, tree [2]. R, mid + 1, r, k - res); 
} 
Int main () {
Int n, m; 
While (~ the scanf (" % d % d ", & amp; N, & amp; M)) {
init(); 
For (int I=1; I<=n; I++) {
The scanf (" % d ", & amp; A [I]); 
B=[I] a [I]; 
} 
Sort (b + 1, b + n + 1); 
Int TMP=unique (b + 1, b + n + 1) - b; 
Root [0]=build (1, TMP); 
For (int I=1; I<=n; I++) {
Int temp=lower_bound (b + 1, b + TMP + 1, a [I]) - b; 
Root [I]=update (root] [I - 1, 1, TMP, temp, 1); 
} 
for (int i=0; IInt l, r, k; 
The scanf (" % d % d % d ", & amp; L, & amp; R, & amp; K); 
Int temp=query (root [l - 1), the root [r], 1, TMP, k); 
Printf (" % d \ n ", b [\]); 
} 
} 

return 0; 
} 

CodePudding user response:

Weak to ask, AC, RE what do you mean? The Accept and Reject?

CodePudding user response:

refer to the second floor catchyrime response:

Quote: refer to 1st floor u010165006 response:

Weak to ask, AC, RE what do you mean? The Accept and Reject?

AC=Accepted, RE=Runtime Error
Chairman said still can't write tree

Chairman of the tree?

CodePudding user response:

reference ooolinux reply: 3/f

Quote: refer to the second floor catchyrime response:

nullnullnullnullnullnull