题解 | #区间翻转#

G. 区间翻转

知识点：时间复杂度、模拟

暴力模拟的时间复杂度是 ，空间复杂度是 ，显然是过不了的。

不难发现实际上这个序列的信息量很少，只需要维护 所在的位置 就行。

• 如果当前的位置 在区间里，则翻转后的位置为 ，
• 如果当前位置 不在区间里，则位置不变。

时间复杂度：

标程

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;
        if (l <= k && k <= r)
            k = l + r - k;
    }
    cout << k << '\n';
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    public static void main(String[] args) {
        int n = io.nextInt(), k = io.nextInt();
        int m = io.nextInt();
        for (int i = 0; i < m; i++) {
            int l = io.nextInt(), r = io.nextInt();
            if (k < l || k > r) continue;
            k = l + r - k;
        }
        io.println(k);

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

n, k = map(int, input().split())
m = int(input())
for _ in range(m):
    l, r = map(int, input().split())
    if l <= k <= r:
        k = l + r - k
print(k)