#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
long long found[100002], sum = 0, l, r, goal;
int kp2(int a[], int l, int r)
{
int k = rand()%(r-l+1)+l;
int s;
std::swap(a[l], a[k]);
float temp = a[l];
int i = l + 1, j = r;
while (1)
{
while (a[i] < temp && i <= r)
{
i++;
}
while (a[j] > temp && j >= l + 1)
{
j--;
}
if (i > j)
break;
std::swap(a[i], a[j]);
i++;
j--;
}
std::swap(a[l], a[j]);
return j;
}
void kp1(int a[], int l, int r)
{
if (l >= r)
return;
int num = kp2(a, l, r);
kp1(a, l, num-1);
kp1(a, num+1, r);
}
void twofen(int b[], int l, int r, int goal)
{
if (l > r)
{
return;
}
int mid = (l + r)/2;
if (b[mid] == goal)
{
sum ++;
found[sum] = goal;
}
if (b[mid] < goal) twofen(b, mid+1, r, goal);
if (b[mid] > goal) twofen(b, l, mid-1, goal);
}
using namespace std;
int main()
{
/*
课时：第三课 3. （扩展，洛谷 P 1 5 7 1）
题目：眼红的 Medusa
预计用时：20 分钟
实际用时：50 分钟
*/
int n, m;
int a[102000], b[102000], min1[101000], ji[101000] = { 0 };
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d", &b[i]);
}
kp1(b, 0, m-1);
l = 0;
r = m - 1;
for (int i = 0; i < n; i++)
{
twofen(b, l, r, a[i]);
}
for (int i = 1; i <= sum; i++)
{
printf("%d ", found[i]);
}
return 0;
}
by Jack_cjj2 @ 2019-01-31 16:48:06
天啊这字体咋弄
by Jack_cjj2 @ 2019-01-31 16:48:31
```cpp
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
long long found[100002], sum = 0, l, r, goal;
int kp2(int a[], int l, int r)
{
int k = rand()%(r-l+1)+l;
int s;
std::swap(a[l], a[k]);
float temp = a[l];
int i = l + 1, j = r;
while (1)
{
while (a[i] < temp && i <= r)
{
i++;
}
while (a[j] > temp && j >= l + 1)
{
j--;
}
if (i > j)
break;
std::swap(a[i], a[j]);
i++;
j--;
}
std::swap(a[l], a[j]);
return j;
}
void kp1(int a[], int l, int r)
{
if (l >= r)
return;
int num = kp2(a, l, r);
kp1(a, l, num-1);
kp1(a, num+1, r);
}
void twofen(int b[], int l, int r, int goal)
{
if (l > r)
{
return;
}
int mid = (l + r)/2;
if (b[mid] == goal)
{
sum ++;
found[sum] = goal;
}
if (b[mid] < goal) twofen(b, mid+1, r, goal);
if (b[mid] > goal) twofen(b, l, mid-1, goal);
}
using namespace std;
int main()
{
/*
课时：第三课 3. （扩展，洛谷 P 1 5 7 1）
题目：眼红的 Medusa
预计用时：20 分钟
实际用时：50 分钟
*/
int n, m;
int a[102000], b[102000], min1[101000], ji[101000] = { 0 };
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d", &b[i]);
}
kp1(b, 0, m-1);
l = 0;
r = m - 1;
for (int i = 0; i < n; i++)
{
twofen(b, l, r, a[i]);
}
for (int i = 1; i <= sum; i++)
{
printf("%d ", found[i]);
}
return 0;
}
```
by Jack_cjj2 @ 2019-01-31 16:49:01