vue 做网站,企业网络需求分析报告,包装设计公司浙江,公司网站做好了怎么做排名题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构#xff0c;来维护一个有序数列#xff0c;其中需要提供以下操作#xff1a;翻转一个区间#xff0c;例如原有序序列是5 4 3 2 1#xff0c;翻转区间是[2,4]的话#xff0c;结果是5 2 …题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构来维护一个有序数列其中需要提供以下操作翻转一个区间例如原有序序列是5 4 3 2 1翻转区间是[2,4]的话结果是5 2 3 4 1 输入输出格式 输入格式 第一行为n,m(n,m100000) n表示初始序列有n个数这个序列依次是(1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r][l,r] 数据保证 1 \leq l \leq r \leq n1≤l≤r≤n 输出格式 输出一行n个数字表示原始序列经过m次变换后的结果 输入输出样例 输入样例 5 3
1 3
1 3
1 4 输出样例 4 3 2 1 5splay模板题维护该序列的中序遍历不变然后每次通过旋转节点使操作的区间变作一颗字树然后打上标记即可。什么是splay?一棵伸展树......什么是伸展树最近刚学我个人的理解大概就是一个能在不破坏二叉搜索树结构(即中序遍历始终为升序)的情况下通过旋转一个节点到他根节点位置使得操作区间恰好全部位于一棵子树内的方法。然后就打上标记之后在类似线段树一样的pushdown传递信息就好了。代码如下 #includealgorithm
#includeiostream
#includecstring
#includecstdio
#includecmath
#define LL long long
#define mod
#define mid (RL1)
#define M 2000010
using namespace std;
LL read(){LL nm0,oe1;char cwgetchar();while(!isdigit(cw)) oecw-?-oe:oe,cwgetchar();while(isdigit(cw)) nmnm*10(cw-0),cwgetchar();return nm*oe;
}
LL n,m,l[M],r[M],tp[M],ad,sz[M],tg[M],ace,a,b,p,q,cnt;
bool flagfalse;
void pushdown(LL x){if(tg[x]0) return;tg[x]0,swap(l[x],r[x]);tg[l[x]]^1,tg[r[x]]^1;
}
void pushup(LL x){sz[x]sz[l[x]]sz[r[x]]1;}
LL build(LL L,LL R,LL rt){if(LR) return 0;tp[mid]rt,sz[mid]1;if(LR) return L;l[mid]build(L,mid-1,mid);r[mid]build(mid1,R,mid);sz[mid]sz[l[mid]]sz[r[mid]];return mid;
}
void rotate(LL x){if(acex) return;LL toptp[x];pushdown(top),pushdown(x);if(topace) acex,tp[x]n1,tp[top]x;else{if(l[tp[top]]top) l[tp[top]]x;else r[tp[top]]x;tp[x]tp[top],tp[top]x;}if(l[top]x) l[top]r[x],tp[r[x]]top,r[x]top;else r[top]l[x],tp[l[x]]top,l[x]top;pushup(top),pushup(x);
}
void oper(LL x){if(xace||tp[x]ace){return;}LL toptp[x];pushdown(top);if(tp[top]ace) rotate(x);else if(l[l[tp[top]]]x||r[r[tp[top]]]x) rotate(top);else rotate(x);
}
LL find(LL x,LL pos){pushdown(x);if(sz[l[x]]pos-1) return x;if(sz[l[x]]pos-1) return find(r[x],pos-sz[l[x]]-1);else return find(l[x],pos);
}
void ans(LL x){if(x0) return;pushdown(x);ans(l[x]);if(xnx1){if(flag) printf( );flagtrue;printf(%lld,x-1);}ans(r[x]);
}
int main(){nread()2,mread(),acebuild(1,n,n1);while(m--){aread(),bread();pfind(ace,a),qfind(ace,b2);while(tp[q]!aceq!ace) oper(q);if(q!ace) rotate(q);while(tp[p]!ace) oper(p);tg[r[p]]^1;}ans(ace);return 0;
} 我这里还是写的比较模糊我也是通过了解别人的博客才理解了splay 就是这个 - http://blog.csdn.net/skydec/article/details/20151805 转载于:https://www.cnblogs.com/OYJason/p/7887057.html
