这个可以认为是 rope 的 bug 吗?

P3391 【模板】文艺平衡树

蒟酱 @ 2023-04-01 07:54:22

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<tuple>
#include<ctime>
#include<random>
#include<ext/rope>
#if __cplusplus>=202002L
#include<ranges>
namespace vw=std::views;
#endif
struct _time{~_time(){std::cerr<<"\n\033[33;40m"<<1.*clock()/CLOCKS_PER_SEC<<"s\033[37;40m";}}_TM;
#define siz(x) int((x).size())
#define cauto const auto
#define elif else if
#define all(x) std::begin(x),std::end(x)
#define rall(x) std::rbegin(x),std::rend(x)
#define sqrt __builtin_sqrt
#define fi first
#define se second
#define continue(x...) {x;continue;}
#define break(x...) {x;break;}
using std::cin;using std::cout;
using std::max;using std::min;
using std::tie;using std::ignore;
template<typename any>constexpr any&cmin(any&x,const any&y){if(y<x)x=y;return x;}
template<typename any>constexpr any&cmax(any&x,const any&y){if(x<y)x=y;return x;}
template<typename any,typename...args>constexpr any&cmin(any&x,const any&y,const args&...z){if(y<x)x=y;return cmin(x,z...);}
template<typename any,typename...args>constexpr any&cmax(any&x,const any&y,const args&...z){if(x<y)x=y;return cmax(x,z...);}
using loli=long long;
using unt=unsigned;
using lolu=unsigned long long;
using lodb=long double;
using venti=__int128_t;
using pii=std::pair<int,int>;
using tiii=std::tuple<int,int,int>;
using inlsi=const std::initializer_list<int>&;
using bsi=std::basic_string<int>;
using bsl=std::basic_string<loli>;
using bsc=std::string;
using std::operator""s;
#if __cplusplus>=201703L
using bscv=std::string_view;
using std::operator""sv;
#endif
std::mt19937 rng(std::random_device{}());
#define type std::pair<T1,T2>
template<typename T1,typename T2>std::istream&operator>>(std::istream&x,type&y){return x>>y.fi>>y.se;}
template<typename T1,typename T2>std::ostream&operator<<(std::ostream&x,const type&y){return x<<y.fi<<' '<<y.se;}
template<typename T1,typename T2>type operator+(const type&x,const type&y){return{x.fi+y.fi,x.se+y.se};}
template<typename T1,typename T2>type operator+=(type&x,const type&y){x.fi+=y.fi;x.se+=y.se;return x;}
template<typename T1,typename T2>type operator-(const type&x,const type&y){return{x.fi-y.fi,x.se-y.se};}
template<typename T1,typename T2>type operator-=(type&x,const type&y){x.fi-=y.fi;x.se-=y.se;return x;}
#undef type
template<typename any>any get(std::istream&x=cin){any y;x>>y;return y;}
template<typename any>any&STLcls(any &x){any{}.swap(x);return x;}
constexpr venti operator""_vt(lolu x){return venti(x);}
constexpr bool ying=false,yang=true;
namespace cxx=__gnu_cxx;
cxx::rope<int>b1,b2;
int n,m;
void rev(int l,int r){
    r++;
    // auto t=b1.substr(l+b1.begin(),r+b1.begin());
    // b1=b1.substr(0+b1.begin(),l+b1.begin())+b2.substr(n-r+b2.begin(),n-l+b2.begin())+b1.substr(r+b1.begin(),siz(b1)+b1.begin());
    // b2=b2.substr(0+b2.begin(),n-r+b2.begin())+t+b2.substr(n-l,siz(b2));
    auto t=b1.substr(l,r);
    b1=b1.substr(0,l)+b2.substr(n-r,n-l)+b1.substr(r,siz(b1));
    b2=b2.substr(0,n-r)+t+b2.substr(n-l,siz(b2));
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)b1+=i,b2+=n-i+1;
    for(int l,r;m--;)cin>>l>>r,rev(l-1,r-1);
    for(int i:b1)cout<<i<<' ';
    return 0; 
}

注释的那几行代码和下面的结果不同,可是按理说他们的效果是一样的


by 蒟酱 @ 2023-04-01 09:06:06

@ud2_


by ud2_ @ 2023-04-01 09:17:11

rope::substr 的重载分别是

rope substr(size_type 起始下标, size_type 长度 = 1) const;
rope substr(iterator 起始位置, iterator 终止位置) const;
rope substr(iterator 起始位置) const;
rope substr(const_iterator 起始位置, const_iterator 终止位置) const;
rope substr(const_iterator 起始位置); // 不知道为什么这里没有 const

接受下标时第二个参数是长度,而接受迭代器时第二个参数是终止位置。


by 蒟酱 @ 2023-04-01 09:27:03

thanks~


|