QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#308037 | #6427. Just Another Game of Stones | Yarema | WA | 0ms | 3544kb | C++14 | 3.6kb | 2024-01-19 14:01:27 | 2024-01-19 14:01:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int LOG = 31;
const LL INF = 1ll << 47;
struct Node
{
LL mn, cnt, mn2, x, ps;
int c[LOG];
Node()
{
mn = INF;
cnt = 0;
mn2 = INF;
x = 0;
ps = -1;
fill(c, c + LOG, 0);
}
void out()
{
cerr << mn << ' ' << cnt << ' ' << mn2 << ' ' << x << '\n';
FOR (j, 0, 4)
cerr << c[j] << ' ';
cerr << '\n';
}
};
struct Segtree
{
int n;
vector<Node> t;
void init(int _n)
{
n = 1;
while (n < _n) n *= 2;
t.resize(2 * n + 1);
}
Node combine(Node a, Node b)
{
Node res;
if (a.mn == b.mn)
{
res.mn = a.mn;
res.cnt = a.cnt + b.cnt;
res.mn2 = min(a.mn2, b.mn2);
}
else
{
res.mn = min(a.mn, b.mn);
res.cnt = a.mn < b.mn ? a.cnt : b.cnt;
res.mn2 = min({a.mn2, b.mn2, max(a.mn, b.mn)});
}
res.x = a.x ^ b.x;
FOR (i, 0, LOG)
res.c[i] = a.c[i] + b.c[i];
return res;
}
void build(int v, int tl, int tr, const vector<LL>& a)
{
if (tl + 1 == tr)
{
if (tl < SZ(a))
{
t[v].mn = a[tl];
t[v].cnt = 1;
t[v].mn2 = INF;
t[v].x = a[tl];
t[v].ps = -1;
FOR (i, 0, LOG) t[v].c[i] = (a[tl] >> i) & 1;
}
return;
}
int tm = (tl + tr) / 2;
build(v * 2 + 1, tl, tm, a);
build(v * 2 + 2, tm, tr, a);
t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}
void build(const vector<LL>& a)
{
init(SZ(a));
build(0, 0, n, a);
}
Node query(int v, int tl, int tr, int l, int r)
{
if (l >= tr || tl >= r)
return {};
if (l <= tl && tr <= r)
return t[v];
push(v);
int tm = (tl + tr) / 2;
return combine(query(v * 2 + 1, tl, tm, l, r),
query(v * 2 + 2, tm, tr, l, r));
}
Node query(int l, int r)
{
return query(0, 0, n, l, r);
}
void push(int v)
{
if (v * 2 + 1 >= SZ(t) || t[v].ps == -1)
{
t[v].ps = -1;
return;
}
up(t[v * 2 + 1], t[v].ps);
up(t[v * 2 + 2], t[v].ps);
t[v].ps = -1;
}
void up(Node& nd, LL x)
{
if (nd.mn >= x)
return;
if (nd.cnt & 1)
nd.x ^= nd.mn ^ x;
FOR (i, 0, LOG)
{
nd.c[i] -= ((nd.mn >> i) & 1) * nd.cnt;
nd.c[i] += ((x >> i) & 1) * nd.cnt;
}
nd.mn = x;
nd.ps = max(nd.ps, x);
}
void upd(int v, int tl, int tr, int l, int r, LL x)
{
if (l >= tr || tl >= r || t[v].mn >= x)
return;
if (l <= tl && tr <= r && t[v].mn2 > x)
{
up(t[v], x);
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(v * 2 + 1, tl, tm, l, r, x);
upd(v * 2 + 2, tm, tr, l, r, x);
t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}
void upd(int l, int r, LL x)
{
upd(0, 0, n, l, r, x);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n, m;
cin >> n >> m;
vector<LL> a(n);
FOR (i, 0, n) cin >> a[i];
Segtree st;
st.build(a);
FOR (i, 0, m)
{
int t, l, r;
LL x;
cin >> t >> l >> r >> x;
l--;
if (t == 1)
{
st.upd(l, r, x);
}
else
{
auto nd = st.query(l, r);
int xr = x ^ nd.x;
if (x == 0)
cout << 0 << '\n';
else
{
int bt = 31 - __builtin_clz(xr);
cout << nd.c[bt] + ((x >> bt) & 1) << '\n';
}
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3544kb
input:
5 4 1 2 1 4 1 2 1 3 1 1 2 4 3 2 2 4 4 2 1 4 4
output:
1 2 3
result:
wrong answer 2nd numbers differ - expected: '0', found: '2'