bzoj3595

作者：章小胭 | 来源：互联网 | 2023-09-14 20:38

Splay每个节点维护一个区间。1**************************************************************2Problem:35

Splay 每个节点维护一个区间。

  1 /**************************************************************
  2     Problem: 3595
  3     User: idy002
  4     Language: C++
  5     Result: Accepted
  6     Time:5428 ms
  7     Memory:56020 kb
  8 ****************************************************************/
  9  
 10 #include 
 11 #include 
 12 #define N 2000000
 13 using namespace std;
 14  
 15 map<int,int> atob, btoa;
 16 map<int,int> rng_id;
 17  
 18 struct Splay {
 19     int son[N][2], pre[N], xlf[N], xrg[N], siz[N], root, ntot;
 20  
 21     int newnode( int p, int lf, int rg ) {
 22         if( lf>rg ) return 0;
 23         int nd = ++ntot;
 24         son[nd][0] = son[nd][1] = 0;
 25         pre[nd] = p;
 26         xlf[nd] = lf;
 27         xrg[nd] = rg;
 28         siz[nd] = rg-lf+1;
 29         return nd;
 30     }
 31     void update( int nd ) {
 32         siz[nd] = siz[son[nd][0]]+siz[son[nd][1]]+(xrg[nd]-xlf[nd]+1);
 33     }
 34     void rotate( int nd, int d ) {
 35         int p=pre[nd];
 36         int s=son[nd][!d];
 37         int ss=son[s][d];
 38  
 39         son[nd][!d] = ss;
 40         son[s][d] = nd;
 41         if( p ) son[p][nd==son[p][1]]=s;
 42         else root=s;
 43  
 44         pre[nd] = s;
 45         pre[s] = p;
 46         if( ss ) pre[ss] = nd;
 47  
 48         update( nd );
 49         update( s );
 50     }
 51     void splay( int nd, int top=0 ) {
 52         while( pre[nd]!=top ) {
 53             int p=pre[nd];
 54             int nl=nd==son[p][0];
 55             if( pre[p]==top ) {
 56                 rotate( p, nl );
 57             } else {
 58                 int pp=pre[p];
 59                 int pl=p==son[pp][0];
 60                 if( nl==pl ) {
 61                     rotate( pp, pl );
 62                     rotate( p, nl );
 63                 } else {
 64                     rotate( p, nl );
 65                     rotate( pp, pl );
 66                 }
 67             }
 68         }
 69     }
 70     void init( int lf, int rg ) {
 71         ntot = 0;
 72         root = newnode( 0, lf, rg );
 73         rng_id[rg] = root;
 74     }
 75     void make_one( int nd ) {
 76         int lnd, rnd;
 77         splay( nd );
 78         lnd = son[nd][0];
 79         rnd = son[nd][1];
 80         while( son[lnd][1] ) lnd=son[lnd][1];
 81         while( son[rnd][0] ) rnd=son[rnd][0];
 82         if( lnd && rnd ) {
 83             splay( lnd );
 84             splay( rnd, lnd );
 85         } else if( lnd ) {
 86             splay( lnd );
 87         } else if( rnd ) {
 88             splay( rnd );
 89         }
 90     }
 91     void split( int nd, int pos ) {
 92         if( xlf[nd]==xrg[nd] ) return;
 93         make_one( nd );
 94         int lnd, rnd;
 95         lnd = newnode( 0, xlf[nd], pos-1 );
 96         rnd = newnode( 0, pos+1, xrg[nd] );
 97         son[nd][0] = lnd;
 98         son[nd][1] = rnd;
 99         if( lnd ) {
100             pre[lnd] = nd;
101             rng_id[pos-1] = lnd;
102         }
103         if( rnd ) {
104             pre[rnd] = nd;
105             rng_id[xrg[nd]] = rnd;
106         }
107         rng_id[pos] = nd;
108         xlf[nd] = xrg[nd] = pos;
109         update( nd );
110         splay( nd );
111     }
112     void erase( int nd ) {
113         make_one( nd );
114         int p=pre[nd];
115         pre[nd] = 0;
116         if( p ) {
117             son[p][ nd==son[p][1] ] = 0;
118             pre[nd] = 0;
119             update( p );
120             splay( p );
121         } else {
122             root = 0;
123             pre[nd] = 0;
124         }
125     }
126     void push_front( int nn ) {
127         if( !root ) {
128             root = nn;
129             return;
130         }
131         int nd=root;
132         while( son[nd][0] ) nd=son[nd][0];
133         son[nd][0] = nn;
134         pre[nn] = nd;
135         splay( nn );
136     }
137     void push_back( int nn ) {
138         if( !root ) {
139             root = nn;
140             return;
141         }
142         int nd=root;
143         while( son[nd][1] ) nd=son[nd][1];
144         son[nd][1] = nn;
145         pre[nn] = nd;
146         splay(nn);
147     }
148     int rank( int nd ) {
149         int rt=siz[son[nd][0]]+1;
150         int nnd=nd;
151         while( pre[nd] ) {
152             int p=pre[nd];
153             if( nd==son[p][1] ) rt += siz[son[p][0]]+(xrg[p]-xlf[p]+1);
154             nd=p;
155         }
156         splay(nnd);
157         return rt;
158     }
159     int nth( int k ) {
160         int nd=root;
161         while(1) {
162             int ls=siz[son[nd][0]];
163             int lcs=ls+(xrg[nd]-xlf[nd]+1);
164             if( k<=ls ) {
165                 nd = son[nd][0];
166             } else if( k<=lcs ) {
167                 int rt = xlf[nd]+k-ls-1;
168                 splay( nd );
169                 return rt;
170             } else {
171                 k -= lcs;
172                 nd = son[nd][1];
173             }
174         }
175     }
176 }T;
177  
178 int n, m;
179 int main() {
180     scanf( "%d%d", &n, &m );
181     T.init( 1, n );
182     int la = 0;
183     for( int i=1; i<=m; i++ ) {
184         int opt, x, y;
185         scanf( "%d%d", &opt, &x );
186         x -= la;
187         if( opt==1 ) {
188             scanf( "%d", &y );
189             y -= la;
190             int pos = btoa.count(x) ? btoa[x] : x;
191             atob[pos] = y;
192             btoa[y] = pos;
193             int nd= rng_id.lower_bound( pos )->second;
194             T.split( nd, pos );
195             printf( "%d\n", la=T.rank(nd) );
196         } else if( opt==2 ) {
197             int pos = btoa.count(x) ? btoa[x] : x;
198             int nd=rng_id.lower_bound( pos )->second;
199             T.split( nd, pos );
200             printf( "%d\n", la=T.rank(nd) );
201             T.erase( nd );
202             T.push_front( nd );
203         } else if( opt==3 ) {
204             int pos = btoa.count(x) ? btoa[x] : x;
205             int nd = rng_id.lower_bound( pos )->second;
206             T.split( nd, pos );
207             printf( "%d\n", la=T.rank(nd) );
208             T.erase( nd );
209             T.push_back( nd );
210         } else {
211             int pos=T.nth(x);
212             int b = atob.count(pos) ? atob[pos] : pos;
213             printf( "%d\n", la=b );
214         }
215     }
216 }

View Code

bzoj 3595

推荐阅读

process
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
match
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
match
基于layUI的图片上传前预览功能的2种实现方式

本文介绍了基于layUI的图片上传前预览功能的两种实现方式：一种是使用blob+FileReader，另一种是使用layUI自带的参数。通过选择文件后点击文件名，在页面中间弹窗内预览图片。其中，layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块，并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]

蜡笔小新 2023-12-14 17:06:58
数组
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
main
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
main
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
数组
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
main
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
数组
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
match
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
数组
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
select
高质量SQL书写的30条建议

本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]

蜡笔小新 2023-12-13 13:24:33
main
指针的引用以及在什么情况下使用指针的引用

本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]

蜡笔小新 2023-12-13 12:54:29
input
猜字母游戏

猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]

蜡笔小新 2023-12-13 12:04:03
input
CentOS 7部署KVM虚拟化环境之一架构介绍

本文介绍了CentOS 7部署KVM虚拟化环境的架构，详细解释了虚拟化技术的概念和原理，包括全虚拟化和半虚拟化。同时介绍了虚拟机的概念和虚拟化软件的作用。 ... [详细]

蜡笔小新 2023-12-12 21:38:57

章小胭

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章