johnchen902's Blog

Compute the longest increasing subsequence while inserting almost-smallest numbers and deleting almost-leftmost numbers.

There are some positions from left to right. Each position may hold a positive integer. You have to handle two operations:

1. Put a number to a specified position.
2. Remove the x-th number from the left.

Additionally, each number increases by 1 before each operation, and you have to print out the length of the longest increasing subsequence (from left to right) after each operation.

Neither the number to add in the first operation nor the x in the second operation is larger than 10.

Recall the static LIS algorithm: Create a list that is initially empty. For each number x, replace the smallest number larger than x on the list with x. If x is already larger than all numbers on the list, append it to the list instead.

I tried to directly emulate the changes, but I failed. Then suddenly I realized I can swap small and large and swap left and right, and the changes can be emulated.

Change the list of numbers to a list of deques. Instead of replacing numbers, append the numbers to the corresponding deque. The largest number is always at the front of some deque, while the rightmost number is always at the back. Moreover, the positions of the fronts are monotonic, and so do the numbers of the backs. Therefore, it's easy to handle insertion and deletion of the largest number or the rightmost number.

To handle an almost-largest number, temporarily remove all larger numbers. To handle an almost-rightmost number, temporarily remove all numbers to its right. As only insertion of almost-largest numbers and deletion of almost-rightmost numbers are needed, the problem is solved.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <stack>
using namespace std;

vector<deque<pair<int, int>>> a;
map<int, int> p2h, h2p;

void insert(int p, int h) {
    stack<pair<int, int>> temp;
    for(auto ite = h2p.end(); ite != h2p.begin(); ) {
        --ite;
        if(ite->first < h)
            break;
        temp.push(make_pair(ite->second, ite->first));
        auto ite2 = partition_point(a.begin(), a.end(),
                [ite](const deque<pair<int, int>> &d) {
                    return d.front().first < ite->second;
                });
        ite2->pop_front();
        if(ite2->empty())
            a.pop_back();
    }
    p2h.insert(make_pair(p, h));
    h2p.insert(make_pair(h, p));
    temp.push(make_pair(p, h));
    while(!temp.empty()) {
        auto pa = temp.top();
        temp.pop();
        auto ite = partition_point(a.begin(), a.end(),
                [pa](const deque<pair<int, int>> &d) {
                    return d.front().first < pa.first;
                });
        if(ite == a.end())
            a.emplace_back(1, pa);
        else
            ite->push_front(pa);
    }
}

void remove(int x) {
    stack<pair<int, int>> temp;
    for(auto ite = p2h.end(); x--; ) {
        --ite;
        temp.push(*ite);
        auto ite2 = partition_point(a.begin(), a.end(),
                [ite](const deque<pair<int, int>> &d) {
                    return d.back().second < ite->second;
                });
        ite2->pop_back();
        if(ite2->empty())
            a.pop_back();
    }

    p2h.erase(temp.top().first);
    h2p.erase(temp.top().second);
    temp.pop();

    while(!temp.empty()) {
        auto pa = temp.top();
        temp.pop();
        auto ite = partition_point(a.begin(), a.end(),
                [pa](const deque<pair<int, int>> &d) {
                    return d.back().second < pa.second;
                });
        if(ite == a.end())
            a.emplace_back(1, pa);
        else
            ite->push_back(pa);
    }
}

int getlis() {
    return a.size();
}

int main() {
    int q;
    scanf("%*d %d", &q);
    for(int i = 0; i < q; i++) {
        int type;
        scanf("%d", &type);
        if(type == 1) {
            int p, h;
            scanf("%d %d", &p, &h);
            insert(-p, i - h);
        } else if(type == 2) {
            int x;
            scanf("%d", &x);
            remove(x);
        }
        printf("%d\n", getlis());
    }
}