算法题（对数组进行左、右循环移位查询） _循环语句

【算法题（对数组进行左、右循环移位查询）】给定一个数组一种of?整数。有三种类型的命令：

1 x：向右循环将数组移动x次。如果数组为a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [n – 1], a [0], a [1] , …。, a [n – 2]。
2年：向左循环将数组y次。如果数组是a [0], a [1], ...., a [n – 1], 则在右移一圈后, 该数组将变为a [1], ...., a [n – 2], a [n – 1], a [0]。
3升打印子数组a [l…r](包括l和r)中的所有整数之和。

给定问查询, 任务是执行每个查询。
例子：

Input : n = 5, arr[] = { 1, 2, 3, 4, 5 }query 1 = { 1, 3 }query 2 = { 3, 0, 2 }query 3 = { 2, 1 }query 4 = { 3, 1, 4 }Output : 1211Initial array arr[] = { 1, 2, 3, 4, 5 }After query 1, arr[] = { 3, 4, 5, 1, 2 }.After query 2, sum from index 0 to index 2 is 12, so output 12.After query 3, arr[] = { 4, 5, 1, 2, 3 }.After query 4, sum from index 1 to index 4 is 11, so output 11.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法1 ：(强力)实现三个函数rotateR(arr, k), 将数组arr右旋转k次； rotateL(arr, k), 将数组arr旋转k次, sum(arr, l, r), 将输出数组arr的和从索引l到索引r。输入值1、2、3时, 调用相应的函数。
方法2 ：(有效方法)
最初, 没有轮换, 并且我们有很多查询要求范围od索引中存在整数的总和。
我们可以评估数组中所有元素的前缀和,
前缀和[i]
将表示直到ith索引的所有整数之和。
现在, 如果要查找两个索引即l和r之间的元素之和, 我们只需计算prefixsum [r]-prefixsum [l-1]就可以在恒定时间内对其进行计算。
现在进行轮换, 如果我们为每个查询轮换数组, 那将是非常低效的。
我们只需要跟踪净旋转。如果跟踪的数字为负, 则表示左旋已占域, 否则右旋已占主导地位。当我们跟踪净旋转时, 我们需要做
模式
。每旋转n次, 数组将返回其原始状态。
我们需要以这样一种方式进行观察：每次旋转数组时, 只有其索引在变化。
如果我们需要回答任何第三种查询, 则有l和r。我们需要找到原始顺序的l和r。我们可以通过将净旋转量添加到索引并取mod n来轻松找到它。
每个命令都可以在O(1)时间执行。
以下是此方法的C ++实现：

// CPP Program to solve queries on Left and Right // Circular shift on array #include < bits/stdc++.h> using namespace std; // Function to solve query of type 1 x. void querytype1( int * toRotate, int times, int n) { // Decreasing the absolute rotation (*toRotate) = ((*toRotate) - times) % n; }// Function to solve query of type 2 y. void querytype2( int * toRotate, int times, int n) { // Increasing the absolute rotation. (*toRotate) = ((*toRotate) + times) % n; }// Function to solve queries of type 3 l r. void querytype3( int toRotate, int l, int r, int preSum[], int n) { // Finding absolute l and r. l = (l + toRotate + n) % n; r = (r + toRotate + n) % n; // if l is before r. if (l < = r) cout < < (preSum[r + 1] - preSum[l]) < < endl; // If r is before l. else cout < < (preSum[n] + preSum[r + 1] - preSum[l]) < < endl; }// Wrapper Function solve all queries. void wrapper( int a[], int n) { int preSum[n + 1]; preSum[0] = 0; // Finding Prefix sum for ( int i = 1; i < = n; i++) preSum[i] = preSum[i - 1] + a[i - 1]; int toRotate = 0; // Solving each query querytype1(& toRotate, 3, n); querytype3(toRotate, 0, 2, preSum, n); querytype2(& toRotate, 1, n); querytype3(toRotate, 1, 4, preSum, n); }// Driver Program int main() { int a[] = { 1, 2, 3, 4, 5 }; int n = sizeof (a) / sizeof (a[0]); wrapper(a, n); return 0; }

输出如下：