当前位置：网站首页>bzoj5063 旅游

bzoj5063 旅游

2022-08-08 16:23:00 【51CTO】

( http://www.elijahqi.win/2018/01/23/bzoj5063-%E6%97%85%E6%B8%B8/%20%E2%80%8E)
Description
小奇成功打开了大科学家的电脑。
大科学家打算前往n处景点旅游，他用一个序列来维护它们之间的顺序。初
始时，序列为1,2,…,n。
接着，大科学家进行m次操作来打乱顺序。每次操作有6步：
1、从序列开头（左端）取出A个数（此时序列剩下n-A个数）
2、从序列开头取出B个数
3、将第1步取出的A个数按原顺序放回序列开头
4、从序列开头取出C个数
5、将第2步取出的B个数逆序放回序列开头
6、将第4步取出的C个数按原顺序放回序列开头
你需要求出最终序列。
Input
第一行两个数n,m。接下来m行，每行三个数A,B,C。
n,m<=100000
Output
输出一行n个数表示最终序列。
Sample Input
10 2
6 2 2
5 3 6
Sample Output
1 2 8 7 3 9 6 5 4 10
这题卡常..
我试着卡了卡常数还差一点就T了说明蒟蒻我好菜呀
拿到题目算一算数据范围常数大的我直接T飞了那怎么搞再看一看题目的要求推导一下题目要求的操作发现哦原来可以化简成两个操作 1、把a+1~a+b一段取出来反转然后在把序列在c后面拆开重新把反转后的放入即可搜了搜题解：发现？结构体比数组快一倍？orzqwq我好菜呀

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 110000
       
using namespace std;
       
inline char gc(){
       
    static char now[1<<16],*S,*T;
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
    return *S++;
       
}
       
inline int read(){
       
    int x=0;char ch=gc();
       
    while(ch<'0'||ch>'9') ch=gc();
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
    return x;
       
}
       
int c[N][2],size[N],fa[N],v[N],rev[N],n,m,root;
       
inline void update(int x){
       
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
       
}
       
inline void build(int f,int l,int r){
       
    if (l>r) return;
       
    int mid=l+r>>1;c[f][mid>f]=mid;fa[mid]=f;v[mid]=mid-1;
       
    if (l==r){size[l]=1;return;}
       
    build(mid,l,mid-1);build(mid,mid+1,r);update(mid);
       
}
       
inline void pushdown(int x){
       
    if (!rev[x]) return;
       
    int l=c[x][0],r=c[x][1];
       
    rev[l]^=1;rev[r]^=1;rev[x]=0;
       
    swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);
       
}
       
inline int find(int x,int sz){
       
    pushdown(x);int l=c[x][0],r=c[x][1];
       
    if (size[l]+1==sz) return x;
       
    if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);
       
}
       
inline void rotate(int x,int &tar){
       
    int y=fa[x],z=fa[y];
       
    if (y==tar) tar=x;else c[z][c[z][1]==y]=x;
       
    int l=c[y][1]==x,r=l^1;
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
}
       
inline void splay(int x,int &tar){
       
    while(x!=tar){
       
        int y=fa[x],z=fa[y];
       
        if (y!=tar){
       
            if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar);
       
        }rotate(x,tar);
       
    }
       
}
       
inline int split(int x,int y){
       
    int xx=find(root,x),yy=find(root,y);
       
    splay(yy,root);splay(xx,c[root][0]);return c[xx][1];
       
}
       
inline void print(int x){
       
    pushdown(x);if (c[x][0]) print(c[x][0]);
       
    if (v[x]!=0&&v[x]!=n+1)printf("%d ",v[x]);
       
    if (c[x][1]) print(c[x][1]);
       
}
       
int main(){
       
    freopen("bzoj5063.in","r",stdin);
       
    n=read();m=read();build(0,1,n+2);root=n+3>>1;
       
    for (int i=1;i<=m;++i){
       
        int a=read(),b=read(),cc=read();
       
        int tmp=split(a+1,a+b+2),f=fa[tmp];c[f][1]=0;update(f);update(fa[f]);
       
        int xx=find(root,cc+1),yy=find(root,cc+2);splay(yy,root);splay(xx,c[root][0]);
       
        rev[tmp]^=1;swap(c[tmp][0],c[tmp][1]);c[xx][1]=tmp;fa[tmp]=xx;update(xx);update(root);
       
    }print(root);
       
    return 0;
       
}
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5556242

当前位置：网站首页>bzoj5063 旅游

bzoj5063 旅游

边栏推荐

猜你喜欢

随机推荐