Advertisement
minimario

<BIT> TEMPLATE

Dec 12th, 2015
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define mp make_pair
  6. #define pb push_back
  7. #define pii pair <int, int>
  8. #define vi vector<int>
  9.  
  10. #define read1(a) int a; scanf("%d", &a)
  11. #define read2(a, b) int a, b; scanf("%d %d", &a, &b)
  12. #define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)
  13.  
  14. #define FOR(i, a, b) for (int i=a; i<b; i++)
  15. #define F0R(i, a) for (int i=0; i<a; i++)
  16.  
  17. #define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
  18. #define readgs(n) F0R(i, n) { scanf(" %c", &arr[i]); }
  19.  
  20. #define f first
  21. #define s second
  22.  
  23. const int MOD = 1000000007;
  24. const int MAX = 100005;
  25.  
  26. int arr[MAX];
  27. ll tree[MAX];
  28. void upd(int idx, ll val) {
  29.     while (idx < MAX - 1) {
  30.         tree[idx] = (tree[idx] + val) % MOD;
  31.         idx += (idx & -idx);
  32.     }
  33. }
  34.  
  35. ll get(int idx) {
  36.     ll ans = 0;
  37.     while (idx > 0) {
  38.         ans = (ans + tree[idx]) % MOD;
  39.         idx -= (idx & -idx);
  40.     }
  41.     return ans;
  42. }
  43.  
  44. int main() {
  45.     upd(2, 1);
  46.     upd(6, 4);
  47.     upd(7, 2);
  48.     cout << get(7) << endl;
  49.     /* 7 */
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement