Rezolvare completă PbInfo #1648 Diez

Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:

  1. Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
  2. Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.

Cerința

Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.

Date de intrare

Fișierul de intrare diez.in conține pe prima linie valorile N şi M, separate printr-un spaţiu cu semnificaţia din enunţ. Pe a doua linie se află un şir de N litere mici ale alfabetului englez iar următoarele M linii conţin câte o operaţie în unul dintre formatele:

  • 1 p x – Datele pentru operaţia de tipul 1.
  • 2 q1 q2 lg – Datele pentru operaţia de tipul 2.

Date de ieșire

În fișierul de ieșire diez.out se vor scrie valori egale cu 0 sau 1, câte una pe o linie, reprezentând răspunsurile date, în ordine, la operaţiile de tipul 2 existente în fişierul de intrare.

Restricții și precizări

  • 1 ≤ N, M ≤ 250 000
  • 0 ≤ p ≤ lungimea şirului la momentul inserării
  • x este literă mică a alfabetului englez
  • q1, q2 ≥ 0; se garantează că pentru fiecare operaţie de tipul 2 există lg caractere în şir începând atât cu poziţia q1 cât şi cu poziţia q2
  • 1 < lg ≤ lungimea şirului la momentul efectuării operaţiei de tipul 2
  • Numerotarea caracterelor din şir începe de la poziţia 0

Exemplul 1

diez.in

8 6
abcasfas
2 0 5 3
1 3 d
2 4 7 2
1 1 s
1 10 b
2 0 8 3

diez.out

0
1
1

Explicație

Se compară secvenţele abc şi fas care sunt diferite → se afişează 0
Caracterul d este inserat înainte de poziţia 3 şi se obţine şirul abcdasfas
Se compară subşirurile as şi as, sunt identice → se afişează 1
Caracterul s este inserat înainte de poziţia 1, se obţine şirul asbcdasfas
Caracterul b este inserat pe poziţia 10, poziţia este egală cu lungimea şirului, se obţine şirul asbcdasfasb
Se compară subşirurile asb si asb , sunt identice → se afişează 1


Exemplu

diez.in

6 3
atmatm
2 0 2 4
1 6 a
2 0 3 4

diez.out

0
1

Explicație

Se compară subşirurile atma şi matm, sunt diferite → se afişează 0
Caracterul a se alipeşte la final, se obţine şirul atmatma
Se compară subşirurile atma atma, sunt identice → se afişează 1

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Diez:

#include <iostream>
#include <vector>
#include <cstdio>
#include <cassert>

using namespace std;

#define BASE 73
#define MOD1 1000000007
#define MOD2 1000000033
#define step(i) (i & (i ^ (i - 1)))
#define leftson  (node * 2)
#define rightson (node * 2 + 1)


class Operation {
public:
    int pos1, pos2, type, lg;
    bool ans;
    char ch;

    Operation(int type, int pos1, int pos2, int lg) {
        this->type = type;
        this->pos1 = pos1;
        this->pos2 = pos2;
        this->lg = lg;
    }

    Operation(int type, int pos1, char ch) {
        this->type = type;
        this->pos1 = pos1;
        this->ch = ch;
    }

    Operation() {
    }
};

struct Node {
    int real_lg, hash1, hash2;

    Node(int lg, int h) {
        real_lg = lg;
        hash1 = hash2 = h;
    }

    Node() {
        real_lg = hash2 = hash1 = 0;
    }
};

bool AreEqual(Node a, Node b) {
    return (a.hash1 == b.hash1 && a.hash2 == b.hash2 && a.real_lg == b.real_lg);
}

int N, M;
vector <Operation> ops;
vector <Node> seg_tree;
vector <int> aib0, aib1;
vector <pair <int, int> > power_base;
vector<char> final_line;

void read_int(int&);
void InsertAIB(vector<int> &aib, int pos, int N, int x);
int QueryAIB(vector<int> &aib, int pos);
Node GetMergeOf(Node &A, Node &B);
void UpdateHashSegmentTree(int node, int st, int mid, int en);
void RemoveSegmentTree(int node, int st, int en, int pos);
void BuildSegmentTree(int node, int st, int en);
Node QuerySegmentTree(int node, int st, int en, int a, int b);
int SearchPosAIB(vector <int> &aib, int target, int total);

void WriteWord(int st, int en) {
    for (; st <= en; ++st) {
        putchar(final_line[st]);
    }
    putchar('\n');
}

char initial_line[600000];

