1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 #include using namespace std; #define LL long long #define PLL pair #define fi first #define se second const int MX = 1e6 + 10; const int mxn = 2e5 + 10; int n, m; LL t[mxn], roz[mxn], pref[mxn]; int d[mxn], id[mxn]; LL min_d[mxn]; vector kolej[MX]; LL suma, curr; LL zas[mxn]; LL wyn[MX]; void wczytaj() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%lld", &t[i]); roz[i] = t[i] - t[i - 1]; pref[i] = roz[i] + pref[i - 1]; } for(int i = 1; i <= m; i++) scanf("%d", &d[i]); } bool mn_ro(PLL a, PLL b) { return a.fi * b.se <= a.se * b.fi; } bool mn(PLL a, PLL b) { return a.fi * b.se < a.se * b.fi; } void policz_id() { for(int i = 1; i <= n; i++) { int v = i - 1; PLL min_sr = {roz[i], 1}; while(v != 0) { int nast = id[v]; if(mn({pref[i] - pref[v], i - v}, {pref[i] - pref[nast], i - nast})) break; v = nast; } id[i] = v; } //for(int i = 1; i <= n; i++)printf("id[%d] = %d\n", i, id[i]); } void policz_min_d() { for(int i = 1; i <= n; i++) { min_d[i] = (pref[i] - pref[id[i]]) / ((LL)i - (LL)id[i]) + 1LL; if(min_d[i] < (LL)MX) kolej[min_d[i]].push_back(i); } for(int i = 0; i < MX; i++) reverse(kolej[i].begin(), kolej[i].end()); //for(int i = 1; i <= n; i++) printf("min_d[%d] = %lld\n", i, min_d[i]); } inline LL dwu(LL a) { return a * (a + 1LL) / 2LL; } void policz_wyn() { for(int i = 0; i < MX; i++) // KUIRWA ZAMIENIC!!!!!!!!!!!!! { for(auto j : kolej[i]) { curr -= dwu(zas[j]); curr -= dwu(zas[id[j]]); zas[j]++; LL roznica = ((LL)i * ((LL)j - (LL)id[j]) - (pref[j] - pref[id[j]])) * zas[j]; suma += roznica; zas[id[j]] += zas[j]; curr += dwu(zas[id[j]]); } wyn[i] = suma; suma += curr; } //for(int i = 0; i < 10; i++) {printf("wyn[%d] = %lld\n", i, wyn[i]);} } int main() { wczytaj(); policz_id(); policz_min_d(); policz_wyn(); for(int i = 1; i <= m; i++) printf("%lld\n", wyn[d[i]]); }