blue_ice26 @ 2024-10-12 17:06:51
比较离谱的是：
在洛谷在线IDE上不开O2能过，开O2RE
提交后无论开不开O2都RE
如果各位对指针写法感到反感，在这里深表歉意(主要是真的写习惯了)
提交记录：https://www.luogu.com.cn/record/181611803
代码：
#include<cstdio>
#include<chrono>
#include<random>
#include<algorithm>
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
namespace FHQ
{
struct node
{
int key,pri,sz;
bool lz;
node *lch,*rch;
node(int x)
{
key=x;
sz=1;
pri=rnd();
lz=0;
lch=rch=nullptr;
}
int size()
{
if(this==nullptr)
return 0;
else
return sz;
}
void update()
{
sz=lch->size()+rch->size()+1;
}
void lazy()
{
if(this!=nullptr)
lz=(!lz);
}
void down()
{
if(lz)
{
std::swap(lch,rch);
lz=0;
lch->lazy();
rch->lazy();
}
}
};
void split(int x,node *p,node *&l,node *&r)
{
if(p==nullptr)
{
l=r=nullptr;
return;
}
p->down();
if(p->lch->size()>=x)
{
r=p;
split(x,p->lch,l,r->lch);
}
else
{
l=p;
split(x-p->lch->size()-1,p->rch,l->rch,r);
}
p->update();
}
node *merge(node *l,node *r)
{
if(l==nullptr)
return r;
if(r==nullptr)
return l;
if(l->pri>r->pri)
{
l->down();
l->rch=merge(l->rch,r);
l->update();
return l;
}
else
{
r->down();
r->lch=merge(l,r->lch);
r->update();
return r;
}
}
void out(node *p)
{
if(p==nullptr)
return;
p->down();
out(p->lch);
printf("%d ",p->key);
out(p->rch);
}
}
int main()
{
using namespace FHQ;
int n,m;
node *tr=nullptr;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
node *r=new node(i);
tr=merge(tr,r);
}
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
node *lp,*mp,*rp,*a;
split(r,tr,a,rp);
split(l-1,a,lp,mp);
// out(mp);
// printf("\n");
mp->lazy();
a=merge(lp,mp);
tr=merge(a,rp);
// out(tr);
}
out(tr);
return 0;
}by cavve @ 2024-10-12 19:39:19
int size()
{
if(this==nullptr)
return 0;
else
return sz;
}
void update()
{
sz=lch->size()+rch->size()+1;
}
void lazy()
{
if(this!=nullptr)
lz=(!lz);
}如果this已经是nullptr的话就没有成员函数size和lazy了
by cavve @ 2024-10-12 19:40:26
改成这样就可以了
@blue_ice26
#include<cstdio>
#include<chrono>
#include<random>
#include<algorithm>
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
namespace FHQ {
struct node {
int key, pri, sz;
bool lz;
node* lch, * rch;
node(int x) {
key = x;
sz = 1;
pri = rnd();
lz = 0;
lch = rch = nullptr;
}
#define size(x) (x == nullptr ? 0 : x->sz)
void update() {
sz = size(lch) + size(rch) + 1;
}
#define lazy(x) (x == nullptr ? 0 : x->lz ^= 1)
void down() {
if(lz) {
std::swap(lch, rch);
lz = 0;
lazy(lch);
lazy(rch);
}
}
};
void split(int x, node* p, node*& l, node*& r) {
if(p == nullptr) {
l = r = nullptr;
return;
}
p->down();
if(size(p->lch) >= x) {
r = p;
split(x, p->lch, l, r->lch);
}
else {
l = p;
split(x - size(p->lch) - 1, p->rch, l->rch, r);
}
p->update();
}
node* merge(node* l, node* r) {
if(l == nullptr)
return r;
if(r == nullptr)
return l;
if(l->pri > r->pri) {
l->down();
l->rch = merge(l->rch, r);
l->update();
return l;
}
else {
r->down();
r->lch = merge(l, r->lch);
r->update();
return r;
}
}
void out(node* p) {
if(p == nullptr)
return;
p->down();
out(p->lch);
printf("%d ", p->key);
out(p->rch);
}
}
int main() {
using namespace FHQ;
int n, m;
node* tr = nullptr;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
node* r = new node(i);
tr = merge(tr, r);
}
for(int i = 1; i <= m; i++) {
int l, r;
scanf("%d%d", &l, &r);
node* lp, * mp, * rp, * a;
split(r, tr, a, rp);
split(l - 1, a, lp, mp);
// out(mp);
// printf("\n");
lazy(mp);
a = merge(lp, mp);
tr = merge(a, rp);
// out(tr);
}
out(tr);
return 0;
}by FanMingxuan @ 2024-10-12 22:01:06
你怎么也玩电教
by blue_ice26 @ 2024-10-14 12:50:51
@cavve 感谢红名大佬
这下O2不能乱开了
by blue_ice26 @ 2024-10-14 12:52:42
@FanMingxuan 找到机会了（