为什么MLE

_LSA_ @ 2023-08-17 22:29:40

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read() {
    ll X = 0,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) {
        X = X*10+ch-'0';
        ch = getchar();
    }
    return X*r;
}
const int N = 1e5+10;
int n,m,cnt,root;
struct FHQ_Tree{
    int ls,rs;
    int num,pri,siz;
    bool tag;
}c[N];
void newNode(int x){
    cnt++;
    c[cnt].ls = c[cnt].rs = 0;
    c[cnt].siz = 1;
    c[cnt].num = x;
    c[cnt].pri = rand();
}
void update(int x){
    c[x].siz = c[c[x].ls].siz+c[c[x].rs].siz+1;
}
void push_down(int x){
    if(c[x].tag){
        swap(c[x].ls,c[x].rs);
        c[c[x].ls].tag ^= 1;
        c[c[x].rs].tag ^= 1;
        c[x].tag = 0;
    }
}
void split(int x,int k,int &L,int &R){
    if(!x){L = R = 0; return;}
    push_down(x);
    if(c[c[x].ls].siz+1 <= k){
        L = x;
        split(c[x].rs,k-c[c[x].ls].siz-1,c[x].rs,R);
    }else{
        R = x;
        split(c[x].ls,k,L,c[x].ls);
    }
    update(x);
}
int merge(int L,int R){
    if(!L || !R) return L+R;
    if(c[L].pri > c[R].pri){
        push_down(L);
        c[L].rs = merge(c[L].rs,R);
        update(L);
        return L;
    }else{
        push_down(R);
        c[R].ls = merge(L,c[R].ls);
        update(R);
        return R;
    }
}
void inorder(int x){
    if(!x) return;
    push_down(x);
    inorder(c[x].ls);
    cout << c[x].num << " ";
    inorder(c[x].rs);
}
int main() {
    srand(time(0));
    n = read(); m = read();
    for(int i=1;i<=n;i++){
        newNode(i);
        root = merge(root,cnt);
    }
    int x,y,L,R,p;
    while(m--){
        x = read(),y = read();
        L = R = p = 0;
        split(root,y,L,R);
        split(root,x-1,L,p);
        c[p].tag ^= 1;
        root = merge(merge(L,p),R);
    }
    inorder(root);
    return 0;
}

by 柠檬熟了 @ 2023-09-04 17:44:00

我也不知道 我FHQ也MLE 甚至在LUOGU IDE都正常

by 柠檬熟了 @ 2023-09-04 18:04:30

改出来了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read() {
    ll X = 0,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) {
        X = X*10+ch-'0';
        ch = getchar();
    }
    return X*r;
}
const int N = 1e5+10;
int n,m,cnt,root;
struct FHQ_Tree{
    int ls,rs;
    int num,pri,siz;
    bool tag;
}c[N];
void newNode(int x){
    cnt++;
    c[cnt].ls = c[cnt].rs = 0;
    c[cnt].siz = 1;
    c[cnt].num = x;
    c[cnt].pri = rand()%65536;
}
void update(int x){
    c[x].siz = c[c[x].ls].siz+c[c[x].rs].siz+1;
}
void push_down(int x){
    if(c[x].tag){
        swap(c[x].ls,c[x].rs);
        c[c[x].ls].tag ^= 1;
        c[c[x].rs].tag ^= 1;
        c[x].tag = 0;
    }
}
void split(int x,int k,int &L,int &R){
    if(!x){L = R = 0; return;}
    push_down(x);
    if(c[c[x].ls].siz+1 <= k){
        L = x;
        split(c[x].rs,k-c[c[x].ls].siz-1,c[x].rs,R);
    }else{
        R = x;
        split(c[x].ls,k,L,c[x].ls);
    }
    update(x);
}
//
int merge(int L,int R){
    if(!L || !R) return L|R; //1

    push_down(L);push_down(R); //2
    if(c[L].pri > c[R].pri){

        c[L].rs = merge(c[L].rs,R);
        update(L);
        return L;
    }else{

        c[R].ls = merge(L,c[R].ls);
        update(R);
        return R;
    }
}
void inorder(int x){
    if(!x) return;
    push_down(x);
    inorder(c[x].ls);
    cout << c[x].num << " ";
    inorder(c[x].rs);
}
int main() {
//    srand(time(0));
    n = read(); m = read();
    for(int i=1;i<=n;i++){
        newNode(i);
        root = merge(root,cnt);
    }
    int x,y,L,R,p;
    while(m--){
        x = read(),y = read();
        int A, B, C, D; //3
        split(root,x-1,A,B); //4
        split(B, y-x+1,C,D); //5
        c[C].tag ^= 1;
        root = merge(merge(A,C),D);

    }
    inorder(root);
    return 0;
}

改的行用注释 //n 标注了

by _LSA_ @ 2023-11-13 19:16:45

好的谢谢（虽然跨越了两个月）

其实只需把注释5那行的root改成L就可以了