博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj3489: A simple rmq problem (主席树)
阅读量:7157 次
发布时间:2019-06-29

本文共 3715 字,大约阅读时间需要 12 分钟。

//==========================

蒟蒻Macaulish:  转载要声明!

//==========================

 

说好的“因为是OJ上的题,就简单点好了。”呢?

 

一开始看不懂,不会写。

然后跪了一个晚上决定看云的题解&……似乎是主席树套主席树!吓傻,还开了40000000的数组。然后一交tle……

然后p是不可能玩常数的。

找不到其他做法。

 

然后找到了神牛dwjshift,好心地提供了题解( )之后还好心地提供了代码!简直业界良心!(dwj必拿AU)

 

一开始写的是主席树套配对堆(因为要个优先队列嘛)然后发现套个配对堆各种问题(就不说了,其实主要还是我太弱,这个里面很恶心。。。。。)

然后就跪了dwj的代码,用treap实现。

关于题解,正题开始:

主席树套主席树的做法详见帖子中吧主的话

然后发现没有那么必要。

主席树套优先队列详见帖子下面。

“给定一个序列,支持两个操作: 1.给区间[l,r]中塞进或去掉一个数 2.查询某个点的值”

然后类似标记永久化。就可以变成单点修改的线段树套优先队列了

(原来主席树也是可以区间修改区间查询?……只要套个标记永久化)

写的时候有个地方傻叉了,就是主席树修改的时候,如果区间被要修改的区间覆盖时就不用改他儿子,这时候注意不要忘记儿子们=旧的点的儿子们,要是一开始新的点的儿子都是旧的点的不就行了,这是个人风格问题!

{
$inline on}const maxn=200000; maxm=12000000;var left,right,size,fix,max2,value:array[0..maxm]of longint; root,lson,rson,max:array[0..maxm]of longint; time,last,next,num:array[0..maxn]of longint; n,m,tot1,tot2,ll,rr:longint; flag:boolean;procedure swap(var x,y:longint);inline;var i:longint;begin i:=x; x:=y; y:=i;end;function mmax(x,y:longint):longint;inline;begin if x
0 then max2[x]:=mmax(max2[x],value[x]);end;procedure leftr(var x:longint);inline;var k:longint;begin k:=right[x]; right[x]:=left[k]; left[k]:=x; max2[k]:=max2[x]; update(x); x:=k;end;procedure rightr(var x:longint);inline;var k:longint;begin k:=left[x]; left[x]:=right[k]; right[k]:=x; max2[k]:=max2[x]; update(x); x:=k;end;procedure insert(var x:longint;y:longint);inline;begin if x=0 then begin inc(tot2); x:=tot2; size[x]:=1; value[x]:=y; fix[x]:=random(maxn); max2[x]:=y; left[x]:=0; right[x]:=0; exit; end; if value[x]=y then begin if flag then inc(size[x]) else dec(size[x]); update(x); end else if value[x]
fix[x] then leftr(x); end else begin insert(left[x],y); update(x); if fix[left[x]]>fix[x] then rightr(x); end;end;procedure change(x,old,l,r,y:longint;var new:longint);inline;var mid:longint;begin inc(tot1); new:=tot1; if (ll<=l) and (r<=rr) then begin insert(root[x],y); max[new]:=max2[root[x]]; lson[new]:=lson[old]; rson[new]:=rson[old]; exit; end; max[new]:=max2[root[x]]; mid:=(l+r)>>1; if ll>mid then begin change(x<<1+1,rson[old],mid+1,r,y,rson[new]); lson[new]:=lson[old]; end else if rr<=mid then begin change(x<<1,lson[old],l,mid,y,lson[new]); rson[new]:=rson[old]; end else begin change(x<<1,lson[old],l,mid,y,lson[new]); change(x<<1+1,rson[old],mid+1,r,y,rson[new]); end;end;function query(x,l,r,y:longint):longint;inline;var mid:longint;begin //writeln(x); if l=r then exit(max[x]); mid:=(l+r)>>1; if y>mid then exit(mmax(max[x],query(rson[x],mid+1,r,y))) else exit(mmax(max[x],query(lson[x],l,mid,y)))end;procedure into;inline;var i,j:longint;begin readln(n,m); for i:=1 to n do read(num[i]); for i:=1 to n do last[i]:=n+1; for i:=n downto 1 do begin next[i]:=last[num[i]]; last[num[i]]:=i; end; for i:=1 to n do if last[i]<>n+1 then begin ll:=last[i]; rr:=next[ll]-1; flag:=true; change(1,time[1],1,n,i,time[1]); end; for i:=2 to n do begin ll:=i-1; rr:=next[i-1]-1; flag:=false; change(1,time[i-1],1,n,num[i-1],time[i]); if next[i-1]<>n+1 then begin ll:=next[i-1]; rr:=next[ll]-1; flag:=true; change(1,time[i],1,n,num[i-1],time[i]); end; end;end;procedure work;inline;var lastans,l,r:longint;begin lastans:=0; while m>0 do begin // writeln(m,'==========='); dec(m); readln(l,r); l:=(l+lastans) mod n+1; r:=(r+lastans) mod n+1; if l>r then swap(l,r); lastans:=query(time[l],1,n,r); writeln(lastans); end;end;begin randomize; into; work;end.
View Code

 

转载于:https://www.cnblogs.com/Macaulish/p/4420613.html

你可能感兴趣的文章
转:Awesome - Image Classification
查看>>
requests模块使用代理
查看>>
jmeter关联技术
查看>>
js_初识js_js基本语法和数据类型
查看>>
《图解HTTP》54~72Page 返回的HTTP状态码 与HTTP协作的Web服务器
查看>>
ubuntu 下安装jdk
查看>>
04-2winPE里面下载系统并安装系统教程
查看>>
盒子模型的二个理论
查看>>
FortiGate部分用户上网慢,丢包严重
查看>>
Chrome 控制台console的用法
查看>>
TreeView 递归选择父节点和子节点
查看>>
jQuery Easy UI 使用
查看>>
SpringBoot整合ElasticSearch实现多版本的兼容
查看>>
Spring Framework 初识
查看>>
AngularJS in Action读书笔记5(实战篇)——在directive中引入D3饼状图显示
查看>>
ID为XXXX的进程当前未运行
查看>>
【数据结构第四周】树知识点整理(下)【平衡二叉树】
查看>>
zabbix监控windows服务器CPU温度
查看>>
2_2 递归与分治策略(分治法的基本思想)
查看>>
C++Singleton的DCLP(双重锁)实现以及性能测评
查看>>