首页 > 代码库 > BZOJ3678: wangxz与OJ
BZOJ3678: wangxz与OJ
3678: wangxz与OJ
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 123 Solved: 23
[Submit][Status]
Description
某天，wangxz神犇来到了一个信息学在线评测系统(Online Judge)。由于他是一位哲♂学的神犇，所以他不打算做题。他发现这些题
目呈线性排列，被标记为1~n号，每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。
1、他可以在某个位置插♂入一些难度值特定的题目。
2、他可以吃♂掉(删除)一段题目。
3、他可以查询某个位置的题目的难度值。
维护一个初始有n个元素的序列(标记为1~n号元素)，支持以下操作：
0 p a b (0<=p<=当前序列元素个数) (a<=b) 在p位置和p+1位置之间插入整数:a,a+1,a+2,...,b-1,b。若p为0，插在序列最前面;
1 a b (1<=a<=b<=当前序列元素个数) 删除a,a+1,a+2,...,b-1,b位置的元素;
2 p (1<=p<=当前序列元素个数) 查询p位置的元素。
Input
输入第一行包括两个正整数n(1<=n<=20000),m(1<=m<=20000),代表初始序列元素个数和操作个数。
接下来n个整数,为初始序列元素。
接下来m行,每行第一个为整数sym,
若sym=0,接下来有一个非负整数p,两个整数a,b;
若sym=1,接下来有两个正整数a,b;
若sym=2,接下来有一个正整数p;
p、x、y的含义及范围见题目描述。
在任何情况下，保证序列中的元素总数不超过100000。
保证题目涉及的所有数在int内。
Output
对每个sym=2，输出一行，包括一个整数，代表询问位置的元素。
Sample Input
5 3
1 2 3 4 5
0 2 1 4
1 3 8
2 2
1 2 3 4 5
0 2 1 4
1 3 8
2 2
Sample Output
2
HINT
Source
From LiZitong
题解：
以前刚学splay的时候写过暴力加入每个点，然后喜闻乐见的T了。。。
如果每个节点代表一个区间，v[x][0]和v[x][1]分别表示左端点和右端点，查询时需要分裂的时候再分裂。
那么pushup函数是这样
View Code
以前刚学splay的时候写过暴力加入每个点，然后喜闻乐见的T了。。。
如果每个节点代表一个区间，v[x][0]和v[x][1]分别表示左端点和右端点，查询时需要分裂的时候再分裂。
那么pushup函数是这样
inline void pushup(int x){ s[x]=s[c[x][0]]+s[c[x][1]]+v[x][1]-v[x][0]+1;}
然后我们发现其他的都一样，比较麻烦的是find函数的编写：
inline int find(int x,int k){ if(s[c[x][0]]>=k)return find(c[x][0],k); else if(s[x]-s[c[x][1]]<k)return find(c[x][1],k-s[x]+s[c[x][1]]); else { k-=s[c[x][0]]; if(k!=1) { fa[c[++tot][0]=c[x][0]]=tot;fa[c[x][0]=tot]=x; v[tot][0]=v[x][0];v[tot][1]=v[x][0]+k-2;v[x][0]=v[tot][1]+1; pushup(tot); k=1; } if(k!=v[x][1]-v[x][0]+1) { fa[c[++tot][1]=c[x][1]]=tot;fa[c[x][1]=tot]=x; v[tot][1]=v[x][1];v[tot][0]=v[x][0]+k;v[x][1]=v[tot][0]-1; pushup(tot); } return x; }}
这样写有效的处理了边界情况
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1000000+5 26 27 #define maxm 20000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,t1,t2,rt,tot,fa[maxn],c[maxn][2],s[maxn],v[maxn][2]; 61 int a[20]; 62 inline void pushup(int x) 63 { 64 s[x]=s[c[x][0]]+s[c[x][1]]+v[x][1]-v[x][0]+1; 65 } 66 inline void rotate(int x,int &k) 67 { 68 int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 69 if(y!=k)c[z][c[z][1]==y]=x;else k=x; 70 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 71 c[y][l]=c[x][r];c[x][r]=y; 72 pushup(y);pushup(x); 73 } 74 inline void splay(int x,int &k) 75 { 76 while(x!=k) 77 { 78 int y=fa[x],z=fa[y]; 79 if(y!=k) 80 { 81 if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 82 } 83 rotate(x,k); 84 } 85 } 86 inline int find(int x,int k) 87 { 88 89 if(s[c[x][0]]>=k)return find(c[x][0],k); 90 else if(s[x]-s[c[x][1]]<k)return find(c[x][1],k-s[x]+s[c[x][1]]); 91 else 92 { 93 k-=s[c[x][0]]; 94 if(k!=1) 95 { 96 fa[c[++tot][0]=c[x][0]]=tot;fa[c[x][0]=tot]=x; 97 v[tot][0]=v[x][0];v[tot][1]=v[x][0]+k-2;v[x][0]=v[tot][1]+1; 98 pushup(tot); 99 k=1;100 }101 if(k!=v[x][1]-v[x][0]+1)102 {103 fa[c[++tot][1]=c[x][1]]=tot;fa[c[x][1]=tot]=x;104 v[tot][1]=v[x][1];v[tot][0]=v[x][0]+k;v[x][1]=v[tot][0]-1;105 pushup(tot);106 }107 return x;108 }109 }110 inline void split(int l,int r)111 {112 t1=find(rt,l);113 t2=find(rt,r);114 splay(t1,rt);splay(t2,c[t1][1]);115 }116 inline void build(int l,int r,int f)117 {118 if(l>r)return;119 int x=(l+r)>>1;120 fa[x]=f;c[f][x>f]=x;121 if(l==r){s[x]=1;return;}122 build(l,x-1,x);build(x+1,r,x);123 pushup(x);124 }125 126 int main()127 128 {129 130 freopen("input.txt","r",stdin);131 132 freopen("output.txt","w",stdout);133 134 n=read();m=read();135 for2(i,2,n+1)v[i][0]=v[i][1]=read();136 build(1,n+2,0);rt=(1+n+2)>>1;tot=n+2;137 while(m--)138 {139 int ch=read();//cout<<ch<<endl;140 if(!ch)141 {142 int p=read(),x=read(),y=read();143 split(p+1,p+2);144 fa[c[t2][0]=++tot]=t2;v[tot][0]=x;v[tot][1]=y;s[tot]=y-x+1;145 pushup(t2);pushup(t1);146 }else if(ch==1)147 {148 int x=read(),y=read();149 split(x,y+2);150 c[t2][0]=0;151 pushup(t2);pushup(t1);152 }else printf("%d\n",v[find(rt,read()+1)][0]);153 }154 155 return 0;156 157 }
BZOJ3678: wangxz与OJ
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。