fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef long double ld;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. typedef vector<bool> vb;
  10. typedef vector<string> vs;
  11. typedef pair<int, int> pii;
  12. typedef pair<ll, ll> pll;
  13. typedef pair<int, ll> pil;
  14. typedef pair<ll, int> pli;
  15. typedef vector<pii> vpii;
  16. typedef vector<pll> vpll;
  17. typedef map<int, int> mii;
  18. typedef map<ll, ll> mll;
  19. typedef set<int> si;
  20. typedef set<ll> sll;
  21. typedef priority_queue<int> max_heap_i;
  22. typedef priority_queue<int, vi, greater<int>> min_heap_i;
  23. typedef priority_queue<ll> max_heap_ll;
  24. typedef priority_queue<ll, vll, greater<ll>> min_heap_ll;
  25.  
  26. #define FOR(a, b, c) for (int a = (b); a <= (c); a++)
  27. #define FORD(a, b, c) for (int a = (b); a >= (c); a--)
  28. #define REP(i, n) for (int i = 0; i < (n); i++)
  29. #define REPD(i, n) for (int i = (n) - 1; i >= 0; i--)
  30. #define endl '\n'
  31. #define fi first
  32. #define se second
  33. #define pb push_back
  34. #define eb emplace_back
  35. #define all(x) (x).begin(), (x).end()
  36. #define rall(x) (x).rbegin(), (x).rend()
  37. #define sz(x) (int)(x).size()
  38.  
  39. #define BIT(n) (1 << (n))
  40. #define SET(k, n) ((n) | BIT(k))
  41. #define CLEAR(k, n) ((n) & ~BIT(k))
  42. #define TOGGLE(k, n) ((n) ^ BIT(k))
  43. #define CHECK(k, n) (!!((n) & BIT(k)))
  44. #define MSB(x) ((x) == 0 ? -1 : 63 - __builtin_clzll(x))
  45.  
  46. #define debug(x) clog << #x << " = " << (x) << endl
  47.  
  48. const int MAXARR = 1e7 + 15;
  49. const int INF = 1e9 + 7;
  50. const ll INF64 = 2e18 + 7;
  51. const int MOD = 1e9 + 7;
  52.  
  53. void fixIO()
  54. {
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57. }
  58.  
  59. void File(const string &fileName = "")
  60. {
  61.     if (fopen((fileName + ".INP").c_str(), "r"))
  62.     {
  63.         freopen((fileName + ".INP").c_str(), "r", stdin);
  64.         freopen((fileName + ".OUT").c_str(), "w", stdout);
  65.     }
  66. }
  67.  
  68. int n, q;
  69.  
  70. void Read()
  71. {
  72.     cin >> n >> q;
  73. }
  74.  
  75. vll tree, lazyadd, lazymul;
  76.  
  77.  
  78. // $x \rightarrow (x \times mul + add) \pmod{MOD}$
  79. void Apply(int node, int left, int right, ll mul, ll add)
  80. {
  81.     ll len = right - left + 1;
  82.     tree[node] = (tree[node] * mul % MOD + add * len % MOD) % MOD;
  83.     lazymul[node] = (lazymul[node] * mul) % MOD;
  84.     lazyadd[node] = (lazyadd[node] * mul % MOD + add) % MOD;
  85. }
  86.  
  87. void Pushdown(int node, int left, int right)
  88. {
  89.     if (lazyadd[node] == 0 && lazymul[node] == 1)
  90.     {
  91.         return;
  92.     }
  93.     int mid = left + (right - left) / 2;
  94.     Apply(node * 2, left, mid, lazymul[node], lazyadd[node]);
  95.     Apply(node * 2 + 1, mid + 1, right, lazymul[node], lazyadd[node]);
  96.     lazymul[node] = 1;
  97.     lazyadd[node] = 0;
  98. }
  99.  
  100. void Update1(int node, int left, int right, int qleft, int qright, ll val)
  101. {
  102.     if (qleft <= left && right <= qright)
  103.     {
  104.         Apply(node, left, right, 1, val % MOD);
  105.         return;
  106.     }
  107.     Pushdown(node, left, right);
  108.     int mid = left + (right - left) / 2;
  109.     if (qleft <= mid)
  110.     {
  111.         Update1(node * 2, left, mid, qleft, qright, val);
  112.     }
  113.     if (qright > mid)
  114.     {
  115.         Update1(node * 2 + 1, mid + 1, right, qleft, qright, val);
  116.     }
  117.     tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % MOD;
  118. }
  119.  
  120. void Update2(int node, int left, int right, int qleft, int qright, ll val)
  121. {
  122.     if (qleft <= left && right <= qright)
  123.     {
  124.         Apply(node, left, right, val % MOD, 0);
  125.         return;
  126.     }
  127.     Pushdown(node, left, right);
  128.     int mid = left + (right - left) / 2;
  129.     if (qleft <= mid)
  130.     {
  131.         Update2(node * 2, left, mid, qleft, qright, val);
  132.     }
  133.     if (qright > mid)
  134.     {
  135.         Update2(node * 2 + 1, mid + 1, right, qleft, qright, val);
  136.     }
  137.     tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % MOD;
  138. }
  139.  
  140. ll Query(int node, int left, int right, int qleft, int qright)
  141. {
  142.     if (qleft <= left && right <= qright)
  143.     {
  144.         return tree[node];
  145.     }
  146.     Pushdown(node, left, right);
  147.     int mid = left + (right - left) / 2;
  148.     ll res = 0;
  149.     if (qleft <= mid)
  150.     {
  151.         res = (res + (Query(node * 2, left, mid, qleft, qright))) % MOD;
  152.     }
  153.     if (qright > mid)
  154.     {
  155.         res = (res + (Query(node * 2 + 1, mid + 1, right, qleft, qright))) % MOD;
  156.     }
  157.     return res;
  158. }
  159.  
  160. void Solve()
  161. {
  162.     tree.assign(4 * n + 7, 0);
  163.     lazyadd.assign(4 * n + 7, 0);
  164.     lazymul.assign(4 * n + 7, 1);
  165.     while(q --)
  166.     {
  167.         int type;
  168.         cin >> type;
  169.         if (type == 1)
  170.         {
  171.             int left, right, val;
  172.             cin >> left >> right >> val;
  173.             Update1(1, 1, n, left, right, val);
  174.         }
  175.         else if (type == 2)
  176.         {
  177.             int left, right, val;
  178.             cin >> left >> right >> val;
  179.             Update2(1, 1, n, left, right, val);
  180.         }
  181.         else
  182.         {
  183.             int left, right;
  184.             cin >> left >> right;
  185.             cout << Query(1, 1, n, left, right) << endl;
  186.         }
  187.     }
  188. }
  189.  
  190. int main()
  191. {
  192.     fixIO();
  193.     File("queryit");
  194.     Read();
  195.     Solve();
  196.     return 0;
  197. }
  198.  
  199. /*
  200.  * Code by github/nmkdeveloper.
  201.  * I didn't fall in love with you. I walked into love with you, with my eyes wide open, choosing to take every step along the way <3.
  202.  */
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
5 5
1 2 3 2
1 1 5 1
3 1 4
2 1 3 2
3 1 4
stdout
copy 
8
15
https://ideone.com/QBfCtz
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

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!