Sadə Tapşırıq (Həll təhlili)

Hər bir hərf üçün - $a$-dan $z$-yə qədər olan hərflər üçün - 26 seqment ağacı qururuq. Hər ağac çoxlu modifikasiyanı dəstəkləməlidir.

Məsələn, '$a$' hərfi və "$abacdabcda$" sətiri üçün uyğun seqment ağacı bu formada görünəcəkdir:

Belə bir ağac vasitəsilə logaritmik vaxtda verilmiş hərfin [l; r] aralığında neçə dəfə təkrarlandığını müəyyən etmək olar.

Sorğunu [l; r] aralığında icra etmək say ilə çeşidləmə tətbiq etməyə endirilir. Əvvəlcə $cnt$ massivində bu aralıqda hər hərfin neçə dəfə təkrarlanması hesablanır.

Sonra $k$ dəyərinə əsasən, bu parçanı yenidən "çəkilirik":

• əgər k = 1, hərflər artan sırada düzülür — yəni, '$a$'-dan '$z$'-yə;

• əgər k = 0, azalacaq qaydada, '$z$'-dən '$a$'-ya.

Bunun üçün [l; r] aralığında hər bir '$a$' + $j$ hərfi üçün, cnt massivindən məlum olan sayı ilə, artan sırada (əgər artan sort etsək) sol tərəfdən ($l$)'dan başlayaraq və ya azalan sıralamadə sağ tərəfdən ($r$)'dan başlayaraq bu hərflər üçün seqment ağacına uyğun sayda birlər yazılır.

Misal üçün, $[10;17]$ aralığında "acbdbcab" alt sırası var. Bu intervallarda hər hərfin sayını hesablayaq:

• '$a$' hərfi $2$ dəfə;

• '$b$' hərfi $3$ dəfə;

• '$c$' hərfi $2$ dəfə;

• '$d$' hərfi $1$ dəfə;

Simvolları $[10;17]$ arasına artan sırada yerləşdirmək üçün, əvvəlcə hər hərf üçün seqment ağacında bu aralıqdakı dəyərləri sıfır etmək və sonra hər əməliyyatı həyata keçiririk:

• '$a$' üçün $[10;11]$ aralığında hər bir eleməntə $1$ dəyəri vermək;

• '$b$' üçün $[12;14]$ aralığında hər bir eleməntə $1$ dəyəri vermək;

• '$c$' üçün $[15;16]$ aralığında hər bir eleməntə $1$ dəyəri vermək;

• '$d$' üçün $[17;17]$ aralığında hər bir eleməntə $1$ dəyəri vermək;

Seqment ağaclarının belə "yenilənməsi" simvolları həmin müsabiqədə yerində dəyişiklik etmədən modellu edir.

Bütün sorğuları apardıqdan sonra yekun sətir seqment ağaclarının məzmunundan bərpa edilir: hər bir hərf üçün onun ağacını ardıcıl gəzərək, dəyəri $1$-ə bərabər olan mövqelərdə uyğun simvol nəticə sətirinə yazılır.

Alqoritmin Tətbiqi

'$a$' və '$z$' arasında olan hər bir hərf üçün seqment ağacları yaradaq. Beləliklə, cəmi ALPHABET = 26 ağac istifadə olunur, hər biri toplama və çoxlu modifikasiyanı dəstəkləyir.

#define MAX 100010
#define ALPHABET 26
struct node
{
  int sum, add;
} SegTree[4*MAX][ALPHABET];

Hər bir hərfin əlavə edilmə miqdarını hesablamaq üçün massiv təqdim edək.

int cnt[ALPHABET];

$s$ sətiri üzrə seqment ağaclarını - hər bir latın əlifbası üçün bir ağac olmaqla - yaradarıq.

void build(int v, int lpos, int rpos)
{
  if (lpos == rpos)
  {
    SegTree[v][s[lpos] - 'a'].sum = 1;
    for (int i = 0; i < ALPHABET; i++)
      SegTree[v][i].add = -1;
  }
  else
  {
    int mid = (lpos + rpos) / 2;
    build(v * 2, lpos, mid);
    build(v * 2 + 1, mid + 1, rpos);
    for (int i = 0; i < ALPHABET; i++)
    {
      SegTree[v][i].sum = 
             SegTree[v * 2][i].sum + SegTree[v * 2 + 1][i].sum;
      SegTree[v][i].add = -1;
    }
  }
}

void Push(int v, int lpos, int mid, int rpos, int ver)
{
  if (SegTree[v][ver].add != -1)
  {
    SegTree[2 * v][ver].add = SegTree[v][ver].add;
    SegTree[2 * v][ver].sum = (mid - lpos + 1) * SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].add = SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].sum = (rpos - mid) * SegTree[v][ver].add;
    SegTree[v][ver].add = -1;
  }
}

Vərs v üçün aralıq [lpos, rpos] uyğun gəlir. Seqment ağacı ilə dəyəri $val$ etmək üçün addımları qururuq.

void SetValue(int v, int lpos, int rpos, int left, int right, 
              int val, int ver)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v][ver].add = val;
    SegTree[v][ver].sum = (right - left + 1) * val;
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

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

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

int Summa(int v, int lpos, int rpos, int left, int right, int ver)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right)) return SegTree[v][ver].sum;

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

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

Seqment ağacında hər mövqedə '$a$' + $ver$ dəyərli hərfləri yerləşdirmək üçün hər vərsiyada olan məlumatları sıxaraq endirim apararaq xətlərin götürülməsinə imkan veririk.

void get(int v, int lpos, int rpos, int ver)
{
  if (SegTree[v][ver].sum == 0) return;
  if (lpos == rpos)
  {
    s[lpos] = ver + 'a';
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

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

Programın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Girişi sətir $s$ üzərinə 26 seqment ağacı yaradılır.

cin >> n >> q;
cin >> s;
s = " " + s;
build(1,1,n);

Növbənöv $q$ sorğularını icra edirik.

for (i = 0; i < q; i++)
{
  cin >> l >> r >> command;

[l; r] aralığında hərflərin bütün sayına uyğun sortlama edək. Əgər verilmiş '$a$' hərfi üçün '$j$'-$a$-dan sayırıqsa, cnt[j]-yə yazsaq.

  for (j = 0; j < ALPHABET; j++)
    cnt[j] = Summa(1, 1, n, l, r, j);

Sonra $pos$ mövqeyindən asılı olaraq komandaya əsasən hərəkət edirik.

  pos = (command == 1) ? l : r;
  for (j = 0; j < ALPHABET; j++)
  {
    if (!cnt[j]) continue;
    SetValue(1, 1, n, l, r, 0, j);
    if (command)
    {
      SetValue(1, 1, n, pos, pos + cnt[j] - 1, 1, j);
      pos += cnt[j];
    }
    else
    {
      SetValue(1, 1, n, pos - cnt[j] + 1, pos, 1, j);
      pos -= cnt[j];
    }
  }
}

Seqment ağaclarının məzmununa əsasən nəticə sətirini generasiya edirik. Funksiya get(1, 1, n, i) seqment ağacının məlumatlarını istifadə edərək '$a$' + $i$ hərfləri atlamalarda yerləşdirir. get funksiyası, hər biri etmək üçün zaman $O(n)$ olmaqla, seqment ağaclarının bütün vərsələrini qəsətir.

for (i = 0; i < ALPHABET; i++)
  get(1, 1, n, i);

Nəticə sətirini çıxarırıq.

cout << s.substr(1);