中英文网站源码 免费,中高风险区域最新名单,个体户营业执照科研做企业网站吗,动漫网站设计方案正题
题目连接:https://www.luogu.org/problemnew/show/P3391 题目大意
一个序列#xff0c;m个操作翻转[l..r][l..r][l..r]区间。求最终序列 解题思路
节点维护编号#xff0c;然后答案就是中序遍历。然后翻转的话我们先考虑一个性质。 若这是初始状态(l-1和r1反了) 然后…正题
题目连接:https://www.luogu.org/problemnew/show/P3391 题目大意
一个序列m个操作翻转[l..r][l..r][l..r]区间。求最终序列 解题思路
节点维护编号然后答案就是中序遍历。然后翻转的话我们先考虑一个性质。 若这是初始状态(l-1和r1反了) 然后将l-1旋到根节点将r1选到根的右节点 然后l∼rl\sim rl∼r就是一个单独的子树可以自己翻转。 但这里不翻转先因为最终只有一次询问所以我们可以用延迟标记。 codecodecode
#includecstdio
#includealgorithm
#define INF 2100000000
#define N 100010
using namespace std;
struct splay{int v[N],father[N],root;int l[N],r[N];int sum[N],mark[N];int n,points;void Updata(int x){sum[x]sum[l[x]]sum[r[x]]1;}void Downdata(int x){if(mark[x]){mark[l[x]]^1;mark[r[x]]^1;mark[x]0;swap(l[x],r[x]);}}void New(int x,int vs,int fa){l[x]r[x]0;sum[x]1;v[x]vs;father[x]fa;}void Rotate(int x){int yfather[x];int zfather[y];int kr[y]x;if(r[z]y) r[z]x;else l[z]x;father[x]z;if(k) r[y]l[x];else l[y]r[x];father[k?l[x]:r[x]]y;if(k) l[x]y;else r[x]y;father[y]x;Updata(y);Updata(x);}void Splay(int at,int to){while(father[at]!to){int yfather[at];int zfather[y];if(z!to)(r[z]y)^(r[z]at)?Rotate(at):Rotate(y);Rotate(at);}if(to0)rootat;}void Insert(int x){int nowroot,ff0;while(now)ffnow,now(xv[now]?r[now]:l[now]);nown;if(ffxv[now]) r[ff]now;else if(ff) l[ff]now;New(now,x,ff);Splay(now,0);}int GetValByRank(int k){int nowroot;while(1){Downdata(now);if(sum[l[now]]k) nowl[now];else if(sum[l[now]]1k) return now;else k-sum[l[now]]1,nowr[now];}}void Work(int ls,int rs){lsGetValByRank(ls);rsGetValByRank(rs2);Splay(ls,0);Splay(rs,ls);mark[l[r[root]]]^1;}void Write(int x,int mn){Downdata(x);if(l[x]) Write(l[x],mn);if(v[x]1v[x]mn2) printf(%d ,v[x]-1);if(r[x]) Write(r[x],mn);}
}a;
int main(){//freopen(testdata.in,r,stdin);//freopen(data.out,w,stdout);int n,m;scanf(%d%d,n,m);for(int i1;in2;i)a.Insert(i);while(m--){int l,r;scanf(%d%d,l,r);a.Work(l,r);}a.Write(a.root,n);
}
