Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

C - Adjacent Swaps

Problem Statement

$N$ balls are arranged in a row from left to right. Initially, the $i$-th ball from the left has the number $i$ written on it.
Perform $Q$ operations, where the $i$-th operation is as follows:

• Let $j$ be the position of the ball with number $x_i$ written on it among the $N$ balls.
• If $j=N$, swap it with the $(j-1)$-th ball; otherwise, swap it with the $(j+1)$-th ball.

Output the numbers written on the balls after all operations. See the output format for details.

$2\le N\le 2\times 10^5$
$1\le Q\le 2\times 10^5$
$1\le x_i\le N$

Input Format

$N~Q$
$x_1$
$\vdots$
$x_Q$

Output Format

Let $a_i$ be the number written on the $i$-th ball from the left after all operations. Output in the following format:
$a_1~a_2~\dots~a_n$
That is, output $a_1,\dots,a_n$ in order on a single line, separated by spaces.

Sample

Refer to AtCoder for samples.

Analysis

Given the constraints, only algorithms with time complexity $\mathcal O(N+Q\log n)$ or better are acceptable.
Brute-force simulation (searching for positions in $\mathcal O(NQ)$) is infeasible.

An efficient approach is to maintain index arrays $p$, where $p_x=i$ when $a_i=x$.
This allows finding the position of $x_i$ in $\mathcal O(1)$ per operation.
When swapping, update both $a$ and $p$. Total time complexity is $\mathcal O(N+Q)$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <cstdio>
#define maxn 200005
using namespace std;

inline void swap(int& x, int& y) { x ^= y ^= x ^= y; }

int pos[maxn], ans[maxn];

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++)
        ans[i] = pos[i] = i;
    while(q--)
    {
        int x;
        scanf("%d", &x);
        int p1 = pos[x];
        int p2 = p1 == n? p1 - 1: p1 + 1;
        swap(pos[x], pos[ans[p2]]);
        swap(ans[p1], ans[p2]);
    }
    for(int i=1; i<=n; i++)
        printf("%d ", ans[i]);
    return 0;
}

D - 250-like Number

Problem Statement

A positive integer $k$ is called “250-like” if:

• $k=p\times q^3$ where $p$ and $q$ are primes with $p < q$.

Count the number of 250-like numbers $k$ that do not exceed $N$.

$1\le N\le 10^{18}$

Input Format

$N$

Output Format

Output the answer as an integer.

Sample

Analysis

Given the large $N$, we note that $q$ is bounded by $\sqrt[3]{N/2}\approx794000$.

Sieve primes up to this bound. For each prime $p$, compute the maximum $q$ such that $p\times q^3\le N$, then add the count of primes in $(p, q]$. Terminate when $p\ge q$.

Use binary search or a two-pointer technique. Total time complexity is approximately $\mathcal O(n^{\frac{7}{22}})$.

Code

This implementation uses a two-pointer approach.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
#include <cmath>
#include <vector>
#define maxp 794000
using namespace std;

using LL = long long;

bool bad[maxp];
vector<int> primes;

inline LL pow3(LL x) { return x * x * x; }

int main()
{
    bad[0] = bad[1] = true;
    for(int i=2; i<maxp; i++)
        if(!bad[i])
        {
            primes.push_back(i);
            for(int j=i<<1; j<maxp; j+=i)
                bad[j] = true;
        }
    LL n;
    scanf("%lld", &n);
    LL ans = 0LL;
    for(int i=0, j=primes.size()-1; i<j; i++)
    {
        while(j >= 0 && primes[i] * pow3(primes[j]) > n) j --;
        if(i >= j) break;
        ans += j - i;
    }
    printf("%lld\n", ans);
    return 0;
}

E - Prefix Equality

Problem Statement

Given two length-$N$ sequences $A=(A_1,\dots,A_N)$ and $B=(B_1,\dots,B_N)$.
For $1\le i\le Q$, answer queries of the form:

• Determine if the sets $\{A_1,\dots,A_{x_i}\}$ and $\{B_1,\dots,B_{y_i}\}$ are equal.

A set is formed by deduplicating and sorting the sequence. For example, $(9,3,5,3,4)$ corresponds to $\{3,4,5,9\}$.

$1\le N,Q\le 2\times 10^5$
$1\le A_i\le B_i\le 10^9$

Input Format

$N$
$A_1~\dots~A_N$
$B_1~\dots~B_N$
$Q$
$x_1~y_1$
$\vdots$
$x_Q~y_Q$

Sample

Sample Input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

5
1 2 3 4 5
1 2 2 4 3
7
1 1
2 2
2 3
3 3
4 4
4 5
5 5

Sample Output

1
2
3
4
5
6
7

Yes
Yes
Yes
No
No
Yes
No

Analysis

We use a hashing approach to solve this efficiently.

A query $(x,y)$ is answered by checking $P_A(x) == P_B(y)$.

To mitigate hash collisions, use a robust hash function like $H(x)=x(x+93)(x+117) \bmod (2^{32}-1)$. Time complexity is $\mathcal O(N+Q)$ with unordered sets.

Code

This code uses natural overflow for modular arithmetic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <cstdio>
#include <unordered_set>
#define maxn 200005
using namespace std;

inline int read()
{
    char c;
    while((c = getchar()) < '0' || c > '9');
    int res = c ^ 48;
    while((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c ^ 48);
    return res;
}

unsigned suma[maxn], sumb[maxn];
inline void hread(unsigned* psum, int n)
{
    unordered_set<int> s;
    for(int i=1, x; i<=n; i++)
    {
        psum[i] = psum[i - 1];
        if(s.insert(x = read()).second)
            psum[i] += x * unsigned(x + 93) * unsigned(x + 117);
    }
}

int main()
{
    int n = read();
    hread(suma, n);
    hread(sumb, n);
    for(int q=read(); q--;)
        puts(suma[read()] == sumb[read()]? "Yes": "No");
    return 0;
}