rc_Taurus @ 2024-08-02 16:40:16
本人用的是FHQ-Treap，代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,rt,p,l,r;
struct FHQ{
int l,r;
int key,val;
int siz,tag;
}tr[N];
void add(int x){
tr[x].val=x;
tr[x].siz=1;
tr[x].key=rand();
tr[x].l=tr[x].r=0;
}
void push_down(int p){
if(tr[p].tag){
swap(tr[p].l,tr[p].r);
tr[tr[p].l].tag^=1;
tr[tr[p].r].tag^=1;
tr[p].tag=0;
}
}
void push_up(int p){
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+1;
}
void split(int p,int x,int &l,int &r){
if(!p){
l=r=0;
return;
}
push_down(p);
if(tr[tr[p].l].siz+1<=x){
l=p;
split(tr[p].r,x-tr[tr[p].l].siz-1,tr[p].r,r);
}else{
r=p;
split(tr[p].l,x,l,tr[p].l);
}
push_up(p);
}
int merge(int l,int r){
if(!l||!r){
return l+r;
}
if(tr[l].key<tr[r].key){
push_down(l);
tr[l].r=merge(tr[l].r,r);
push_up(l);
return l;
}else{
push_down(r);
tr[r].l=merge(l,tr[r].l);
push_up(r);
return r;
}
}
void print(int u){
push_down(u);
if(tr[u].l)print(tr[u].l);
cout<<tr[u].val<<' ';
if(tr[u].r)print(tr[u].r);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
add(i);
rt=merge(rt,i);
}
while(m--){
int x,y;
cin>>x>>y;
split(rt,y,l,r);
split(rt,x-1,l,p);
tr[p].tag^=1;
rt=merge(merge(l,p),r);
}
print(rt);
return 0;
}提交记录
为什么会MLE啊啊啊啊啊啊啊啊？
悬两关，求条
by MysteriousEast @ 2024-08-02 16:42:34
@rc_Taurus 空间超限
by rc_Taurus @ 2024-08-02 16:44:51
@MysteriousEast 我说的是为什么会MLE,我当然知道空间超了:(
by ACcepted917 @ 2024-08-02 16:51:56
你可以参考我的代码：
#include<bits/stdc++.h>
using namespace std;
//P3391
const int N=1e6+10;
#define fup(l,r) for(int i=l;i<=r;i++)
//用静态数组来模拟树
int cnt,root;
std::mt19937 rnd(233);
struct node{
int val,pri,ls,rs,size,lazy;
}t[N];
int newNode(int x){
t[++cnt]={x,rnd(),0,0,1,0};//初始化一个新结点
return cnt;
}
void update(int u){
t[u].size=t[t[u].ls].size+t[t[u].rs].size+1;
}
//懒标记下移
void pushdown(int u){
if(t[u].lazy){
swap(t[u].ls,t[u].rs);
t[t[u].ls].lazy ^= 1;
t[t[u].rs].lazy ^= 1;
t[u].lazy=0;//清空懒标记
}
}
//排名分裂--按顺序分裂
void Split(int u,int x,int& L,int& R){
if(u==0){
L=R=0;
return;
}
pushdown(u);
if(t[t[u].ls].size+1<=x){
L=u;
Split(t[u].rs,x-(t[t[u].ls].size+1),t[u].rs,R);
}
else{
R=u;
Split(t[u].ls,x,L,t[u].ls);
}
update(u);
}
int Merge(int L,int R){
if(L==0||R==0) return L+R;
if(t[L].pri>t[R].pri){
pushdown(L);
t[L].rs=Merge(t[L].rs,R);
update(L);
return L;
}
else{
pushdown(R);
t[R].ls=Merge(L,t[R].ls);
update(R);
return R;
}
}
//中序遍历
void inorder(int u){
if(u==0) return ;
pushdown(u);
inorder(t[u].ls);
printf("%d ",t[u].val);
inorder(t[u].rs);
}
int x,y,l,r,p;
int main(){
int n,m;
cin>>n>>m;
fup(1,n){
root=Merge(root,newNode(i));
}
while(m--){
scanf("%d%d",&x,&y);
Split(root,x-1,l,p);
Split(p,y-x+1,p,r);
t[p].lazy^=1;
root=Merge(l,Merge(p,r));
}
inorder(root);
return 0;
}by ACcepted917 @ 2024-08-02 17:02:07
找到问题了！！！
main函数中的这两行：
split(rt,y,l,r);
split(rt,x-1,l,p);应该为：
split(rt,x-1,l,p);
split(p,y-x+1,p,r);by ACcepted917 @ 2024-08-02 17:03:45
改完是这样的：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,rt,p,l,r;
struct FHQ{
int l,r;
int key,val;
int siz,tag;
}tr[N];
void add(int x){
tr[x].val=x;
tr[x].siz=1;
tr[x].key=rand();
tr[x].l=tr[x].r=0;
}
void push_down(int p){
if(tr[p].tag){
swap(tr[p].l,tr[p].r);
tr[tr[p].l].tag^=1;
tr[tr[p].r].tag^=1;
tr[p].tag=0;
}
}
void push_up(int p){
tr[p].siz=tr[tr[p].l].siz+tr[tr[p].r].siz+1;
}
void split(int p,int x,int &l,int &r){
if(!p){
l=r=0;
return;
}
push_down(p);
if(tr[tr[p].l].siz+1<=x){
l=p;
split(tr[p].r,x-tr[tr[p].l].siz-1,tr[p].r,r);
}else{
r=p;
split(tr[p].l,x,l,tr[p].l);
}
push_up(p);
}
int merge(int l,int r){
if(!l||!r){
return l+r;
}
if(tr[l].key<tr[r].key){
push_down(l);
tr[l].r=merge(tr[l].r,r);
push_up(l);
return l;
}else{
push_down(r);
tr[r].l=merge(l,tr[r].l);
push_up(r);
return r;
}
}
void print(int u){
push_down(u);
if(tr[u].l)print(tr[u].l);
cout<<tr[u].val<<' ';
if(tr[u].r)print(tr[u].r);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
add(i);
rt=merge(rt,i);
}
while(m--){
int x,y;
cin>>x>>y;
split(rt,x-1,l,p);
split(p,y-x+1,p,r);
tr[p].tag^=1;
rt=merge(merge(l,p),r);
}
print(rt);
return 0;
}by ACcepted917 @ 2024-08-02 17:04:21
@rc_Taurus
by rc_Taurus @ 2024-08-02 19:06:19
@ACcepted917 orzorz已关