抄作业

国庆之前在家继续寻找为数不多的多巴胺，没想到竟然连通了脑回路，快乐加倍。
Atcoder ABC Contest 425 C.Rotate and Sum Query
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 350 points

Problem Statement
You are given an integer sequence A=(A1,A2 ,…,AN) of length N.
Process Q queries in order. There are two types of queries, given in the following formats:
1 c: Perform the operation of moving the first element of A to the end c times.
2 l r: Output the value of i=l∑rAi.
Constraints
1≤N≤2×10**5
1≤Q≤2×10**5
1≤Ai ≤10**9
1≤c≤N
1≤l≤r≤N
At least one query of the second type exists.
All input values are integers.

昨晚遇到上面这题，发现可以抄下面这题的作业。425C和410C形成了梦幻联动。

Atcoder ABC Contest 410 C.Rotatable Array
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 300 points

Problem Statement
There is an integer sequence A of length N, initially Ai =i. Process a total of Q queries of the following types:
Type 1: Change Ap to x.
Type 2: Output Ap .
Type 3: Repeat the operation "move the first element of A to the end" k times.
Formally, replace A with (A2,A3,…,AN,A1) k times.
Constraints
All input values are integers.
1≤N≤10**6
1≤Q≤3×10**5
All queries satisfy the following constraints:
1≤p≤N
1≤x≤10**6
1≤k≤10**9

如下是425C的解

class Queuearray
  def initialize(num,n)
    @num = num
    @len = n
    @flag = 0
    @prefix = [0]
    for i in 0...n
      @prefix.push(@prefix[-1]+num[i])
    end
  end

  def puts_sum(l,r)
    l1 = (l-1-@flag) % @len
    r1 = (r-1-@flag) % @len
    if l1 <= r1
      puts @prefix[r1+1] - @prefix[l1]
    else
      puts @prefix[-1] - @prefix[l1] + @prefix[r1+1]
    end
  end

  def rotate_a(c)
    m = c % @len
    @flag -= m
  end
end

n,q = gets.split(" ").map(&:to_i)
num = gets.split(" ").map(&:to_i)
x = Queuearray.new(num,n)
for i in 0...q
  t = gets.split(" ")
  if t[0] == "1"
    x.rotate_a(t[1].to_i)
  else
    x.puts_sum(t[1].to_i,t[2].to_i)
  end
end

如下是410C的解

class Queuearray
  def initialize(n)
    @num = (1..n).to_a
    @len = n
    @flag = 0
  end
  
  def change(p,b)
    @num[(p-1-@flag) % @len] = b
  end
  
  def puts_a(p)
    puts @num[(p-1-@flag) % @len]
  end
  
  def rotate_a(k)
    m = k % @len
    @flag -= m
  end
end

n,q = gets.split(" ").map {|i| i.to_i}
abc = Queuearray.new(n)
for i in 0...q
  t = gets.chomp
  if t[0] == "1"
    t = t.split(" ").map {|i| i.to_i}
    abc.change(t[1],t[2])
  elsif t[0] == "2"
    t = t.split(" ").map {|i| i.to_i}
    abc.puts_a(t[1])
  else
    t = t.split(" ").map {|i| i.to_i}
    abc.rotate_a(t[1])
  end
end