POJ 3580:SuperMemo(Splay)_weixin_30898109的博客-程序员宅基地

http://poj.org/problem?id=3580

题意:有6种操作,其中有两种之前没做过,就是Revolve操作和Min操作。Revolve一开始想着一个一个删一个一个插,觉得太暴力了,后来发现可以把要放到前面的一段切开,丢到前面去,就和上一题的Cut是一样的了。还有Min操作,一开始特别ZZ地想着只要找keytree的最左边就好了,然后发现并不是那样的,要维护一个 mi 值,一开始两个节点设成 INF,然后 pushup 的时候先把 val 赋给 mi,然后再和左右儿子对比。WA了好几次,找了下数据。。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <string>
  7 #include <iostream>
  8 #include <stack>
  9 #include <map>
 10 #include <queue>
 11 using namespace std;
 12 #define N 1000100
 13 #define INF 0x7fffffff
 14 #define lson ch[x][0]
 15 #define rson ch[x][1]
 16 #define keytree ch[ch[root][1]][0]
 17 
 18 struct SplayTree
 19 {
 20     int num[N], rev[N], ch[N][2], fa[N], val[N], sz[N], col[N], mi[N];
 21     int n, root, cnt;
 22 
 23     void PushDown(int x)
 24     {
 25         if(rev[x]) {
 26             swap(lson, rson);
 27             if(lson) rev[lson] ^= 1;
 28             if(rson) rev[rson] ^= 1;
 29             rev[x] = 0;
 30         }
 31         if(col[x]) {
 32             if(lson) {
 33                 col[lson] += col[x];
 34                 val[lson] += col[x];
 35                 mi[lson] += col[x];
 36             }
 37             if(rson) {
 38                 col[rson] += col[x];
 39                 val[rson] += col[x];
 40                 mi[rson] += col[x];
 41             }
 42             col[x] = 0;
 43         }
 44     }
 45 
 46     void PushUp(int x)
 47     {
 48         sz[x] = sz[lson] + sz[rson] + 1;
 49         mi[x] = val[x];
 50         if(lson) mi[x] = min(mi[x], mi[lson]);
 51         if(rson) mi[x] = min(mi[x], mi[rson]);
 52     }
 53 
 54     int NewNode(int w, int f, int kind)
 55     {
 56         int x = ++cnt;
 57         ch[x][0] = ch[x][1] = rev[x] = col[x] = 0;
 58         sz[x] = 1; val[x] = w; fa[x] = f;
 59         mi[x] = w;
 60         ch[f][kind] = cnt;
 61         return x;
 62     }
 63 
 64     void Build(int l, int r, int &x, int f, int kind)
 65     {
 66         if(l > r) return ;
 67         int m = (l + r) >> 1;
 68         x = NewNode(num[m], f, kind);
 69         Build(l, m - 1, ch[x][0], x, 0);
 70         Build(m + 1, r, ch[x][1], x, 1);
 71         PushUp(x);
 72     }
 73 
 74     void Init()
 75     {
 76         root = cnt = 0;
 77         rev[0] = val[0] = col[0] = fa[0] = sz[0] = ch[0][0] = ch[0][1] = 0;
 78         mi[0] = INF;
 79         root = NewNode(INF, 0, 0);
 80         ch[root][1] = NewNode(INF, root, 1);
 81         val[ch[root][1]] = INF;
 82         sz[root] = 2;
 83         Build(1, n, keytree, ch[root][1], 0);
 84         PushUp(ch[root][1]); PushUp(root);
 85     }
 86 
 87     void Rotate(int x, int kind)
 88     {
 89         int y = fa[x], z = fa[y];
 90         PushDown(y); PushDown(x);
 91         ch[y][!kind] = ch[x][kind];
 92         if(ch[y][!kind]) fa[ch[y][!kind]] = y;
 93         if(z) {
 94             if(y == ch[z][0]) ch[z][0] = x;
 95             else ch[z][1] = x;
 96         }
 97         fa[x] = z; fa[y] = x;
 98         ch[x][kind] = y;
 99         PushUp(y);
100     }
101 
102     void Splay(int x, int goal)
103     {
104 //        printf("%d, %d\n", x, fa[x]);
105         PushDown(x);
106         while(fa[x] != goal) {
107             int y = fa[x], z = fa[y];
108             PushDown(z); PushDown(y); PushDown(x);
109             int kind1 = x == ch[y][0];
110             int kind2 = y == ch[z][0];
111             if(z == goal) {
112                 Rotate(x, kind1);
113             } else {
114                 if(kind1 == kind2) {
115                     Rotate(y, kind1);
116                 } else {
117                     Rotate(x, kind1);
118                 }
119                 Rotate(x, kind2);
120             }
121         }
122         PushUp(x);
123         if(goal == 0) root = x;
124     }
125 
126     void RTO(int k, int goal)
127     {
128         int x = root;
129         PushDown(x);
130         while(k != sz[lson] + 1) {
131             if(k <= sz[lson]) x = lson;
132             else k -= sz[lson] + 1, x = rson;
133             PushDown(x);
134         }
135 //        printf("%d, %d, %d\n", x, val[x], goal);
136         Splay(x, goal);
137     }
138 
139     void Add(int l, int r, int d)
140     {
141         RTO(l, 0); RTO(r + 2, root);
142         col[keytree] += d;
143         val[keytree] += d;
144         mi[keytree] += d;
145         PushUp(ch[root][1]); PushUp(root);
146     }
147 
148     void Reverse(int l, int r)
149     {
150         RTO(l, 0); RTO(r + 2, root);
151         rev[keytree] ^= 1;
152         PushUp(ch[root][1]); PushUp(root);
153     }
154 
155     void Cut(int l, int r, int c)
156     {
157         RTO(l, 0); RTO(r + 2, root);
158         PushUp(ch[root][1]); PushUp(root);
159 //      Debug();
160 //      puts("---------");
161         int tmp = keytree;
162         keytree = 0;
163         RTO(c, 0); RTO(c + 1, root);
164         keytree = tmp;
165         fa[tmp] = ch[root][1];
166         PushUp(ch[root][1]); PushUp(root);
167     }
168 
169     void Revolve(int l, int r, int t)
170     {
171         t = (t % (r - l + 1) + (r - l + 1)) % (r - l + 1);
172         if(t == 0) return ;
173         Cut(r - t + 1, r, l);
174 //        Debug();
175         PushUp(ch[root][1]); PushUp(root);
176     }
177 
178     void Insert(int index, int w)
179     {
180         RTO(index + 1, 0); RTO(index + 2, root);
181         keytree = NewNode(w, ch[root][1], 0);
182         PushUp(ch[root][1]); PushUp(root);
183     }
184 
185     void Delete(int index)
186     {
187         RTO(index, 0); RTO(index + 2, root);
188         keytree = 0;
189         PushUp(ch[root][1]); PushUp(root);
190     }
191 
192     int Query(int l, int r)
193     {
194         RTO(l, 0);
195         RTO(r + 2, root);
196 //        Debug();
197         return mi[keytree];
198     }
199 
200     void Travel(int x)
201     {
202         if(lson) Travel(lson);
203         printf("ttt : %d, %d, %d\n", x, val[x], mi[x]);
204         if(rson) Travel(rson);
205     }
206 
207     void Debug()
208     {
209         Travel(root);
210     }
211 }spy;
212 
213 int main()
214 {
215     int n;
216     while(~scanf("%d", &n)) {
217         spy.n = n;
218         for(int i = 1; i <= n; i++) scanf("%d", &spy.num[i]);
219         spy.Init();
220         int m;
221         scanf("%d", &m);
222         while(m--) {
223             char s[10];
224             int a, b, c;
225             scanf("%s", s);
226             if(s[0] == 'A') {
227                 scanf("%d%d%d", &a, &b, &c);
228                 spy.Add(a, b, c);
229             } else if(s[0] == 'M') {
230                 scanf("%d%d", &a, &b);
231                 printf("%d\n", spy.Query(a, b));
232             } else if(s[0] == 'R' && s[3] == 'E') {
233                 scanf("%d%d", &a, &b);
234                 spy.Reverse(a, b);
235             } else if(s[0] == 'R' && s[3] == 'O') {
236                 scanf("%d%d%d", &a, &b, &c);
237                 spy.Revolve(a, b, c);
238             } else if(s[0] == 'I') {
239                 scanf("%d%d", &a, &b);
240                 spy.Insert(a, b);
241             } else if(s[0] == 'D') {
242                 scanf("%d", &a);
243                 spy.Delete(a);
244             }
245 //            spy.Debug();
246         }
247     }
248     return 0;
249 }
250 
251 /*
252 5
253 1
254 2
255 3
256 4
257 5
258 2
259 REVOLVE 1 5 4
260 MIN 4 5
261 
262 10
263 1 2 3 4 5 6 7 8 9 10
264 15
265 ADD 4 8 3
266 MIN 5 7
267 MIN 7 10
268 REVERSE 2 5
269 MIN 2 6
270 MIN 2 3
271 INSERT 3 4
272 MIN 3 4
273 MIN 5 10
274 DELETE 6
275 MIN 3 5
276 MIN 4 4
277 REVOLVE 3 6 7
278 MIN 5 8
279 MIN 7 10
280 **************************
281 282 283 284 285 286 287 288 289 290 291 */

 

