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 `#include #define f first #define s second using namespace std; typedef pair par; priority_queue, greater > q; vector v; long long tab[1000009], wyn[1000009], odl[1000009]; int uf[200009], moc[1000009], mi[1000009], ma[1000009], ti[1000009], ad[1000009]; int find(int u) { return uf[u]==u?u:uf[u]=find(uf[u]); } void Union(int u, int u1) { uf[find(u)]=find(u1); return; } long long kwa(long long l) { int l1=l-1; l*=l1; return l/2; } int main() { int n,m,a=0,b,f,g,h; par p; long long c,d=0,e,A=0,B=0; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { uf[i]=i; moc[i]=1; mi[i]=i; ma[i]=i; } for(int i=1; i<=n; i++) { scanf("%lld", &c); tab[i]=c; if(i=i) break; //printf("!"); q.pop(); b=p.s; g=find(b-1); b=find(b); if(b==g) break; f=mi[g]; g=ma[b]; c=kwa(moc[b]); d=kwa(moc[g]); e=kwa(moc[b]+moc[g]); //printf("?%lld %lld %lld %lld %lld\n", A, B, c, d, e); A=A-c-d+e; c=moc[b]+moc[g]; Union(p.s, p.s-1); b=find(p.s); moc[b]=c; mi[b]=min(mi[b],f); ma[b]=max(ma[b],g); f=ma[b]; g=f+1; c=odl[g]-(i-ti[g]-1)*ad[g]; //printf("-->%lld %d %d %lld %d %d\n", c, f, g, odl[g], i-ti[g], ad[g]); odl[g]=c; ti[g]=i; ad[g]=moc[b]+moc[find(g)]-1; //printf("->%lld\n", c); if(c%ad[g]==0) c/=ad[g]; else c=c/ad[g]+1; q.push(par(c+i,g)); } B+=A; wyn[i]=B; } //printf("\n\n"); for(int i=0; i