We measure the evolution of the rest-frame near-ultraviolet (NUV)-V colors for early-type galaxies in clusters at 0 < z < 1.1 using data from the Hyper Suprime-Cam Subaru Strategic Program, CFHT Large Area U-band Deep Survey, and local Sloan Digital Sky Survey clusters observed with Galaxy Evolution Explorer. Our results show that there is an excess in the ultraviolet spectrum in most quiescent galaxies (compared to the expectations from models fitting their optical/infrared colors and spectra) below z ~ 0.6, beyond which the excess UV emission fades rapidly. This evolution of the UV color is only consistent with the presence of a highly evolved, hot horizontal branch subpopulation in these galaxies (among the majority of cool and optically bright stars), comprising on average 10% of the total stellar mass and forming at z > 3. The blue UV colors of early-type galaxies at low-intermediate redshifts are likely driven by this subpopulation being enriched in helium up to ~44%. At z > 0.8 (when the extra UV component has not yet appeared) the data allow us to constrain the star formation histories of galaxies by fitting models to the evolution of their UV colors: we find that the epoch at which the stellar populations formed lies in the range 3 < _zform < 10 (corresponding to 0.5-2.2 Gyr after the Big Bang) with a star formation e-folding timescale of τ = 0.35-0.7 Gyr, suggesting that these galaxies formed the majority of stars at very high redshift, with a brief yet intense burst of star formation activity. The star formation history and chemical evolution of early-type galaxies resemble those of globular clusters, albeit on much larger scales.