sliding_window_minimum_3221.cpp (640B)
1 #include <algorithm> 2 #include <deque> 3 #include <iostream> 4 #include <vector> 5 6 int main() { 7 long long n, k, x, a, b, c; 8 std::cin >> n >> k >> x >> a >> b >> c; 9 10 std::vector<long long> v(k); 11 std::deque<long long> q; 12 for (long long i = 0; i < k; i++) { 13 v[i] = x; 14 while (!q.empty() && q.back() >= x) q.pop_back(); 15 q.push_back(x); 16 x = (a*x + b) % c; 17 } 18 19 long long sol = q.front(); 20 for (long long i = 0; i < n-k; i++) { 21 if (q.front() == v[i%k]) q.pop_front(); 22 v[i%k] = (a*v[(i-1+k)%k] + b) % c; 23 while (!q.empty() && q.back() >= v[i%k]) q.pop_back(); 24 q.push_back(v[i%k]); 25 sol ^= q.front(); 26 } 27 28 std::cout << sol << "\n"; 29 }