Advertisement
Guest User

Untitled

a guest
Apr 4th, 2016
1,524
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn=2e3+7;
  5.  
  6. vector<int> a;
  7. vector<int> t(4*maxn);
  8. vector<int> add(4*maxn,0);
  9.  
  10. void push(int v)
  11. {
  12. if(add[v])
  13. {
  14. add[v*2]+=add[v];
  15. add[v*2+1]+=add[v];
  16. add[v]=0;
  17. }
  18. }
  19. void build(int v,int tl,int tr)
  20. {
  21. if(tl==tr)
  22. {
  23. t[v]=a[tl];
  24. }
  25. else
  26. {
  27. int tm=(tl+tr)/2;
  28. build(v*2,tl,tm);
  29. build(v*2+1,tm+1,tr);
  30. }
  31. }
  32.  
  33. int get(int v,int tl,int tr,int pos)
  34. {
  35. if(tl==tr)
  36. {
  37. t[v]+=add[v];
  38. add[v]=0;
  39. return t[v];
  40. }
  41. else
  42. {
  43. int tm=(tl+tr)/2;
  44. push(v);
  45. if(pos<=tm)
  46. {
  47. return get(v*2,tl,tm,pos);
  48. }
  49. else
  50. {
  51. return get(v*2+1,tm+1,tr,pos);
  52. }
  53. }
  54. }
  55.  
  56. void Add(int v,int tl,int tr,int l,int r,int val)
  57. {
  58. if(l>r)
  59. {
  60. return;
  61. }
  62. if(tl==l && tr==r)
  63. {
  64. add[v]+=val;
  65. return;
  66. }
  67. else
  68. {
  69. int tm=(tl+tr)/2;
  70. Add(v*2,tl,tm,l,min(r,tm),val);
  71. Add(v*2+1,tm+1,tr,max(tm+1,l),r,val);
  72. }
  73. }
  74. void solve()
  75. {
  76. int n;
  77. cin >> n;
  78. a.resize(n);
  79. for(int i=0;i<n;i++)
  80. {
  81. cin >> a[i];
  82. }
  83. build(1,0,n-1);
  84. while(1)
  85. {
  86. int x;
  87. cin >> x;
  88. if(x==1)
  89. {
  90. int l,r,val;
  91. cin >> l >> r >> val;
  92. Add(1,0,n-1,l-1,r-1,val);
  93. // прибавление на отрезке
  94. }
  95. else
  96. {
  97. int pos;
  98. cin >> pos;
  99. // вывод элемента
  100. cout << get(1,0,n-1,pos-1)<<endl;
  101. }
  102. }
  103.  
  104.  
  105. }
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112. #define FILE "random"
  113. int main()
  114. {
  115.  
  116. // freopen("input.txt","r",stdin);
  117. // freopen("output.txt","w",stdout);
  118.  
  119. // freopen(FILE".in","r",stdin);
  120. // freopen(FILE".out","w",stdout);
  121. if(!debug)
  122. {
  123. ios_base::sync_with_stdio(0);
  124. cin.tie(0);
  125. cout.tie(0);
  126. }
  127. int t=1;
  128. while(t--)
  129. solve();
  130. return 0;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement