2022-04-15 swipe questions and punch in every day

Code source - daily question

Longest common subsequence - Title - Daimayuan Online Judge

Give two permutations P1 and P2 from 1 to n, and find their longest common subsequence.

Input format

The first line is a positive integer n.

The next two lines, n numbers per line, are an arrangement of natural numbers 1,2,..., n.

Output format

A number, that is, the length of the longest common subsequence.

Data range

1≤n≤10^5

sample input

5 
3 2 1 4 5
2 1 3 4 5

sample output

4

At first glance, I thought it was a template question, but I knew it was not simple when I looked at the data range.

We may have written two-dimensional dp to find the longest common subsequence, and its time complexity is n^2. But here, the data is mentioned as 1e5. First of all, we can't open the two-dimensional array of 1e5*1e5 without exceeding the timeout. So what should I do? Is there any way to reduce the complexity to nlogn (or lower?) without using two-dimensional arrays.

First, there are two points. First, the two arrays given here are the arrangement of natural numbers 1, 2, 3... n, but the positions in the two arrays are different. Second, we should consider the meaning of common subsequence. In other words, the relative position of a sequence in two arrays is the same. For example, in the example, 2 is after 1, 4 is after 2, and 5 is after 2. So their longest common sequence is 2145, with a length of 4. Then more intuitively, if we make an array of the elements of an array according to the occurrence position of another array, then the longest common subsequence is the longest ascending subsequence of the array.

For example, in the second array b:21345, the subscript of element 2 in the first array A is 1, the subscript of 1 is 2,... 5 is 4, so we can get an array: 1 2 0 3 4, and then the elements with the subscript of 1 2 3 4 in the first array are the longest common subsequence of the second array, because their order of occurrence is the same (ascending sequence in a and ascending sequence in b)

So now the problem has changed from finding the longest common subsequence to the longest ascending subsequence. Fortunately, we happen to know how to write the nlogn of the longest ascending subsequence.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 100100;
int a[N], b[N], dp[N];
unordered_map<int, int>mymap;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        mymap[a[i]] = i;
    }
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        b[i] = mymap[x];
    }
    int len = 1;
    dp[0] = -1e7;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (dp[mid] < b[i])l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        dp[r + 1] = b[i];
    }
    cout << len-1 << endl;
    return 0;
}

CodeForces - segment tree topic

C - Segment Tree, part 1 - Codeforces

Given an array of 2n numbers, each number from 1 to n in it occurs exactly twice. We say that the segment y is nested inside the segment x if both occurrences of the number y are between the occurrences of the number x. Find for each segment ii how many segments that are nested inside it.

Input

The first line contains the number n (1≤n≤10^5), the second line contains 2n numbers. It is guaranteed that every number from 1 to n occurs exactly twice.

Output

Print n numbers, the i-th number is equal to the number of segments nested inside the segment i.

Example

input

5
5 1 2 2 3 1 3 4 5 4

output

1 0 0 0 3 

This question means that there are 2n numbers. The array is composed of 1~n. each number has two. The same two numbers are called a paragraph. Ask you how many paragraphs are included in a paragraph. For example, paragraphs 1, 2 and 3 are included between 5 and 5. 4 does not count because the right end of 4 is outside.

At the beginning, prepare a segment tree with all leaves of 0. When we go from left to right, we first record the subscript at the left end of each segment. When we go to the right end, we record the sum of the interval from the left end to the right end. The sum of the intervals indicates how many segments there are. After calculating the interval sum, we change the position of the left segment point from 0 to 1.

First of all, we will change the value of the left endpoint of a segment from 0 to 1 only after we finish walking the left and right ends of the segment. If the interval sum of a segment is not 0, then the number of interval sum indicates how many complete segments have been included. If only the left endpoint is included, the value of the left endpoint is still 0 before reaching the right endpoint. If only the right endpoint is included, but we only change the value of the left endpoint to 1, so the right endpoint will not be recorded.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n';
typedef long long ll;
typedef pair<int, int> PII;
const int N = 300050;
int f[4 * N], a[N], n;

void revise(int k, int l, int r, int x)
{
    if (l == r)
    {
        f[k] = 1;
        return;
    }
    int m = (l + r) / 2;
    if (x <= m)revise(k + k, l, m, x);
    else
        revise(k + k + 1, m + 1, r, x);
    f[k] = f[k + k] + f[k + k + 1];
}

int calc(int k, int l, int r, int x, int y)
{
    if (l == x && y == r)
    {
        return f[k];
    }
    int m = (l + r) / 2;
    if (y <= m)return calc(k + k, l, m, x, y);
    else
        if (x > m)return calc(k + k + 1, m + 1, r, x, y);
        else return calc(k + k , l, m, x, m) + calc(k + k+1, m + 1, r, m + 1, y);
}

int main()
{
    unordered_map<int, int>mymap;
    map<int, int>cnt;
    cin >> n;
    for (int i = 1; i <= 2*n; i++)
    {
        cin >> a[i];
        if (mymap[a[i]] == 0)mymap[a[i]] = i;
    }
    for (int i = 1; i <= 2*n; i++)
    {
        if (cnt[a[i]] == 0)
            cnt[a[i]] = 1;
        else
        {
            cnt[a[i]] = calc(1, 1, 2*n, mymap[a[i]], i);
            revise(1, 1, 2*n, mymap[a[i]]);

        }
    }
    for (auto i : cnt)cout << i.second << " ";
    return 0;
}