QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#415929 | #5409. Perotation | zzy0922 | 0 | 0ms | 0kb | C++14 | 4.9kb | 2024-05-21 12:43:49 | 2024-05-21 12:43:50 |
answer
#include <bits/stdc++.h>
#define tree TrEe
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
char c=getchar();int x=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return x;
}
constexpr int N = 100005, B = 2005;
int n, q;
int bl[N], br[N], blk[N], bc = 1;
struct node {
int ls, rs, t, v, r0, r1;
}tree[10000005];
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define t(p) tree[p].t
#define v(p) tree[p].v
#define r0(p) tree[p].r0
#define r1(p) tree[p].r1
int tot = 0;
inline int new_n() {
return ++tot;
}
inline void rev(int p) {
std::swap(r0(p), r1(p));
t(p) ^= 1;
}
inline void pushup(int p) {
r0(p) = std::max(r0(ls(p)), r0(rs(p)));
r1(p) = std::max(r1(ls(p)), r1(rs(p)));
v(p) = v(ls(p)) ^ v(rs(p));
}
inline void pushdown(int p) {
if (t(p)) {
if (ls(p)) rev(ls(p));
if (rs(p)) rev(rs(p));
t(p) = 0;
}
}
inline void ins(int p, int _l, int _r, int x, int v) {
if (x > _r || x < _l)
return;
if (_l == _r) {
v(p) = 1;
(v ? r1(p) : r0(p)) = _l;
return;
}
pushdown(p);
int mid = (_l + _r) >> 1;
if (x <= mid) {
if (!ls(p))
ls(p) = new_n();
ins(ls(p), _l, mid, x, v);
} else {
if (!rs(p))
rs(p) = new_n();
ins(rs(p), mid + 1, _r, x, v);
}
pushup(p);
}
inline void del(int p, int _l, int _r, int x) {
if (x > _r || x < _l)
return;
if (_l == _r) {
v(p) = 0;
r0(p) = r1(p) = 0;
return;
}
pushdown(p);
int mid = (_l + _r) >> 1;
if (x <= mid)
del(ls(p), _l, mid, x);
else
del(rs(p), mid + 1, _r, x);
pushup(p);
}
inline void rev_lr(int p, int _l, int _r, int l, int r) {
if (!p)
return;
if (l > _r || r < _l)
return;
if (l <= _l && _r <= r) {
rev(p);
return;
}
pushdown(p);
int mid = (_l + _r) >> 1;
rev_lr(ls(p), _l, mid, l, r);
rev_lr(rs(p), mid + 1, _r, l, r);
pushup(p);
}
inline int get_v(int p, int _l, int _r, int x) {
if (!p)
return 0;
if (_l == _r)
return v(p);
int mid = (_l + _r) >> 1;
if (x + 1 <= mid)
return get_v(ls(p), _l, mid, x) ^ v(rs(p));
else
return get_v(rs(p), mid + 1, _r, x);
}
int rt[N];
int a[N], pos[N];
inline int get_01(int x) {
int res = 0;
for (int i = 1; i <= blk[a[x] - 1] - 1; i++)
res ^= get_v(rt[i], 1, n, x);
for (int i = bl[blk[a[x] - 1]]; i <= a[x] - 1; i++)
if (pos[i] > x)
res ^= 1;
// std::cout << res << '\n';
return res;
}
inline int get_ans() {
int ans = 0;
for (int i = 1; i <= bc; i++)
ans = std::max(ans, r1(rt[i]) + 1);
return ans;
}
int main() {
freopen("perotation.in", "r", stdin);
freopen("perotation.out", "w", stdout);
std::cin.tie(0)->sync_with_stdio(0);
// std::cin >> n >> q;
n = read(), q = read();
for (int &i = bc; (i - 1) * B + 1 <= n; i++) {
bl[i] = (i - 1) * B + 1;
br[i] = std::min(i * B, n);
for (int j = bl[i]; j <= br[i]; j++)
blk[j] = i;
}
--bc;
for (int i = 1; i <= bc; i++)
rt[i] = new_n();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
pos[a[i]] = i;
for (int i = n; i >= 1; i--)
ins(rt[blk[a[i]]], 1, n, i, (i == n ? 0 : get_01(i)));
// std::cout << tot << '\n';
int x, y;
while (q--) {
// std::cin >> x >> y;
x = read(), y = read();
if (x > y)
std::swap(x, y);
int l = std::min(a[x], a[y]) + 1, r = std::max(a[x], a[y]) - 1;
if (l <= r) {
if (blk[l] == blk[r]) {
for (int i = l; i <= r; i++)
if (pos[i] >= x && pos[i] <= y)
rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
} else {
for (int i = l; i <= br[blk[l]]; i++)
if (pos[i] >= x && pos[i] <= y)
rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
for (int i = blk[l] + 1; i <= blk[r] - 1; i++)
rev_lr(rt[i], 1, n, x, y);
for (int i = bl[blk[r]]; i <= r; i++)
if (pos[i] >= x && pos[i] <= y)
rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
}
}
del(rt[blk[a[x]]], 1, n, x);
del(rt[blk[a[y]]], 1, n, y);
std::swap(pos[a[x]], pos[a[y]]);
std::swap(a[x], a[y]);
ins(rt[blk[a[y]]], 1, n, y, get_01(y));
ins(rt[blk[a[x]]], 1, n, x, get_01(x));
std::cout << get_ans() << '\n';
}
}
詳細信息
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
2 1 1 2 2 1
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%