fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long mo = 1e9 + 7;
  5.  
  6. int a[1000007], n, q;
  7. long long st[4000007], st_2[4000007], st_3[4000007];
  8. long long lz[4000007];
  9.  
  10. int nxt[1000007], f[1000007];
  11.  
  12. inline void apply(int id, int len, long long x) {
  13.     x %= mo;
  14.     if (x < 0) x += mo;
  15.  
  16.     long long x2 = x * x % mo;
  17.     long long x3 = x2 * x % mo;
  18.  
  19.     st_3[id] = (
  20.         st_3[id]
  21.         + 3LL * st_2[id] % mo * x
  22.         + 3LL * st[id] % mo * x2
  23.         + 1LL * len * x3
  24.     ) % mo;
  25.  
  26.     st_2[id] = (
  27.         st_2[id]
  28.         + 2LL * st[id] % mo * x
  29.         + 1LL * len * x2
  30.     ) % mo;
  31.  
  32.     st[id] = (st[id] + 1LL * len * x) % mo;
  33.  
  34.     lz[id] += x;
  35.     if (lz[id] >= mo) lz[id] -= mo;
  36. }
  37.  
  38. void build(int id, int l, int r) {
  39.     if (l == r) {
  40.         st[id] = a[l] % mo;
  41.         st_2[id] = 1LL * a[l] * a[l] % mo;
  42.         st_3[id] = st_2[id] * a[l] % mo;
  43.         return;
  44.     }
  45.  
  46.     int g = (l + r) >> 1;
  47.  
  48.     build(id << 1, l, g);
  49.     build(id << 1 | 1, g + 1, r);
  50.  
  51.     st[id] = (st[id << 1] + st[id << 1 | 1]) % mo;
  52.     st_2[id] = (st_2[id << 1] + st_2[id << 1 | 1]) % mo;
  53.     st_3[id] = (st_3[id << 1] + st_3[id << 1 | 1]) % mo;
  54. }
  55.  
  56. void down(int id, int l, int r) {
  57.     if (l == r || lz[id] == 0) return;
  58.  
  59.     int g = (l + r) >> 1;
  60.  
  61.     apply(id << 1, g - l + 1, lz[id]);
  62.     apply(id << 1 | 1, r - g, lz[id]);
  63.  
  64.     lz[id] = 0;
  65. }
  66.  
  67. void up(int id, int l, int r, int u, int v, long long x) {
  68.     if (l > v || r < u) return;
  69.  
  70.     if (l >= u && r <= v) {
  71.         apply(id, r - l + 1, x);
  72.         return;
  73.     }
  74.  
  75.     down(id, l, r);
  76.  
  77.     int g = (l + r) >> 1;
  78.  
  79.     up(id << 1, l, g, u, v, x);
  80.     up(id << 1 | 1, g + 1, r, u, v, x);
  81.  
  82.     st[id] = (st[id << 1] + st[id << 1 | 1]) % mo;
  83.     st_2[id] = (st_2[id << 1] + st_2[id << 1 | 1]) % mo;
  84.     st_3[id] = (st_3[id << 1] + st_3[id << 1 | 1]) % mo;
  85. }
  86.  
  87. long long get(int id, int l, int r, int u, int v) {
  88.     if (l > v || r < u) return 0;
  89.  
  90.     if (l >= u && r <= v) {
  91.         return st[id];
  92.     }
  93.  
  94.     down(id, l, r);
  95.  
  96.     int g = (l + r) >> 1;
  97.  
  98.     return (
  99.         get(id << 1, l, g, u, v)
  100.         + get(id << 1 | 1, g + 1, r, u, v)
  101.     ) % mo;
  102. }
  103.  
  104. int32_t main() {
  105.     ios_base::sync_with_stdio(0);
  106.     cin.tie(0);
  107.  
  108.     cin >> n;
  109.  
  110.     for (int i = 1; i <= n; i++) {
  111.         cin >> a[i];
  112.     }
  113.  
  114.     for (int i = n; i > 0; i--) {
  115.         nxt[i] = f[a[i]];
  116.         f[a[i]] = i;
  117.     }
  118.  
  119.     for (int i = 1; i <= n; i++) {
  120.         f[a[i]] = 0;
  121.     }
  122.  
  123.     for (int i = 1; i <= n; i++) {
  124.         if (!f[a[i]]) {
  125.             up(1, 1, n, i, n, 1);
  126.         }
  127.  
  128.         f[a[i]] = 1;
  129.     }
  130.  
  131.     long long ans = 0;
  132.  
  133.     for (int i = 1; i <= n; i++) {
  134.         ans += st_3[1];
  135.  
  136.         ans %= mo;
  137.  
  138.         up(1, 1, n, i, n, -1);
  139.  
  140.         if (nxt[i] != 0) {
  141.             up(1, 1, n, nxt[i], n, 1);
  142.         }
  143.     }
  144.  
  145.     cout << ans;
  146.  
  147.     return 0;
  148. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OWvDPL
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!