Guest User

Untitled

a guest
Sep 8th, 2013
261
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <iostream>
  3. #include <sstream>
  4. using namespace std;
  5.  
  6. class SegmentTree{
  7. private:
  8. long *A,*M,*L,*R,*T;
  9. long n;
  10. void preprocess(long node,long lo,long hi);
  11. long *query(long node,long i,long j,long lo,long hi);
  12. void update(long node,long i,long val,long lo,long hi);
  13. public :
  14. SegmentTree(long *A,long n);
  15. void preprocess();
  16. long query(long i,long j);
  17. void printM();
  18. void update(long i,long val);
  19. };
  20.  
  21. void SegmentTree::update(long i,long val){
  22. update(1,i,val,0,n-1);
  23. }
  24.  
  25. void SegmentTree::update(long node,long idx,long val,long lo,long hi){
  26. if(lo==hi && idx==hi) M[node]=val, L[node]=val, R[node]=val, T[node]=val;
  27. else{
  28. long mid=(hi+lo)/2;
  29. if(idx<=mid) update(node*2,idx,val,lo,mid);
  30. else update(node*2+1,idx,val,mid+1,hi);
  31.  
  32. //fix M[node]
  33. long left=M[2*node];
  34. long right=M[2*node+1];
  35. long max_lr=max(left,right);
  36. long tmp=R[2*node]+L[2*node+1];
  37. M[node]=max(max_lr,tmp);
  38.  
  39. //fix L[node]
  40. tmp=T[node*2]+L[2*node+1];
  41. L[node]=max(tmp,L[node*2]);
  42.  
  43. //fix R[node]
  44. tmp=T[node*2+1]+R[2*node];
  45. R[node]=max(tmp,R[2*node+1]);
  46.  
  47. // fix T[node]
  48. T[node]=T[node*2]+T[node*2+1];
  49. }
  50. }
  51.  
  52. long SegmentTree::query(long i,long j){
  53. long *a=query(1,i,j,0,n-1);
  54.  
  55. return a[0];
  56. }
  57.  
  58. long *SegmentTree::query(long node,long i,long j,long lo,long hi){
  59. //cout<<lo<<' '<<hi<<endl;
  60. if(i>hi || j<lo) return NULL;
  61.  
  62. // 0-max 1-left 2-right 3-total
  63. long *temp=new long[4];
  64. if(i<=lo && j>=hi) {
  65. temp[0]=M[node], temp[1]=L[node], temp[2]=R[node], temp[3]=T[node];
  66. //cout<<temp[0]<<endl;;
  67. return temp;
  68. }
  69. long *left=query(node*2,i,j,lo,(hi+lo)/2);
  70. long *right=query(node*2+1,i,j,(hi+lo)/2+1,hi);
  71. if(left==NULL) return right;
  72. if(right==NULL) return left;
  73.  
  74. //fix max
  75. long max_lr=max(left[0],right[0]);
  76. //cout<<lo<<"---"<<hi<<endl;
  77. //cout<<M[node*2]<<' '<<M[node*2+1]<<endl;
  78. long tmp1=left[2]+right[1];
  79. temp[0]=max(max_lr,tmp1);
  80.  
  81. // fix left
  82. long tmp2=left[3]+right[1];
  83. temp[1]=max(tmp2,left[1]);
  84.  
  85. //fix right
  86. long tmp3=left[2]+right[3];
  87. temp[2]=max(tmp3,right[2]);
  88.  
  89. //fix total
  90. long tmp4=left[3]+right[3];
  91. temp[3]=tmp4;
  92.  
  93. return temp;
  94. }
  95.  
  96. void SegmentTree::printM(){
  97. for(long i=1;i<(n<<1);i++) cout<<M[i]<<'\t'<<L[i]<<'\t'<<R[i]<<'\t'<<T[i]<<endl;
  98. }
  99.  
  100. SegmentTree::SegmentTree(long *A,long n){
  101. this->A=A;
  102. this->n=n;
  103. M=new long[n<<1], L=new long[n<<1], R=new long[n<<1], T=new long[n<<1];
  104. }
  105.  
  106. void SegmentTree::preprocess(long node,long lo,long hi){
  107. if(hi==lo) M[node]=A[hi], L[node]=A[hi], R[node]=A[hi], T[node]=A[hi];
  108. else{
  109. preprocess(node*2,lo,(hi+lo)/2);
  110. preprocess(node*2+1,(hi+lo)/2+1,hi);
  111.  
  112. //fix M[node]
  113. long left=M[2*node];
  114. long right=M[2*node+1];
  115. long max_lr=max(left,right);
  116. long mid=R[2*node]+L[2*node+1];
  117. M[node]=max(max_lr,mid);
  118.  
  119. //fix L[node]
  120. long tmp=T[node*2]+L[2*node+1];
  121. L[node]=max(tmp,L[node*2]);
  122.  
  123. //fix R[node]
  124. tmp=T[node*2+1]+R[2*node];
  125. R[node]=max(tmp,R[2*node+1]);
  126.  
  127. // fix T[node]
  128. T[node]=T[node*2]+T[node*2+1];
  129. }
  130. }
  131.  
  132. void SegmentTree::preprocess(){
  133. preprocess(1,0,n-1);
  134. }
  135.  
  136. int main(){
  137. ios_base::sync_with_stdio(false);
  138. stringstream ss;
  139. long n;
  140. cin>>n;
  141. long *a=new long[n];
  142. for(long i=0;i<n;i++) cin>>a[i];
  143. SegmentTree *seg_tree=new SegmentTree(a,n);
  144. seg_tree->preprocess();
  145.  
  146. long m;
  147. cin>>m;
  148. while(m--){
  149. long i,j;
  150. cin>>i>>j;
  151. ss<<seg_tree->query(i-1,j-1)<<'\n';
  152. }
  153. cout<<ss.str();
  154. return 0;
  155. }
RAW Paste Data