Kəçik, hansı ki, saymağı öyrənirdi#4483

Kəçik, hansı ki, saymağı öyrənirdi (Həll təhlili)

Uşaq $[l; r]$ [l; r] seqmentindəki iki sərnişini yalnız və yalnız bu seqmentdəki heyvanların kütlələrindən ən kiçik ikisinin cəmi $k$ -dan artıq olmadıqda seçə bilər. Həqiqətən, əgər hər hansı bir heyvan cütü uyğun gəlirsə, onda ən yüngül iki heyvanın cütü daha çox uyğun gələcək.

Buna görə də, hər təpəsində öz seqmentindəki iki minimumu saxlayan bir seqment ağacı qurmaq olar. Lakin bizi minimumların özləri yox, yalnız cəmi $k$ -dan artıq olmayan iki ədədin mövcud olub-olmaması maraqlandırır. Bu, hər təpədə yalnız bir ədəd saxlamağa imkan verir.

Təpələrdəki dəyərlər. Seqment ağacının yarpaqları heyvanların kütlələrini saxlayır. Hər daxili təpə aşağıdakıları saxlayır:

əgər onun seqmentində ümumi kütləsi $k$ -dan artıq olmayan iki heyvan varsa, $0$ ;
əks halda, onun seqmentindəki heyvanın minimum kütləsini.

Heyvanların kütlələri müsbətdir, ona görə $0$ dəyəri heç bir kütlə ilə üst-üstə düşmür və birmənalı şəkildə uyğun cütün tapıldığını bildirir.

Uşaqların birləşdirilməsi. Təpənin dəyəri onun uşaqlarının $x$ və $y$ dəyərlərindən hesablanır. Təpənin seqmentindəki uyğun heyvan cütü ya tamamilə onun yarılarından birində yerləşir, ya da sol yarıdan bir heyvandan və sağ yarıdan bir heyvandan ibarətdir. Ona görə:

əgər $x = 0$ x = 0 və ya $y = 0$ y = 0 olarsa, uyğun cüt yarılardan birində yerləşir, və təpənin dəyəri $0$ -dır;
əks halda, $x$ və $y$ yarılardakı minimum kütlələrdir, və müxtəlif yarılardan olan heyvanların ən yaxşı cütünün ümumi kütləsi $x + y$ x + y-dir. Əgər $x + y \leq k$ x + y \le k olarsa, təpənin dəyəri $0$ -dır, əks halda $min (x, y)$ \min(x, y)-dir.

Belə bir birləşdirmə funksiyası ilə məsələ nöqtəvi yeniləmələrlə standart seqment ağacı vasitəsilə həll olunur.

$1$ tipli sorğu üçün, əgər $[l; r]$ [l; r] seqmentindəki dəyər $0$ -a bərabərdirsə, cavab "Yes"-dir, əks halda "No"-dur.

Nümunə

Nümunədəki sorğulara baxaq, $k = 9$ k = 9. Başlanğıcda heyvanların kütlələri $1, 3, 1, 6, 6, 7$ 1, 3, 1, 6, 6, 7-dir:

$116$ : ən yüngül iki heyvanın kütləsi $1$ və $1$ -dir, $1 + 1 = 2 \leq 9$ 1 + 1 = 2 \le 9, cavab "Yes"-dir;
$112$ : $1 + 3 = 4 \leq 9$ 1 + 3 = 4 \le 9, cavab "Yes"-dir;
$247$ : dördüncü heyvanın kütləsi $7$ olur;
$145$ : $7 + 6 = 13 > 9$ 7 + 6 = 13 > 9, cavab "No"-dur;
$156$ : $6 + 7 = 13 > 9$ 6 + 7 = 13 > 9, cavab "No"-dur;
$217$ və $238$ : birinci və üçüncü heyvanların kütlələri $7$ və $8$ olur.

Son $116$ sorğusundan əvvəl heyvanların kütlələri $7, 3, 8, 7, 6, 7$ 7, 3, 8, 7, 6, 7-dir. Onlar üçün seqment ağacı aşağıda göstərilmişdir. Hər təpədə onun seqmenti və saxlanılan dəyər göstərilir. Yarpaqlar sarı rənglə, dəyəri $0$ olan təpə isə narıncı rənglə vurğulanmışdır.

Daxili təpələrdəki dəyərləri hesablayaq:

