%%%vfk %%%陳老師
本蒟蒻覺得用重量平衡樹打tag像是在線的離散…… 看到這題的第一感覺也是能不能用很小的復雜度對每一次操作后離散一遍，感覺這確實是個好方法
#include <cstdio>#include <iostream>#include <algorithm>#define N 600010using namespace std;struct lef{ lef *fa,*ch[2],*x,*y; int sz; double w;}PR[N],*t,*A[N],*rt,*q[N],*fix;int tail;void clear(){ t=pr; A[0]=t++; A[0]->w=0;}bool Operator <(lef a,lef b){ if(a.x->w==b.x->w) return a.y->w<b.y->w; return a.x->w<b.x->w;}bool operator ==(lef a,lef b){ return a.x->w==b.x->w&&a.y->w==b.y->w;}inline lef *born(lef* l,lef* r){ lef *p=t++; p->x=l; p->y=r; p->fa=p->ch[0]=p->ch[1]=0; return p;}void dfs(lef *x){ if(!x) return; dfs(x->ch[0]); q[++tail]=x; dfs(x->ch[1]);}inline void updat(lef *x){ if(!x) return; x->sz=1; if(x->ch[0]) x->sz+=x->ch[0]->sz; if(x->ch[1]) x->sz+=x->ch[1]->sz;}lef *build(int l,int r,double x,double y){ if(l>r) return 0; int mid=l+r>>1; double md=(x+y)/2.0; q[mid]->w=md; q[mid]->ch[0]=build(l,mid-1,x,md); q[mid]->ch[1]=build(mid+1,r,md,y); updat(q[mid]); return q[mid];}lef *rebuild(lef *x,double l,double r){ tail=0; dfs(x); return build(1,tail,l,r);}inline int max(lef *a,lef *b){ int mx=0; if(a) mx=max(mx,a->sz); if(b) mx=max(mx,b->sz); return mx;}lef *InserT(lef *&x,lef *y,double l,double r){ double mid=(l+r)/2.0; if(!x){y->w=mid;x=y;return y;} if(*x==*y){y->w=mid;return x;} lef *p; if(x->sz++,*y<*x) p=InserT(x->ch[0],y,l,mid); else p=InserT(x->ch[1],y,mid,r); if(x->sz*0.75<=max(x->ch[0],x->ch[1])) fix=x; else if(fix){ if(fix==x->ch[0]) x->ch[0]=rebuild(x->ch[0],l,mid); else x->ch[1]=rebuild(x->ch[1],mid,r); fix=0; } return p;}struct seg{ int l,r,mx;}T[N<<2];inline void updat(int x){ if(A[T[x<<1].mx]->w>=A[T[x<<1|1].mx]->w) T[x].mx=T[x<<1].mx; else T[x].mx=T[x<<1|1].mx;}void build(int g,int l,int r){ T[g].l=l; T[g].r=r; T[g].mx=1; if(l==r){T[g].mx=l;return;} int mid=l+r>>1; build(g<<1,l,mid); build(g<<1|1,mid+1,r); updat(g);}void modify(int g,int x){ if(T[g].l==T[g].r) {T[g].mx=x;return;} int mid=T[g].r+T[g].l>>1; if(x<=mid) modify(g<<1,x); else modify(g<<1|1,x); updat(g);}int query(int g,int l,int r){ if(T[g].l==l&&T[g].r==r) return T[g].mx; int mid=T[g].l+T[g].r>>1; if(r<=mid) return query(g<<1,l,r); if(l>mid) return query(g<<1|1,l,r); int lq=query(g<<1,l,mid),rq=query(g<<1|1,mid+1,r); if(A[lq]->w<A[rq]->w) return rq; else return lq;}int n,m,x,y,z;char op;inline char C(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2) return EOF; } return *p1++;}inline void reaD(int &x){ char Ch=C();x=0; for(;Ch>'9'||Ch<'0';Ch=C()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());}int main(){ reaD(n); reaD(m); clear(); for(int i=1;i<=n;i++) A[i]=InserT(rt,born(A[0],A[0]),0,1); build(1,1,n); for(int i=1;i<=m;i++){ while((op=C())!='C'&&op!='Q'); if(op=='C'){ reaD(x); reaD(y); reaD(z); A[z]=InserT(rt,born(A[x],A[y]),0,1); if(fix) rt=rebuild(rt,0,1),fix=0; modify(1,z); } else{ reaD(x); reaD(y); printf("%d/n",query(1,x,y)); } }}?新聞熱點
疑難解答
