您需要写一种数据结构&＃xff08;可参考题目标题&＃xff09;&＃xff0c;来维护一个有序数列&＃xff0c;其中需要提供以下操作&＃xff1a;翻转一个区间&＃xff0c;例如原有序序列是5 4 3 2 1&＃xff0c;翻转区间是[2,4]的话&＃xff0c;结果是5 2 3 4 1
N,M<&＃61;100000
Sample Output4 3 2 1 5 Hint
第一行为n,m n表示初始序列有n个数&＃xff0c;这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<&＃61;l<&＃61;r<&＃61;n
输出一行n个数字&＃xff0c;表示原始序列经过m次变换后的结果
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include//#pragma GCC optimize(2)//#include//#pragma GCC optimize("O3")using namespace std;#define maxn 100005#define inf 0x3f3f3f3f#define INF 9999999999#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod &＃61; 1e9 &＃43; 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-3typedef pair pii;#define pi acos(-1.0)//const int N &＃61; 1005;#define REP(i,n) for(int i&＃61;0;i<(n);i&＃43;&＃43;)inline ll rd() {ll x &＃61; 0;char c &＃61; getchar();bool f &＃61; false;while (!isdigit(c)) {if (c &＃61;&＃61; &＃39;-&＃39;) f &＃61; true;c &＃61; getchar();}while (isdigit(c)) {x &＃61; (x <<1) &＃43; (x <<3) &＃43; (c ^ 48);c &＃61; getchar();}return f ? -x : x;}ll gcd(ll a, ll b) {return b &＃61;&＃61; 0 ? a : gcd(b, a%b);}ll sqr(ll x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x &＃61; 1; y &＃61; 0; return a;}ans &＃61; exgcd(b, a%b, x, y);ll t &＃61; x; x &＃61; y; y &＃61; t - a / b * y;return ans;}*/ll qpow(ll a, ll b, ll c) {ll ans &＃61; 1;a &＃61; a % c;while (b) {if (b % 2)ans &＃61; ans * a%c;b /&＃61; 2; a &＃61; a * a%c;}return ans;}struct splay {int fa, ch[2], size;int lazy, rev, maxx, value;}Sp[maxn];int n, m, root, a[maxn];void pushup(int rt) {Sp[rt].size &＃61; Sp[Sp[rt].ch[0]].size &＃43; Sp[Sp[rt].ch[1]].size &＃43; 1;Sp[rt].maxx &＃61; max(Sp[rt].value, max(Sp[Sp[rt].ch[0]].maxx, Sp[Sp[rt].ch[1]].maxx));}void pushdown(int rt) {if (Sp[rt].lazy) {if (Sp[rt].ch[0]) {Sp[Sp[rt].ch[0]].lazy &＃43;&＃61; Sp[rt].lazy;Sp[Sp[rt].ch[0]].maxx &＃43;&＃61; Sp[rt].lazy;Sp[Sp[rt].ch[0]].value &＃43;&＃61; Sp[rt].lazy;}if (Sp[rt].ch[1]) {Sp[Sp[rt].ch[1]].lazy &＃43;&＃61; Sp[rt].lazy;Sp[Sp[rt].ch[1]].maxx &＃43;&＃61; Sp[rt].lazy;Sp[Sp[rt].ch[1]].value &＃43;&＃61; Sp[rt].lazy;}Sp[rt].lazy &＃61; 0;}if (Sp[rt].rev) {if (Sp[rt].ch[0]) {Sp[Sp[rt].ch[0]].rev ^&＃61; 1;swap(Sp[Sp[rt].ch[0]].ch[0], Sp[Sp[rt].ch[0]].ch[1]);}if (Sp[rt].ch[1]) {Sp[Sp[rt].ch[1]].rev ^&＃61; 1;swap(Sp[Sp[rt].ch[1]].ch[0], Sp[Sp[rt].ch[1]].ch[1]);}Sp[rt].rev &＃61; 0;}}int id(int x) {return Sp[Sp[x].fa].ch[1] &＃61;&＃61; x;}void link(int son, int fa, int k) {Sp[son].fa &＃61; fa; Sp[fa].ch[k] &＃61; son;}void rotate(int x) {int y &＃61; Sp[x].fa;int z &＃61; Sp[y].fa;int yk &＃61; id(x);int zk &＃61; id(y);int b &＃61; Sp[x].ch[yk ^ 1];link(b, y, yk); link(y, x, yk ^ 1);link(x, z, zk);pushup(y); pushup(x);}void SPLAY(int x, int aim) {while (Sp[x].fa !&＃61; aim) {int y &＃61; Sp[x].fa;int z &＃61; Sp[y].fa;if (z !&＃61; aim)id(x) &＃61;&＃61; id(y) ? rotate(y) : rotate(x);rotate(x);}if (aim &＃61;&＃61; 0)root &＃61; x;}int kth(int k) {int now &＃61; root;while (1) {pushdown(now);int left &＃61; Sp[now].ch[0];if (Sp[left].size &＃43; 1 &＃61; k)now &＃61; left;else return now;}}int build(int l, int r, int fa) {if (l > r)return 0;if (l &＃61;&＃61; r) {Sp[l].fa &＃61; fa; Sp[l].maxx &＃61; Sp[l].value &＃61; a[l];Sp[l].size &＃61; 1; return l;}int mid &＃61; (l &＃43; r) >> 1;Sp[mid].ch[0] &＃61; build(l, mid - 1, mid);Sp[mid].ch[1] &＃61; build(mid &＃43; 1, r, mid);Sp[mid].value &＃61; a[mid];Sp[mid].fa &＃61; fa;pushup(mid);return mid;}int split(int l, int r) {l &＃61; kth(l); r &＃61; kth(r &＃43; 2);SPLAY(l, 0); SPLAY(r, l);return Sp[Sp[root].ch[1]].ch[0];}void upd(int l, int r, int v) {int now &＃61; split(l, r);Sp[now].lazy &＃43;&＃61; v; Sp[now].maxx &＃43;&＃61; v; Sp[now].value &＃43;&＃61; v;pushup(Sp[root].ch[1]); pushup(root);}void Reverse(int l, int r) {int now &＃61; split(l, r);Sp[now].rev ^&＃61; 1;swap(Sp[now].ch[0], Sp[now].ch[1]);pushup(Sp[root].ch[1]); pushup(root);}int query(int l, int r) {return Sp[split(l, r)].maxx;}void dfs(int rt) {pushdown(rt);if (Sp[rt].ch[0])dfs(Sp[rt].ch[0]);if (Sp[rt].value !&＃61; inf && Sp[rt].value !&＃61; -inf) {cout <}int main(){//ios::sync_with_stdio(0);rdint(n); rdint(m);for (int i &＃61; 2; i <&＃61; n &＃43; 1; i&＃43;&＃43;)a[i] &＃61; i - 1;a[1] &＃61; -inf; a[n &＃43; 2] &＃61; inf;root &＃61; build(1, n &＃43; 2, 0);while (m--) {int l, r; rdint(l); rdint(r);Reverse(l, r);}dfs(root); cout <}
转:https://www.cnblogs.com/zxyqzy/p/10073020.html
京公网安备 11010802041100号