QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#349795#8335. Fast Hash Transformucup-team2894#Compile Error//C++2018.9kb2024-03-10 05:36:062024-03-10 05:36:06

Judging History

你现在查看的是最新测评结果

  • [2024-03-10 05:36:06]
  • 评测
  • [2024-03-10 05:36:06]
  • 提交

answer

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("strict-overflow")
#pragma GCC target("popcnt,lzcnt,abm,bmi,bmi2")
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
#define popcnt(x) __builtin_popcountll(x)

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
mt19937 rndll(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
mt19937 rndll(223);
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 2e4 + 100, inf = 1e9 + 100;


namespace segtree {

// This implementation is disgusting, but it seems to work and do it faster than previous version.

    template<typename Item>
    Item tree_merge(const Item& a, const Item& b) {
        Item i;
        i.update(a, b);
        return i;
    }

    template<typename Item, bool lazy>
    struct Pusher {};

    template<typename Item>
    struct Pusher<Item, false> {
        void push(const vector<Item>&, int, int, int) {}
        Item ask_on_segment(const vector<Item>& tree, int n, int l, int r) {
            l |= n;
            r |= n;
            Item resl, resr;
            while (l <= r) {
                if (l & 1) {
                    resl = tree_merge(resl, tree[l]);
                    ++l;
                }
                if (!(r & 1)) {
                    resr = tree_merge(tree[r], resr);
                    --r;
                }
                l >>= 1;
                r >>= 1;
            }
            return tree_merge(resl, resr);
        }
        void push_point(const vector<Item>&, int, int) {}

        template<typename P>
        int lower_bound(const vector<Item>& tree, int n, int l, P p) {
            Item cur;
            if (p(cur)) return l - 1;
            l |= n;
            int r = n | (n - 1);
            // carefully go up
            while (true) {
                if (p(tree_merge(cur, tree[l]))) {
                    break;
                }
                if (l == r) return n;
                if (l & 1) {
                    cur = tree_merge(cur, tree[l]);
                    ++l;
                }
                l >>= 1;
                r >>= 1;
            }

            // usual descent from l
            while (l < n) {
                if (p(tree_merge(cur, tree[l * 2]))) {
                    l = l * 2;
                } else {
                    cur = tree_merge(cur, tree[l * 2]);
                    l = l * 2 + 1;
                }
            }
            return (l ^ n);
        }

        template<typename P>
        int lower_bound_rev(const vector<Item>& tree, int n, int r, P p) {
            Item cur;
            if (p(cur)) return r + 1;
            r |= n;
            int l = n;
            // carefully go up
            while (true) {
                if (p(tree_merge(tree[r], cur))) {
                    break;
                }
                if (l == r) return -1;
                if (!(r & 1)) {
                    cur = tree_merge(tree[r], cur);
                    --r;
                }
                l >>= 1;
                r >>= 1;
            }

            // usual descent from r
            while (r < n) {
                if (p(tree_merge(tree[r * 2 + 1], cur))) {
                    r = r * 2 + 1;
                } else {
                    cur = tree_merge(tree[r * 2 + 1], cur);
                    r = r * 2;
                }
            }
            return (r ^ n);
        }
    };

    template<typename Item>
    struct Pusher<Item, true> {
        void push(vector<Item>& tree, int ind, int l, int r) {
            tree[ind].push(tree[ind * 2], tree[ind * 2 + 1], l, r);
        }

        Item ask_on_segment(vector<Item>& tree, int n, int l, int r) {
            int vl = 0, vr = n - 1;
            int i = 1;
            Item result;
            while (vl != vr) {
                int m = (vl + vr) / 2;
                if (l > m) {
                    push(tree, i, vl, vr);
                    i = i * 2 + 1;
                    vl = m + 1;
                } else if (r <= m) {
                    push(tree, i, vl, vr);
                    i = i * 2;
                    vr = m;
                } else {
                    break;
                }
            }
            if (l == vl && r == vr) {
                return tree[i];
            }
            push(tree, i, vl, vr);
            // left
            {
                int ind = i * 2;
                int L = vl, R = (vl + vr) / 2;
                while (l != L) {
                    int m = (L + R) / 2;
                    push(tree, ind, L, R);
                    if (l <= m) {
                        result = tree_merge(tree[ind * 2 + 1], result);
                        ind *= 2;
                        R = m;
                    } else {
                        ind = ind * 2 + 1;
                        L = m + 1;
                    }
                }
                result = tree_merge(tree[ind], result);
            }
            // right
            {
                int ind = i * 2 + 1;
                int L = (vl + vr) / 2 + 1, R = vr;
                while (r != R) {
                    int m = (L + R) / 2;
                    push(tree, ind, L, R);
                    if (r > m) {
                        result = tree_merge(result, tree[ind * 2]);
                        ind = ind * 2 + 1;
                        L = m + 1;
                    } else {
                        ind = ind * 2;
                        R = m;
                    }
                }
                result = tree_merge(result, tree[ind]);
            }
            return result;
        }

        void push_point(vector<Item>& tree, int n, int ind) {
            int l = 0, r = n - 1;
            int i = 1;
            while (l != r) {
                push(tree, i, l, r);
                int m = (l + r) / 2;
                if (ind <= m) {
                    r = m;
                    i *= 2;
                } else {
                    l = m + 1;
                    i = i * 2 + 1;
                }
            }
        }

        template<typename P>
        pair<int, Item> _lower_bound(vector<Item>& tree, int l, P p, Item cur, int i, int vl, int vr) {
            if (vl == vr) {
                if (p(tree_merge(cur, tree[i]))) {
                    return {vl, tree[i]};
                } else {
                    return {vl + 1, tree[i]};
                }
            }

            push(tree, i, vl, vr);
            int m = (vl + vr) / 2;
            if (l > m) {
                return _lower_bound(tree, l, p, cur, i * 2 + 1, m + 1, vr);
            } else if (l <= vl) {
                if (!p(tree_merge(cur, tree[i]))) {
                    return {vr + 1, tree_merge(cur, tree[i])};
                }
                if (p(tree_merge(cur, tree[i * 2]))) {
                    return _lower_bound(tree, l, p, cur, i * 2, vl, m);
                } else {
                    return _lower_bound(tree, l, p, tree_merge(cur, tree[i * 2]), i * 2 + 1, m + 1, vr);
                }
            } else {
                auto [ind, it] = _lower_bound(tree, l, p, cur, i * 2, vl, m);
                if (ind <= m) return {ind, it};
                return _lower_bound(tree, l, p, it, i * 2 + 1, m + 1, vr);
            }
        }

        template<typename P>
        int lower_bound(vector<Item>& tree, int n, int l, P p) {
            Item cur;
            if (p(cur)) return l - 1;
            return _lower_bound(tree, l, p, cur, 1, 0, n - 1).first;
        }

        template<typename P>
        pair<int, Item> _lower_bound_rev(vector<Item>& tree, int r, P p, Item cur, int i, int vl, int vr) {
            if (vl == vr) {
                if (p(tree_merge(tree[i], cur))) {
                    return {vl, tree[i]};
                } else {
                    return {vl - 1, tree[i]};
                }
            }

            push(tree, i, vl, vr);
            int m = (vl + vr) / 2;
            if (r <= m) {
                return _lower_bound_rev(tree, r, p, cur, i * 2, vl, m);
            } else if (r >= vr) {
                if (!p(tree_merge(tree[i], cur))) {
                    return {vl - 1, tree_merge(cur, tree[i])};
                }
                if (p(tree_merge(tree[i * 2 + 1], cur))) {
                    return _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
                } else {
                    return _lower_bound_rev(tree, r, p, tree_merge(tree[i * 2 + 1], cur), i * 2, vl, m);
                }
            } else {
                auto [ind, it] = _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
                if (ind > m) return {ind, it};
                return _lower_bound_rev(tree, r, p, it, i * 2, vl, m);
            }
        }

        template<typename P>
        int lower_bound_rev(vector<Item>& tree, int n, int r, P p) {
            Item cur;
            if (p(cur)) return r + 1;
            return _lower_bound_rev(tree, r, p, cur, 1, 0, n - 1).first;
        }
    };

    template<typename Item, bool lazy = false>
    struct Segtree {
        vector<Item> tree;
        Pusher<Item, lazy> pusher;
        int n;
        int n0;

        Segtree(int n = 0) {
            build(n);
        }

        template<typename U>
        Segtree(const vector<U>& v) {
            build(v);
        }

        void build(int n) {
            this->n0 = n;
            while (n & (n - 1)) ++n;
            this->n = n;
            tree.assign(n * 2, {});
        }

        template<typename U>
        void build(const vector<U>& v) {
            build(v.size());
            for (int i = 0; i < v.size(); ++i) {
                tree[n | i].init(v[i], i);
            }
            build();
        }

        void build() {
            for (int i = n - 1; i >= 1; --i) {
                tree[i].update(tree[i * 2], tree[i * 2 + 1]);
            }
        }

        void push(int ind, int l, int r) {
            pusher.push(tree, ind, l, r);
        }

        template<typename T>
        void set(int ind, const T& t) {
            pusher.push_point(tree, n, ind);
            ind |= n;
            tree[ind].init(t, ind ^ n);
            ind >>= 1;
            while (ind) {
                tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                ind >>= 1;
            }
        }

        template<typename T>
        void update(int ind, const T& t) {
            pusher.push_point(tree, n, ind);
            ind |= n;
            tree[ind].update(t, ind ^ n);
            ind >>= 1;
            while (ind) {
                tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                ind >>= 1;
            }
        }

        Item& ith(int ind) {
            static_assert(!lazy, "don't use this method with lazy propagation, unless you're sure you need it");
            return tree[ind | n];
        }

        const Item& root() const {
            return tree[1];
        }

        Item ask(int l, int r) {
            l = max(l, 0);
            r = min(r, n - 1);
            if (l > r) return {};
            return pusher.ask_on_segment(tree, n, l, r);
        }

        template<typename T>
        void modify(int l, int r, const T& t) {
            static_assert(lazy, "lazy must be set to true to use this function");
            l = max(l, 0);
            r = min(r, n - 1);
            if (l > r) return;
            int vl = 0, vr = n - 1;
            int i = 1;
            while (vl != vr) {
                int m = (vl + vr) / 2;
                if (l > m) {
                    push(i, vl, vr);
                    i = i * 2 + 1;
                    vl = m + 1;
                } else if (r <= m) {
                    push(i, vl, vr);
                    i = i * 2;
                    vr = m;
                } else {
                    break;
                }
            }
            if (l == vl && r == vr) {
                tree[i].modify(t, l, r);
            } else {
                push(i, vl, vr);
                // left
                {
                    int ind = i * 2;
                    int L = vl, R = (vl + vr) / 2;
                    while (l != L) {
                        int m = (L + R) / 2;
                        push(ind, L, R);
                        if (l <= m) {
                            tree[ind * 2 + 1].modify(t, m + 1, R);
                            ind *= 2;
                            R = m;
                        } else {
                            ind = ind * 2 + 1;
                            L = m + 1;
                        }
                    }
                    tree[ind].modify(t, L, R);
                    ind >>= 1;
                    while (ind != i) {
                        tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                        ind >>= 1;
                    }
                }
                // right
                {
                    int ind = i * 2 + 1;
                    int L = (vl + vr) / 2 + 1, R = vr;
                    while (r != R) {
                        int m = (L + R) / 2;
                        push(ind, L, R);
                        if (r > m) {
                            tree[ind * 2].modify(t, L, m);
                            ind = ind * 2 + 1;
                            L = m + 1;
                        } else {
                            ind = ind * 2;
                            R = m;
                        }
                    }
                    tree[ind].modify(t, L, R);
                    ind >>= 1;
                    while (ind != i) {
                        tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
                        ind >>= 1;
                    }
                }
                tree[i].update(tree[i * 2], tree[i * 2 + 1]);
            }
            i >>= 1;
            while (i) {
                tree[i].update(tree[i * 2], tree[i * 2 + 1]);
                i >>= 1;
            }
        }

        // first index r such that p(tree.ask(l, r)) == true
        // if p() is true for empty item, return l-1
        // if p() is never true, returns n
        template<typename P>
        int lower_bound(int l, P p) {
            l = max(l, 0);
            if (l >= n0) return n0;
            return min(n0, pusher.lower_bound(tree, n, l, p));
        }

        // similarly to lower_bound, returns first (largest) l such that p(tree.ask(l, r)) == true
        template<typename P>
        int lower_bound_rev(int r, P p) {
            r = min(r, n0 - 1);
            if (r < 0) return -1;
            return pusher.lower_bound_rev(tree, n, r, p);
        }
    };

}
using segtree::Segtree;

#define uint oleg
using uint = uint64_t;

using Mat = array<uint, 64>;

const uint one = 1;

inline bool mult(uint x, uint y) {
    return popcnt(x & y) & 1;
}

struct Li {
    Mat a{};
    uint b{};

    void upd(int i, int j, bool w) {
        if (w)
            a[j] ^= (one << i);
    }

    uint apply(uint x) const {
        uint w = 0;
        for (int i = 0; i < 64; i++)
            if (mult(x, a[i]))
                w ^= (one << i);
        return w ^ b;
    }
};

Li def() {
    Li q{};
    for (int i = 0; i < 64; i++)
        q.upd(i, i, 1);
    return q;
}

Mat c{};

Li comb(Li const &x, Li const &y) {
    c = {};
    Li q{};
    for (int i = 0; i < 64; i++)
        for (int j = 0; j < 64; j++)
            if (x.a[j] & (one << i))
                c[i] ^= (one << j);
    for (int i = 0; i < 64; i++)
        for (int j = 0; j < 64; j++)
            q.upd(i, j, mult(c[i], y.a[j]));
    q.b = y.apply(x.b);
    return q;
}

Li a[maxn];

#define cin if(1)cin

Li read_hash() {
    int m = 64;
    cin >> m;
    Li q;
    for (int it = 0; it < m; it++) {
        int s = it, o = rnd() & 1;
        uint A = rndll();
        cin >> s >> o >> A;
        if (o == 0) {
            // or
            for (int i = 0; i < 64; i++)
                if (A & (one << i)) {
                    q.b ^= (one << i);
                }
            A = ~A;
        }
        {
            // and
            for (int i = 0; i < 64; i++) {
                int pe = (i + s) % 64;
                q.upd(i, pe, (A >> pe) & 1);
            }
        }
    }
    uint b;
    cin >> b;
    q.b ^= b;
//    for (int j = 0; j < 64; j++)
//        cerr << q.a[j] << '\n';
//    cerr << q.b << '\n';
//    cerr << "-----------------\n";
    return q;
}

struct Item {
    Li w = def();
    template<typename T>
    void init(const T& t, int ind) {
        w = t;
    }

    void update(const Item& a, const Item& b) {
        w = comb(a.w, b.w);
    }

    //// similar to init, but more convenient for doing a[i] += x, implement only if needed
    // template<typename T>
    // void update(const T& t, int ind) {}

    //// apply here, save for children
    // template<typename T>
    // void modify(const T& m, int l, int r) {}

    // void push(Item& a, Item& b, int l, int r) {
    //     int m = (l + r) / 2;
    //     a.modify(mod, l, m);
    //     b.modify(mod, m + 1, r);
    //     // reset mod
    // }
};

void solve() {
    int n, zaps, C;
    n = zaps = 20000;
    C = 1;
    cin >> n >> zaps >> C;
    vector<Li> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = read_hash();
    }
    cerr << "\n\nreading " << TIME << endl;
    Segtree<Item> t(a);
    cerr << "\n\nbuilding " << TIME << endl;
    while (zaps--) {
        int tp;
        tp = rnd() & 1;
//        tp = 0;
        cin >> tp;
        if (tp == 0) {
            int l, r;
            l = rnd() % n + 1;
            r = rnd() % n + 1;
            if (l > r)
                swap(l, r);
            uint x = rndll();
            cin >> l >> r >> x;
            l--;
            r--;
//            Li z = def();
//            for (int i = l; i <= r; i++)
//                z = comb(z, a[i]);
            x = t.ask(l, r).w.apply(x);
            cout << x << '\n';
        } else {
            int i;
            i = rnd() % n + 1;
            cin >> i;
            i--;
            a[i] = read_hash();
            t.set(i, a[i]);
        }
    }
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    solve();
    cerr << "\n\nConsumed " << TIME << endl;
}

