Subtask 1, 2: ~n, q \le 5000~.

Thực hiện y như những gì đề bài bảo trong ~O~ (~n \times q~).

Độ phức tạp: ~O~ (~n \times q~).

Subtask 3, 4: ~n, q \le 3 \times 10^5~.

Ta thấy: ~(i - l + 1)^2~ ~=~ ~i^2 + (2 \times l - 2) \times i + (l - 1)^2~.

Đặt ~A = -2 \times l - 2~, ~B = (l - 1)^2~.

Vậy, mỗi truy vấn, ta thấy ~A_i~ được tăng ~x \times (i^2 + A \times i + B)~ đơn vị.

Đến đây, ta có thể sử dụng cây phân đoạn + cập nhật lười để xử lý.

Độ phức tạp: ~O~ (~n \times log~ ~(n))~.

Subtask 5, 6: ~n, q \le 10^7~.

Thay vì sử dụng cây phân đoạn, ở đây, chúng ta sẽ sử dụng ba mảng hiệu tương ứng với ba tham số ở trên.

Độ phức tạp: ~O~ (~n + q~) (có hằng số).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e7 + 9;
const int mod = 1e9 + 7;

int n, q, a[3][N];

void add (int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub (int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    if (fopen ("input.txt", "r")){
        freopen ("input.txt", "r", stdin);
        freopen ("output.txt", "w", stdout);
    }
    cin >> n >> q;
    int l = 0;
    int r = 0;
    int x = 0;
    int l1, l2, r1, r2, capx;
    cin >> l1 >> l2 >> r1 >> r2 >> capx;
    while (q--){
        l = (l * l1 + l2) % n + 1;
        r = (r * r1 + r2) % n + 1;
        x = (x * l + r) % capx + 1;
        if (l > r) swap (l, r);
        int A = 0;
        sub (A, l << 1);
        add (A, 2);
        A *= x; A %= mod;
        int B = l - 1;
        B *= (l - 1); B *= x; B %= mod;
        add (a[2][l], x);
        add (a[1][l], A);
        add (a[0][l], B);
        sub (a[2][r + 1], x);
        sub (a[1][r + 1], A);
        sub (a[0][r + 1], B);
    }
    for (int i = 1; i <= n; i++){
        add (a[2][i], a[2][i - 1]);
        add (a[1][i], a[1][i - 1]);
        add (a[0][i], a[0][i - 1]);
    }
    int res = 0;
    int cont = 0;
    for (int i = 1; i <= n; i++){
        add (cont, (i << 1) - 1);
        int ans = cont * a[2][i] % mod;
        add (ans, i * a[1][i] % mod);
        add (ans, a[0][i]);
        res ^= ans;
    }
    cout << res;
}