Start from the identity permutation
$$A^{(0)}=(0,1,2,\dots,n-1).$$
Let the reversal endpoints be
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$
and for each step \(j=0,1,\dots,k-1\), reverse the closed interval
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right],$$
then update
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$
The target is the weighted sum
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
The challenge is that \(n\) is enormous, so the final permutation cannot be built element by element.
The implementation succeeds by tracking only the large monotone blocks created by the reversals, not the individual entries. Those blocks always remain simple arithmetic progressions with common difference \(+1\) or \(-1\).
The endpoints satisfy a Fibonacci-like recurrence modulo \(n\):
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
So the \(j\)-th reversal interval is known as soon as the \((j-1)\)-st step finishes. No table of all intervals is needed. Starting from \((1,1)\), the unreduced pairs are
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
which shows why consecutive Fibonacci numbers keep appearing behind the modular updates.
Call a block a run if it has the form
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
Initially the whole permutation is one increasing run:
$$B(0,1,n).$$
Now reverse any subarray of a sequence that is already a concatenation of such runs. Only the two boundary runs may need to be cut. Every interior run is reversed as a whole block, and the reverse of
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
is again an arithmetic run, namely
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x,$$
which simply flips the sign of the step. Therefore the representation is invariant under every operation.
Because only the two boundary runs can be split, a single reversal creates at most two new runs. If we start with one real run, then after \(k\) reversals the number of real runs is at most
$$2k+1.$$
This is the crucial compression: the permutation has length \(n\), but its description has size only \(O(k)\). A self-adjusting sequence tree can therefore manage the whole process efficiently.
Suppose a run occupies positions \(p,p+1,\dots,p+\delta\), where \(\delta=\ell-1\). Define the standard sums
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
If the run is increasing, its values are \(x,x+1,\dots,x+\delta\), so
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
If the run is decreasing, its values are \(x,x-1,\dots,x-\delta\), so
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
Thus the final weighted sum can be accumulated run by run, without expanding the full permutation.
Take \(n=5\). The intervals come from the endpoint sequence
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
Now apply the reversals:
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
Therefore
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all use the same fast idea: store the permutation as an ordered collection of maximal runs inside an implicit sequence tree. Each node records the first and last value of one run, a lazy reversal flag, and the total number of array positions represented by its subtree.
For every reversal, the implementation locates the two boundary positions by rank, splits a boundary run only if the cut lands inside it, isolates the middle interval, and marks that interval as reversed. Laziness is enough because reversing a concatenation of runs only requires two effects: reverse the order of the blocks and flip the direction inside each block.
After all \(k\) steps, an in-order traversal visits the runs from left to right. The current starting index of each run is known from subtree sizes, so the formulas from Step 4 give the contribution of the entire run modulo \(10^9\) in constant time.
The Python and Java versions delegate to the same optimized solver logic, so their mathematical behavior is identical to the C++ implementation.
Let \(m_j\) be the number of runs after \(j\) reversals. Since each reversal adds at most two runs, \(m_j=O(j)\), hence \(m_k=O(k)\). Each operation performs only a constant number of positional searches, local splits, and subtree reversals in an implicit splay tree, giving amortized \(O(\log m_j)\) time per step. Summing over all \(k\) steps yields
$$O(k\log k)$$
time. The final traversal is linear in the number of runs, so it costs \(O(k)\). The memory usage is also
$$O(k),$$
because only the compressed run representation is stored.
Ausgangspunkt ist die Identitätspermutation
$$A^{(0)}=(0,1,2,\dots,n-1).$$
Die Umkehrgrenzen seien
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$
und in jedem Schritt \(j=0,1,\dots,k-1\) wird das abgeschlossene Intervall
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right]$$
umgedreht. Danach werden die Grenzen durch
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n$$
fortgeschrieben. Gesucht ist
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
Da \(n\) extrem groß ist, darf die Endpermutation nicht explizit aufgebaut werden.
Der entscheidende Gedanke ist, die Permutation nicht elementweise zu speichern, sondern als Folge großer monotoner Blöcke. Jeder solche Block ist eine arithmetische Folge mit Differenz \(+1\) oder \(-1\).
Die Endpunkte erfüllen modulo \(n\) eine Fibonacci-artige Rekursion:
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
Damit ist das nächste Intervall sofort bekannt, sobald der vorige Schritt beendet ist. Eine vollständige Liste aller Intervalle muss also nicht gespeichert werden. Ohne die Modulo-Reduktion beginnt die Folge mit
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
also genau mit aufeinanderfolgenden Fibonacci-Zahlen.
Ein Lauf sei ein Block der Form
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
Anfangs ist die gesamte Permutation genau ein aufsteigender Lauf:
$$B(0,1,n).$$
Wird nun ein Teilarray einer bereits so dargestellten Sequenz umgedreht, dann müssen höchstens die beiden Randläufe aufgespalten werden. Jeder innere Lauf wird als ganzer Block umgekehrt, und die Umkehrung von
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
ist wieder ein arithmetischer Lauf, nämlich
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
Die Klasse der Darstellungen bleibt also unter jeder Operation erhalten.
Da nur die beiden Randläufe geschnitten werden können, erzeugt eine einzelne Umkehrung höchstens zwei neue Läufe. Ausgehend von einem realen Lauf gilt nach \(k\) Schritten daher
$$\text{Anzahl der Läufe}\le 2k+1.$$
Das ist die zentrale Kompression: Die Permutation besitzt Länge \(n\), ihre Beschreibung aber nur Größe \(O(k)\). Genau deshalb reicht ein selbstanpassender Sequenzbaum aus.
Liegt ein Lauf an den Positionen \(p,p+1,\dots,p+\delta\), wobei \(\delta=\ell-1\), dann benutzen wir
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
Für einen aufsteigenden Lauf mit Werten \(x,x+1,\dots,x+\delta\) gilt
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
Für einen absteigenden Lauf mit Werten \(x,x-1,\dots,x-\delta\) gilt
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
Damit lässt sich die Zielsumme laufweise berechnen, ohne je das vollständige Array zu materialisieren.
Für \(n=5\) liefern die Endpunkte die Folge
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
Die Umkehrungen ergeben
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
Also
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe schnelle Idee: Die Permutation wird als geordnete Menge maximaler Läufe in einem impliziten Sequenzbaum gehalten. Jeder Knoten speichert den ersten und letzten Wert seines Laufs, ein Lazy-Umkehrbit und die Gesamtzahl der durch den Teilbaum repräsentierten Positionen.
Bei jeder Umkehrung werden die beiden Randpositionen per Rangsuche gefunden. Falls ein Schnitt in der Mitte eines Laufs liegt, wird genau dieser Lauf geteilt. Danach wird der mittlere Teilbaum isoliert und nur logisch umgedreht. Das genügt, weil bei einer Umkehrung zweierlei passiert: Die Reihenfolge der Blöcke wird gespiegelt, und innerhalb jedes Blocks kippt die Richtung.
Nach allen \(k\) Schritten läuft eine In-Order-Traversierung von links nach rechts über die Läufe. Aus den Teilbaumgrößen ist die Startposition jedes Laufs bekannt, und die Formeln aus Schritt 4 liefern dessen gesamten Summenbeitrag modulo \(10^9\) in \(O(1)\).
Die Python- und Java-Versionen delegieren an dieselbe optimierte Kernlogik, daher ist ihr mathematisches Verhalten identisch mit der C++-Implementierung.
Sei \(m_j\) die Anzahl der Läufe nach \(j\) Umkehrungen. Wegen der höchstens zwei neuen Läufe pro Schritt gilt \(m_j=O(j)\), also insgesamt \(m_k=O(k)\). Jede Operation benötigt nur konstant viele Rangabfragen, lokale Splits und Teilbaum-Umkehrungen in einem impliziten Splay-Baum. Das ergibt amortisiert \(O(\log m_j)\) Zeit pro Schritt und insgesamt
$$O(k\log k)$$
Zeit. Die abschließende Traversierung kostet \(O(k)\), und der Speicherverbrauch ist ebenfalls
$$O(k),$$
weil nur die komprimierte Laufdarstellung gespeichert wird.
Başlangıç dizisi özdeşlik permütasyonudur:
$$A^{(0)}=(0,1,2,\dots,n-1).$$
Ters çevirme uçları
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n$$
olarak başlar. Her \(j=0,1,\dots,k-1\) adımında
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right]$$
kapalı aralığı ters çevrilir, sonra da
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n$$
güncellemesi yapılır. Aranan büyüklük
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}$$
değeridir. \(n\) çok büyük olduğu için son permütasyonu tek tek üretmek mümkün değildir.
Çözüm, diziyi eleman bazında değil, büyük monoton bloklar halinde temsil eder. Bu blokların her biri ortak farkı \(+1\) veya \(-1\) olan bir aritmetik dizidir.
Uç noktalar modulo \(n\) altında Fibonacci benzeri bir bağıntı izler:
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
Bu yüzden bir sonraki aralık, bir önceki adım biter bitmez hesaplanabilir. Tüm aralıkları önceden saklamaya gerek yoktur. Mod alma yapılmadan bakılırsa sıra
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
şeklindedir; yani ardışık Fibonacci sayıları doğal olarak ortaya çıkar.
Şu biçimde bir blok tanımlayalım:
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
Başlangıçta bütün permütasyon tek bir artan bloktur:
$$B(0,1,n).$$
Zaten böyle blokların birleşimi olarak yazılmış bir dizinin herhangi bir alt aralığını ters çevirdiğimizde, yalnızca iki sınır bloğunun bölünmesi gerekebilir. İçeride kalan her blok bütünüyle ters döner ve
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
bloğunun tersi yine aynı türden bir bloktur:
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
Dolayısıyla temsil sınıfı her adımda korunur.
Sadece iki sınır bloğu kesilebildiği için tek bir ters çevirme en fazla iki yeni blok oluşturur. Bir gerçek blokla başladığımıza göre \(k\) adım sonunda gerçek blok sayısı en fazla
$$2k+1$$
olur. Kritik sıkıştırma budur: permütasyonun uzunluğu \(n\) olsa da açıklaması yalnızca \(O(k)\) boyutundadır.
Bir blok \(p,p+1,\dots,p+\delta\) konumlarını kaplasın; burada \(\delta=\ell-1\). Standart toplamlar
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}$$
olsun. Blok artansa, değerleri \(x,x+1,\dots,x+\delta\) biçimindedir ve
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta)$$
olur. Blok azalıyorsa, değerler \(x,x-1,\dots,x-\delta\) olur ve
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta)$$
elde edilir. Böylece tam diziye açmadan ağırlıklı toplam blok blok biriktirilir.
\(n=5\) için uç noktalar
$$ (1,1)\to(2,3)\to(0,3)\to(3,1) $$
sırasını verir. Ters çevirmeleri uygularsak
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
Bu yüzden
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27$$
olur; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı hızlı fikri kullanır: permütasyon, örtük bir sıra ağacında tutulan maksimal blokların sıralı koleksiyonu olarak temsil edilir. Her düğüm bir bloğun ilk ve son değerini, tembel ters çevirme işaretini ve alt ağacın temsil ettiği toplam konum sayısını saklar.
Her ters çevirme için uygulama önce iki sınır konumu sıra numarasına göre bulur. Kesim noktası bir bloğun ortasına düşüyorsa yalnızca o blok bölünür. Sonra orta parça ayrıştırılır ve mantıksal olarak ters çevrilir. Bunun yeterli olmasının sebebi, ters çevirmenin yalnızca iki etkisinin olmasıdır: blokların sırası tersine döner ve her bloğun iç yönü değişir.
Tüm \(k\) adım bittikten sonra soldan sağa bir dolaşım yapılır. Alt ağaç boyutlarından her bloğun başlangıç indisi bilindiği için, Adım 4'teki formüller kullanılarak o bloğun toplam katkısı \(10^9\) modunda sabit zamanda eklenir.
Python ve Java sürümleri aynı optimize çekirdek çözüme delege olduğundan matematiksel davranışları C++ uygulamasıyla birebir aynıdır.
\(j\) ters çevirmeden sonraki blok sayısına \(m_j\) diyelim. Her adım en fazla iki yeni blok eklediği için \(m_j=O(j)\), dolayısıyla toplamda \(m_k=O(k)\) olur. Her işlem örtük splay ağacında sabit sayıda sıra araması, yerel bölme ve alt ağaç ters çevirme içerir; bunların amortize maliyeti adım başına \(O(\log m_j)\)'dir. Toplam süre
$$O(k\log k)$$
olur. Son dolaşım \(O(k)\), bellek kullanımı da
$$O(k)$$
seviyesindedir; çünkü yalnızca sıkıştırılmış blok gösterimi tutulur.
Se parte de la permutación identidad
$$A^{(0)}=(0,1,2,\dots,n-1).$$
Los extremos de inversión comienzan en
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$
y en cada paso \(j=0,1,\dots,k-1\) se invierte el intervalo cerrado
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right].$$
Después se actualizan mediante
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$
La cantidad buscada es
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
Como \(n\) es gigantesco, no se puede construir la permutación final posición por posición.
La clave es guardar solo los grandes bloques monótonos generados por las inversiones. Cada bloque sigue siendo una progresión aritmética de diferencia \(+1\) o \(-1\).
Los extremos obedecen una recurrencia tipo Fibonacci módulo \(n\):
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
Por tanto, el intervalo del paso siguiente se conoce inmediatamente al terminar el paso anterior. No hace falta almacenar toda la secuencia de intervalos. Sin reducir módulo \(n\), los pares iniciales son
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
y por eso aparecen números de Fibonacci consecutivos detrás de la dinámica.
Llamemos tramo a un bloque de la forma
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
Al inicio toda la permutación es un solo tramo creciente:
$$B(0,1,n).$$
Si invertimos un subarreglo de una secuencia ya escrita como concatenación de tramos, solo los dos tramos de borde pueden necesitar corte. Cada tramo interior se invierte completo, y la inversión de
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
vuelve a ser un tramo aritmético:
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
Así, la clase de representaciones se conserva tras cada operación.
Como solo pueden partirse los dos tramos fronterizos, una inversión crea a lo sumo dos tramos nuevos. Partiendo de un único tramo real, después de \(k\) inversiones hay como máximo
$$2k+1$$
tramos reales. Esa compresión es el punto central: la permutación tiene longitud \(n\), pero su descripción tiene tamaño \(O(k)\).
Supongamos que un tramo ocupa las posiciones \(p,p+1,\dots,p+\delta\), con \(\delta=\ell-1\). Definimos
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
Si el tramo es creciente, con valores \(x,x+1,\dots,x+\delta\), entonces
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
Si es decreciente, con valores \(x,x-1,\dots,x-\delta\), entonces
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
Por eso el valor final se acumula tramo por tramo, sin desplegar el arreglo completo.
Para \(n=5\), la sucesión de extremos es
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
Las inversiones producen
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
Luego
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
en acuerdo con el punto de control de la implementación.
Las implementaciones en C++, Python y Java siguen la misma idea rápida: guardar la permutación como una colección ordenada de tramos máximos dentro de un árbol implícito para secuencias. Cada nodo almacena el primer y el último valor del tramo, una marca perezosa de inversión y el número total de posiciones cubiertas por su subárbol.
En cada inversión, la implementación localiza los dos límites por rango. Si el corte cae dentro de un tramo, solo ese tramo se divide. Después aísla el subárbol central y lo marca como invertido. Esa pereza basta porque una inversión solo hace dos cosas: invierte el orden de los bloques y cambia la orientación interna de cada bloque.
Al terminar los \(k\) pasos, un recorrido en orden visita los tramos de izquierda a derecha. Con los tamaños de subárbol se conoce el índice inicial de cada tramo, y las fórmulas del Paso 4 permiten sumar su contribución completa módulo \(10^9\) en tiempo constante.
Las versiones de Python y Java delegan en la misma lógica optimizada del solucionador, así que su comportamiento matemático coincide exactamente con el de la implementación en C++.
Sea \(m_j\) el número de tramos después de \(j\) inversiones. Como cada paso añade a lo sumo dos tramos nuevos, \(m_j=O(j)\) y por tanto \(m_k=O(k)\). Cada operación realiza solo un número constante de búsquedas por rango, divisiones locales y reversiones de subárbol en un splay implícito, con costo amortizado \(O(\log m_j)\) por paso. En total el tiempo es
$$O(k\log k).$$
El recorrido final cuesta \(O(k)\), y la memoria también es
$$O(k),$$
porque solo se guarda la representación comprimida por tramos.
初始排列是恒等排列
$$A^{(0)}=(0,1,2,\dots,n-1).$$
反转端点从
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n$$
开始。对每个步骤 \(j=0,1,\dots,k-1\)，先把闭区间
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right]$$
反转，然后更新为
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$
要求计算
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
真正困难的地方在于 \(n\) 非常大，因此绝不能把最终排列完整展开。
核心思想不是逐个元素维护排列，而是只维护每次反转之后留下来的大块单调区间。每个区间始终都是公差为 \(+1\) 或 \(-1\) 的等差数列。
端点在模 \(n\) 意义下满足一个 Fibonacci 型递推：
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
因此只要完成当前一步，就能立即得到下一步的反转区间，不需要预先存储所有区间。若暂时忽略取模，前几个端点对是
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
这正说明了为什么连续的 Fibonacci 数会自然出现在这个过程里。
把下面这种块称为一个“段”：
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
初始时整个排列就是唯一的一段递增段：
$$B(0,1,n).$$
如果当前序列已经写成若干段的拼接，再去反转其中一个子区间，那么只有左右两个边界段可能需要被切开。处在中间的整段会整体翻转，而
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
翻转之后仍然是同类对象：
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
也就是说，段的方向变了，但“等差且相邻”的结构完全保留，所以这种表示在每一步之后都成立。
由于只有两个边界段可能被切开，一次反转最多新增两个段。开始时真实数据只有一段，所以做完 \(k\) 次操作之后，真实段数至多是
$$2k+1.$$
这正是压缩的关键。原排列长度是 \(n\)，但它的描述规模只剩下 \(O(k)\)。只要维护这些段，而不是维护全部 \(n\) 个元素，问题就变得可处理。
设某一段覆盖的位置是 \(p,p+1,\dots,p+\delta\)，其中 \(\delta=\ell-1\)。定义
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
若该段递增，值为 \(x,x+1,\dots,x+\delta\)，则
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
若该段递减，值为 \(x,x-1,\dots,x-\delta\)，则
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
因此最终要求的 \(\sum iA_i\) 可以在最后一次遍历中按段累加，而不需要把整段展开成单个元素。
取 \(n=5\)。端点序列为
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
对应的反转过程是
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
所以
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
与实现中的校验值完全一致。这个例子也清楚展示了为什么“按段维护”是自然的：序列虽然变化了，但始终可以拆成少量递增段和递减段。
C++、Python 和 Java 三个实现都遵循同一个快速思路：把当前排列表示成一棵按位置排序的隐式序列树，树中的每个节点对应一个最大等差段。节点记录该段的首值、末值、懒惰反转标记，以及整棵子树覆盖的总位置数。
每次反转时，程序先按秩找到左右边界。如果切点落在某个段的内部，就只把那一个段拆成两段。随后把中间部分单独隔离出来，并给它打上“反转”标记。这样做已经足够，因为区间反转对段结构只造成两种影响：段与段之间的顺序颠倒，每一段内部的方向也同时翻转。
所有操作完成后，程序按中序顺序从左到右遍历这些段。借助子树大小可以知道每一段在最终排列中的起始位置，再用步骤 4 的闭式公式在 \(O(1)\) 时间内算出该段对答案的整段贡献，并在模 \(10^9\) 下累加。
Python 和 Java 版本都委托给同一套优化后的求解核心，因此它们的数学行为与 C++ 实现完全一致。
设做完 \(j\) 次反转后共有 \(m_j\) 个段。由于每次操作最多新增两个段，所以 \(m_j=O(j)\)，从而最终 \(m_k=O(k)\)。每一步只需要常数次按秩查找、局部分裂和子树反转，而这些在隐式 splay 树中的摊还代价是 \(O(\log m_j)\)。把所有步骤加总，时间复杂度为
$$O(k\log k).$$
最后一次按段遍历是 \(O(k)\)，空间复杂度也是
$$O(k),$$
因为程序只存储压缩后的段表示，而不是长度为 \(n\) 的完整数组。
Начинаем с тождественной перестановки
$$A^{(0)}=(0,1,2,\dots,n-1).$$
Границы разворота задаются как
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n,$$
и на каждом шаге \(j=0,1,\dots,k-1\) разворачивается замкнутый отрезок
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right].$$
После этого выполняется обновление
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$
Нужно вычислить
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
Главная трудность в том, что \(n\) огромно, поэтому хранить итоговую перестановку поэлементно нельзя.
Идея состоит в том, чтобы хранить не отдельные элементы, а большие монотонные блоки, возникающие после разворотов. Каждый такой блок остается арифметической прогрессией с разностью \(+1\) или \(-1\).
Концы интервала удовлетворяют рекуррентному соотношению типа Фибоначчи по модулю \(n\):
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
Значит, очередной интервал известен сразу после завершения предыдущего шага. Никакой массив всех интервалов не нужен. Если временно забыть о модуле, получаем пары
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
то есть подряд идущие числа Фибоначчи.
Назовем блоком последовательность вида
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
В начале вся перестановка состоит из одного возрастающего блока:
$$B(0,1,n).$$
Если перевернуть подотрезок последовательности, которая уже записана как конкатенация таких блоков, то разрезать, возможно, придется только два граничных блока. Каждый внутренний блок переворачивается целиком, а разворот
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
снова дает арифметический блок:
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
Следовательно, нужное представление сохраняется после каждой операции.
Поскольку разрезаться могут только два крайних блока, за один разворот появляется не более двух новых блоков. Если начать с одного реального блока, то после \(k\) операций число реальных блоков не превосходит
$$2k+1.$$
В этом и состоит компрессия: длина перестановки равна \(n\), но ее описание имеет размер всего \(O(k)\).
Пусть блок занимает позиции \(p,p+1,\dots,p+\delta\), где \(\delta=\ell-1\). Обозначим
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
Если блок возрастающий и его значения равны \(x,x+1,\dots,x+\delta\), то
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
Если блок убывающий и имеет вид \(x,x-1,\dots,x-\delta\), то
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
Поэтому итоговую сумму можно считать по блокам, совсем не разворачивая массив длины \(n\).
Возьмем \(n=5\). Последовательность концов интервала равна
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
Соответствующие развороты дают
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
Следовательно,
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java опираются на одну и ту же быструю идею: хранить текущую перестановку как упорядоченный набор максимальных блоков внутри неявного дерева последовательности. В каждом узле записаны первый и последний элемент блока, ленивый флаг разворота и общее число позиций, покрываемых поддеревом.
Для каждого разворота программа сначала находит обе границы по рангу. Если точка разреза попадает внутрь блока, делится только этот блок. Затем средняя часть выделяется в отдельное поддерево и помечается как перевернутая. Ленивой метки достаточно, потому что разворот меняет лишь две вещи: порядок блоков в поддереве и направление внутри каждого блока.
После выполнения всех \(k\) шагов inorder-обход перечисляет блоки слева направо. По размерам поддеревьев известен стартовый индекс каждого блока, а формулы из шага 4 дают вклад всего блока в ответ по модулю \(10^9\) за \(O(1)\).
Версии на Python и Java делегируют той же оптимизированной вычислительной логике, поэтому математически полностью совпадают с реализацией на C++.
Пусть \(m_j\) обозначает число блоков после \(j\) разворотов. Так как каждый шаг добавляет не более двух новых блоков, имеем \(m_j=O(j)\), а значит и \(m_k=O(k)\). Каждый шаг делает лишь константное число поисков по рангу, локальных разбиений и разворотов поддерева в неявном splay-дереве, что дает амортизированную стоимость \(O(\log m_j)\) на шаг. Итого время работы равно
$$O(k\log k).$$
Финальный обход стоит \(O(k)\), а память также равна
$$O(k),$$
поскольку хранится только сжатое представление блоков.
نبدأ من التبديل المحايد
$$A^{(0)}=(0,1,2,\dots,n-1).$$
وتبدأ حدود العكس من
$$a_0\equiv 1 \pmod n,\qquad b_0\equiv 1 \pmod n.$$
في كل خطوة \(j=0,1,\dots,k-1\) نعكس الفترة المغلقة
$$\left[\min(a_j,b_j),\max(a_j,b_j)\right],$$
ثم نحدّث الحدود وفق
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv b_j+a_{j+1} \pmod n.$$
القيمة المطلوبة هي
$$R(n,k)=\sum_{i=0}^{n-1} i\,A_i^{(k)} \pmod{10^9}.$$
الصعوبة الأساسية أن \(n\) ضخم جدًا، لذلك لا يمكن بناء التبديل النهائي عنصرًا عنصرًا.
الفكرة الحاسمة هي تتبع الكتل الأحادية الكبيرة الناتجة عن عمليات العكس بدل تتبع كل عنصر على حدة. كل كتلة تبقى متتالية حسابية فرقها \(+1\) أو \(-1\).
نهايتا الفترة تتبعان علاقة شبيهة بفيبوناتشي بترديد \(n\):
$$a_{j+1}\equiv a_j+b_j \pmod n,\qquad b_{j+1}\equiv a_j+2b_j \pmod n.$$
لهذا يمكن معرفة فترة الخطوة التالية فور انتهاء الخطوة الحالية، من دون تخزين جميع الفترات مسبقًا. وإذا تجاهلنا الترديد للحظات نحصل على الأزواج
$$ (1,1),\ (2,3),\ (5,8),\ (13,21),\dots $$
وهذا يوضح ظهور أعداد فيبوناتشي المتتالية في خلفية التحديثات.
لنسمّ مقطعًا أي كتلة من الشكل
$$B(x,\sigma,\ell)=\bigl(x,\ x+\sigma,\ x+2\sigma,\ \dots,\ x+(\ell-1)\sigma\bigr),\qquad \sigma\in\{1,-1\}.$$
في البداية يكون التبديل كله مقطعًا تصاعديًا واحدًا:
$$B(0,1,n).$$
إذا عكسنا جزءًا من تسلسل مكتوب أصلًا كمجموعة من هذه المقاطع، فإن المقطعين الحدّيين فقط قد يحتاجان إلى انقسام. أما المقاطع الداخلية فتنقلب كاملة، وعكس
$$x,\ x+\sigma,\ \dots,\ x+(\ell-1)\sigma$$
يعطي من جديد مقطعًا حسابيًا من النوع نفسه:
$$x+(\ell-1)\sigma,\ x+(\ell-2)\sigma,\ \dots,\ x.$$
إذن هذا التمثيل يبقى صحيحًا بعد كل عملية.
بما أن الانقسام قد يحدث فقط في المقطعين الحدّيين، فإن كل عملية عكس تنشئ في أسوأ الأحوال مقطعين جديدين فقط. وإذا بدأنا بمقطع حقيقي واحد، فإن عدد المقاطع الحقيقية بعد \(k\) عمليات لا يتجاوز
$$2k+1.$$
هذا هو جوهر الضغط: طول التبديل يساوي \(n\)، لكن وصفه المضغوط حجمه \(O(k)\) فقط.
افترض أن مقطعًا يشغل المواقع \(p,p+1,\dots,p+\delta\)، حيث \(\delta=\ell-1\). نستخدم المجموعين القياسيين
$$S_1(\delta)=\sum_{u=0}^{\delta} u=\frac{\delta(\delta+1)}{2},\qquad S_2(\delta)=\sum_{u=0}^{\delta} u^2=\frac{\delta(\delta+1)(2\delta+1)}{6}.$$
إذا كان المقطع تصاعديًا وقيمه \(x,x+1,\dots,x+\delta\)، فإن
$$\sum_{u=0}^{\delta} (p+u)(x+u)=(\delta+1)px+(p+x)S_1(\delta)+S_2(\delta).$$
أما إذا كان تنازليًا وقيمه \(x,x-1,\dots,x-\delta\)، فإن
$$\sum_{u=0}^{\delta} (p+u)(x-u)=(\delta+1)px+(x-p)S_1(\delta)-S_2(\delta).$$
وهكذا يمكن حساب \(\sum iA_i\) في النهاية مقطعًا مقطعًا من دون توسيع التبديل كاملًا.
خذ \(n=5\). متتالية الحدود هي
$$ (1,1)\to(2,3)\to(0,3)\to(3,1). $$
وبتطبيق عمليات العكس نحصل على
$$\begin{aligned} A^{(0)}&=(0,1,2,3,4),\\ [1,1]&:\ (0,1,2,3,4),\\ [2,3]&:\ (0,1,3,2,4),\\ [0,3]&:\ (2,3,1,0,4),\\ [1,3]&:\ (2,0,1,3,4). \end{aligned}$$
لذلك
$$R(5,4)=0\cdot2+1\cdot0+2\cdot1+3\cdot3+4\cdot4=27,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تعتمد تطبيقات C++ وPython وJava على الفكرة السريعة نفسها: تمثيل التبديل الحالي على شكل مجموعة مرتبة من المقاطع القصوى داخل شجرة تسلسلية ضمنية. كل عقدة تخزن أول قيمة في المقطع وآخر قيمة فيه، وعلامة عكس كسولة، وعدد المواقع الكلي الذي يغطيه ذلك الجزء من الشجرة.
عند كل عملية عكس، تبحث الشيفرة عن الحدين بحسب الرتبة. وإذا وقع القطع داخل مقطع ما، ينقسم ذلك المقطع وحده. ثم يُعزل الجزء الأوسط ويُعلَّم بعلامة العكس. يكفي هذا التأجيل لأن عكس فترة لا يسبب إلا تأثيرين: قلب ترتيب المقاطع، وقلب اتجاه كل مقطع داخليًا.
بعد انتهاء جميع الخطوات \(k\)، يُجرى مرور ترتيبي من اليسار إلى اليمين على المقاطع. ومن أحجام الأجزاء الفرعية يُعرف موضع البداية لكل مقطع، ثم تُستخدم صيغ الخطوة 4 لحساب مساهمة المقطع كاملةً بتكلفة ثابتة وتراكمها بترديد \(10^9\).
إصدارا Python وJava يفوضان إلى المنطق المحسن نفسه، لذلك فالسلوك الرياضي فيهما مطابق تمامًا لسلوك تنفيذ C++.
ليكن \(m_j\) عدد المقاطع بعد \(j\) عمليات عكس. بما أن كل خطوة تضيف في أقصى حد مقطعين جديدين، فإن \(m_j=O(j)\)، وبالتالي \(m_k=O(k)\). وكل خطوة تحتاج إلى عدد ثابت من عمليات البحث بحسب الرتبة، والانقسام المحلي، وعكس الأجزاء الفرعية داخل شجرة splay ضمنية، وهذا يعطي كلفة مضمرة مقدارها \(O(\log m_j)\) لكل خطوة. وعليه يكون الزمن الكلي
$$O(k\log k).$$
أما المرور النهائي فتكلفته \(O(k)\)، واستهلاك الذاكرة أيضًا
$$O(k),$$
لأن المخزن هو التمثيل المضغوط للمقاطع فقط.