func_code_string: #include <bits/stdc++.h>   using namespace std;   typedef struct {     int y, i;     double p;   } ele;   int cmp(ele a, ele b) { return a.y > b.y || (a.y == b.y && a.i > b.i); }   vector<ele> pu[100514];   int a[100514];   double dp[5140][5140];   int mp[5140];   vector<int> e[5140];   ele sk[5140];   int top;   void sol() {     int n, q;     scanf( %d %d , &n, &q);     for (int i = 0; i < n; i++) {       scanf( %d , a + i);     }     pu[0].push_back((ele){n - 1, q, 0});     for (int i = 0; i < q; i++) {       int x, y;       double p;       scanf( %d %d %lf , &x, &y, &p);       pu[x - 1].push_back((ele){y - 1, i, p});     }     for (int i = 0; i <= q; i++) mp[i] = -7122;     top = 0;     for (int i = 0; i < n; i++) {       sort(pu[i].begin(), pu[i].end(), cmp);       for (int j = 0; j < (int)pu[i].size(); j++) {         sk[top++] = pu[i][j];       }       mp[sk[top - 1].i] = max(mp[sk[top - 1].i], a[i]);       for (; top && sk[top - 1].y == i; top--) {         int t = sk[top - 1].i;         double p = sk[top - 1].p;         for (int j = 0; j < (int)e[t].size(); j++) {           mp[t] = max(mp[t], mp[e[t][j]]);         }         for (int k = 0; k <= q + 1; k++) {           dp[t][k] = 1;           for (int j = 0; j < (int)e[t].size(); j++) {             int nk = mp[t] + k - mp[e[t][j]];             if (q + 1 >= nk) {               dp[t][k] *= dp[e[t][j]][nk];             }           }         }         for (int k = q + 1; k >= 1; k--) {           dp[t][k] = dp[t][k] * (1 - p) + dp[t][k - 1] * p;         }         dp[t][0] = dp[t][0] * (1 - p);         if (top >= 2) e[sk[top - 2].i].push_back(t);       }       pu[i].clear();     }     double ans = mp[q];     for (int i = 1; i <= q + 1; i++) {       ans += (dp[q][i] - dp[q][i - 1]) * i;     }     printf( %.10f n , ans);     for (int i = 0; i <= q; i++) e[i].clear();   }   int main() {     while (1) {       sol();       break;     }     return 0;   }   