首页 > 代码库 > 【Foreign】神秘物质 [Splay]
【Foreign】神秘物质 [Splay]
神秘物质
Time Limit: 10 Sec Memory Limit: 256 MBDescription
Input
Output
Sample Input
Sample Output
1
2
1
5
HINT
Main idea
每个点有一个权值，维护一个结构，支持合并相邻两点，删除单点，加入单点，查询区间子集极差的最大值和最小值。
Solution
首先我们可以发现，区间子集极差的最大值显然就是整个区间的最大值-区间最小值，然后区间子集极差最小值只有相邻点的才会产生贡献。
那么我们用Splay来维护这个结构即可，维护一下子树最大值、子树最小值、子树邻差最小值即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64; 10 11 const int ONE = 300005; 12 const int INF = 2147483640; 13 14 int n,m; 15 int x,y,a[ONE]; 16 int root,cnt; 17 int lc[ONE],rc[ONE],fa[ONE]; 18 int size[ONE],val[ONE]; 19 int maxx[ONE],minn[ONE],del[ONE]; 20 int Ls[ONE],Rs[ONE]; 21 char ch[10]; 22 23 inline int get() 24 { 25 int res=1,Q=1; char c; 26 while( (c=getchar())<48 || c>57) 27 if(c==‘-‘)Q=-1; 28 if(Q) res=c-48; 29 while((c=getchar())>=48 && c<=57) 30 res=res*10+c-48; 31 return res*Q; 32 } 33 34 void Up(int i) 35 { 36 size[i] = size[lc[i]] + size[rc[i]] + 1; 37 maxx[i] = minn[i] = val[i]; 38 del[i] = INF; 39 Ls[i] = Rs[i] = i; 40 if(lc[i]) 41 { 42 Ls[i] = Ls[lc[i]]; 43 maxx[i] = max(maxx[i], maxx[lc[i]]); 44 minn[i] = min(minn[i], minn[lc[i]]); 45 del[i] = min(del[i], del[lc[i]]); 46 del[i] = min(del[i], abs( val[i]-val[Rs[lc[i]]] ) ); 47 } 48 if(rc[i]) 49 { 50 Rs[i] = Rs[rc[i]]; 51 maxx[i] = max(maxx[i], maxx[rc[i]]); 52 minn[i] = min(minn[i], minn[rc[i]]); 53 del[i] = min(del[i], del[rc[i]]); 54 del[i] = min(del[i], abs( val[i]-val[Ls[rc[i]]] ) ); 55 } 56 } 57 58 void Turn(int x) 59 { 60 int y = fa[x], z = fa[y]; 61 int b = x==lc[y] ? rc[x]:lc[x]; 62 63 fa[y] = x; fa[x] = z; 64 if(b) fa[b] = y; 65 66 if(z) 67 { 68 if(y == lc[z]) lc[z] = x; 69 else rc[z] = x; 70 } 71 72 if(x==lc[y]) rc[x] = y,lc[y] = b; 73 else lc[x] = y, rc[y] = b; 74 75 Up(y); Up(x); 76 } 77 78 void Splay(int x,int pos) 79 { 80 while(fa[x] != pos) 81 { 82 if(fa[fa[x]] != pos) 83 { 84 if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]); 85 else Turn(x); 86 } 87 Turn(x); 88 } 89 if(pos == 0) root = x; 90 } 91 92 int Build(int i,int l,int r) 93 { 94 int mid = l+r >> 1; 95 fa[mid] = i; 96 if(l <= mid-1) lc[mid] = Build(mid, l,mid-1); 97 if(mid+1 <= r) rc[mid] = Build(mid, mid+1,r); 98 Up(mid); 99 return mid;100 }101 102 int Getid(int num)103 {104 int i = root;105 while(size[lc[i]] + 1 != num)106 {107 if(size[lc[i]] + 1 < num)108 num -= size[lc[i]] + 1, i = rc[i];109 else i = lc[i];110 }111 return i;112 }113 114 void Delete(int i)115 {116 int x = Getid(i);117 Splay(x, 0);118 int L = Rs[lc[x]]; Splay(L,0);119 int R = Ls[rc[x]]; Splay(R,L);120 lc[R] = 0;121 Splay(R,0);122 }123 124 void Insert(int i,int Val)125 {126 int x = Getid(i);127 Splay(x,0);128 int R = Ls[rc[x]]; Splay(R,x);129 val[++cnt] = Val; fa[cnt] = R; lc[R] = cnt;130 Splay(cnt,0);131 }132 133 int main()134 {135 n=get(); m=get();136 for(int i=1;i<=n;i++)137 val[i+1] = get();138 val[1] = val[n+2] = INF;139 140 cnt = n+2;141 root = n+3 >> 1;142 Build(0,1,n+2);143 144 while(m--)145 {146 scanf("%s",ch+1); x=get(); y=get();147 x++;148 149 if(ch[3] == ‘r‘)150 {151 Insert(x+1,y);152 Delete(x); Delete(x);153 }154 if(ch[3] == ‘s‘)155 Insert(x,y);156 if(ch[3] == ‘x‘)157 {158 y++;159 x = Getid(x-1); y = Getid(y+1);160 Splay(x,0); Splay(y,x);161 printf("%d\n", maxx[lc[y]] - minn[lc[y]]);162 }163 if(ch[3] == ‘n‘)164 {165 y++;166 x = Getid(x-1); y = Getid(y+1);167 Splay(x,0); Splay(y,x);168 printf("%d\n", del[lc[y]]);169 }170 171 }172 }
【Foreign】神秘物质 [Splay]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。