NOIp2017 Day2T3 列队（Treap）
Posted On 2017年12月28日
P3960 列队
Description
Solution
fhq Treap
手动模拟可以发现，每次询问/操作只会影响到第\(x\)行与最后一列
显然可以建\(n+1\)棵Treap，分别模拟\(n\)行与最后一列的状态
因为空间不支持保存全部节点，所以可以让每个节点保存\(l至r\)（连续），对于每一次操作拆分该节点即可
可以发现这样做时间复杂度为\(O(nlogn)\)
空间复杂度\(O(n)\)
开始脑抽写了个\(O(nlog^2n)\)卡了半天常70分QAQ
|
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 |
#include <cstdio> #include <cstdlib> #define ll long long inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=3*1e6+100,maxt=maxn<<2; struct mc{int lc,rc;ll l,r,len;int rnd,siz;}t[maxt]; int rt[maxn]; inline void maintain(const int&cur) { if (!cur){t[cur].siz=t[cur].len=0;return;} t[cur].siz=t[t[cur].lc].siz+1+t[t[cur].rc].siz; t[cur].len=t[t[cur].lc].len+(t[cur].r-t[cur].l+1)+t[t[cur].rc].len; } int merge(int x,int y) { if (!x||!y){maintain(x+y);return x+y;} if (t[x].rnd<t[y].rnd) { t[x].rc=merge(t[x].rc,y); maintain(x); return x; } t[y].lc=merge(x,t[y].lc); maintain(y); return y; } void split(const int cur,const int k,int&x,int&y) { if (!k){x=0;y=cur;maintain(cur);return;} if (t[cur].siz==k){x=cur;y=0;maintain(cur);return;} if (k<=t[t[cur].lc].siz)split(t[cur].lc,k,x,t[cur].lc),y=cur; else split(t[cur].rc,k-t[t[cur].lc].siz-1,t[cur].rc,y),x=cur; maintain(cur); } int ord(const int cur,const int k) { if (!k)return 0; if (t[t[cur].lc].len<k&&k<=t[t[cur].lc].len+(t[cur].r-t[cur].l+1)) return t[t[cur].lc].siz+1; return k<=t[t[cur].lc].len?ord(t[cur].lc,k): t[t[cur].lc].siz+1+ord(t[cur].rc,k-t[t[cur].lc].len-(t[cur].r-t[cur].l+1)); } int main() { srand(20171226); int n=read(),m=read(),q=read(),x,y,l,tot=n<<1,tmp,x1,y1,x2,y2,x3,y3,x4,y4;ll ans; for (register int i=1;i<=n;i++) rt[i]=i,t[i]=(mc){0,0,1ll*(i-1)*m+1,1ll*i*m-1,m-1,rand()<<15|rand(),1}; for (register int i=1;i<=n;i++) t[n+i]=(mc){0,0,1ll*i*m,1ll*i*m,1,rand()<<15|rand(),1},rt[n+1]=merge(rt[n+1],n+i); while(q--) { x=read(),y=read(); if (y==m) { split(rt[n+1],x-1,x1,y1); split(y1,1,x2,y2); printf("%lld\n",t[x2].l); rt[n+1]=merge(merge(x1,y2),x2); continue; } l=ord(rt[x],y); split(rt[x],l-1,x1,y1);split(y1,1,x2,y2); printf("%lld\n",ans=y-t[x1].len-1+t[x2].l); split(rt[n+1],x-1,x3,y3),split(y3,1,x4,y4),rt[n+1]=merge(x3,y4); if (t[x2].len>=3) { if (t[x2].l==ans) t[x2].l++,t[x2].len--,rt[x]=merge(merge(merge(x1,x2),y2),x4); else if (t[x2].r==ans) t[x2].r--,t[x2].len--,rt[x]=merge(merge(merge(x1,x2),y2),x4); else t[++tot]=(mc){0,0,t[x2].l,ans-1,ans-1-t[x2].l+1,rand()<<15|rand(),1}, t[x2]=(mc){0,0,ans+1,t[x2].r,t[x2].r-(ans+1)+1,rand()<<15|rand(),1}, rt[x]=merge(merge(merge(merge(x1,tot),x2),y2),x4); } else if (t[x2].len==2) { if (ans==t[x2].l)t[x2].l++; else if (ans==t[x2].r)t[x2].r--; t[x2].len=1; rt[x]=merge(merge(merge(x1,x2),y2),x4); } else if (t[x2].len==1)rt[x]=merge(merge(x1,y2),x4); t[++tot]=(mc){0,0,ans,ans,1,rand()<<15|rand(),1}; rt[n+1]=merge(rt[n+1],tot); } } |
Subscribe
0 评论