转载于:https://www.cnblogs.com/fightfordream/p/6063541.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30898109/article/details/98655554

智能推荐

明智在线教育——系统架构_weixin_49258031的博客-程序员宅基地

一、功能简介明智在线学院,是一个B2C模式的职业技能在线教育系统,分为前台用户系统和后台运营平台。二、系统模块三、系统架构架构设计需要考虑的几个方面:性能:主要考虑访问频率,每个用户每天的访问次数。项目初始阶段用户的访问量并不大,如果考虑做运营推广,可能会迎来服务器访问量骤增,因此要考虑分布式部署,引入缓存可扩展性:系统功能会随着用户量的增加以及多变的互联网用户需求不断地扩展,因此考虑到系统的可扩展性的要求需要使用微服务架构,引入消息中间件高可用:系统一旦宕机,将会带来不可挽回的损失,因此必

POJ1651 Multiplication Puzzle 区间DP_weixin_30371875的博客-程序员宅基地

Multiplication PuzzleTime Limit:1000MSMemory Limit:65536KTotal Submissions:14834Accepted:9107DescriptionThe multiplication puzzle is played with a row of card...

mysql表打包到程序中_C#/winform程序打包布署 如何把SQL 数据库 一起打包进去?_觉主小VV的博客-程序员宅基地