int main() {
    freopen("diez.in", "r", stdin);
    freopen("diez.out", "w", stdout);

    int i, j, type, pos1, pos2, lg, cnt1 = 0;
    char ch;

    scanf("%d %d\n", &N, &M);
    ops.resize(M);
    initial_line[0] = '#';
    scanf("%s", (initial_line + 1));

    for (i = 0; i < M; ++i) {
        scanf("%d", &type);
        if (type == 1) {
            ++cnt1;
            scanf("%d", &pos1);
            ++pos1;
            cin >> ch;
            ops[i] = Operation(type, pos1, ch);
        }
        else {
            scanf("%d", &pos1);
            ++pos1;
            scanf("%d", &pos2);
            ++pos2;
            scanf("%d", &lg);
            ops[i] = Operation(type, pos1, pos2, lg);
        }
    }

    int total = N + cnt1;
    final_line.resize(1 + total);
    seg_tree.resize(1 + 4 * total);
    aib0.resize(1 + total);
    aib1.resize(1 + total);
    power_base.resize(1 + total);

    power_base[0] = make_pair(1, 1);
    for (i = 1; i <= total; ++i) {
        assert(i < power_base.size());
        power_base[i].first  = ((long long) power_base[i - 1].first  * BASE) % MOD1;
        power_base[i].second = ((long long) power_base[i - 1].second * BASE) % MOD2;
    }

    for (i = 1; i <= total; ++i) {
        assert(i < aib0.size());
        aib0[i] = step(i);
    }

    for (i = M - 1; i >= 0; --i) {
        if (ops[i].type == 1) {
            int pos = SearchPosAIB(aib0, ops[i].pos1, total);
            InsertAIB(aib0, pos, total, -1);
            assert(pos < final_line.size());
            final_line[pos] = ops[i].ch;
        }
    }

    for (i = 1, j = 1; i <= N; ++j) {
        if (final_line[j] == 0) {
            assert(j < final_line.size());
            final_line[j] = initial_line[i++];
        }
    }

    BuildSegmentTree(1, 1, total);
    int hasha = 0, hashb = 0;
    for (i = 1; i <= total; ++i) {
        hasha = ((long long) hasha * BASE + final_line[i] - 'a' + 1) % MOD1;
        hashb = ((long long) hashb * BASE + final_line[i] - 'a' + 1) % MOD2;
    }
    assert(make_pair(hasha, hashb) == make_pair(seg_tree[1].hash1, seg_tree[1].hash2));

    for (i = 1; i <= total; ++i) {
        assert(i < aib1.size());
        aib1[i] = step(i);
    }

    for (i = M - 1; i >= 0; --i) {
        if (ops[i].type == 1) {
            int pos = SearchPosAIB(aib1, ops[i].pos1, total);
            final_line[pos] = '#';
            InsertAIB(aib1, pos, total, -1);
            RemoveSegmentTree(1, 1, total, pos);
        }
        else {
            int st1, en1, st2, en2;
            st1 = SearchPosAIB(aib1, ops[i].pos1, total);
            en1 = SearchPosAIB(aib1, ops[i].pos1 + ops[i].lg - 1, total);
            st2 = SearchPosAIB(aib1, ops[i].pos2, total);
            en2 = SearchPosAIB(aib1, ops[i].pos2 + ops[i].lg - 1, total);
            assert(st1 < final_line.size());
            assert(st2 < final_line.size());
            Node ans1 = QuerySegmentTree(1, 1, total, st1, en1);
            Node ans2 = QuerySegmentTree(1, 1, total, st2, en2);
            ops[i].ans = AreEqual(ans1, ans2);
        }
    }

    for (i = 0; i < M; ++i) {
        if (ops[i].type == 2) {
            putchar('0' + (int) ops[i].ans);
            putchar('\n');
        }
    }

    return 0;
}

void read_int(int &number) {
    number = 0;
    char ch;
    while (!isdigit(ch = getchar()) && ch != -1);
    if (ch == -1) {
        return;
    }
    do {
        number = number * 10 + (ch - '0');
    } while (isdigit(ch = getchar()) && ch != -1);
}

void InsertAIB(vector<int> &aib, int pos, int N, int x) {
    for (; pos <= N; pos += step(pos)) {
        aib[pos] += x;
    }
}
int QueryAIB(vector<int> &aib, int pos) {
    int ans = 0;
    for (; pos; pos -= step(pos)) {
        ans += aib[pos];
    }
    return ans;
}

Node GetMergeOf(Node &A, Node &B) {
    Node ans = A;
    ans.hash1 = ((long long) ans.hash1 * power_base[B.real_lg].first  + B.hash1) % MOD1;
    ans.hash2 = ((long long) ans.hash2 * power_base[B.real_lg].second + B.hash2) % MOD2;
    ans.real_lg += B.real_lg;
    return ans;
}

void UpdateHashSegmentTree(int node, int st, int mid, int en) {
    assert(0 < node && node < seg_tree.size());
    assert(0 < st && st < final_line.size());
    assert(0 < en && st < en && en < final_line.size());
    seg_tree[node] = GetMergeOf(seg_tree[leftson], seg_tree[rightson]);
}

void RemoveSegmentTree(int node, int st, int en, int pos) {
    if (st == en) {
        seg_tree[node] = Node();
        return;
    }

    int mid = (st + en) / 2;
    if (pos <= mid) {
        RemoveSegmentTree(leftson, st, mid, pos);
    }
    else {
        RemoveSegmentTree(rightson, mid + 1, en, pos);
    }
    UpdateHashSegmentTree(node, st, mid, en);
}

void BuildSegmentTree(int node, int st, int en) {
    assert(0 < node && node < seg_tree.size());
    assert(0 < st && st < final_line.size());
    assert(0 < en && en < final_line.size());
    if (st == en) {
        seg_tree[node] = Node(1, final_line[st] - 'a' + 1);
        return;
    }
    assert(0 < st && st < final_line.size());
    assert(0 < en && st < en && en < final_line.size());

    int mid = (st + en) / 2;
    BuildSegmentTree(leftson, st, mid);
    BuildSegmentTree(rightson, mid + 1, en);
    UpdateHashSegmentTree(node, st, mid, en);
}

Node QuerySegmentTree(int node, int st, int en, int a, int b) {
    if (a <= st && en <= b) {
        return seg_tree[node];
    }

    int mid = (st + en) / 2;
    Node ans1, ans2, final_ans;
    if (a <= mid) {
        ans1 = QuerySegmentTree(leftson, st, mid, a, b);
    }
    if (mid < b) {
        ans2 = QuerySegmentTree(rightson, mid + 1, en, a, b);
    }

    return GetMergeOf(ans1, ans2);
}

int SearchPosAIB(vector <int> &aib, int target, int total) {
    int pos = 0;
    for (int pw = 1 << 23; pw; pw >>= 1) {
        if (pos + pw <= total) {
            if (QueryAIB(aib, pos + pw) < target) {
                pos += pw;
            }
        }
    }
    return pos + 1;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1648 Diez

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1648 Diez de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!