document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /* c652              */
  2. /* AC (0.2s, 18.4MB) */
  3. #pragma warning( disable : 4996 )
  4. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. using int16 = short;
  12. using uint16 = unsigned short;
  13. using uint = unsigned int;
  14. using int64 = long long;
  15. using uint64 = unsigned long long;
  16.  
  17. /* main code */
  18. constexpr int MAXN = 300001;
  19.  
  20. int N, Q, ql, qr;
  21.  
  22. uint64 arr[MAXN], Sum[MAXN * 4], Max[MAXN * 4];
  23. uint64 initMax(int l, int r, int nowNode)
  24. {
  25.     if (l == r)
  26.     {
  27.         Max[nowNode] = arr[l];
  28.         return arr[l];
  29.     }
  30.  
  31.     int mid = (l + r) >> 1;
  32.     Max[nowNode] = max<uint64>(initMax(l, mid, nowNode << 1), initMax(mid + 1, r, nowNode << 1 | 1));
  33.  
  34.     return Max[nowNode];
  35. }
  36. uint64 initSum(int l, int r, int nowNode)
  37. {
  38.     if (l == r)
  39.     {
  40.         Sum[nowNode] = arr[l];
  41.         return arr[l];
  42.     }
  43.  
  44.     int mid = (l + r) >> 1;
  45.     Sum[nowNode] = initSum(l, mid, nowNode << 1) + initSum(mid + 1, r, nowNode << 1 | 1);
  46.  
  47.     return Sum[nowNode];
  48. }
  49.  
  50. void updata_range(int l, int r, int nowNode)
  51. {
  52.     if (Max[nowNode] <= 1) return;
  53.  
  54.     uint64 tmp;
  55.     int mid;
  56.     if (l == r)
  57.     {
  58.         tmp = arr[l] - (uint64)sqrt(arr[l]);
  59.         Sum[nowNode >> 1] -= tmp;
  60.         arr[l] -= tmp;
  61.         Sum[nowNode] = Max[nowNode] = arr[l];
  62.         return;
  63.     }
  64.     tmp = Sum[nowNode];
  65.     mid = (l + r) >> 1;
  66.     if (ql <= mid) updata_range(l, mid, nowNode << 1);
  67.     if (qr >= mid + 1) updata_range(mid + 1, r, nowNode << 1 | 1);
  68.  
  69.     Max[nowNode] = max<uint64>(Max[nowNode << 1], Max[nowNode << 1 | 1]);
  70.     Sum[nowNode >> 1] -= (tmp - Sum[nowNode]);
  71. }
  72.  
  73. uint64 query_Sum(int l, int r, int nowNode)
  74. {
  75.     if (ql <= l && qr >= r) return Sum[nowNode];
  76.     int mid = (l + r) >> 1;
  77.    
  78.     uint64 res = 0;
  79.     if (ql <= mid) res += query_Sum(l, mid, nowNode << 1);
  80.     if (qr >= mid + 1) res += query_Sum(mid + 1, r, nowNode << 1 | 1);
  81.    
  82.     return res;
  83. }
  84.  
  85. int main()
  86. {
  87.     scanf("%d %d", &N, &Q);
  88.     for (int i = 1; i <= N; ++i)
  89.         scanf("%llu", arr + i);
  90.     initMax(1, N, 1);
  91.     initSum(1, N, 1);
  92.     for (int i = 0, op; i < Q; ++i)
  93.     {
  94.         scanf("%d %d %d", &op, &ql, &qr);
  95.         if (op == 0)
  96.             printf("%llu\\n", query_Sum(1, N, 1));
  97.         else
  98.             updata_range(1, N, 1);
  99.     }
  100.  
  101.     return 0;
  102. }
');