Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- //#define int ll
- #define sz(x) int(x.size())
- typedef pair<int, int> pii;
- mt19937 rng(1000 - 7);
- const int C = 30;
- struct Hasher {
- int operator()(pair <int, int> x) const {
- static int kek = rng();
- return x.first ^ x.second ^ kek;
- }
- };
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- int q;
- cin >> q;
- vector <int> a;
- vector <tuple <int, int, int, int>> qq;
- while (q--) {
- char type;
- cin >> type;
- if (type == '+') {
- int x;
- cin >> x;
- a.push_back(x);
- }
- else {
- int l, r, x, k;
- cin >> l >> r >> x >> k;
- l--, r--;
- qq.push_back({ l, r, x, k });
- }
- }
- int n = a.size();
- //unordered_map <pair<int, int>, vector <int>, Hasher> suff;
- //unordered_map <pair<int, int>, vector <vector <int>>, Hasher> sum;
- map <pair<int, int>, vector <int>> suff;
- map <pair<int, int>, vector <vector <int>>> sum;
- for (int i = 0; i < n; i++) {
- int x = a[i];
- suff[make_pair(x, -1)].push_back(i);
- for (int j = 0; j < C; j++) {
- x = x & (~0 - (1 << j));
- suff[make_pair(x, j)].push_back(i);
- }
- }
- for (auto& [k, v] : suff) {
- sum[k] = vector <vector <int>> (v.size(), vector <int> (C));
- vector <vector <int>>& ref = sum[k];
- int x = a[v.front()];
- for (int j = 0; j < C; j++) {
- ref.front()[j] = x >> j & 1;
- }
- for (int i = 1; i < sz(v); i++) {
- x = a[v[i]];
- for (int j = 0; j < C; j++) {
- ref[i][j] = ref[i - 1][j] + (x >> j & 1);
- }
- }
- }
- auto get = [&] (pair <int, int> mask, int i, int j, int x) -> ll {
- if (j < 0) return 0LL;
- vector <vector <int>>& s = sum[mask];
- ll res = 0;
- for (int b = 0; b < C; b++) {
- if (x >> b & 1) {
- res += (1LL << b) * (j + 1 - s[j][b]);
- }
- else {
- res += (1LL << b) * s[j][b];
- }
- }
- if (i >= 0) {
- for (int b = 0; b < C; b++) {
- if (x >> b & 1) {
- res -= (1LL << b) * (i + 1 - s[i][b]);
- }
- else {
- res -= (1LL << b) * s[i][b];
- }
- }
- }
- return res;
- };
- auto ind = [&] (pair <int, int> mask, int l, int r) {
- vector <int>& ref = suff[mask];
- int i = lower_bound(ref.begin(), ref.end(), l) - ref.begin() - 1;
- int j = upper_bound(ref.begin(), ref.end(), r) - ref.begin() - 1;
- return make_pair(i, j);
- };
- for (auto [l, r, x, k] : qq) {
- int mask = 0;
- ll ans = 0;
- for (int i = C - 1; i >= 0; i--) {
- if (x >> i & 1) {
- auto [u, v] = ind({ mask, i - 1 }, l, r);
- int cnt = v - u;
- if (k > cnt) {
- ans += get({ mask, i - 1 }, u, v, x);
- mask |= (1 << i);
- k -= cnt;
- }
- }
- else {
- auto [u, v] = ind({ mask | (1 << i), i - 1 }, l, r);
- int cnt = v - u;
- if (k <= cnt) {
- mask |= (1 << i);
- }
- else {
- ans += get({ mask | (1 << i), i - 1 }, u, v, x);
- k -= cnt;
- }
- }
- }
- auto [u, v] = ind({ mask, -1 }, l, r);
- ans += get({ mask, -1 }, u, v, x);
- cout << ans << "\n";
- }
- /*
- for (auto [x, y] : suff) {
- cout << x << endl;
- for (int e : y) {
- cout << e << " ";
- }
- cout << endl;
- }
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement