关键词:
【题目分析】
模板题目。
首尾两个虚拟结点,十分方便操作。
【代码】
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <queue> #include <string> #include <iostream> #include <algorithm> using namespace std; #define maxn 500005 #define inf 0x3f3f3f3f #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define L ch[o][0] #define R ch[o][1] void Finout() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); #endif } int Getint() { int x=0,f=1; char ch=getchar(); while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m; struct Bit_Tree{ int a[maxn],b[maxn]; void add(int x,int y,int z) { for (int i=x;i<=n;i+=i&(-i)) b[i]+=z; for (int i=y+1;i<=n;i+=i&(-i)) b[i]-=z; for (int i=x;i<=n;i+=i&(-i)) a[i]+=(n-x)*z; for (int i=y+1;i<=n;i+=i&(-i)) a[i]-=(n-y-1)*z; } int getsum(int x) { int ret=0,tmp=0; for (int i=x;i;i-=i&(-i)) ret+=a[i]; for (int i=x;i;i-=i&(-i)) tmp+=b[i]; return ret-(n-x-1)*tmp; } void init() { memset(a,0,sizeof a); memset(b,0,sizeof b); } }t; int rt=0,a[maxn],s,T,id[maxn],cnt=0; char opt[10]; int num[maxn],ch[maxn][2],siz[maxn],fa[maxn],list[maxn]; void update(int o) { siz[o]=siz[L]+siz[R]+1; } void rot(int x,int &k) { // cout<<"rot"<<x<<endl; int y=fa[x],z=fa[y],l,r; if (ch[y][0]==x) l=0; else l=1; r=l^1; if (y==k) k=x; else { if (ch[z][0]==y) ch[z][0]=x; else ch[z][1]=x; } fa[x]=z; fa[y]=x; fa[ch[x][r]]=y; ch[y][l]=ch[x][r]; ch[x][r]=y; update(y); update(x); } void splay(int x,int &k) { int y,z; while (x!=k) { y=fa[x];z=fa[y]; if (y!=k) { if ((ch[z][0]==y)^(ch[y][0]==x)) rot(x,k); else rot(y,k); } rot(x,k); } } void ins(int & o,int x,int lst) { if (!o) { o=++cnt; fa[o]=lst; num[o]=x; siz[o]=1; list[o]=a[x-1]; splay(o,rt); return ; } if (x<num[o]) ins(ch[o][0],x,o); else ins(ch[o][1],x,o); update(o); } int find(int o,int x) { // cout<<"qnum"<<num[o]<<" "<<x<<endl; if (siz[L]+1==x) return o; if (siz[L]>=x) return find(L,x); else return find(R,x-siz[L]-1); } void print(int o) { if (!o) return ; print(L); // cout<<"now is "<<o<<endl; // cout<<L<<" "<<R<<endl; // cout<<num[o]<<" "<<siz[o]<<endl; cout<<num[o]<<" "; print(R); } void Mov(int o,int k) { splay(o,rt); int pre=find(rt,siz[L]),nxt=find(rt,siz[L]+2); splay(pre,rt); splay(nxt,ch[rt][1]); ch[nxt][0]=0; fa[o]=0; update(nxt); update(pre); splay(nxt,rt); pre=find(rt,k-1);nxt=find(rt,k); splay(pre,rt); splay(nxt,ch[rt][1]); ch[nxt][0]=o; fa[o]=nxt; splay(o,rt); } int main() { Finout(); scanf("%d%d",&n,&m); F(i,1,n) scanf("%d",&a[i]),id[a[i]]=i+1; F(i,0,n+1) ins(rt,i,0); // print(rt); // cout<<rt<<endl; F(i,1,m) { // print(rt); // cout<<endl; scanf("%s",opt); scanf("%d",&s); if (opt[0]==‘Q‘) { // cout<<"QUERY"<<endl; printf("%d ",a[find(rt,s+1)-1]); } else if (opt[0]==‘A‘) { // cout<<"ASK"<<endl; splay(id[s],rt); printf("%d ",siz[ch[rt][0]]-1); } else if (opt[0]==‘T‘) { // cout<<"TOP"<<endl; Mov(id[s],1+1); } else if (opt[0]==‘B‘) { // cout<<"BOT"<<endl; Mov(id[s],n+1); } else { T=Getint(); splay(id[s],rt); int tmp=siz[ch[rt][0]]; Mov(id[s],tmp+T+1); } } }
[bzoj1861][zjoi2006]book书架
[BZOJ1861][Zjoi2006]Book书架试题描述小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一... 查看详情
bzoj1861[zjoi2006]book书架
1#include<bits/stdc++.h>2usingnamespacestd;3constintN=8e4+5;4constintinf=1e9;5intfa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;6voidupdate(intx)7{8size[x]=size[c[x][0]]+size[c[x][1]]+1;9}10voidr 查看详情
bzoj1861:[zjoi2006]book书架
这题想写三次了。结果前两次太困╯﹏╰没写成,大数据结构题就是烦人啊。没什么值得注意的,就按题意一步步来吧。(写了map表示对应树上位置,担心编号大爆掉,不加好像也没啥关系)#include<cstdio>#include<iostream>#i... 查看详情
bzoj1861[zjoi2006]book书架——splay
【题目分析】 模板题目。 首尾两个虚拟结点,十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情
bzoj1861:[zjoi2006]book书架splay
1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[题解]bzoj1861book书架-splay
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到 查看详情
bzoj1861:[zjoi2006]书架——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1861(题面复制于洛谷)题目描述小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一... 查看详情
[bzoj1861][zjoi2006]书架
BZOJLuoguDescription小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太... 查看详情
[zjoi2006]book书架
pre.cjk{font-family:"DroidSansFallback",monospace}p{margin-bottom:0.25cm;line-height:120%}a:link{}1861:[Zjoi2006]Book书架TimeLimit:4Sec MemoryLimit:64MBSubmit:1581 Solved:884[Submi 查看详情
bzoj1861:[zjoi2006]book书架(平衡树)(代码片段)
原题链接题目描述:小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些... 查看详情
1861.[zjoi2006]书架平衡树-splay(代码片段)
Description小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[zjoi2006]书架(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树 时间复杂度:O(MlogN)[代码] &n 查看详情
[zjoi2006]book书架(代码片段)
DescriptionSally有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
「luogu2596」[zjoi2006]书架(代码片段)
用平衡树维护每本书的位置1#include<bits/stdc++.h>2usingnamespacestd;3constintN=80010;4intn,m,maxpos,minpos,book[N<<2],bookpos[N];5introot,fa[N<<2],ch[N<<2][2],siz[N<<2],pos[N<<2 查看详情
bzoj1861书架splay版
单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情
bzoj1861书架(代码片段)
题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1,就把x从平衡树中删掉,然后将其权值变为最小值,重新插入。操作2,与操作1类似,只要将其权值变为最大值再重新插入就行了。操作3,其... 查看详情