【JZOJ 4986】神秘物质

2019-11-06 09:10:43

字体：大中小

来源：转载

供稿：网友

Description

这里写图片描述

Solution

裸的Splay版子，不解释。

复杂度：O(nlog(n)) $O(n/log(n))$

Code

#include <cstdio>#include <cstdlib>#include <cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fod(i,a,b) for(int i=a;i>=b;i--)#define min(q,w) ((q)<(w)?(q):(w))#define max(q,w) ((q)>(w)?(q):(w))using namespace std;typedef long long LL;const int N=200500;int read(int &n){ char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;}int n,m;int b0,root;struct QQww{ int mx,mi,l,r,nv,co,v,fa,lv,rv;}b[N];void merge(int e){ int l=b[e].l,r=b[e].r; b[e].lv=b[l].lv?b[l].lv:b[e].v; b[e].rv=b[r].rv?b[r].rv:b[e].v; b[e].mx=max(b[l].mx,max(b[r].mx,b[e].v)); b[e].mi=min(b[l].mi,min(b[r].mi,b[e].v)); b[e].co=b[l].co+b[r].co+1; if(b[e].co-1)b[e].nv=min(b[l].nv,min(b[r].nv, min(((b[l].rv)?abs(b[e].v-b[l].rv):(int)1e9),((b[r].lv)?abs(b[e].v-b[r].lv):(int)1e9)))); else b[e].nv=1e9;}void UP(int q){ int t=b[q].fa; if(b[t].l==q) { b[t].l=b[q].r; b[b[q].r].fa=t; b[q].r=t; }else { b[t].r=b[q].l; b[b[q].l].fa=t; b[q].l=t; } if(b[b[t].fa].l==t)b[b[t].fa].l=q; else b[b[t].fa].r=q; b[q].fa=b[t].fa; b[t].fa=q; merge(t); merge(q);}bool SD(int q){return q==b[b[q].fa].l;}void rotate(int q,int w){ while(b[q].fa!=w) { if(b[b[q].fa].fa!=w) if(SD(q)==SD(b[q].fa))UP(b[q].fa); else UP(q); UP(q); } if(!w)root=q;}int search(int q,int w){ if(b[b[q].l].co>=w)return search(b[q].l,w); w-=b[b[q].l].co+1; return w?search(b[q].r,w):q;}int main(){ int q,w,e,_; read(n),read(_); b[0].mi=b[0].nv=1e9; b[1]=b[0];b[1].fa=2;b[1].co=1; fo(i,2,n+1) { read(b[i].v); b[i].l=i-1; b[i].fa=i+1; merge(i); } b[n+2].l=n+1; merge(n+2);root=n+2; b0=2+n; rotate(n/2,0); rotate(n/3,n/2); fo(i,1,_) { char ch,ch1; for(ch=getchar();ch!='m'&&ch!='i';ch=getchar()); ch1=getchar(); read(q),read(w); q++; if(ch1=='e') { int t=search(root,q-1); rotate(t,0); rotate(t=search(root,q+2),root); b[t].l=0; merge(t); merge(root); ch='i',q--; } if(ch=='i') { rotate(q=search(root,q),0); b0++; b[b0].v=w; b[b0].r=b[q].r; b[b0].fa=q; b[b[q].r].fa=b0; b[q].r=b0; merge(b0); merge(q); }else { w++; rotate(search(root,q-1),0); rotate(q=search(root,w+1),root); q=b[q].l; if(ch1=='a') { PRintf("%d/n",b[q].mx-b[q].mi); } if(ch1=='i') { printf("%d/n",b[q].nv); } } } return 0;}

上一篇：Hello World

下一篇：nyoj 211&&poj 3660

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注