fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int MOD = 1e9;
  7. const int N = 500005;
  8.  
  9. int n;
  10. int a[N];
  11. int minL[N], maxL[N], minR[N], maxR[N];
  12.  
  13. // Các mảng cộng dồn phục vụ tính toán O(1)
  14. int sum_j[N], sum_minR_j[N], sum_maxR_j[N], sum_prodR_j[N];
  15. int sum_1[N], sum_minR[N], sum_maxR[N], sum_prodR[N];
  16.  
  17. int divide_and_conquer(int l, int r) {
  18.     if (l == r) {
  19.         // Đoạn con độ dài 1: min * max * length = a[l] * a[l] * 1
  20.         return (a[l] % MOD * a[l] % MOD) % MOD;
  21.     }
  22.  
  23.     int m = (l + r) >> 1;
  24.     int ans = (divide_and_conquer(l, m) + divide_and_conquer(m + 1, r)) % MOD;
  25.  
  26.     // Tiền xử lý cực trị cho nửa bên trái [l, m]
  27.     minL[m] = maxL[m] = a[m];
  28.     for (int i = m - 1; i >= l; i--) {
  29.         minL[i] = min(minL[i + 1], a[i]);
  30.         maxL[i] = max(maxL[i + 1], a[i]);
  31.     }
  32.  
  33.     // Tiền xử lý cực trị cho nửa bên phải [m + 1, r]
  34.     minR[m + 1] = maxR[m + 1] = a[m + 1];
  35.     for (int j = m + 2; j <= r; j++) {
  36.         minR[j] = min(minR[j - 1], a[j]);
  37.         maxR[j] = max(maxR[j - 1], a[j]);
  38.     }
  39.  
  40.     // Tạo các mảng prefix sum tổng cho nửa bên phải để tính nhanh
  41.     // Lưu ý: Mọi phép tính nhân/cộng cần được lấy modulo cẩn thận
  42.     auto get_mod = [](int x) { return (x % MOD + MOD) % MOD; };
  43.  
  44.     for (int j = m + 1; j <= r; j++) {
  45.         int r_min = minR[j] % MOD;
  46.         int r_max = maxR[j] % MOD;
  47.         int r_prod = (r_min * r_max) % MOD;
  48.  
  49.         sum_1[j] = get_mod(sum_1[j - 1] + 1);
  50.         sum_j[j] = get_mod(sum_j[j - 1] + j);
  51.  
  52.         sum_minR[j] = get_mod(sum_minR[j - 1] + r_min);
  53.         sum_minR_j[j] = get_mod(sum_minR_j[j - 1] + r_min * j);
  54.  
  55.         sum_maxR[j] = get_mod(sum_maxR[j - 1] + r_max);
  56.         sum_maxR_j[j] = get_mod(sum_maxR_j[j - 1] + r_max * j);
  57.  
  58.         sum_prodR[j] = get_mod(sum_prodR[j - 1] + r_prod);
  59.         sum_prodR_j[j] = get_mod(sum_prodR_j[j - 1] + r_prod * j);
  60.     }
  61.  
  62.     // Dùng 2 con trỏ p1 và p2 để tìm ranh giới nơi minR và maxR bị chế ngự bởi minL và maxL
  63.     int p1 = m + 1; // p1 là vị trí đầu tiên mà minR[p1] < minL[i]
  64.     int p2 = m + 1; // p2 là vị trí đầu tiên mà maxR[p2] > maxL[i]
  65.  
  66.     for (int i = m; i >= l; i--) {
  67.         while (p1 <= r && minR[p1] >= minL[i]) p1++;
  68.         while (p2 <= r && maxR[p2] <= maxL[i]) p2++;
  69.  
  70.         // Chia các đoạn j thành các khoảng dựa trên p1 và p2 để tính toán đóng góp từng phần
  71.         // Ta có thể đẩy tất cả các điều kiện so sánh vào các hàm tính khoảng tổng [L, R] thu được từ p1, p2
  72.         // Để code ngắn gọn và tránh nhầm lẫn chỉ số, ta biểu diễn qua một hàm lambda tính tổng đoạn [L, R]
  73.         auto query_sum = [&](int L, int R) {
  74.             if (L > R) return 0LL;
  75.             int total = 0;
  76.  
  77.             // Lấy mẫu vị trí bất kỳ (chọn L) để biết mối quan hệ min/max của khoảng này với nhánh trái i
  78.             int j_sample = L;
  79.             int final_min = (minR[j_sample] < minL[i]) ? minR[j_sample] : minL[i];
  80.             int final_max = (maxR[j_sample] > maxL[i]) ? maxR[j_sample] : maxL[i];
  81.  
  82.             // Tách các trường hợp phụ thuộc vào việc min, max lấy từ bên nào
  83.             bool min_from_left = (minR[j_sample] >= minL[i]);
  84.             bool max_from_left = (maxR[j_sample] <= maxL[i]);
  85.  
  86.             int cur_minL = minL[i] % MOD;
  87.             int cur_maxL = maxL[i] % MOD;
  88.  
  89.             if (min_from_left && max_from_left) {
  90.                 // Trọng số = minL * maxL * (j - i + 1)
  91.                 int factor = (cur_minL * cur_maxL) % MOD;
  92.                 int sum_len = get_mod((sum_j[R] - sum_j[L - 1]) - (i - 1) * (sum_1[R] - sum_1[L - 1]));
  93.                 total = (factor * sum_len) % MOD;
  94.             } 
  95.             else if (!min_from_left && !max_from_left) {
  96.                 // Trọng số = minR * maxR * (j - i + 1)
  97.                 int term1 = get_mod((sum_prodR_j[R] - sum_prodR_j[L - 1]));
  98.                 int term2 = get_mod((sum_prodR[R] - sum_prodR[L - 1]) * (i - 1));
  99.                 total = get_mod(term1 - term2);
  100.             } 
  101.             else if (min_from_left && !max_from_left) {
  102.                 // Trọng số = minL * maxR * (j - i + 1)
  103.                 int term1 = get_mod((sum_maxR_j[R] - sum_maxR_j[L - 1]));
  104.                 int term2 = get_mod((sum_maxR[R] - sum_maxR[L - 1]) * (i - 1));
  105.                 total = (cur_minL * get_mod(term1 - term2)) % MOD;
  106.             } 
  107.             else {
  108.                 // Trọng số = minR * maxL * (j - i + 1)
  109.                 int term1 = get_mod((sum_minR_j[R] - sum_minR_j[L - 1]));
  110.                 int term2 = get_mod((sum_minR[R] - sum_minR[L - 1]) * (i - 1));
  111.                 total = (cur_maxL * get_mod(term1 - term2)) % MOD;
  112.             }
  113.             return total;
  114.         };
  115.  
  116.         // Gom các khoảng rời nhau từ m+1 đến r tạo bởi các điểm chia p1, p2
  117.         vector<int> borders = {m + 1, p1, p2, r + 1};
  118.         sort(borders.begin(), borders.end());
  119.         borders.erase(unique(borders.begin(), borders.end()), borders.end());
  120.  
  121.         for (size_t k = 0; k < borders.size() - 1; k++) {
  122.             ans = (ans + query_sum(borders[k], borders[k + 1] - 1)) % MOD;
  123.         }
  124.     }
  125.  
  126.     return ans;
  127. }
  128.  
  129. signed main() {
  130.     ios_base::sync_with_stdio(0);
  131.     cin.tie(0); cout.tie(0);
  132.  
  133.     if (!(cin >> n)) return 0;
  134.     for (int i = 1; i <= n; i++) cin >> a[i];
  135.  
  136.     cout << divide_and_conquer(1, n) << "\n";
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0.01s 13992KB
comments (?)
stdin
copy 
4
2
4
1
4
stdout
copy 
109
https://ideone.com/lQznCH
language:
C++14 (gcc 8.3)
created:
3 days 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!