bzoj3551 Peaks加强版

这个题……感觉离线和在线的代码难度差不多(pb_ds不要说话)。

离线的话，就是把所有询问按照w排个序，然后一边Kruskal+平衡树启发式合并一边回答询问就好了。

在线也不难写。首先Kruskal重构树(这个Kruskal重构树是不按秩合并还要添虚点的那种……)，那么每个点可以到达的点一定在某个子树里。子树的dfs序是连续的，所以可以对dfs序建主席树来求区间k大。又因为只有叶子节点的点权是有意义的，所以可以只对叶子的dfs序建主席树。查询的时候倍增跳到最高的w<=询问的w的点然后主席树就好了。

其实树剖跳父亲也可以，先跳整条链，整条链跳不动的时候就在最后一条链上二分，也是O(logn)的。不过可能是太弱，二分写挂了，结果WA到死……无奈用倍增重写了一遍。

限时20s，结果我跑了19.8s，这速度真是感人肺腑……

还有，copy的那个a一开始忘了+1了，调了一节课，虚死……

 /**************************************************************

     Problem: 3551

     User: hzoier

     Language: C++

     Result: Accepted

     Time:19800 ms

     Memory:114432 kb

 ****************************************************************/

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=,maxe=;

 struct edge{

     int from,to,w;

     bool operator<(const edge &e)const{return w<e.w;}

 }e[maxe+maxn];

 void Kruskal();

 int findroot(int);

 void mergeset(int,int);

 void dfs(int);

 void build(int,int,int&,int);

 void query(int,int,int,int);

 int sm[maxn<<],lc[maxn<<],rc[maxn<<],root[maxn],tree_cnt=;

 int n,M=,m,q,h[maxn],a[maxn],cnt,prt[maxn],w[maxn],f[maxn][],ch[maxn][],L[maxn],R[maxn],pr=,x,d,k,ans;

 int main(){

     scanf("%d%d%d",&n,&m,&q);

     while((<<M)<(n<<))M++;

     for(int i=;i<=n;i++)scanf("%d",&h[i]);

     copy(h+,h+n+,a+);

     sort(a+,a+n+);

     for(int i=;i<=n;i++)h[i]=lower_bound(a+,a+n+,h[i])-a;

     for(int i=;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);

     for(int i=;i<=n;i++){

         e[++m].from=;

         e[m].to=i;

         e[m].w=~(<<);

     }

     cnt=n;

     Kruskal();

     dfs(cnt);

     for(int j=;j<=M;j++)for(int i=;i<=cnt;i++)f[i][j]=f[f[i][j-]][j-];

     while(q--){

         scanf("%d%d%d",&x,&d,&k);

         if(ans!=-){x^=ans;d^=ans;k^=ans;}

         for(int j=M;j!=-;j--)if(f[x][j]&&w[f[x][j]]<=d)x=f[x][j];

         query(,n,root[R[x]],root[L[x]-]);

         printf("%d\n",ans);

     }

     return ;

 }

 void Kruskal(){

     for(int i=;i<=n;i++)prt[i]=i;

     stable_sort(e+,e+m+);

     for(int i=;i<=m;i++)if(findroot(e[i].from)!=findroot(e[i].to)){

         cnt++;

         prt[cnt]=cnt;

         w[cnt]=e[i].w;

         ch[cnt][]=findroot(e[i].from);

         ch[cnt][]=findroot(e[i].to);

         mergeset(e[i].from,cnt);

         mergeset(e[i].to,cnt);

     }

 }

 int findroot(int x){return prt[x]==x?x:(prt[x]=findroot(prt[x]));}

 void mergeset(int x,int y){prt[findroot(x)]=findroot(y);}

 void dfs(int x){

     if(ch[x][]){

         f[ch[x][]][]=f[ch[x][]][]=x;

         dfs(ch[x][]);

         dfs(ch[x][]);

         L[x]=L[ch[x][]];

         R[x]=R[ch[x][]];

     }

     else{

         k=h[x];

         build(,n,root[pr+],root[pr]);

         L[x]=R[x]=++pr;

     }

 }

 void build(int l,int r,int &rt,int pr){

     sm[rt=++tree_cnt]=sm[pr]+;

     if(l==r)return;

     lc[rt]=lc[pr];rc[rt]=rc[pr];

     int mid=(l+r)>>;

     if(k<=mid)build(l,mid,lc[rt],lc[pr]);

     else build(mid+,r,rc[rt],rc[pr]);

 }

 void query(int l,int r,int rt,int pr){

     if(sm[rt]-sm[pr]<k){

         ans=-;

         return;

     }

     if(l==r){

         ans=a[l];

         return;

     }

     int mid=(l+r)>>;

     if(k<=sm[rc[rt]]-sm[rc[pr]])query(mid+,r,rc[rt],rc[pr]);

     else{

         k-=sm[rc[rt]]-sm[rc[pr]];

         query(l,mid,lc[rt],lc[pr]);

     }

 }

尽头和开端，总有一个在等你。

巴特西

bzoj3551 Peaks加强版

最新文章

热门文章