QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307692 | #6427. Just Another Game of Stones | Yarema | RE | 1ms | 3604kb | C++14 | 4.1kb | 2024-01-19 03:46:30 | 2024-01-19 03:46:31 |
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 = 30;
const int INF = 1e9 + 47;
struct Node
{
int 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 VI& 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 VI& a)
{
init(SZ(a));
build(0, 0, n, a);
}
Node query(int v, int tl, int tr, int l, int r)
{
//cerr << v << ' ' << l << ' ' << r << ' ' << tl << ' ' << tr << '\n';
if (l >= tr || tl >= r)
return {};
if (l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) / 2;
//auto n1 = query(v * 2 + 1, tl, tm, l, r);
//auto n2 = query(v * 2 + 2, tm, tr, l, r);
//cerr << v << ' ' << l << ' ' << r << ' ' << tl << ' ' << tr << '\n';
//n1.out();
//n2.out();
//auto ans = combine(n1, n2);
//ans.out();
//cerr << "\n\n\n";
//return ans;
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, int x)
{
if (nd.cnt & 1)
nd.x ^= nd.mn ^ x;
FOR (i, 0, LOG)
{
nd.c[i] -= (nd.mn >> i) & 1;
nd.c[i] += (x >> i) & 1;
}
nd.mn = x;
nd.ps = max(nd.ps, x);
}
void upd(int v, int tl, int tr, int l, int r, int x)
{
//cerr << v << ' ' << tl << ' ' << tr << ' ' << l << ' ' << r << '\n';
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, int 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;
VI a(n);
FOR (i, 0, n) cin >> a[i];
Segtree st;
st.build(a);
//FOR (i, 0, st.n * 2 - 1)
//{
// cerr << i << "\n";
// st.t[i].out();
//}
//cerr << "\n\n";
FOR (i, 0, m)
{
int t, l, r, x;
cin >> t >> l >> r >> x;
l--;
if (t == 1)
{
st.upd(l, r, x);
}
else
{
auto nd = st.query(l, r);
//cerr << i << ": \n";
//nd.out();
x ^= nd.x;
if (x == 0)
cout << 0 << '\n';
else
{
int bt = 31 - __builtin_clz(x);
//cerr << bt << '\n';
cout << nd.c[bt] << '\n';
}
}
//cerr << "------------------------\n\n\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
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 0 3
result:
ok 3 number(s): "1 0 3"
Test #2:
score: -100
Runtime Error
input:
200000 200000 962352030 173642520 1008864183 74920228 684681800 500911321 1001441054 257633652 185843534 59168654 317689197 731348417 123888883 708119712 340055368 876566011 980078202 969174443 814012870 715639041 596932238 173757742 314504576 1045746913 740811577 570187156 999816627 12441059 122507...