1451 - Average（数形结合）(二)
r (int i = 1; i <= n; i++) { p[i].x = i; if (str[i] == '0') p[i].y = y; else p[i].y = ++y; } } void solve() { int l = 0, r = -1, ansl = 0, ansr = L; Line Max(p[0], p[L]); for (int k = L; k <= n; k++) { int i = k - L; while (r > l && Line(Q[r - 1], p[i]) >= Line(Q[r], p[i])) r--; Q[++r] = p[i]; while (r > l && Line(Q[l + 1], p[k]) >
= Line(Q[l], p[k])) l++; Line t = Line(Q[l], p[k]); if (t > Max || (t == Max && t.xlen() < Max.xlen())) { Max = t; ansl = Max.p1.x; ansr = Max.p2.x; } } printf("%d %d\n", ansl + 1, ansr); } int main() { scanf("%d", &t); while (t--) { init(); solve(); } return 0; }