2018/2019 region tour 1 task 3

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

using i32 = int32_t;
using ui32 = uint32_t;



class TTree {
private:
    ui32 Size;
    vector<i32> Data;

public:
    TTree(ui32 size) {
        for (Size = 1; Size < size; Size *= 2);
        Data.resize(2 * Size - 1);
    }

    void Change(ui32 index, i32 value) {
        index += Size - 1;
        if (index >= Data.size()) {
            return;
        }
        Data[index] += value;
        while (index) {
            index = (index - 1) / 2;
            Data[index] += value;
        }
    }

    i32 GetSum(ui32 left, ui32 right) {
        if (left > right) {
            return 0;
        }
        return GetSum(0, 0, Size - 1, left, right);
    }

    i32 GetValue(ui32 index) {
        return Data[index + Size - 1];
    }


private:
    i32 GetSum(ui32 index, ui32 realLeft, ui32 realRight, ui32 queryLeft, ui32 queryRight) const {
        if (queryLeft <= realLeft && realRight <= queryRight) {
            return Data[index];
        }
        if (queryRight < realLeft || realRight < queryLeft) {
            return 0;
        }
        ui32 middle = (realLeft + realRight) / 2;
        return GetSum(index * 2 + 1, realLeft, middle, queryLeft, queryRight)
            + GetSum(index * 2 + 2, middle + 1, realRight, queryLeft, queryRight);
    }
};

void pushToCloud(ui32 value, set<ui32>& cloud, vector<ui32>& items) {
    cloud.insert(value);
    items.push_back(value);
    //cout << value << " ";
}

void fillNext(const vector<ui32>& items, vector<ui32>& next) {
    unordered_map<ui32, ui32> next_index;
    next.resize(items.size());
    ui32 size = items.size();
    for (ui32 i = size; i >= 1; --i) {
        ui32 index = i - 1;
        if (next_index.count(items[index])) {
            next[index] = next_index[items[index]];
        }
        else {
            next[index] = size;
        }
        next_index[items[index]] = index;
    }
}


int main() {
    ui32 N, M;
    scanf("%u%u", &N, &M);

    vector<ui32> a(M), b(N);
    for (ui32 i = 0; i < M; ++i) {
        scanf("%u", &a[i]);
    }
    for (ui32 i = 0; i < N; ++i) {
        scanf("%u", &b[i]);
    }

    ui32 current = 0;
    vector<ui32> items;
    set<ui32> cloud;
    for (ui32 i = 0; i < M; ++i) {
        ui32 found = false;
        if (current < N && a[i] == b[current]) {
            found = true;
            pushToCloud(b[current++], cloud, items);
        }
        else {
            if (cloud.count(a[i])) {
                pushToCloud(a[i], cloud, items);
                found = true;
            }
        }
        while (!found) {
            if (b[current] == a[i]) {
                found = true;
            }
            pushToCloud(b[current++], cloud, items);
        }
    }

    vector<ui32> next;
    fillNext(items, next);

    TTree tree(items.size());
    for (ui32 i = 0; i < items.size(); ++i) {
        tree.Change(i, 1);
    }
    for (ui32 i = 0; i < items.size(); ++i) {
        if (next[i] != items.size() && tree.GetValue(i)) {
            ui32 index = next[i];
            while (index < items.size()) {
                tree.Change(index, -1);
                index = next[index];
            }
        }
    }

    printf("%u\n", items.size());
    for (ui32 i = 0; i < items.size(); ++i) {
        i32 countOfDifferent = tree.GetSum(i + 1, next[i] - 1);
        printf("%d ", countOfDifferent + 1);
        tree.Change(next[i], 1);
    }
    printf("\n");
    return 0;
}