求助块链

yizhiming @ 2023-02-02 21:52:17

by yizhiming @ 2023-02-02 21:52:25

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N =  605;
struct KL{
    int nxt,siz;bool flg;
    int val[N*2];
}node[N*4];
int pool[N*4],top;
int newnode(){
    return pool[top++];
} 
void del(int x){
    node[x].flg = 0;
    pool[--top] = x;
}
void init(){
    for(int i=1;i<4*N;i++){
        pool[i] = i;
    }
    top = 1;
    node[0].nxt = -1;
    node[0].siz = 0;
}
void add(int x,int y,int len,int a[]){
//  cout<<"ADD:"<<" "<<x<<" "<<node[x].nxt<<" "<<y<<" "<<node[y].nxt<<"\n";
    if(y!=-1){
        node[y].nxt = node[x].nxt;

        node[y].siz = len;
        for(int i=0;i<len;i++){
            node[y].val[i] = a[i];
        }
    }
    node[x].nxt = y;
}
int res[N*4];
void pushdown(int x){
    if(node[x].flg){
        node[x].flg = 0;
        for(int i=0;i<node[x].siz;i++){
            res[i] = node[x].val[i];
        }
        for(int i=0;i<node[x].siz;i++){
            node[x].val[i] = res[node[x].siz-1-i];
        }
    }
}
void merge(int x,int y){
    pushdown(x);pushdown(y);
    for(int i=0;i<node[y].siz;i++){
        node[x].val[i+node[x].siz] = node[y].val[i];
    }
    node[x].siz+=node[y].siz;
//  cout<<"XY"<<" "<<x<<" "<<node[x].nxt<<" "<<y<<" "<<node[y].nxt<<'\n';
    node[x].nxt = node[y].nxt;
//  cout<<"Z"<<" "<<x<<" "<<node[x].nxt<<" "<<y<<" "<<node[y].nxt<<'\n';
    del(y);
}
int pos(int &k){
    int now = 0;
    while(now!=-1&&node[now].siz<k){
        k-=node[now].siz;
        now = node[now].nxt; 
    }
    return now;
}
void split(int x,int pos){
    if(x==-1||pos==node[x].siz){
        return;
    }
    pushdown(x);
    add(x,newnode(),node[x].siz-pos,node[x].val+pos);
    node[x].siz = pos;
}
void mt(){
    int now = 0;
    while(node[now].nxt!=-1){
        if(node[now].siz+node[node[now].nxt].siz<N){
            merge(now,node[now].nxt);
        }else{
            now = node[now].nxt;
        }
    }
}
void ins(int x,int len,int a[]){
    int now = pos(x);
    split(now,x);
    int tot = 0,y=-1;
    while(tot+N<=len){
        y = newnode();
        add(now,y,N,a+tot);
        tot+=N;
        now = y;
    }
    if(len-tot){
        y = newnode();
        add(now,y,len-tot,a+tot);
    }
    mt();
//  if(y!=-1&&node[now].siz+node[y].siz<N){
//      merge(now,y);
//  }
//  if(node[u].nxt != -1&&node[u].siz+node[node[u].nxt].siz<N){
//      merge(u,node[u].nxt);
//  }
}
int sta[N*4];

void rev(int l,int r){
    int now1 = pos(l),now2 = pos(r); 
    if(now1==now2){
        pushdown(now1);
        for(int i=l;i<=r;i++){
            res[i] = node[now1].val[i]; 
        }
        for(int i=l;i<=r;i++){
            node[now1].val[i] = res[r-i+l];
        }
    }else{
        int cnt = 0;
        split(now1,l);
        int nxt = node[now1].nxt;
        split(now2,r);
        int end = node[now2].nxt;
        while(nxt!=now2&&nxt!=-1){
            sta[++cnt] = nxt;
            node[nxt].flg^=1;
            nxt = node[nxt].nxt;
        }
        sta[++cnt] = now2;
        node[now2].flg^=1;
        for(int i=cnt;i>=1;i--){
            int u = sta[i];
            node[now1].nxt = u;
            now1 = u;
        }
        node[now1].nxt = end;
        mt();
    }
}
void print(){
    int now = 0;
//  cout<<"Begin:\n";
    while(now!=-1){
        pushdown(now);
        for(int i=0;i<node[now].siz;i++){
            cout<<node[now].val[i]<<" ";
        } 
//      cout<<"NOw:"<<" "<<now<<" "<<node[now].nxt<<"\n";
        now = node[now].nxt;
    }
//  cout<<"\n";
}
const int SN = 1e5+5;
int n,m;
int a[SN];
int main(){
    init();
    n = read();m = read();
    for(int i=1;i<=n;i++){
        a[i-1] = i;
    }
    ins(0,n,a);
//  cout<<"Now:"<<0<<" "<<node[0].nxt<<"\n";
//  print();
    int l,r;
    while(m--){
        l = read()-1;r = read()-1;
        rev(l,r);
    }
    print();
    return 0;
}

by yizhiming @ 2023-04-04 11:07:32

破案了，我的伞兵 rev 会导致其他操作也需要一块反过来