$[1; 2]$ : $7 + 3 = 10 > 9$ 7 + 3 = 10 > 9, dəyər $min (7, 3) = 3$ \min(7, 3) = 3-dür;
$[1; 3]$ : $3 + 8 = 11 > 9$ 3 + 8 = 11 > 9, dəyər $min (3, 8) = 3$ \min(3, 8) = 3-dür;
$[4; 5]$ : $7 + 6 = 13 > 9$ 7 + 6 = 13 > 9, dəyər $min (7, 6) = 6$ \min(7, 6) = 6-dır;
$[4; 6]$ : $6 + 7 = 13 > 9$ 6 + 7 = 13 > 9, dəyər $min (6, 7) = 6$ \min(6, 7) = 6-dır;
$[1; 6]$ : $3 + 6 = 9 \leq 9$ 3 + 6 = 9 \le 9, dəyər $0$ -dır.

Yalnız $[1; 6]$ təpəsi $0$ saxlayır: kütlələri $3$ və $6$ olan ən yüngül iki heyvan seqmentin müxtəlif yarılarındadır, və onların ümumi kütləsi $9$ -dur. Beləliklə, son sorğunun cavabı "Yes"-dir.

Alqoritmin tətbiqi

Sabitləri və işçi massivləri elan edək. $S e g T r ee$ SegTree massivi seqment ağacını saxlayır, heyvanların kütlələri isə $a$ massivində saxlanılır. $I N F$ sabiti hər hansı bir heyvanın kütləsindən böyükdür və boş seqment üçün neytral element kimi istifadə olunur. $I N F$ ilə istənilən kütlənin cəmi $2 \cdot 1 0^{9} + 10$ 2 \cdot 10^9 + 10-dan artıq olmur və $in t$ tipinə sığır.

#define MAX 1000001
#define INF 1000000010
int SegTree[4 * MAX];
int a[MAX];

f funksiyası uşaqların $x$ və $y$ dəyərlərini birləşdirir. Əgər uşaqlardan ən azı birində $0$ varsa, onda onun seqmentində artıq uyğun iki sərnişin var. Əgər $x + y \leq k$ x + y \le k olarsa, sol və sağ yarıların ən yüngül heyvanları uyğun cüt təşkil edir. Hər iki halda $0$ qaytarın; əks halda $x$ və $y$ -nin minimumunu qaytarın.

int f(int x, int y)
{
  if (x == 0 || y == 0 || x + y <= k) return 0;
  return min(x, y);
}

BuildTree funksiyası $a$ massivindən seqment ağacını qurur. $v$ təpəsi $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlir. Yarpaqlar heyvanların kütlələrini saxlayır, daxili təpələrdəki dəyərlər isə $f$ funksiyası ilə hesablanır.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2 * v, lpos, mid);
    BuildTree(2 * v + 1, mid + 1, rpos);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

Query funksiyası $[l e f t; r i g h t]$ [left; right] seqmentindəki dəyəri qaytarır: əgər onda ümumi kütləsi $k$ -dan artıq olmayan iki sərnişin varsa $0$ , əks halda heyvanın minimum kütləsini. $v$ təpəsi $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlir. Boş seqment üçün $I N F$ neytral dəyəri qaytarılır.

int Query(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return INF;
  if ((lpos == left) && (rpos == right)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return f(Query(2 * v, lpos, mid, left, min(right, mid)),
           Query(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

C++

Update funksiyası $p os$ indeksli elementə $v a l$ dəyərini mənimsədir və yarpaqdan köyə qədər olan yol üzərindəki bütün təpələrdəki dəyərləri yenidən hesablayır. $v$ təpəsi $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlir.

void Update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos)
     SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) Update(2 * v, lpos, mid, pos, val);
    else Update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

Proqramın əsas hissəsi. Heyvanların sayı $n$ -i və qalan tutumu $k$ -nı oxuyun. Heyvanların kütlələrini $1$ indeksindən başlayaraq $a$ massivinə oxuyun.

scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

$a [1 \dots n]$ a[1 \ldots n] massivinin elementlərindən seqment ağacını qurun.

BuildTree(1, 1, n);

$q$ sorğusunu bir-bir emal edin. Heyvanlar $1$ -dən başlayaraq nömrələnir, $a$ massivinin elementləri də $1$ indeksindən başlayaraq saxlanılır, ona görə sorğulardan olan indekslər dəyişiklik olmadan istifadə olunur.

scanf("%d", &q);
for (j = 0; j < q; j++)
{
  scanf("%d %d %d", &t, &l, &r);

$1$ tipli sorğu: $[l; r]$ [l; r] seqmentindəki dəyəri hesablayın. Əgər o $0$ -a bərabərdirsə, iki sərnişin tapılıb.

  if (t == 1)
  {
    int Res = Query(1, 1, n, l, r);
    if (Res == 0) printf("Yes\n"); else printf("No\n");
  }

$2$ tipli sorğu: $l$ indeksli heyvana $r$ kütləsini mənimsədin.

  else
    Update(1, 1, n, l, r);
}