题解
又是一道题一晚上系列(数据结构一生之敌)
调了很久的原因其实是写错了一个变量,其实还是很简单的
这里用的平衡树是Treap
你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存
用vector就很舒服
然后对于第三个操作,其实只要每次进入平衡树的元素查找下前驱后继与它本身作差取最小值即可(这里的前驱后继是非严格的)
对于第二个操作,每次插入一个元素,总会创造两个差值关系并且减去一个差值关系
我们可以用两个小根堆分别维护产生的差值和删去的差值,每次询问时,不断弹出顶端相同元素后,第一个堆顶就是答案了
这种做法还是有点慢的(最慢1500ms,开了O2 790ms),如果当年省选不开O2的话有点悬
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
#include<bits/stdc++.h> using namespace std; const int MAXN=600304,INF=0x7fffffff; int pos[MAXN];//可以不用 int minn=INF; vector<int>b[MAXN]; struct delhp{ priority_queue<int>q1,q2; void insert(int kind,int x){ if(kind==1)q1.push(-x);//小根堆 else q2.push(-x); } int top(){ while(q1.size()&&q2.size()){ if(q1.top()!=q2.top())return -q1.top(); q1.pop();q2.pop(); } } }q; struct Treap{ int l,r; int val,dat; int cnt,size; }a[MAXN]; int tot,root; int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } void update(int p){ a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt; } int New(int x){ a[++tot].val=x; a[tot].dat=rand(); a[tot].size=a[tot].cnt=1; return tot; } void build(){ New(-INF);New(INF); a[1].r=2; root=1; update(root); } void zig(int &p){ int q=a[p].l; a[p].l=a[q].r;a[q].r=p;p=q; update(a[p].r);update(p); } void zag(int &p){ int q=a[p].r; a[p].r=a[q].l;a[q].l=p;p=q; update(a[p].l);update(p); } void insert(int &p,int val){ if(p==0){ p=New(val); return; } if(val==a[p].val){ a[p].cnt++; update(p); return; } if(val<a[p].val){ insert(a[p].l,val); if(a[a[p].l].dat>a[p].dat)zig(p); } else { insert(a[p].r,val); if(a[a[p].r].dat>a[p].dat)zag(p); } update(p); } int GetPre(int val){ int ans=1; int p=root; while(p){ if(val==a[p].val){ if(a[p].cnt>1)return a[p].val; else if(a[p].l>0){ p=a[p].l; while(a[p].r>0)p=a[p].r; ans=p; } break; } if(a[p].val<val&&a[p].val>a[ans].val)ans=p; p=val<a[p].val?a[p].l:a[p].r; } return a[ans].val; } int GetNext(int val){ int ans=2; int p=root; while(p){ if(val==a[p].val){ if(a[p].cnt>1)return a[p].val; else if(a[p].r>0){ p=a[p].r; while(a[p].l>0)p=a[p].l; ans=p; } break; } if(a[p].val>val&&a[p].val<a[ans].val)ans=p; p=val<a[p].val?a[p].l:a[p].r; } return a[ans].val; } int main(){ int n=read(),m=read(); build(); for(int i=1;i<=n;i++){ int x=read(); pos[i]=x; b[i].push_back(x); if(i!=1)q.insert(1,abs(pos[i]-pos[i-1])); if(minn!=0){//维护操作3 insert(root,pos[i]); int xx=GetNext(pos[i]); int yy=GetPre(pos[i]); if(xx!=INF&&xx!=-INF)minn=min(minn,xx-pos[i]); if(yy!=INF&&yy!=-INF)minn=min(minn,pos[i]-yy); } } for(int i=1;i<=m;i++){ char s[20]; scanf("%s",s); int len=strlen(s); if(len==6){ int x=read(),k=read(); b[x].push_back(k); if(minn!=0)insert(root,k); q.insert(1,abs(k-*(b[x].end()-2)));//*号为解除引用,如果不加上则返回的是迭代器 if(b[x+1].size()){//防止越界RE q.insert(1,abs(k-*(b[x+1].begin()))); q.insert(2,abs(*(b[x].end()-2)-*(b[x+1].begin()))); } if(minn!=0){ int xx=GetNext(k); int yy=GetPre(k); if(xx!=INF&&xx!=-INF)minn=min(minn,xx-k); if(yy!=INF&&yy!=-INF)minn=min(minn,k-yy); } } else if(len==7){ printf("%d\n",q.top()); } else { printf("%d\n",minn); } } return 0; } |