fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. struct SegmentTree {
  9.     int n;
  10.     vector<long long> tree, lazy;
  11.  
  12.     SegmentTree(int n) : n(n), tree(4 * n + 5, 0), lazy(4 * n + 5, 0) {}
  13.  
  14.     // Đẩy giá trị lazy xuống các con
  15.     void push(int node, int l, int r) {
  16.         if (lazy[node] != 0) {
  17.             int mid = (l + r) / 2;
  18.  
  19.             tree[2 * node] = (tree[2 * node] + lazy[node] * (mid - l + 1)) % MOD;
  20.             lazy[2 * node] = (lazy[2 * node] + lazy[node]) % MOD;
  21.  
  22.             tree[2 * node + 1] = (tree[2 * node + 1] + lazy[node] * (r - mid)) % MOD;
  23.             lazy[2 * node + 1] = (lazy[2 * node + 1] + lazy[node]) % MOD;
  24.  
  25.             lazy[node] = 0;
  26.         }
  27.     }
  28.  
  29.     // Cộng val vào đoạn [ql, qr]
  30.     void update(int node, int l, int r, int ql, int qr, long long val) {
  31.         if (ql > r || qr < l) return;
  32.         if (ql <= l && r <= qr) {
  33.             tree[node] = (tree[node] + val * (r - l + 1)) % MOD;
  34.             lazy[node] = (lazy[node] + val) % MOD;
  35.             return;
  36.         }
  37.         push(node, l, r);
  38.         int mid = (l + r) / 2;
  39.         update(2 * node, l, mid, ql, qr, val);
  40.         update(2 * node + 1, mid + 1, r, ql, qr, val);
  41.         tree[node] = (tree[2 * node] + tree[2 * node + 1]) % MOD;
  42.     }
  43.  
  44.     // Truy vấn tổng trên đoạn [ql, qr]
  45.     long long query(int node, int l, int r, int ql, int qr) {
  46.         if (ql > r || qr < l) return 0;
  47.         if (ql <= l && r <= qr) return tree[node];
  48.         push(node, l, r);
  49.         int mid = (l + r) / 2;
  50.         return (query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr)) % MOD;
  51.     }
  52. };
  53.  
  54. int main() {
  55.     // Tối ưu I/O
  56.     ios_base::sync_with_stdio(false);
  57.     cin.tie(NULL);
  58.  
  59.     int n;
  60.     if (!(cin >> n)) return 0;
  61.  
  62.     vector<int> a(n + 1);
  63.     for (int i = 1; i <= n; ++i) {
  64.         cin >> a[i];
  65.     }
  66.  
  67.     SegmentTree st(n);
  68.     vector<int> last(n + 1, 0); // Lưu vị trí xuất hiện gần nhất của giá trị v
  69.     long long total_beauty = 0;
  70.  
  71.     for (int R = 1; R <= n; ++R) {
  72.         int x = a[R];
  73.         int prev_pos = last[x];
  74.  
  75.         // 1. Cộng 1 vào các L thuộc [prev_pos + 1, R]
  76.         st.update(1, 1, n, prev_pos + 1, R, 1);
  77.  
  78.         // 2. Lấy tổng số phần tử phân biệt của mọi đoạn con kết thúc tại R
  79.         long long current_sum = st.query(1, 1, n, 1, R);
  80.         total_beauty = (total_beauty + current_sum) % MOD;
  81.  
  82.         // 3. Cập nhật vị trí xuất hiện mới nhất
  83.         last[x] = R;
  84.     }
  85.  
  86.     cout << (total_beauty % MOD + MOD) % MOD << "\n";
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/psQLcy
language:
C++14 (gcc 8.3)
created:
1 day 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!