這題并不難想，但是很難寫。
首先先轉化為開區間，然后一個就是掛左鏈，一個是掛右鏈。
然后變成了一個點與左鏈上掛的點的距離的問題。
然后就分討吧！
此處省略一萬字。

寫完之后，編譯了一下程序，電腦死機了。
然后發現自己CMLE了。(CMLE，即編譯器內存超限）
原因是在c++11標準下struct內二維數組開太大了，過了一會發現是g++版本太低的鍋，然而uoj版本也很低。
就不得不套上了一個詭異的東西，變長了也變慢了，可是終于能過編譯了。

uoj 暫時代碼長度rank 倒1,運行時間rank 倒2，慘。

#include <bits/stdc++.h> using namespace std; namespace Fastio{const int BUFF=7e5;char ch[BUFF],*l=ch,*r=ch;char gc(){if (l==r) l=ch,r=l+fread(ch,1,BUFF,stdin);if (l==r) return EOF;return *(l++);}void read(int &x) {x = 0;char ch = gc();while(!isdigit(ch)) ch = gc();while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();} }; using namespace Fastio; namespace container{template<class T,size_t BLOCK_SIZE>class myarray{struct period{T a[BLOCK_SIZE];period* ne=NULL;period(){}period(const T &v){fill(a,a+BLOCK_SIZE,v);}};period *Be;size_t Sz;class iterator{period *ip;size_t pos;myarray *po;public:typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef T* pointer;typedef T& reference;typedef ptrdiff_t difference_type;iterator():ip(nullptr),pos(0),po(nullptr){}iterator(const iterator &it){(*this)=it;}iterator(period * const &ip,const size_t &pos,myarray * const &po):ip(ip),pos(pos),po(po){}bool operator !=(const iterator &it) const{return ip!=it.ip||pos!=it.pos;}bool operator ==(const iterator &it) const{return ip==it.ip&&pos==it.pos;}iterator operator ++(){if (++pos==BLOCK_SIZE&&ip->ne!=NULL){ip=ip->ne;pos=0;}return *this;}const iterator operator ++(int){iterator tmp(*this);if (++pos==BLOCK_SIZE&&ip->ne!=NULL){ip=ip->ne;pos=0;}return tmp;}iterator operator --(){if (pos){--pos;return (*this);}period *tBe=po->Be;while (tBe->ne!=ip) tBe=tBe->ne;ip=tBe;pos=BLOCK_SIZE-1;return (*this);}const iterator operator --(int){iterator tmp(*this);if (pos){--pos;return tmp;}period *tBe=po->Be;while (tBe->ne!=ip) tBe=tBe->ne;ip=tBe;pos=BLOCK_SIZE-1;return tmp;}iterator operator +(const size_t &len) const{//ip!=NULL BUGif (BLOCK_SIZE>pos+len) return iterator(ip,pos+len,po);size_t tmp=len-(BLOCK_SIZE-1-pos);if (ip->ne==NULL) return iterator(ip,BLOCK_SIZE,po);period *tip=ip->ne;while (tmp>BLOCK_SIZE){if (tip->ne==NULL) return iterator(tip,BLOCK_SIZE,po);tip=tip->ne;tmp-=BLOCK_SIZE;}return iterator(tip,tmp-1,po);}iterator operator +=(const size_t &len){return ((*this)=(*this)+len);}size_t operator -(const iterator &it) const{//onlyif (ip==it.ip) return pos-it.pos;period *tmp=it.ip->ne;size_t ret=BLOCK_SIZE-it.pos;while (tmp!=ip){ret+=BLOCK_SIZE;tmp=tmp->ne;}return ret+pos;}iterator operator -(const size_t &len) const{return (po->begin()+((*this)-(po->begin())-len));}iterator operator -=(const size_t &len){return ((*this)=(*this)-len);}bool operator <(const iterator &it) const{//same fatherreturn ((*this)-po->begin())<(it-(po->begin()));}bool operator <=(const iterator &it) const{//same fatherreturn ((*this)-po->begin())<=(it-(po->begin()));}T & operator *() const{return ip->a[pos];}};public:typedef T value_type;typedef T& reference;typedef const T& const_reference;typedef size_t size_type;myarray(){Be=NULL;Sz=0;}myarray(const size_t &sz){construct(sz);}myarray(const size_t &sz,const T &v){construct(sz,v);}~myarray(){myfree(Be);}myarray(const myarray &rhs){if (this==&rhs) return;construct(rhs.size());auto j=begin();for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);}myarray(const initializer_list<T> &args){construct(args.size());auto j=begin();for (auto it=args.begin(); it!=args.end(); ++it) *(j++)=(*it);}myarray& operator =(const myarray &rhs){if (this==&rhs) return (*this);myfree(Be);construct(rhs.size());auto j=begin();for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);return *this;}void myfree(period * const &Be){period *tBe=Be,*tmp;while (tBe!=NULL){tmp=tBe->ne;delete tBe;tBe=tmp;}}void construct(const size_t &sz){Be=new period();//slow but safeSz=sz;size_t tSz=sz;period *tBe=Be;while (tSz>BLOCK_SIZE){tBe=(tBe->ne=new period);tSz-=BLOCK_SIZE;}}void construct(const size_t &sz,const T &v){Be=new period(v);Sz=sz;size_t tSz=sz;period *tBe=Be;while (tSz>BLOCK_SIZE){tBe=(tBe->ne=new period);tSz-=BLOCK_SIZE;}}iterator begin() const{return iterator(Be,0,(myarray*)this);}iterator end() const{//Slow And Dangerousif (Be==NULL) return iterator(NULL,0,(myarray*)this);period *tBe=Be;while (tBe->ne!=NULL) tBe=tBe->ne;return iterator(tBe,((int)Sz-1)%(int)BLOCK_SIZE+1,(myarray*)this);}void push_back(const T &v){if (Be==NULL){Be=new period;Be->a[Sz++]=v;return;}period *tBe=Be;while (tBe->ne!=NULL) tBe=tBe->ne;size_t tSz=(Sz++)%BLOCK_SIZE;if (tSz==0) tBe=(tBe->ne=new period);tBe->a[tSz]=v;}void pop_back(){if ((--Sz)%BLOCK_SIZE) return;if (Sz==0){delete Be;Be=NULL;return;}period *tBe=Be;while (tBe->ne->ne!=NULL) tBe=tBe->ne;delete tBe->ne;tBe->ne=NULL;}T& operator [](const size_t &pos) const{size_t tpos=pos;for (period* i=Be; i!=NULL; i=i->ne)if (tpos<BLOCK_SIZE) return i->a[tpos];else tpos-=BLOCK_SIZE;throw;}T& front() const{//unusualreturn Be->a[0];}T& back() const{return *(--end());}size_t size() const{return Sz;}bool empty() const{return Sz==0;}template<class U>struct iterator_traits{typedef typename U::value_type value_type;typedef typename U::iterator_category iterator_category;typedef typename U::difference_type difference_type;typedef typename U::pointer pointer;typedef typename U::reference reference;};}; } template<class T,size_t BLOCK_SIZE> using arr=container::myarray<T,BLOCK_SIZE>; typedef long long ll; typedef pair<ll,int> p; const int N=200005; int nodenum,fa[N*2][20]; int son[N*2][2]; int dep[N*2]; int clk,dfn[N*2],en[N*2]; void Rebuild(){for (int j=1; j<=17; ++j)for (int i=1; i<=nodenum; ++i)fa[i][j]=fa[fa[i][j-1]][j-1]; } int upto(const int &x,const int &y){int tmp=x;int dis=dep[tmp]-dep[y]-1;for (int j=17; j>=0; --j)if ((dis>>j)&1) tmp=fa[tmp][j];return tmp; } bool inrange(const int &x){return x>=1&&x<=nodenum; } int Getlca(int x,int y){if (!inrange(x)) return 0;if (!inrange(y)) return 0;if (dep[x]>dep[y]) swap(x,y);for (int j=17; j>=0; --j) if (fa[y][j]&&dep[x]<=dep[fa[y][j]]) y=fa[y][j];if (x==y) return x;for (int j=17; j>=0; --j)if (fa[x][j]!=fa[y][j]){x=fa[x][j];y=fa[y][j];}return fa[x][0]; } p operator +(const p &A,const p &B){return {A.first+B.first,A.second+B.second}; } namespace Pre{int tim,n,mid[N],trans[N*2];void Divide(int x,int l,int r){//cerr<<"Divide"<<x<<" "<<l<<" "<<r<<endl;if (l==r) return;int curtim=tim;int now=curtim+n;trans[++*trans]=now;if (l==mid[curtim]){son[now][0]=l;trans[++*trans]=l;}else{son[now][0]=n+tim+1;Divide(++tim,l,mid[curtim]);}if (mid[curtim]+1==r){son[now][1]=r;trans[++*trans]=r;}else{son[now][1]=n+tim+1;Divide(++tim,mid[curtim]+1,r);}}void Build_tree(){scanf("%d",&n);for (int i=1; i<n; ++i){scanf("%d",&mid[i]);}nodenum=n+n-1;Divide(tim=1,1,n);} }struct line{arr<p,18> sum[N*2];line(){for (int i=1; i<N*2; ++i) sum[i]=arr<p,18>(1);}void Ups(){for (int i=1; i<=nodenum; ++i){p tmp=sum[i][0];sum[i]=arr<p,18>(18);sum[i][0]=tmp;}}void Append(int x){sum[x][0]=p({dep[x],1});}void Rebuild(){for (int j=1; j<=17; ++j)for (int i=1; i<=nodenum; ++i){int faf=fa[i][j-1];//grand fatherif (!faf) continue;sum[i][j]=sum[i][j-1]+sum[faf][j-1];}}p cat_chain(const int &x,const int &y){int tmp=x;int dis=dep[tmp]-dep[y];p ret=p({0ll,0});for (int j=17; j>=0; --j)if ((dis>>j)&1){ret=ret+sum[tmp][j];tmp=fa[tmp][j];}return ret;}bool is_child(const int &a,const int &b){//a==b 1return dfn[b]<=dfn[a]&&en[a]<=en[b];}bool linear_relative_in_order(const int &a,const int &b,const int &c){return is_child(a,b)&&is_child(b,c);}ll Downchain(int x,int top,int y,int d){//cerr<<"Downchain"<<x<<" "<<top<<" "<<y<<endl;if (dep[x]<dep[top]) return 0;p tmp=cat_chain(x,top);int lca=Getlca(top,y);ll ret=tmp.first+(ll)tmp.second*dep[y];ret-=2ll*tmp.second*dep[lca];if (inrange(son[top][d^1])){int plca=Getlca(son[top][d^1],y);ret+=2*dep[lca];ret-=2*dep[plca];}//cerr<<"Ret"<<ret<<endl;return ret;}ll Upchain(int x,int top,int y){//cerr<<"Upchain"<<x<<" "<<top<<" "<<y<<endl;if (dep[x]<dep[top]) return 0;p tmp=cat_chain(x,top);ll ret=tmp.first+(ll)tmp.second*dep[y];ret-=2ll*(tmp.first-tmp.second);//the sum of lca's dep//cerr<<"Ret"<<ret<<endl;return ret;}int Dis(int x,int y){//cerr<<"Dis"<<x<<" "<<y<<endl;return dep[x]+dep[y]-2*dep[Getlca(x,y)];}ll Askdistance(int x,int top,int y,int d){//cerr<<"Askdistance"<<x<<" "<<top<<" "<<y<<endl;//True functionif (x<1||x>Pre::n) return 0;int ignore_pos=Getlca(x,y);//cerr<<"IGP"<<ignore_pos<<endl;if (linear_relative_in_order(x,ignore_pos,top)){return Downchain(x,ignore_pos,y,d)+Upchain(ignore_pos,top,y);}if (is_child(top,ignore_pos)) return Downchain(x,top,y,d);return Upchain(x,top,y);} }le,ri; //le 左鏈 //ri 右鏈 void Dfs(int x,int fa,bool iri){//cerr<<"Dfs"<<x<<" "<<fa<<" "<<iri<<endl;if (!x) return;dfn[x]=++clk;dep[x]=dep[fa]+1;::fa[x][0]=fa;if (fa){if (iri) ri.Append(x); else le.Append(x);}Dfs(son[x][0],x,0);Dfs(son[x][1],x,1);en[x]=clk; } int main(){Pre::Build_tree();Dfs(Pre::n+1,0,0);le.Ups();ri.Ups();Rebuild();le.Rebuild();ri.Rebuild();int m;read(m);for (int i=1; i<=m; ++i){int u,l,r;read(u);read(l);read(r);u=Pre::trans[u];--l;++r;if (l==0&&r==Pre::n+1){cout<<le.Dis(Pre::n+1,u)<<'\n';continue;}//cerr<<u<<" "<<l<<" "<<r<<endl;int lca=(l<1||l>Pre::n||r<1||r>Pre::n?0:Getlca(l,r));//cerr<<"lca"<<lca<<endl;cout<<le.Askdistance(l,upto(l,lca),u,0)+ri.Askdistance(r,upto(r,lca),u,1)<<'\n';//bug here} }

轉載于:https://www.cnblogs.com/Yuhuger/p/10505842.html

總結

以上是生活随笔為你收集整理的ZJOI 2017 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。