fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <string.h>
  27. #include <fstream>
  28. #include <cassert>
  29. using namespace std;
  30.  
  31. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  32. #define sz(a) int((a).size())
  33. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  34. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  35. #define fore(x, a) for(auto &&x : a)
  36. typedef long long ll;
  37. const int mod = 1000000007;
  38. const int N = 100005;
  39.  
  40. ll po(ll x, ll y) {
  41.   if (y == 0) return 1;
  42.   ll ret = po(x, y / 2);
  43.   ret = (ret * ret) % mod;
  44.   if (y % 2) {
  45.     ret = (ret * x) % mod;
  46.   }
  47.   return ret;
  48. }
  49.  
  50.  
  51. ll inv(ll x) {
  52.   return po(x, mod - 2);
  53. }
  54.  
  55. ll f(ll n) {
  56.   ll res = po(7, n);
  57.   ll y = (6 * n-1) % mod;
  58.   res = (res*y) % mod;
  59.   res = ((res + 1) * 7) % mod;
  60.   res = (res*inv(36)) % mod;
  61.   if (res < 0) res += mod;
  62.   return res;
  63. }
  64.  
  65. ll a[N];
  66.  
  67. ll read(int x) {
  68.   ll sum = 0;
  69.   while (x > 0) {
  70.     sum += a[x];
  71.     if (sum >= mod) sum -= mod;
  72.     x -= (x&-x);
  73.   }
  74.   return sum;
  75. }
  76.  
  77. void upd(int x, int v) {
  78.   while (x < N) {
  79.     a[x] += v;
  80.     if (a[x] >= mod) a[x] -= mod;
  81.     if (a[x] < 0) a[x] += mod;
  82.     x += (x&-x);
  83.   }
  84. }
  85.  
  86. int b[N];
  87.  
  88. int main() {
  89. #ifdef loc
  90.   if(!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
  91.     assert(0);
  92.   }
  93.   freopen((string(FOLDER) + "out.txt").c_str(), "w", stdout);
  94. #endif
  95.   boost;
  96.   int n, q;
  97.   cin >> n >> q;
  98.   rep(i, 1, n) {
  99.     int x;
  100.     cin >> x;
  101.     upd(i, f(x));
  102.     b[i] = x;
  103.   }
  104.   while (q-- > 0) {
  105.     int ty;
  106.     cin >> ty;
  107.     if (ty == 1) {
  108.       int x, v;
  109.       cin >> x >> v;
  110.       upd(x, -f(b[x]));
  111.       b[x] = v;
  112.       upd(x, f(v));
  113.     }
  114.     else {
  115.       int l, r, s;
  116.       cin >> l >> r >> s;
  117.       int ans = read(r) - read(l - 1);
  118.       if (ans < 0) ans += mod;
  119.       ans = (ans + s*1LL*(r - l + 1)) % mod;
  120.       cout << ans << '\n';
  121.     }
  122.   }
  123.   return 0;
  124. }
Runtime error #stdin #stdout 0.38s 4640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OrBTQ3
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!