QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768626#9727. Barkley IIIi_wish_a_girl_friendCompile Error//C++236.8kb2024-11-21 13:02:382024-11-21 13:02:45

Judging History

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

  • [2025-01-13 03:55:43]
  • hack成功,自动添加数据
  • (/hack/1447)
  • [2024-11-21 13:02:45]
  • 评测
  • [2024-11-21 13:02:38]
  • 提交

answer

#pragma GCC optimize("ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define pb push_back
#define LNF 1e18
#define INF 0x7fffffff
#define int long long
#define lowbit(x) ((x) & (-x))
#define abs(x) llabs(x)
#define endl '\n'
#define Y() cout << "Yes" << endl
#define N() cout << "No" << endl
const db eps = 1e-9;
const int mod = 9223372036854775807;
const int MAXN = 1e6 + 5;

int val[1000006];
struct node
{
    int num, is, lazy, siz, sum;
} tr[MAXN << 2];
void push_down(int p)
{
    if (tr[p].lazy ^ mod)
    {
        tr[p << 1].lazy &= tr[p].lazy;
        tr[p << 1 | 1].lazy &= tr[p].lazy;
        if (tr[p << 1].siz == 1)
        {
            tr[p << 1].sum &= tr[p].lazy;
            tr[p << 1].num |= (mod ^ tr[p].lazy);
        }
        else
        {
            tr[p << 1].sum &= tr[p].lazy;
            tr[p << 1].is |= (mod ^ tr[p].lazy);
            tr[p << 1].num &= (tr[p].lazy);
        }
        if (tr[p << 1 | 1].siz == 1)
        {
            tr[p << 1 | 1].sum &= tr[p].lazy;
            tr[p << 1 | 1].num |= (mod ^ tr[p].lazy);
        }
        else
        {
            tr[p << 1 | 1].sum &= tr[p].lazy;
            tr[p << 1 | 1].is |= (mod ^ tr[p].lazy);
            tr[p << 1 | 1].num &= (tr[p].lazy);
        }
        tr[p].lazy = mod;
    }
}
inline void push_up(int p)
{
    tr[p].sum = tr[p << 1].sum & tr[p << 1 | 1].sum;
    tr[p].is = (tr[p << 1].num & tr[p << 1 | 1].num) | tr[p << 1].is | tr[p << 1 | 1].is;
    tr[p].num = (tr[p << 1].num ^ tr[p << 1 | 1].num) & (mod ^ tr[p].is);
}
inline  inline void merge(node &a, node b)
{

    a.sum = a.sum & b.sum;
    a.is = (a.num & b.num) | a.is | b.is;
    a.num = (a.num ^ b.num) & (mod ^ a.is);
    // cout << a.num << " " << b.num << endl;
}
void build(int p, int l, int r)
{
    tr[p].siz = r - l + 1;
    tr[p].lazy = mod;
    if (l == r)
    {
        tr[p].num = (mod ^ val[l]);
        tr[p].sum = val[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    push_up(p);
    // if (l == 6 && r == 9)
    // {
    //     cout << "!" << tr[p].num << endl;
    // }
}
void modify(int p, int l, int r, int pos, int nu)
{
    if (l == r)
    {
        tr[p].sum = nu;
        tr[p].num = (mod ^ nu);
        return;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (pos <= mid)
        modify(p << 1, l, mid, pos, nu);
    else
        modify(p << 1 | 1, mid + 1, r, pos, nu);
    push_up(p);
}
void modify_and(int p, int l, int r, int ql, int qr, int nu)
{
    if (l >= ql && r <= qr)
    {
        if (tr[p].siz == 1)
        {
            tr[p].sum &= nu;
            tr[p].num |= (mod ^ nu);
        }
        else
        {
            tr[p].sum &= nu;
            tr[p].lazy &= nu;
            tr[p].num &= nu;
            tr[p].is |= (mod ^ nu);
        }
        return;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (ql <= mid)
        modify_and(p << 1, l, mid, ql, qr, nu);
    if (qr > mid)
        modify_and(p << 1 | 1, mid + 1, r, ql, qr, nu);
    push_up(p);
}

node query_bit(int p, int l, int r, int ql, int qr)
{
    if (l >= ql && r <= qr)
    {
        return tr[p];
    }
    push_down(p);
    int mid = l + r >> 1;
    node ans = {0, 0, 0, 0, mod};
    if (ql <= mid)
        merge(ans, query_bit(p << 1, l, mid, ql, qr));
    if (qr > mid)
        merge(ans, query_bit(p << 1 | 1, mid + 1, r, ql, qr));
    push_up(p);
    return ans;
}
int query_pos(int p, int l, int r, int ql, int qr, int nu)
{ // 已经被提取的最高位
    if (l == r)
    {
        if (!(tr[p].is & nu) && !(tr[p].sum & nu))
            return l;
        else
            return 0;
    }
    push_down(p);
    int mid = l + r >> 1;
    int ans = 0;
    if (l >= ql && r <= qr)
    {
        if (!(tr[p << 1].is & nu) && !(tr[p << 1].sum & nu))
        {
            ans |= query_pos(p << 1, l, mid, ql, qr, nu);
        }
        if (!(tr[p << 1 | 1].is & nu) && !(tr[p << 1 | 1].sum & nu))
        {
            ans |= query_pos(p << 1 | 1, mid + 1, r, ql, qr, nu);
        }
    }
    else
    {
        if (ql <= mid)
            ans |= query_pos(p << 1, l, mid, ql, qr, nu);
        if (qr > mid)
            ans |= query_pos(p << 1 | 1, mid + 1, r, ql, qr, nu);
    }
    push_up(p);
    return ans;
}
int query_val(int p, int l, int r, int ql, int qr)
{
    if (l >= ql && r <= qr)
    {
        return tr[p].sum;
    }
    push_down(p);
    int mid = l + r >> 1;
    int ans = mod;
    if (ql <= mid)
        ans &= query_val(p << 1, l, mid, ql, qr);
    if (qr > mid)
        ans &= query_val(p << 1 | 1, mid + 1, r, ql, qr);
    push_up(p);
    return ans;
}
void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    build(1, 1, n);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, x;
            cin >> l >> r >> x;
            modify_and(1, 1, n, l, r, x);
        }
        else if (op == 2)
        {
            int s, x;
            cin >> s >> x;
            modify(1, 1, n, s, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            if (l == r)
            {
                cout << 0 << endl;
                continue;
            }
            node nu = query_bit(1, 1, n, l, r);
            // cout << nu.sum << endl;
            // cout << nu.num << endl;
            // cout << nu.is << endl;
            int res = ((nu.is | nu.sum) ^ mod) & mod;
            // cout << res << endl;
            int ws = -1;
            for (int i = 62; i >= 0; i--)
            {
                if (res & (1ll << i))
                {
                    ws = i;
                    break;
                }
            }
            // cout << ws << endl;

            if (ws == -1)
            {
                cout << nu.sum << endl;
                continue;
            }
            int pos = query_pos(1, 1, n, l, r, (1ll << ws));
            // cout << pos << endl;
            int ans = mod;
            if (pos != l)
            {
                ans &= query_val(1, 1, n, l, pos - 1);
            }
            if (pos != r)
            {
                ans &= query_val(1, 1, n, pos + 1, r);
            }
            cout << ans << endl;
        }
    }
    // cout << -1 << endl;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(0);
    // cout << -1 << endl;
    int T = 1;
    // cout << (!(0)) << endl;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

詳細信息

answer.code:1:29: warning: bad option ‘-fofast’ to pragma ‘optimize’ [-Wpragmas]
    1 | #pragma GCC optimize("ofast")
      |                             ^
answer.code:27:21: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
   27 | void push_down(int p)
      |                     ^
answer.code:58:26: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
   58 | inline void push_up(int p)
      |                          ^
answer.code:64:9: error: duplicate ‘inline’
   64 | inline  inline void merge(node &a, node b)
      |         ^~~~~~
      |         ------
answer.code:64:42: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
   64 | inline  inline void merge(node &a, node b)
      |                                          ^
answer.code:72:31: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
   72 | void build(int p, int l, int r)
      |                               ^
answer.code:91:49: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
   91 | void modify(int p, int l, int r, int pos, int nu)
      |                                                 ^
answer.code:107:60: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  107 | void modify_and(int p, int l, int r, int ql, int qr, int nu)
      |                                                            ^
answer.code:134:51: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  134 | node query_bit(int p, int l, int r, int ql, int qr)
      |                                                   ^
answer.code:150:58: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  150 | int query_pos(int p, int l, int r, int ql, int qr, int nu)
      |                                                          ^
answer.code:183:50: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  183 | int query_val(int p, int l, int r, int ql, int qr)
      |                                                  ^
answer.code:199:12: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  199 | void solve()
      |            ^
answer.code:269:13: warning: bad option ‘-fofast’ to attribute ‘optimize’ [-Wattributes]
  269 | signed main()
      |             ^