Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <unordered_map>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <ctime>
- #include <random>
- #include <cassert>
- #include <memory.h>
- #include <chrono>
- #define pii pair<int, int>
- #define pb push_back
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define endl '\n'
- using namespace std;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- const long long INF = (long long)(1e9) + 7;
- const double EPS = 0.00000000001;
- const long long N = 1000001, R = 1LL << 19, ABC = 26, Logn = 20, MOD = 1e9;
- struct Node {
- int sum;
- Node *left = nullptr, *right = nullptr;
- Node(int a) : sum(a) {}
- Node() : sum(0) {}
- };
- Node* build(Node* root, int l, int r) {
- if (l == r) {
- root->sum = 0;
- return root;
- }
- root->left = new Node;
- root->right = new Node;
- int m = (l + r) / 2;
- root->left = build(root->left, l, m);
- root->right = build(root->right, m + 1, r);
- root->sum = root->left->sum + root->right->sum;
- return root;
- }
- Node* push(Node* root) {
- root->left = new Node(*root->left);
- root->right = new Node(*root->right);
- return root;
- }
- void update(Node* root, int nl, int nr, int idx) {
- if (idx == nl && idx == nr) {
- root->sum++;
- return;
- }
- root = push(root);
- int nm = (nl + nr) / 2;
- if (nm < idx)
- update(root->right, nm + 1, nr, idx);
- else
- update(root->left, nl, nm, idx);
- root->sum = root->left->sum + root->right->sum;
- }
- int get(Node* rootl, Node* rootr, int nl, int nr, int k) {
- if (nl == nr) {
- return nl;
- }
- int nm = (nl + nr) / 2;
- if (rootr->left->sum - rootl->left->sum >= k)
- return get(rootl->left, rootr->left, nl, nm, k);
- else
- return get(rootl->right, rootr->right, nm + 1, nr, k - (rootr->left->sum - rootl->left->sum));
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout.precision(17);
- srand(time(0));
- long long n, l, m;
- cin >> n;
- vector<long long> vc(n + 1);
- cin >> vc[1] >> l >> m;
- for (int i = 2; i <= n; i++) {
- vc[i] = (vc[i - 1] * l + m) % MOD;
- }
- vector<long long> a;
- a = vc;
- sort(all(a));
- a.erase(unique(all(a)), a.end());
- for (int i = 0; i <= n; i++) {
- vc[i] = (long long)(lower_bound(all(a), vc[i]) - a.begin());
- }
- int b;
- cin >> b;
- vector<Node*> roots(1, new Node);
- roots[0] = build(roots[0], 0, R - 1);
- for (int i = 1; i <= n; i++) {
- roots.push_back(new Node(*roots.back()));
- update(roots.back(), 0, R - 1, vc[i]);
- }
- long long ans = 0;
- for (int i = 0; i < b; i++) {
- int g;
- cin >> g;
- long long x1, lx, mx, y1, ly, my;
- cin >> x1 >> lx >> mx >> y1 >> ly >> my;
- long long k1, lk, mk;
- cin >> k1 >> lk >> mk;
- long long left = min(x1, y1), right = max(x1, y1);
- //cout << get(roots[left-1], roots[right], 0, R - 1, k1) << endl;
- ans += a[get(roots[left - 1], roots[right], 0, R - 1, k1)];
- long long kg = k1;
- for (int j = 1; j < g; j++) {
- long long xg = ((left - 1) * lx + mx) % n + 1;
- long long yg = ((right - 1) * ly + my) % n + 1;
- left = min(xg, yg);
- right = max(xg, yg);
- kg = (((kg - 1) * lk + mk) % (right - left + 1)) + 1;
- //cout << get(roots[left - 1], roots[right], 0, R - 1, kg) << endl;
- ans += a[get(roots[left - 1], roots[right], 0, R - 1, kg)];
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement