三亚专业网站建设,网站建设维护多少钱,四川建设网有限责任公司是国企吗,蓝色大气企业网站题目链接 题目描述
您需要写一种数据结构#xff08;可参考题目标题#xff09;#xff0c;来维护一个有序数列。
其中需要提供以下操作#xff1a;翻转一个区间#xff0c;例如原有序序列是 543215\ 4\ 3\ 2\ 15 4 3 2 1#xff0c;翻转区间是 [2,4][2,4][2,4] 的话可参考题目标题来维护一个有序数列。
其中需要提供以下操作翻转一个区间例如原有序序列是 543215\ 4\ 3\ 2\ 15 4 3 2 1翻转区间是 [2,4][2,4][2,4] 的话结果是 523415\ 2\ 3\ 4\ 15 2 3 4 1。
输入格式
第一行两个正整数 n,mn,mn,m 表示序列长度与操作个数。序列中第 iii 项初始为 iii。 接下来 mmm 行每行两个正整数 l,rl,rl,r表示翻转的区间。
输出格式
输出一行 nnn 个正整数表示原始序列经过 mmm 次变换后的结果。
输入输出样例
输入 #1
5 3
1 3
1 3
1 4输出 #1
4 3 2 1 5说明/提示
对于 100%100\%100% 的数据1≤n,m≤1051≤l≤r≤n1 \le n, m \leq 10^51 \le l \le r \le n1≤n,m≤1051≤l≤r≤n。 Solution
模板题。
Code
FHQ Treap
#includecstdio
#includecstdlib
#includealgorithm
#includectime
using namespace std;
const int maxn1000020;
int n,m,root,tot;
struct FHQ{int lc,rc;int val,dat,siz,tag;
}tr[maxn];
inline int newnode(int v){tr[tot].siz1;tr[tot].valv;tr[tot].datrand();return tot;
}
inline void pushup(int u){tr[u].siztr[tr[u].lc].siztr[tr[u].rc].siz1;
}
inline void pushdown(int u){if(tr[u].tag){swap(tr[u].lc,tr[u].rc);tr[tr[u].lc].tag^1;tr[tr[u].rc].tag^1;tr[u].tag0;}
}
inline int merge(int x,int y){if(!x||!y)return xy;pushdown(x),pushdown(y);if(tr[x].dattr[y].dat){tr[x].rcmerge(tr[x].rc,y);pushup(x);return x;}else{tr[y].lcmerge(x,tr[y].lc);pushup(y);return y;}
}
inline void spilt(int u,int k,int x,int y){if(!u){xy0;return;}pushdown(u);if(ktr[tr[u].lc].siz)yu,spilt(tr[u].lc,k,x,tr[u].lc);elsexu,spilt(tr[u].rc,k-tr[tr[u].lc].siz-1,tr[u].rc,y);pushup(u);
}
inline int build(int l,int r){int mid(lr)1;int unewnode(mid);if(lmid)tr[u].lcbuild(l,mid-1);if(midr)tr[u].rcbuild(mid1,r);pushup(u);return u;
}
inline void rev(int l,int r){int a,b,c,d;spilt(root,l-1,a,b);spilt(b,r-l1,c,d);tr[c].tag^1;rootmerge(a,merge(c,d));
}
inline void print(int u){pushdown(u);if(tr[u].lc)print(tr[u].lc);if(tr[u].val1tr[u].valn)printf(%d ,tr[u].val);if(tr[u].rc)print(tr[u].rc);
}
int main(){srand(time(0));scanf(%d%d,n,m);rootbuild(0,n1);for(int i1;im;i){int l,r;scanf(%d%d,l,r);rev(l1,r1);}print(root);return 0;
}Splay
#includecstdio
#includealgorithm
const int maxn100010;
struct Splay{int val,son[2],fa,tag,siz;
}tr[maxn];
int n,m,tot,root;
inline void pushup(int u){tr[u].siztr[tr[u].son[0]].siztr[tr[u].son[1]].siz1;
}
inline void pushdown(int u){if(tr[u].tag){tr[tr[u].son[0]].tag^1;tr[tr[u].son[1]].tag^1;std::swap(tr[u].son[0],tr[u].son[1]);tr[u].tag0;}
}
inline int build(int l,int r,int fa){int utot;int mid(lr)1;tr[u].valmid;tr[u].fafa;if(lmid)tr[u].son[0]build(l,mid-1,u);if(midr)tr[u].son[1]build(mid1,r,u);pushup(u);return u;
}
inline void rotate(int x){int ytr[x].fa,ztr[y].fa;int ktr[y].son[1]x;tr[z].son[tr[z].son[1]y]x,tr[x].faz;tr[y].son[k]tr[x].son[k^1],tr[tr[x].son[k^1]].fay;tr[x].son[k^1]y,tr[y].fax;pushup(y),pushup(x);
}
inline void splay(int x,int goal){while(tr[x].fa!goal){int ytr[x].fa,ztr[y].fa;if(z!goal)tr[y].son[1]x^tr[z].son[1]y?rotate(x):rotate(y);rotate(x);}if(!goal)rootx;
}
inline int ask(int u,int rank){pushdown(u);if(tr[tr[u].son[0]].sizrank)return ask(tr[u].son[0],rank);else if(tr[tr[u].son[0]].siz1rank)return u;else return ask(tr[u].son[1],rank-tr[tr[u].son[0]].siz-1);
}
inline void print(int u){pushdown(u);if(tr[u].son[0])print(tr[u].son[0]);if(tr[u].val1tr[u].valn)printf(%d ,tr[u].val);if(tr[u].son[1])print(tr[u].son[1]);
}
int main(){scanf(%d%d,n,m);rootbuild(0,n1,0);while(m--){int l,r;scanf(%d%d,l,r);lask(root,l);rask(root,r2);splay(l,0);splay(r,l);if(tr[r].son[0])tr[tr[r].son[0]].tag^1;}print(root);return 0;
}