打包数据库到安装程序中方法1. 备份/恢复先备份数据库:backup database 数据库 to disk='c:\备份.bak'将备份文件打包到安装程序中.在第一次运行程序的时候,进行数据库恢复(或专门做一个系统配置的程序,来控制完成此工作)restore database 数据库 from disk='c:\备份.bak'方法2. 分离/附加先分离数据库:sp_detach_db '数据库...

解决CentOS中JDK7中文验证码乱码问题_hao_hl1314的博客-程序员宅基地

redhed 没出现乱码 本身就jdk就支持中文,centos中的jdk不支持中文乱码如下:第一种方法:(可能不通用)  1.从windows  C:\WINDOWS\Fonts里拿取simsun.ttc(宋体)。       注:根据自己在awt中使用的字体,自主选择  2.放到linux /usr/share/fonts/truetype中 在用fc-cac

Soul网关源码阅读01-网关入门_lq9616的博客-程序员宅基地

1、clone fork的源码```git clonehttps://github.com/SpaceEmpire/soul.git```2、编译,编译完成大概需要2分多钟:```➜soulgit:(master)mvn clean package install -Dmaven.test.skip=true -Dmaven.javadoc.skip=true -Drat.skip=true -Dcheckstyle.skip=true[I...

java项目中的pom依赖在哪_java – 如何包含pom项目中的所有模块_爱电子产品的博客-程序员宅基地

我正在寻找一种方法,从另一个pom.xml包含项目中的所有模块.所以在我的情况下,我有一个父pom,包装设置为pom.它包含3个子模块,用于在另一个api模块中实现我的接口.我想在maven中动态地包含我项目中的所有子模块.在这种情况下,我想在另一个模块中包含connector1,connector2,connector3,而不必隐式指定connector1,2,3.connectors - pa...

随便推点

Linux判断两个文件是否是同一个文件_cxxx17的博客-程序员宅基地_linux判断两个文件是否相同

如何判断两个文件是不是同一个文件使用md5sum命令:md5sum file1md5sum file2如果file1 file2打印出来的码是一样的,那么二者是同一个文件,否则不是。

vue获取原生html节点,Vue框架写代码时原生js获取元素内容的方法_西红柿气象台的博客-程序员宅基地

在用vue框架写代码的时候,碰到个问题,想获取其中一个div的内容去做判断,html部分代码如下:{{presentContent}}js部分代码如下:presentClick(){let a=document.getElementsByClassName('present');let presentText=a[0].innerHTML;console.log('presentText='+pr...

html5 input file img,HTML5读取input[type=file]中的图片_踽踽独行着的博客-程序员宅基地

概述在我们做用户注册的时候经常会设计到用户头像之类的上传,这时我们会用到一个标签,但是我们该怎样获取标签中选取的图片呢?这里我们使用HTML5中的FileReader接口来实现这样的操作。demo我用如下代码来讲述该怎样实现这样的操作:HTML代码:获取图片 首先,肯定会有一个已经,form写不写action和method无所谓,因为既然我们要用JS/JQ来获取表单的文件,那多半是要...

很好的一篇嵌入式入门文章_weixin_33695450的博客-程序员宅基地

发信人: redtiger (红虎), 信区: Embedded标 题: 很好的一篇入门文章,特别推荐发信站: 饮水思源 (Sun Nov 18 15:43:03 2001) , 转信...... 北京计算机学会副理事长 北京嵌入式系统学会理事长 曹名扬教授 摘要:从嵌入式系统定义出发,分析嵌入式系统组成,和单片微机的关系,嵌入式系统开发工具,及嵌入式 系统的突出优点,提出了嵌入式系统的...

白噪声检验python_python 加一个白噪声跟老齐学Python之Python安装_weixin_39758712的博客-程序员宅基地

任何高级语言都是需要一个自己的编程环境的,这就好比写字一样,需要有纸和笔,在计算机上写东西,也需要有文字处理软件,比如各种名称的OFFICE。笔和纸以及office软件,就是写东西的硬件或软件,总之,那些文字只能写在那个上边,才能最后成为一篇文章。那么编程也是,要有个什么程序之类的东西,要把程序写到那个上面,才能形成最后类似文章那样的东西。刚才又有了一个术语――“程序”,什么是程序?本文就不讲了。...

Java学习笔记【入门】(2):JVM、JRE与JDK的关系_写Bug 的大潘的博客-程序员宅基地

1、JVMJVM(Java Virtual Machine),Java虚拟机,它是运行所有Java程序的虚拟计算机,好比是街机游戏的模拟器。JVM是Java语言的运行环境,也是Java 最具吸引力的特性之一。JVM用于读取并处理编译过的与平台无关的字节码(.class)文件,从而实现Java的可移植性。但是值得注意的是Java虚拟机是不跨平台的。也就是说在Win下得装Win版的JVM,在L...

推荐文章

热门文章

相关标签