@OceanEye9年前
04/23
15:45
还是可并堆的题目……而且一如既往的很裸
合并，弹出都是log的复杂度
看代码吧……没什么细节但是我还是没有1A
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 1000010 struct node { int lc,rc,val; int fa; }pool[N]; int n,m; #define Lc pool[x].lc #define Rc pool[x].rc int merge(int x,int y) { if(!y) return x; if(!x) return y; if(pool[y].val<pool[x].val) swap(x,y); pool[x].rc=merge(y,pool[x].rc); pool[pool[x].rc].fa=x; return x; } int pop(int x) { pool[x].fa=-1; pool[Lc].fa=0; pool[Rc].fa=0; merge(Lc,Rc); return pool[x].val; } void pre() { read(n); for(int i=1;i<=n;i++) read(pool[i].val); } int main() { freopen("roman.in","r",stdin); int _,__; pre(); read(m); char cmd[10]; while(m--) { scanf("%s",cmd); if(cmd[0]=='M') { read(_);read(__); while(pool[_].fa&&~pool[_].fa) _=pool[_].fa; while(pool[__].fa&&~pool[__].fa) __=pool[__].fa; if(pool[_].fa==-1||pool[__].fa==-1) continue; if(_==__) continue; merge(_,__); } if(cmd[0]=='K') { read(__); while(pool[__].fa&&~pool[__].fa) __=pool[__].fa; if(~pool[__].fa) printf("%d\n",pop(__)); else puts("0"); } } return 0; } |