lkrkerry @ 2024-05-28 20:13:16
该题目用C++17提交可以AC,但使用C++14提交会WA+RE
#include <vector>
#include <iostream>
#define int long long
using namespace std;
int n, m;
struct Node
{
int fa, ch[2], val, sz;
bool lazy;
Node(int val = 0, int fa = 0, int l = 0, int r = 0, int sz = 0, bool lazy = false)
: val(val), fa(fa), sz(sz), lazy(lazy)
{
ch[0] = l;
ch[1] = r;
}
};
struct SplayTree
{
vector<Node> tree;
int rt;
SplayTree()
{
tree.push_back(Node());
rt = 0;
}
int build(int l, int r, int f, vector<int> &a)
{
if (l > r)
return 0;
int mid = (l + r) / 2;
tree.push_back(Node(a[mid], f));
int cur = tree.size() - 1;
tree[cur].ch[0] = build(l, mid - 1, cur, a);
tree[cur].ch[1] = build(mid + 1, r, cur, a);
maintain(cur);
cout << cur << endl;
return rt = cur;
}
void maintain(int x)
{
tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz + 1;
}
bool get(int x)
{
return x == tree[tree[x].fa].ch[1];
}
void revlazy(int x)
{
swap(tree[x].ch[0], tree[x].ch[1]);
tree[x].lazy ^= 1;
}
void push_down(int x)
{
if (tree[x].lazy)
{
revlazy(tree[x].ch[0]);
revlazy(tree[x].ch[1]);
tree[x].lazy = 0;
}
}
void rotate(int x)
{
// rotate in dir automaticaly
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if (tree[x].ch[chk ^ 1])
{
tree[tree[x].ch[chk ^ 1]].fa = y;
}
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;
tree[x].fa = z;
if (z)
tree[z].ch[y == tree[z].ch[1]] = x;
maintain(y);
maintain(x);
}
void splay(int x, int goal = 0)
{
if (goal == 0)
rt = x;
while (tree[x].fa != goal)
{
int f = tree[x].fa, g = tree[f].fa;
if (g != goal)
{
if (get(f) == get(x)) // same turn
rotate(f);
else
rotate(x);
}
rotate(x);
}
}
int kth(int k)
{
int cur = rt;
while (1)
{
cout << tree[cur].val << " " << k << endl;
system("pause");
push_down(cur);
if (tree[cur].ch[0] && k <= tree[tree[cur].ch[0]].sz)
{
cur = tree[cur].ch[0];
}
else
{
// minus rank from left tree
k -= (1 + tree[tree[cur].ch[0]].sz);
if (k <= 0)
{
splay(cur);
return cur;
}
cur = tree[cur].ch[1];
}
}
}
void reverse(int l, int r)
{
int l2 = kth(l), r2 = kth(r + 2); // remember to - and +
splay(l2);
splay(r2, l2); // make l,r together to swap
int tmp = tree[tree[l2].ch[1]].ch[0]; // ch 1 is r2, ch 1 ch 0 is used
revlazy(tmp);
}
void print(int x)
{
push_down(x);
if (tree[x].ch[0])
print(tree[x].ch[0]);
if (tree[x].val >= 1 && tree[x].val <= n)
cout << tree[x].val << " ";
if (tree[x].ch[1])
print(tree[x].ch[1]);
}
};
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
auto tree = SplayTree();
auto a = vector<int>(n + 2);
for (int i = 1; i <= n + 1; i++)
{
a[i] = i;
}
int rt = tree.build(0, n + 1, 0, a);
for(int i=0;i<=n+1;i++){
cout << tree.tree[i].val << " " << tree.tree[i].sz << endl;
}
cout << endl;
for (int i = 1; i <= m; i++)
{
int l, r;
cin >> l >> r;
tree.reverse(l, r);
}
tree.print(tree.rt);
cout << endl;
return 0;
}
by cmk666 @ 2024-05-28 20:39:06
在函数 build
里:
...
tree.push_back(...);
...
tree[...] = build(...);
...
在调用 build
的时候,会给 tree
这个 vector
进行 push_back
,可能会导致扩容,致使迭代器、引用失效。在 C++14 及以前,tree[...] = build(...)
这一句的行为可能是:
tree[...]
的引用;build(...)
;C++17 及以后,标准规定了 =
是先算右边再算左边,即上述过程的
by lkrkerry @ 2024-05-29 11:21:48
谢谢,关注了