如何优化我的代码以交换给定范围的索引的数组元素与相关元素？

Question

考虑具有N个元素的整数数组A,其中每个元素与另一个数组元素具有一对一的关系.

对于每个i,其中1≤i≤N,在元素i和元素N-i + 1之间存在1-> 1的关系

任务是对此阵列执行以下操作,如下所示:

给定两个整数(L,R),我们必须将该范围内的每个元素与其相关元素交换.(参见下面的示例说明)

样本输入

5
1 2 3 4 5
2
1 2
2 3

样本输出

5 2 3 4 1

解释对于第一个查询,我们将1与5和2交换为4.现在数组变为 - 5 4 3 2 1

同样现在,对于第二个查询,我们将4与2和3交换.所以最终的阵列将是5 2 3 4 1

我的程序是这样的:

import java.util.Scanner;
public class ProfessorAndOps {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner in=new Scanner(System.in);
    int n=in.nextInt();//length of array
    int a[]=new int[n];//array declaration
    for(int i=0;i<n;i++){
        //inputting array elements
        a[i]=in.nextInt();
    }
    int q=in.nextInt();//number of queries
    for(int i=0;i<q;i++){
        int l=in.nextInt();//left limit
        int r=in.nextInt();//right limit
        //swapping while iterating over the given range of array elements:
        for(int j=l-1;j<=r-1;j++){
            int temp=a[j];
            a[j]=a[n-j-1];
            a[n-j-1]=temp;
            }
        }
    //Printing the output array:
    for(int i=0;i<n;i++){
        if(i!=n-1){
        System.out.print(a[i]+" ");
        }
        else{
            System.out.println(a[i]);
        }

    }

}
}

我只能提出BruteForce解决方案.我很确定会有一些预处理步骤或一些带l和r变量的优化技术,无论我能想到什么,给我错误的答案.请帮我优化这段代码.具体来说,我需要将代码的时间复杂度从O(N + Q*(RL))减少到O(Q + N)

Answer 1

这是一个O(Q + N)时间、O(N)空间算法。L想象一下仅针对元素及其之上的相应交换计数的列表R（我们将使用负数作为计数R）。如果我们在遍历时维护一个虚拟堆栈怎么办？（我所说的“虚拟”是指它不是一个真正的堆栈，只是一个具有一定理论相似性的整数。）

例如：

1  2  3  4  5  6  7  8  9  10

O(Q) processing:

q [1,3]
1  9  8  7  5 ...  <- what would happen to the array
0  1  0 -1  0 <- counts (what we actually store)

q [2,4]
1  9  3  4  6 ...  <- what would happen to the array
0  1  1 -1 -1 <- counts (what we actually store)

O(N) traversal:

index 0 didn't move,                     no change, stack: 0
index 1 moved once,          odd count,  changed,   stack: 1
index 2 moved 2 (stack + 1), even count, no change, stack: 2
index 3 moved 2 (stack),     even count, no change, stack: 2 - 1
index 4 moved 1 (stack),     odd count,  changed,   stack: 1 - 1