Bibble və Kapitan Snappy#4486

Bibble və Kapitan Snappy (Həll təhlili)

Məsələni açıqlayan bir xətti ağaç quracıq, bu ağac toplama əməliyyatını dəstəkləyir. Hər bir zirvədə (əsas segment $[a; b]$ ) əlavə olaraq $l e f t$ dəyərini saxlayacağıq. Əgər $l e f t > 0$ left > 0 isə, bu zaman zirvədə $[a; b]$ gecikdirilmiş bir əməliyyat var: onun alt ağacının bütün zirvələrinə $l e f t, l e f t + 1, ..., l e f t + b - a$ left, left + 1, ..., left + b - a dəyərləri təsis edilməlidir. Əvvəlcə, bütün zirvələrdə $l e f t$ 0-a bərabərdir.

Dəyərləri ötürmə prosesinə nəzər salaq. Tutaq ki, sorğu $q (x, y)$ q(x, y) hər iki alt ağacı qismən kəsir, yəni $x \leq m < y$ x \le m < y. Bu halda:

Sol övlad üçün $l e f t = 1$ left = 1 təsis edirik.
Sağ övlad üçün $l e f t$ dəyərini $[x; m]$ intervalının uzunluğu ilə 1 artıraraq dəqiqləşdiririk.

Əgər $a \neq = x (b \neq = y)$ a \ne x~(b \ne y), bu halda $l e f t$ dəyəri daha ötürülməlidir.

Əgər $x \geq m + 1$ x \ge m + 1 (sorğu intervalı tamamilə sağ alt ağacda yerləşirsə), bu halda sol övlad üçün $l e f t$ dəyəri 0 olaraq qalır.

Tutaq ki, sorğu $q (x, y)$ q(x, y) $[a_{1}, b_{1}], [a_{2}, b_{2}], ..., [a_{k}, b_{k}]$ [a_1, b_1], [a_2, b_2], ..., [a_k, b_k] əsas segmentləri ilə örtülür. Bu halda $[a_{i}, b_{i}]$ [a_i, b_i] segmenti üçün $l e f t$ dəyərini

1 + ə v v ə l k i [a_{j}, b_{j}] se g m e n tl ə r inin u z u n l u q l a r ı n ı n c ə mi, j < i o l d u q d a

1~+~əvvəlki~[a_j,b_j]~segmentlərinin~uzunluqlarının~cəmi,~j < i~olduqda

müəyyən edirik.

Məsələn, ağac $[1..8]$ intervalında qurulubsa və sorğu $q (2, 7)$ q(2, 7) aşağıdakı əsas segmentləri örtürsə:

Nümunə

Növbəti testi nəzərdən keçirək:

Hər bir zirvənin yaxınında düzbucaqda intervalın sum resm halı yazılmışdır.

Alqoritmin realizasiyası

Dəmir ağacı saxlamaq üçün $S e g T r ee$ SegTree massivini elan edək.

struct node
{
  long long summa;
  int left;
};
vector<node> SegTree;

BuildTree funksiyası xətti ağacı qurur.

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

C++

Sum funksiyası $a$ ilə $b$ arasındaki rəqəmlərin cəmini hesablayır.

long long Sum(int a, int b)
{
  return 1LL * (a + b) * (b - a + 1) / 2;
}

Push funksiyası $v$ zirvəsindən onun oğullarına $l e f t$ dəyərini ötürür. Oğullar üçün $s u m$ yenidən hesablanır.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v].left)
  {
     SegTree[2 * v].left = SegTree[v].left;
     SegTree[2 * v].sum = Sum(SegTree[2 * v].left, 
                              SegTree[2 * v].left + mid - lpos);

     SegTree[2 * v + 1].left = SegTree[v].left + mid - lpos + 1;
     SegTree[2 * v + 1].sum = Sum(SegTree[2 * v + 1].left, 
                        SegTree[2 * v + 1].left + rpos - mid - 1);
     SegTree[v].left = 0;
  }
}

C++

Update funksiyası $[l e f t; r i g h t]$ [left; right] intervallını, $f r o m, f r o m + 1, f r o m + 2, ...$ from, from + 1, from + 2, ... ardıcıllığı ilə doldurur.

void Update(int v, int lpos, int rpos, int left, int right, int from)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v].left = from;
    SegTree[v].sum = Sum(from, from + right - left);
    return;
  }

  int mid = (lpos + rpos) / 2;
  int midval = mid - left + 1;

C++

Əgər sorğu intervalı $[mi d + 1; r p os]$ [mid + 1; rpos] sağ alt ağacda tamamilə yerləşirsə, sağ oğula $f r o m$ dəyərini dəqiq dəyişiklik etmədən ötürürük (bu halda $mi d v a l$ 0 olaraq təyin edilir).

  if (midval < 0) midval = 0;
  Push(v, lpos, mid, rpos);
  Update(2 * v, lpos, mid, left, min(mid, right), from);
  Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                             right, from + midval);
  SegTree[v].sum = SegTree[2 * v].sum + SegTree[2 * v + 1].sum;
}

C++

Summa funksiyası $[l e f t; r i g h t]$ [left; right] intervalında rəqəmlərin cəmini qaytarır.

long long Summa(int v, int lpos, int rpos, int Left, int Right)
{
  if (Left > Right) return 0;
  if ((lpos == Left) && (rpos == Right)) return SegTree[v].sum;
    
  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos);

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

C++

Proqramın əsas hissəsi. Giriş rəqəmlər massivini oxuyuruq.

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

Xətti ağacı qururuq.

SegTree.resize(4 * n);
BuildTree(1, 1, n);

$q$ sorğularını ardıcıl olaraq işləyirik.

scanf("%d", &q);
for(i = 0; i < q; ++i)
{
  scanf("%d %d %d", &type, &l, &r);
  if(type == 1)
    printf("%lld\n", Summa(1,1,n,l,r));
  else
    Update(1,1,n,l,r,1);
}

C++