Advertisement
Guest User

Untitled

a guest
Sep 12th, 2019
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. struct a{
  4. int bestleft, bestright, wholesum, bestsum;
  5. };
  6. a seg[1000000];
  7. int arr[1000000];
  8. void update(int s, int e, int us, int ue, int k, int idx){
  9. if(s>=us && e<=ue){
  10.     seg[idx].wholesum+=k;
  11.     //cout<<seg[idx].wholesum;
  12.     return;
  13. }
  14. else if(e<us || s>ue){
  15.     return;
  16. }
  17. int mid=(s+e)/2;
  18. update(mid+1, e, us, ue, k, idx*2+1);
  19. update(s, mid, us, ue, k, idx*2);
  20. seg[idx].wholesum=seg[idx*2].wholesum+seg[idx*2+1].wholesum;
  21. //cout<<seg[idx].wholesum<<endl;
  22. }
  23. void update1(int s, int e, int us, int ue, int idx){
  24. if(s>=us && e<=ue){
  25.     seg[idx].bestleft=seg[idx].wholesum;
  26.     seg[idx].bestright=seg[idx].wholesum;
  27.     return;
  28. }
  29. else if(e<us || s>ue)
  30.     return;
  31. int mid=(s+e)/2;
  32. update1(mid+1, e, us, ue, idx*2+1);
  33. update1(s, mid, us, ue, idx*2);
  34. seg[idx].bestleft=max(seg[idx*2].bestleft, seg[idx*2].wholesum+seg[idx*2+1].bestleft);
  35. seg[idx].bestright=max(seg[idx*2+1].bestright, seg[idx*2+1].wholesum+seg[idx*2].bestright);
  36. }
  37. void update2(int s, int e, int us, int ue, int idx){
  38. if(s>=us && e<=ue){
  39.     seg[idx].bestsum=seg[idx].wholesum;
  40.     return;
  41. }
  42. else if(e<us || s>ue)
  43.     return;
  44. int mid=(s+e)/2;
  45. update2(mid+1, e, us, ue, idx*2+1);
  46. update2(s, mid, us, ue, idx*2);
  47. seg[idx].bestsum=max(max(seg[idx*2].bestsum, seg[idx*2+1].bestsum), seg[idx*2].bestright+seg[idx*2+1].bestleft);
  48. }
  49. int query(int s, int e, int us, int ue, int idx){
  50. if(s==us && e==ue)
  51.     return seg[idx].bestsum;
  52. else if(e<us || s>ue)
  53.     return 0;
  54. int mid=(s+e)/2;
  55. return query(mid+1, e, us, ue, idx)+query(s, mid, us, ue, idx);
  56. }
  57. int main(){
  58. ios::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. int n;
  62. cin>>n;
  63. for(int i=0; i<n; i++){
  64.     cin>>arr[i];
  65.     update(1, n, i+1, i+1, arr[i], 1);
  66. }
  67. for(int i=0; i<n; i++)
  68.     update1(1, n, i+1, i+1, 1);
  69. for(int i=0; i<n; i++)
  70.     update2(1, n, i+1, i+1, 1);
  71. //for(int i=1; i<=7; i++){
  72.     //cout<<seg[i].bestleft<<" "<<seg[i].bestright<<" "<<seg[i].bestsum<<" "<<seg[i].wholesum<<endl;
  73. //}
  74. int m;
  75. cin>>m;
  76. for(int i=0; i<m; i++){
  77.     int a, b;
  78.     cin>>a>>b;
  79.     query(1, n, a, b, 1);
  80.     //cout<<query(1, n, a, b, 1)<<endl;
  81. }
  82. //for(int i=1; i<=5; i++){
  83.     //cout<<seg[i].bestsum<<endl;
  84. //}
  85. return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement