# STL database review

Happy New Year! The first blog in 2022 is mainly because I don't like summarizing, so I need to read more and summarize more. Then it's today's review!

## 1.vector

vector<int>a;
a.push_back();
a.pop_back();
a.insert(a.begin() + i, k);//Insert from position i
for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
cout << *i << endl;
}//Printing a vector requires iterations
//I didn't even know

## Title Description

There are n(n \le 2 \times 10^6)n(n ≤ 2 × 106 students entered the classroom one after another. We know that the student number of each student (between 1 and 10 ^ 9109) is given in the order of entering the classroom. After class, the teacher wants to know the student number of the second student entering the classroom (the first student entering the classroom i=1i=1), and the number of inquiries shall not exceed 10 ^ 5105 times.

## Input format

The first line contains two integers n and m, which represent the number of students and the number of inquiries.

n integers in the second line represent the student numbers entering the classroom in order.

The third line is m integers, which means to ask the first student to enter the classroom.

## Output format

m integers represent the answer, separated by a newline.

## Sample input and output

Enter #1 copy

10 3
1 9 2 60 8 17 11 4 5 14
1 5 9


Output #1 copy

1
8
5

A very simple topic, the input element can be pressed into the vector and output

#include <iostream>
#include <vector>
using namespace std;
vector<int>vec;
int main()
{
int n, m;
int t;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> t;
vec.push_back(t);
}
for (int i = 1; i <= m; i++) {
cin >> t;
cout << vec[t-1] << endl;
}
}

## 2.stack

First in and last out: the basic operations are also routine operations. This is relatively familiar, so just look at the examples.

## Title Description

Define the following rule sequence (string):

1. An empty sequence is a regular sequence;

2. If s is a regular sequence, then (S) and [S] are also regular sequences;

3. If both A and B are regular sequences, AB is also A regular sequence.

For example, the following strings are regular sequences:

()，[]，(())，([])，()[]，()[()]

The following are not:

