Ticarət#7482

Ticarət (Həll təhlili)

$[1; n]$ diapazonunda seqment ağacı quraq və əvvəlcə onu sıfırlayaq. Ticarətçi $[l_{i}; r_{i}]$ [l_i; r_i] yaşayış məntəqələrində papaqlar satırdısa və qiyməti $p_{i}$ p_i ilə başlayırdısa, $[l_{i}; r_{i}]$ [l_i; r_i] seqmentini əsas seqmentlərə ayıraq: $[l x_{1}; r y_{1}], [l x_{2}; r y_{2}], ..., [l x_{k}; r y_{k}]$ [lx_1; ry_1], [lx_2; ry_2], ..., [lx_k; ry_k]. Sonra $[l x_{q}; r y_{q}] (1 \leq q \leq k)$ [lx_q; ry_q]~(1 \le q \le k) seqmentinə

p_{i} + se q m e n tl ə r in u z u n l u q l a r ı n ı n c ə mi [l x_{t}; r y_{t}], b u ¨ t u ¨ n t < q u ¨ c \c u ¨ n .

p_i + seqmentlərin~uzunluqlarının~cəmi~[lx_t; ry_t], bütün~t < q~üçün.

mənasını əlavə edək.

Məsələn, $n = 5$ n = 5 və ilk ticarət 2-dən 5-ə qədər nömrəli şəhərləri əhatə etdiyini düşünək və 4 qiyməti ilə başlayırıq. Sonra $[2; 5]$ seqmenti əsas seqmentlərə çevriləcəkdir: $[2; 2], [3; 3], [4; 5]$ [2; 2], [3; 3], [4; 5]. İlk əməliyyatdan sonra seqment ağacı bu şəkildə görünəcək:

Əgər əsas seqment $[a; b]$ qiymətini $p$ saxlayırsa, bu o deməkdir ki:

Ticarətçi bütün $a$ -dan $b$ -yə qədər şəhərlərdə papaqlar satmışdır.
$a$ şəhərində papaq $p$ qiymətinə satılırdı, $a + 1$ a + 1 şəhərində $p + 1$ p + 1 qiymətinə və beləliklə, $b$ şəhərində qiyməti $p + b - a$ p + b - a qədər olurdu.

$[l e f t; r i g h t]$ [left; right] (ticarətçinin ticarət etdiyi seqment) sorğusunun $[l p os; r p os]$ [lpos; rpos] diapazonunda işlənməsi prosedurunu nəzərdən keçirək, əgər papağın başlanğıc qiyməti $x$ -dirsə.

Sol alt seqmentdə ticarətçi $x$ qiymətindən başlayaraq $l e n = min (mi d, r i g h t) - l e f t + 1$ len = min(mid, right) - left + 1 şəhərlərində papaqları satacaqdır. Sağ alt seqmentdə ticarətçinin gələcəyi şəhərdə papağın ilk qiyməti $x + l e n$ x + len olacaqdır. Beləliklə, $[ma x (l e f t, mi d + 1), r i g h t]$ [max(left, mid + 1), right] aralığında ticarət $x + l e n$ x + len qiymətindən başlanacaq. Ancaq əgər $l e n < 0$ len < 0-dursa (bu mümkündür, əgər sorğu aralığının bütün seqmenti sağ alt seqmentdədirsə), $l e n = 0$ len = 0 qoymalıyıq.

$[a; b]$ seqmentini nəzərdən keçirdikdə, bu seqmentin iki alt seqmenti var: $[a; m]$ və $[m + 1; b]$ [m + 1; b]. Əgər $a$ şəhərində ticarətçi papağı $p$ qiymətinə satırsa, onda $m + 1$ m + 1 şəhərində onun qiyməti $p + m + 1 - a$ p + m + 1 - a olacaqdır.

Sorğuların işlənməsi prosesində maksimumu dəstəkləyən dəyərlərin itələməsini tətbiq edək.

Cavabın çıxışını vermək üçün ağac boyunca keçərək bütün dəyərləri yarpaqlara qədər itələyib və nəticəni çıxış edək.

Nümunə

Nümunədə verilmiş iki sorğunun icrasını nəzərdən keçirək. Sorğu seqmentlərini əsas seqmentlərə bölək:

$[1; 3] = [1; 3]$ [1; 3] = [1; 3];
$[2; 4] = [2; 2] + [3; 3] + [4; 4]$ [2; 4] = [2; 2] + [3; 3] + [4; 4].

Alqoritm realizasiyası

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

#define MAX 300010
long long SegTree[4*MAX];

Push funksiyası $v$ zirvəsindən onun davamçılarına dəyəri itələyir.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v])
  {
    SegTree[2 * v] = max(SegTree[2 * v], SegTree[v]);
    SegTree[2 * v + 1] = max(SegTree[2 * v + 1], 
                             SegTree[v] + mid - lpos + 1);
    SegTree[v] = 0;
  }
}

C++

Update funksiyası $x$ qiymətindən başlayaraq $[l e f t; r i g h t]$ [left; right] aralığında papaqların satışını yerinə yetirir.

void Update(int v, int lpos, int rpos, int left, int right, 
            long long x)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
    SegTree[v] = max(SegTree[v], x);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    int len = min(mid, right) - left + 1;
    if (len < 0) len = 0;
    Update(2 * v, lpos, mid, left, min(mid, right), x);
    Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                                         right, x + len);
    }
}

C++

PrintResult funksiyası daxili zirvələrdən dəyərləri yarpaqlara itələyir və massivinin son vəziyyətini çıxış edir.

void PrintResult(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    printf("%lld ", SegTree[v]);
  else
  {
    int mid = (lpos + rpos) / 2;
    Push(v, lpos, mid, rpos);

    PrintResult(2 * v, lpos, mid);
    PrintResult(2 * v + 1, mid + 1, rpos);
  }
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d", &n, &m);
memset(SegTree,0,sizeof(SegTree));

$m$ sorğuları işlədirik.

for(i = 0; i < m; i++)
{
  scanf("%d %d %lld", &l, &r, &x);
  Update(1,1,n,l,r,x);
}

Nəticəni çıxış edirik.

PrintResult(1,1,n);
printf("\n");