论如何让STL卡过

我是小何子啊 @ 2021-04-07 13:55:50

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,l,r,a[100001];
inline int read(){
    int x=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
inline void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i) a[i]=i;
    for(register int i=1;i<=m;++i){
        l=read(),r=read();
        reverse(a+l,a+r+1);
    }
    for(register int i=1;i<=n;++i) write(a[i]),putchar(' ');
    exit(0);
}

by oisdoaiu @ 2021-04-07 14:00:18

@我是小何子啊 这要能卡过就奇怪了吧..

by SSH_automaton @ 2021-04-07 14:03:17

@我是小何子啊 这复杂度不是假的吗，O(nm) 能过？

by xzggzh1 @ 2021-04-07 14:10:22

@我是小何子啊

别论了，复杂度不对，reverse 是 \mathcal O(n) 的，相当于暴力翻转。

by PrincessQi @ 2021-04-07 14:18:48

vector 可能可以？

by _LHF_ @ 2021-04-07 14:33:17

@我是小何子啊 哦哟，reverse的时间复杂度明明是 O(n) 的，做 m 次理论时间复杂度是 O(nm)，如果连这都能过，那只能说明数据太水了。

by lcyxds @ 2021-04-07 14:43:34

@我是小何子啊 卡不过的

数组整体移动速度很快但是这个不是数组整体移动所以速度较慢，n方过1e4估计可以1e5不太可能了

所以水过普通平衡树是绰绰有余的，文艺平衡树不行

by 我是小何子啊 @ 2021-04-08 12:22:39

谢谢各位dalao们，看来只能认真学习Splay了orz

by 聊机 @ 2021-04-09 17:40:54

@我是小何子啊 我之前试过测试记录

帖子

by littlefrog @ 2021-04-22 20:06:07

@我是小何子啊 reverse是 的，你这么做和暴力翻转每一个区间没什么区别，甚至有时候STL还不如手写暴力反转

by RedLycoris @ 2021-04-30 21:45:17

@我是小何子啊 STL里的rope可以卡过