(，[，]，)(，())，([()

Now, I'll give you some sequences composed of '(', ')', '[', ']'. What you need to do is to complete the sequence of parentheses, that is, scan the original sequence, and for each right parenthesis, find the matching left parenthesis closest to it on its left, and give up if it doesn't. After matching the original sequence in this way, complete the remaining unmatched parentheses.

## Input format

The input file has only one line, which is composed of '(', ')', '[', ']', without other characters, and the length is no more than 100.

## Output format

The output file also has only one line, all of which are composed of '(', ')', '[', ']', without other characters. You can output the completed rule sequence.

## Sample input and output

Enter #1 copy

([()


Output #1 copy

()[]()


## Description / tips

Complete the first two left parentheses.

#include <iostream>
#include <stack>
using namespace std;
stack<int>v;
string s, b;
int main()
{
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') {
b[i] = ')';
v.push(i);
}
if (s[i] == '[') {
b[i] = ']';
v.push(i);//Push the marked i onto the stack
}
if (s[i] == ')' || s[i] == ']') {
if (v.empty() || b[v.top()] != s[i]) {
if (s[i] == ')') {
b[i] = '(';
}
else {
b[i] = '[';
}
}
else {//If they are equal, they will be converted to '' in the b array, and then the top of the stack will be deleted
b[v.top()] = ' '; v.pop();
}
}
}
for (int i = 0; i < s.size(); i++) {
if (b[i] == '(' || b[i] == '[') {
cout << b[i];
}
cout << s[i];//Output original sequence
if (b[i] == ')' || b[i] == ']') {
cout << b[i];
}
}
}

## 3.queue

First in first out (I'm good at it, so please look at the example)

## Title Description

Xiaok is a customs officer in a seaport. Many ships arrive at the seaport every day. There are usually many passengers from different countries on board.

Xiao K is very interested in these ships that arrive at the harbor. He records every ship that arrives at the harbor according to the time; For the ith arriving ship, he recorded the arrival time ti (unit: Second) and the number of passengers on board k_iki, and the nationality of each passenger {x_{i,1}, x_{i,2},…,x_{i,k}xi,1​,xi,2​,…,xi,k​.

Xiaok has counted the information of nn ships. I hope you can help calculate how many different countries all passengers arriving by ship come from within 2424 hours (2424 hours = 8640086400 seconds) until the arrival time of each ship.

Formally, you need to calculate nn pieces of information. For the second piece of information output, you need to make statistics to meet t_ i-86400<t_ p \le t_ Ship pp with ITI − 86400 < TP ≤ ti, in all x_ How many different numbers are there in {P, J} XP, J}.

## Input format

In the first line, enter a positive integer nn, indicating that small K counts the information of nn ships.

Next nn lines, each line describes the information of a ship: the first two integers t_iti and k_iki ， respectively represents the time when the ship arrives at the harbor and the number of passengers on board, and then k_iki# integer x_{i,j}xi,j} indicates the nationality of the passengers on board.

Guaranteed input t_iti is incremented in seconds; It means that the timing starts from the first work of xiaok, and the ship is at t_iti # seconds to the harbor.

Ensure that 1 \le n \le 10^51 ≤ n ≤ 105, \ sum{k_i} \le 3*10^5 ∑ ki ≤ 3 * 105, 1\le x_{i,j} \le 10^51≤xi,j​≤105， 1 \le t_{i-1}\le t_i \le 10^91≤ti−1​≤ti​≤109.

Where \ sum{k_i}Σki represents all k_ The sum of IKI.

## Output format

Output line nn, and an integer in line ii represents the statistical information after the arrival of ship ii.

## Sample input and output

Enter #1 copy

3
1 4 4 1 2 2
2 2 2 3
10 1 3

Output #1 copy

3
4
4


Enter #2 copy

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

Output #2 copy

3
3
3
4

#include <iostream>
#include <queue>
using namespace std;
struct node {
int t;
int x;
};
queue<node>v;
int n, m, t, b;
int ans = 0;
int a[1001000];//The array needs to be larger
node k;
int main()
{
cin >> n;
while (n--) {
cin >> t >> m;
while (!v.empty()) {
k = v.front();//Take the head of the line
if (k.t + 86400 <= t) {
a[k.x]--;
if (a[k.x] == 0) {
ans--;//Persons without the nationality of that country, persons with the nationality of that country - 1
}
v.pop();
continue;//Skip this cycle and enter the next cycle
}
break;
}
for (int i = 1; i <= m; i++) {
cin >> b;
k.t = t; k.x = b;
v.push(k);
a[k.x]++;//The number of occurrences of this number is increased by 1
if (a[k.x] == 1) {
ans++;
}
}
cout << ans << endl;
}
}

## 6.list / / linked list

push_back(x);//Add an element at the end of the container
pop_back();//Delete the last element in the container
push_front(x);//Insert an element at the beginning of the container
pop_front();//Remove the first element from the beginning of the container
insert(a,b);//Insert a copy of element b in position a and return the location of the new data.
clear();//Remove all data from the container
erase(begin,end);//Delete the data in the [begin,end) interval and return the position of the next data.
erase(a);//Delete the data at position a and return to the position of the next data.
remove(a);//Delete all elements in the container that match the a value.



## 9.algorithm / / header file

max();
min();
abs();
swap(a,b)
reverse(a.begin(),a.end())//Flip function
sort(a,b,cmp)
unique()//De duplication function, used after sort
find(x)//If there is x, return the position of X; if not, return the subscript of n+1
upper_bound(x);//Returns the position of the first subscript greater than x
lower_bound(x);//Returns the first position greater than or equal to the x subscript
fill();//Function in filled interval
count(a,a+n,b);//Calculate the number of b in the interval
__gcd(a,b)//Find the greatest common factor
next_permutation(a,a+n)//Full arrangement
nth_element(a.begin(),a.begin()+2,a.end())//Put the number with the original position of 2 on the second largest position to ensure that the number in front is less than this number and the number behind is greater than this number.

Today's review is over, and the linear table Luogu is over immediately. I'm so happy. In the future, I should also convert knowledge into systematic knowledge, so that I can apply it more flexibly in the subject, make progress slowly, understand slowly, come on, I wish you a happy New Year!!! Zhong Yimiao continued to make progress in the new year.

Review greed and order tomorrow!

Keywords: C++ Database Algorithm STL

Added by binujayaraj on Thu, 03 Feb 2022 05:52:23 +0200