Toplam#2307

Toplam (Həll təhlili)

Bütün elementlərə təyin etmə və toplama qrup əməliyyatlarını dəstəkləyən seqment ağacını həyata keçirmək lazımdır.

Hər ağac düyünündə olan $a dd$ dəyişənində bu düyünə aid seqmentin bütün elementlərinə təyin edilmiş dəyər saxlanılır. Əgər ağacın zirvəsi seqmentə uyğun gəlirsə $[l; r]$ [l; r], bu seqmentdəki ədədlərin cəmi $a dd \cdot (r - l + 1)$ add \cdot (r - l + 1)-yə bərabərdir.

Təyin etmə və toplama əməliyyatları yerinə yetirilərkən, ağacın kökündən yarpaqlara enən prosesdə hər zirvədə $a dd$ dəyəri ağacın növbəti səviyyəsinə basdırılmalıdır.

Təyin etmə əməliyyatı yerinə yetirilərkən $s_{1}$ s_1 və $s_{2}$ s_2 alt zirvələrindəki əvvəlki cəm dəyərləri ilə $a_{1}$ a_1 və $a_{2}$ a_2 təxirə salınmış təyin etmə dəyərləri itirilir.

Seqment ağacı qurularkən, hər zirvədəki $a dd$ dəyişənini seqment elementlərinə heç vaxt təyin edilməyəcək bir dəyər ilə (məsələn, $- 1$ ) başlatırıq.

Alqoritmin həyata keçirilməsi

Seqment ağacı $n o d e$ tipinə malik array kimi saxlanılır. Hər ağac zirvəsi arraydə müəyyən seqmentə uyğun gəlir və bu seqment haqqında məlumat saxlayır.

Struktorda iki sahə var:

$s u m$ — müvafiq seqmentdəki elementlərin cəmi;
$a dd$ — təxirə salınmış təyin etmə dəyəri (layizü üsuli).

Konstruktor hər ağac zirvəsi yaradılarkən avtomatik olaraq çağırılır:

$s u m$ sıfırla başlatılır, çünki hələ quraşdırılma mərhələsində zirvədə element dəyərləri haqqında məlumat toplanmayıb;
$a dd$ $- 1$ dəyəri ilə başlatılır, hansı ki, xüsusi simbolik işarə kimi istifadə edilir və təxirə salınmış təyin etmənin olmamasını bildirir. Bu dəyərin heç vaxt arrayın elementlərinə təyin edilməyəcəyi güman edilir.

struct node
{
  long long sum, add;
  node() : sum(0), add(-1) {}
};
vector<node> SegTree;

Push funksiyası $v$ zirvəsindən onun oğullarına $a dd$ dəyərini basdırır. Əgər $a dd \neq = - 1$ add \ne -1-dirsə, bu dəyəri ağacın bir səviyyə aşağıya basdırmaq lazımdır. Basdırma bitdikdən sonra $v$ zirvəsindəki $a dd$ dəyərini $- 1$ -lə əvəz edirik.

void Push(int v, int lpos, int mid, int rpos)
{

Əgər $a dd = - 1$ add = -1-dirsə, $v$ zirvəsində təxirə salınmış əməliyyat yoxdur.

  if (SegTree[v].add == -1) return;

$v$ zirvəsinin oğullarında $a dd$ və $s u m$ dəyərlərinin yenidən hesablanması.

  SegTree[2*v].add = SegTree[v].add;
  SegTree[2*v].sum = (mid - lpos + 1) * SegTree[v].add;
  SegTree[2*v+1].add = SegTree[v].add;
  SegTree[2*v+1].sum = (rpos - mid) * SegTree[v].add;

Basdırma bitdikdən sonra $a dd = - 1$ add = -1-lə $v$ zirvəsində təyin edilir.

  SegTree[v].add = -1;
}

SetValue funksiyası $[l e f t; r i g h t]$ [left; right] seqmentindəki bütün elementləri $v a l$ -ə bərabər təyin edir. $v$ zirvəsinə uyğun gələn seqment $[l p os; r p os]$ [lpos; rpos].

void SetValue(int v, int lpos, int rpos, int left, int right, int val)
{
    if (left > right) return;

Əgər $[l e f t; r i g h t]$ [left; right] $[l p os; r p os]$ [lpos; rpos] seqmentinə uyğun gəlirsə, hansı ki ağac zirvəsində saxlanılır, bu zirvədə $a dd$ və $s u m$ dəyişənlərinə müvafiq dəyərlər təyin edirik.

  if ((lpos == left) && (rpos == right))
  {

    SegTree[v].add = val;
    SegTree[v].sum = (long long)(right - left + 1) * val;
    return;
  }

C++

Seqmentin ortasını tapırıq $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Basdırmanı həyata keçiririk, əgər $a dd$ $- 1$ -lə bərabərdirsə.

  Push(v, lpos, mid, rpos);

Seqment ağacı zirvəsinin sol və sağ oğullarını rekursiv olaraq işləyirik.

  SetValue(2*v, lpos, mid, left, min(mid, right), val);
  SetValue(2*v+1, mid+1, rpos, max(left, mid+1), right, val);

$v$ zirvəsində cəm dəyərini onun uşaqların cəm dəyərləri ilə yenidən hesablayırıq.

  SegTree[v].sum = SegTree[2*v].sum + SegTree[2*v+1].sum;
}

Summa funksiyası $[l e f t; r i g h t]$ [left; right] seqmentindəki elementlərin cəmini geri qaytarır.

$v$ zirvəsinə uyğun gələn seqment $[l p os; r p os]$ [lpos; rpos].

long long Summa(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;

Əgər $[l e f t; r i g h t]$ [left; right] aghac $v$ zirvəsində saxlanan $[l p os; r p os]$ [lpos; rpos] seqmenti ilə üst-üstə düşərsə, bu zirvədəki cəm dəyərini qaytarırıq.

  if ((lpos == left) && (rpos == right)) 
    return SegTree[v].sum;

Seqmentin ortasını tapırıq $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Basdırmanı yerinə yetiririk, $a dd$ $- 1$ -dən fərqlidirsə.

  Push(v, lpos, mid, rpos);

Seqmenti $[l p os; r p os]$ [lpos; rpos] iki alt seqmentə bölürük: $[l p os; mi d]$ [lpos; mid] və $[mi d + 1; r p os]$ [mid + 1; rpos]. Bu alt seqmentlərdə cəm hesabatı edir və əldə edilən dəyərləri topluyuruq.

  return Summa(2*v, lpos, mid, left, min(mid, right)) +
         Summa(2*v+1, mid+1, rpos, max(left, mid+1), right);
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq. Seqment ağacını başlatırıq.

cin >> n >> k;
SegTree.resize(4 * n);

$k$ sorğuları işləyirik. Sorğuların növündən asılı olaraq, ya qrup təyin etməni, ya da verilmiş seqmentdə cəmin hesablanmasını yerinə yetiririk.

while (k--)
{
  cin >> c;
  if (c == 'A')
  {
    cin >> l >> r >> x;
    SetValue(1, 1, n, l, r, x);
  }
  else
  {
    cin >> l >> r;
    cout << Summa(1, 1, n, l, r) << endl;
  }
}

C++