Details

answer.code:7:39: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
    7 | #pragma GCC optimize("strict-overflow")
      |                                       ^
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
    8 | #pragma GCC target("popcnt,lzcnt,abm,bmi,bmi2")
      |                                               ^
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:8:47: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:40:49: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
   40 |     Item tree_merge(const Item& a, const Item& b) {
      |                                                 ^
answer.code:51:53: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
   51 |         void push(const vector<Item>&, int, int, int) {}
      |                                                     ^
answer.code:52:74: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
   52 |         Item ask_on_segment(const vector<Item>& tree, int n, int l, int r) {
      |                                                                          ^
answer.code:70:54: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
   70 |         void push_point(const vector<Item>&, int, int) {}
      |                                                      ^
answer.code:73:68: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
   73 |         int lower_bound(const vector<Item>& tree, int n, int l, P p) {
      |                                                                    ^
answer.code:105:72: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  105 |         int lower_bound_rev(const vector<Item>& tree, int n, int r, P p) {
      |                                                                        ^
answer.code:139:60: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  139 |         void push(vector<Item>& tree, int ind, int l, int r) {
      |                                                            ^
answer.code:143:68: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  143 |         Item ask_on_segment(vector<Item>& tree, int n, int l, int r) {
      |                                                                    ^
answer.code:204:59: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  204 |         void push_point(vector<Item>& tree, int n, int ind) {
      |                                                           ^
answer.code:221:101: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  221 |         pair<int, Item> _lower_bound(vector<Item>& tree, int l, P p, Item cur, int i, int vl, int vr) {
      |                                                                                                     ^
answer.code:251:62: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  251 |         int lower_bound(vector<Item>& tree, int n, int l, P p) {
      |                                                              ^
answer.code:258:105: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  258 |         pair<int, Item> _lower_bound_rev(vector<Item>& tree, int r, P p, Item cur, int i, int vl, int vr) {
      |                                                                                                         ^
answer.code:288:66: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  288 |         int lower_bound_rev(vector<Item>& tree, int n, int r, P p) {
      |                                                                  ^
answer.code:302:26: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
  302 |         Segtree(int n = 0) {
      |                          ^
answer.code:307:35: warning: bad optio...