Cim və göydələnlər#11720

Cim və göydələnlər (Həll təhlili)

Tutaq ki, eyni hündürlükdə bloklardan "divarlar" qururuq.

Cütlük $(i, j)$ "dəhliz" əmələ gətirir, əgər bu divarların arasında daha hündür divar yoxdursa. Məsələnin həlli üçün monotondan ibarət stekdən istifadə edəcəyik. Stek cütlərini saxlayır $(q i y m ə t, s a y)$ (qiymət, say):

$q i y m ə t$ qiymət — divarın hündürlüyü (məna $h [i]$ ).
$s a y$ — bu hündürlükdə ardıcıl olaraq neçə eyni elementin göründüyünü, gələcəkdə bu cür elementlərlə cütlər təşkil edə bilənlərin sayını göstərir.

Yəni:

Hər "eyni rəqəmlər dəstəsi" üçün yalnız iki parametr saxlayırıq: rəqəm və bu rəqəmin neçə dəfə ardıcıl göründüyü.
Yeni element meydana gəldikdə, onun neçə cüt təşkil etdiyini dərhal deyə bilərik: bu rəqəm stekin zirvəsi üçün tam olaraq $s a y$ -dır.

Məsələn, cari rəqəm $a = 5$ a = 5-ə bərabər olsun və əvvəllər bu rəqəm $3$ dəfə görülmüş olsun (beləliklə, mövcud anda $a = 5$ a = 5-ci rəqəm dördüncü dəfədir görünür). Tutaq ki, bu rəqəmlərin arasında yalnız daha kiçik elementlər var. O zaman yeni indeks cütləri $(i, j)$ sayı, harada ki $j$ cari indeksdir və şərt $h_{i} = h_{j} = a$ h_i = h_j = a belədir, $3$ -ə bərabər olacaq.

Növbəti $h_{i}$ h_i rəqəmi işlənərkən:

Əgər stekin zirvəsindəkı rəqəm $h_{i}$ h_i-dən kiçikdirsə, bu rəqəmi stekdən çıxarırıq.
Əgər stekin zirvəsindəki rəqəm $h_{i}$ h_i-yə bərabərdirsə və əvvəllər $x$ dəfə görünmüşdürsə, cüt indekslərin sayını $x$ qədər artırırıq və $h_{i}$ h_i-nin görünmə sayını $x + 1$ x + 1 ilə yeniləyirik.
Əgər stek boşdursa və ya stekin zirvəsindəki rəqəm $h_{i}$ h_i-dən böyükdürsə, o zaman stekinə $(h_{i}, 1)$ (h_i, 1) cütü əlavə edirik. Bu o deməkdir ki, mövcud $h_{i}$ h_i rəqəmi ilk dəfədir görünür (ola bilsin ki, həmin rəqəm əvvəllər giriş ardıcıllığında görünmüşdü, amma daha böyük elementə görə stekdən çıxarılmışdı).

Nümunə

İlk testi nəzərdən keçirək.

Alqoritmin həyata keçirilməsi

Giriş məlumatlarını oxuyuruq.

scanf("%d", &n);
vector<int> v(n);
for (i = 0; i < n; ++i)
  scanf("%d", &v[i]);

$r es$ dəyişənində tapılan indeks cütlərinin sayını saxlayacağıq.

res = 0;

Cütlər stekini elan edək.

stack<pair<int, int>> st;

Massivin bütün rəqəmlərini ardıcıl emal edirik.

for (i = 0; i < v.size(); i++)
{

Stekin zirvəsində $v [i]$ -dən kiçik olan bir rəqəm olduğu müddətcə, bu rəqəmi stekdən çıxarırıq.

  while (!st.empty() && st.top().first < v[i])
    st.pop();

Əgər stekin zirvəsində $v [i]$ -yə bərabər olan bir rəqəm varsa və bu rəqəm əvvəllər $x$ dəfə görünüb (bu dəyər $s t . t o p () . seco n d$ st.top().second-də saxlanılır), o zaman cavabımız $r es$ -i $x$ qədər artırırıq. Bundan sonra isə $v [i]$ -nin görünmə sayını $x + 1$ x + 1-ə yeniləyirik.

  if (!st.empty() && v[i] == st.top().first)
  {
    res += st.top().second;
    st.top().second += 1;
  }
  else

Əgər $v [i]$ rəqəmi ilk dəfə görünürsə, o zaman stekə $(v [i], 1)$ (v[i], 1) cütünü əlavə edirik.

    st.push({ v[i], 1 });
}

Cavabı çıxarırıq.

printf("%lld\n", res);