首页 > 代码库 > [模板]洛谷T2042 NOI2005 维护数列 Splay
[模板]洛谷T2042 NOI2005 维护数列 Splay
PS：某大佬讲，当心情特别好or特别不好的时候，可以来攻略这个题。。。果然萌新足足被这题恶心了半个月。。。
进入正题：
这道题题意如此之裸-Splayの究极进化，那么就没有什么好讲的，直接说搞法好了。。。
为了代码写起来方便，萌新封装得可能有些过，若不合诸位大佬的口味还请见谅~
节点node结构体定义：
key：节点原值；size：子树大小；ch[2]：子树指针；
set_pd：记录是否打了MAKE-SAME的懒标记；setv：MAKE-SAME的修改值；turn：记录是否旋转；
sum：子树元素总和；lmax,rmax,zdh：当前节点所控制区间的最大前缀和、最大后缀和、最大子段和。
成员函数：
maintain()：维护节点信息；
update_same()：打MAKE-SAME的懒标记；
update_rev()：打REVERSE的懒标记；
pushdown()：下放懒标记；
cmp(int x)：求在当前节点所控制区间中，排名为x的元素相对于当前节点的位置，0为左，1为右，-1为当前节点自身；
son_order(int x,bool d)：求在当前节点所控制区间中，排名为x的元素在d指向的子树中的排名。
主程序函数：
rotate()：萌新采用了先下放再考虑如何旋转的写法，所以不必考虑改变旋转方向之类的东西。。。注意下放、维护就好了；
splay()：此函数，萌新的自行研制写法，相对大佬们的代码，看上去长了许多。。。不过也可以放心食用啦~无父指针Splay赛高~
build()：建立完全平衡的BST，此题中应用这种建树方式，可极大地提高代码速度；
recycle()：回收删除的区间所占用的空间，如果没有这个，会导致个别点MLE；
get_range()：
这个函数的功能是抽取区间。。。
为什么要写这个呢？因为萌新太弱了。。。
我们知道，在抽取区间时，对边界情况，直接Splay就解决不了了；
这时一般会用“在头和尾加虚拟节点”的方法；
萌新曾试着这样写过。。。但最终没能解决虚拟节点的信息维护问题，尤其是最大子段和什么的。。。
于是放弃，采用了略为繁琐的分类讨论写法，具体如下：
1.若区间为整个序列，则不作任何操作，root即可代表整个序列；
2.若区间为[1,x]，其中x<n，则将x+1号元素splay至root，则root->ch[0]即为该区间；
3.若区间为[x,n]，其中x>1，则采取类似上面的操作；
4.若区间为[l,r]，其中1<l<=r<n，那么将l-1、r+1分别splay至root、root->ch[1]，则root->ch[1]->ch[0]即为该区间。
操作完后，返回一个值，用于在后续操作中进行对不同情况的识别。
work()：依据不同的区间情况和不同的指令，进行相应操作。
change()：依据不同的区间情况进行对相关节点的信息维护。
大坑警示！！！个别点中，操作的区间可能长度为0！！！
萌新就是因为这个问题而莫名RE了好久。。。后来终于对照某大佬的代码才发现了问题。。。
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<ctime> 6 #include<cstdlib> 7 8 #include<string> 9 #include<stack> 10 #include<queue> 11 #include<vector> 12 #include<algorithm> 13 #include<map> 14 15 #define inf 2147483647 16 17 using namespace std; 18 19 void read(int &x){ 20 x=0; 21 char t=getchar(); 22 bool f=0; 23 24 while(t<‘0‘ || t>‘9‘){ 25 if(t==‘-‘)f=1; 26 t=getchar(); 27 } 28 29 while(t>=‘0‘ && t<=‘9‘){ 30 x=(x<<3)+(x<<1)+t-‘0‘; 31 t=getchar(); 32 } 33 34 if(f)x=-x; 35 } 36 37 struct node{ 38 int key; 39 int size; 40 node *ch[2]; 41 42 bool set_pd; 43 int setv; 44 bool turn; 45 46 int sum; 47 48 int lmax; 49 int rmax; 50 int zdh; 51 52 void maintain(){ 53 size=1; 54 if(ch[0]!=NULL)size+=ch[0]->size; 55 if(ch[1]!=NULL)size+=ch[1]->size; 56 57 sum=key; 58 if(ch[0]!=NULL)sum+=ch[0]->sum; 59 if(ch[1]!=NULL)sum+=ch[1]->sum; 60 61 if(ch[0]==NULL && ch[1]==NULL){ 62 lmax=rmax=max(0,key); 63 zdh=key; 64 } 65 else if(ch[1]==NULL){ 66 lmax=max(ch[0]->lmax,ch[0]->sum+key); 67 rmax=max(0,key+ch[0]->rmax); 68 zdh=max(ch[0]->zdh,ch[0]->rmax+key); 69 } 70 else if(ch[0]==NULL){ 71 lmax=max(0,key+ch[1]->lmax); 72 rmax=max(ch[1]->rmax,ch[1]->sum+key); 73 zdh=max(ch[1]->zdh,key+ch[1]->lmax); 74 } 75 else{ 76 lmax=max(ch[0]->lmax,ch[0]->sum+key+ch[1]->lmax); 77 rmax=max(ch[1]->rmax,ch[1]->sum+key+ch[0]->rmax); 78 zdh=max(max(ch[0]->zdh,ch[1]->zdh),ch[0]->rmax+key+ch[1]->lmax); 79 } 80 } 81 82 void update_same(int fix){ 83 set_pd=1; 84 key=setv=fix; 85 86 sum=fix*size; 87 88 lmax=rmax=max(0,sum); 89 zdh=max(sum,key); 90 91 turn=0; //打了MAKE-SAME之后就可以无视旋转了 92 } 93 94 void update_rev(){ 95 turn^=1; 96 97 lmax^=rmax; 98 rmax^=lmax; 99 lmax^=rmax; //在上层节点抽取本节点信息时，要求必须在旋转时交换lmax和rmax 100 } 101 102 void pushdown(){ 103 if(set_pd){ 104 if(ch[0]!=NULL)ch[0]->update_same(setv); 105 if(ch[1]!=NULL)ch[1]->update_same(setv); 106 107 set_pd=0; 108 turn=0; 109 } 110 if(turn){ 111 node *t=ch[0]; 112 ch[0]=ch[1]; 113 ch[1]=t; 114 115 if(ch[0]!=NULL)ch[0]->update_rev(); 116 if(ch[1]!=NULL)ch[1]->update_rev(); 117 118 turn=0; 119 } 120 } 121 122 int cmp(int x){ 123 int s=0; 124 if(ch[0]!=NULL)s=ch[0]->size; 125 126 if(x<=s)return 0; 127 else if(x==s+1)return -1; 128 else return 1; 129 } 130 131 int son_order(int x,bool d){ 132 if(d==0)return x; 133 else{ 134 if(ch[0]==NULL)return x-1; 135 else return x-ch[0]->size-1; 136 } 137 } 138 }; 139 140 void rotate(node* &,bool); //没有自带对当前根节点的懒标记下放 141 void splay(node* &,int); //按照排名伸展 142 void build(node* &,int,int,int); 143 void recycle(node *); 144 145 int get_range(); 146 void work(int); 147 void change(); 148 149 node *root=NULL; 150 node *temp; 151 152 int longtao[500010]; 153 154 char s[15]; 155 int n,m,i,j; 156 int pos,tot,fix,kind; 157 158 int main(){ 159 read(n);read(m); 160 161 for(i=1;i<=n;i++)read(longtao[i]); 162 build(root,1,n,(1+n)>>1); 163 164 for(i=1;i<=m;i++){ 165 scanf("%s",s); 166 167 switch(s[2]){ 168 case ‘S‘:{ 169 read(pos);read(tot); 170 if(tot==0)break; 171 172 for(j=1;j<=tot;j++)read(longtao[j]); 173 temp=NULL; 174 build(temp,1,tot,(1+tot)>>1); 175 176 if(pos==0){ 177 splay(root,1); 178 root->ch[0]=temp; 179 root->maintain(); 180 } 181 else if(pos==root->size){ 182 splay(root,inf); 183 root->ch[1]=temp; 184 root->maintain(); 185 } 186 else{ 187 splay(root,pos); 188 splay(root->ch[1],1); 189 root->ch[1]->ch[0]=temp; 190 root->ch[1]->maintain(); 191 root->maintain(); 192 } 193 194 break; 195 } 196 197 case ‘L‘:{ 198 read(pos);read(tot); 199 if(tot==0)break; 200 201 kind=get_range(); 202 work(2); 203 change(); 204 205 break; 206 } 207 208 case ‘K‘:{ 209 read(pos);read(tot);read(fix); 210 if(tot==0)break; 211 212 kind=get_range(); 213 work(3); 214 change(); 215 216 break; 217 } 218 219 case ‘V‘:{ 220 read(pos);read(tot); 221 if(tot==0)break; 222 223 kind=get_range(); 224 work(4); 225 change(); 226 227 break; 228 } 229 230 case ‘T‘:{ 231 read(pos);read(tot); 232 if(tot==0){ 233 printf("0\n"); 234 break; 235 } 236 237 kind=get_range(); 238 work(5); 239 240 break; 241 } 242 243 case ‘X‘:{ 244 printf("%d\n",root->zdh); 245 246 break; 247 } 248 } 249 } 250 251 return 0; 252 } 253 254 void rotate(node* &p,bool f){ 255 node *t=p->ch[f^1]; 256 257 t->pushdown(); 258 259 p->ch[f^1]=t->ch[f]; 260 t->ch[f]=p; 261 262 p->maintain(); 263 t->maintain(); 264 265 p=t; 266 } 267 268 void splay(node* &p,int x){ 269 p->pushdown(); 270 271 int d1=p->cmp(x); 272 if(d1==-1 || p->ch[d1]==NULL)return; 273 274 p->ch[d1]->pushdown(); 275 276 int x2=p->son_order(x,d1); 277 int d2=p->ch[d1]->cmp(x2); 278 if(d2==-1 || p->ch[d1]->ch[d2]==NULL){ 279 rotate(p,d1^1); 280 return; 281 } 282 else{ 283 int x3=p->ch[d1]->son_order(x2,d2); 284 285 splay(p->ch[d1]->ch[d2],x3); 286 287 if(d1==d2){ 288 rotate(p,d1^1); 289 rotate(p,d2^1); 290 } 291 else{ 292 rotate(p->ch[d1],d1); 293 rotate(p,d2); 294 } 295 } 296 } 297 298 void build(node* &p,int l,int r,int mid){ 299 p=(node *)malloc(sizeof(node)); 300 301 p->key=longtao[mid]; 302 p->ch[0]=p->ch[1]=NULL; 303 p->set_pd=0; 304 p->turn=0; 305 306 if(mid-1>=l)build(p->ch[0],l,mid-1,(l+mid-1)>>1); 307 if(mid+1<=r)build(p->ch[1],mid+1,r,(mid+1+r)>>1); 308 309 p->maintain(); 310 } 311 312 void recycle(node *p){ 313 if(p->ch[0]!=NULL)recycle(p->ch[0]); 314 if(p->ch[1]!=NULL)recycle(p->ch[1]); 315 316 free(p); 317 } 318 319 int get_range(){ 320 if(tot==root->size)return 1; 321 else if(pos==1){ 322 splay(root,pos+tot); 323 return 2; 324 } 325 else if(pos+tot-1==root->size){ 326 splay(root,pos-1); 327 return 3; 328 } 329 else{ 330 splay(root,pos-1); 331 splay(root->ch[1],tot+1); 332 return 4; 333 } 334 } 335 336 void work(int f){ 337 node **t; 338 if(kind==1)t=&root; 339 if(kind==2)t=&(root->ch[0]); 340 if(kind==3)t=&(root->ch[1]); 341 if(kind==4)t=&(root->ch[1]->ch[0]); 342 343 if(f==2){ 344 recycle(*t); 345 (*t)=NULL; 346 } 347 else if(f==3)(*t)->update_same(fix); 348 else if(f==4)(*t)->update_rev(); 349 else printf("%d\n",(*t)->sum); 350 } 351 352 void change(){ 353 if(kind==2 || kind==3)root->maintain(); 354 else if(kind==4){ 355 root->ch[1]->maintain(); 356 root->maintain(); 357 } 358 }
[模板]洛谷T2042 NOI2005 维护数列 Splay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。