首页 > bzoj 2588 Spoj 10628. Count on a tree （可持久化线段树）

bzoj 2588 Spoj 10628. Count on a tree （可持久化线段树）

Spoj 10628. Count on a tree

Time Limit: 12 Sec  Memory Limit: 128 MB

Submit: 7669  Solved: 1894

[Submit][Status][Discuss]

Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

 

Input

第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5

105 2 9 3 8 5 7 7

1 2

1 3

1 4

3 5

3 6

3 7

4 8

2 5 1

0 5 2

10 5 3

11 5 4

110 8 2

Sample Output

2

8

9

105

7

HINT

 







HINT：


N,M<=100000


暴力自重。。。

 

Source

鸣谢seter

题解，可持久化权值线段树上二分即可，
很好理解的，我自己写的runtime了好久，不知道为什么。
改成hzwer的就过了，GG。
AC代码
  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 
  7 #define N 100007
  8 #define M 2000007
  9 using namespace std;
 10 inline int read()
 11 {
 12     int x=0,f=1;char ch=getchar();
 13     while(ch>'9'||ch<'0'){ if (ch=='-') f=-1;ch=getchar();}
 14     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 
 18 int n,m,top,sz,ind;
 19 int a[N],zhi[N];
 20 int num[N],fx[N];
 21 int cnt,head[N],next[2*N],rea[2*N];
 22 int ls[M],rs[M],sum[M],root[N];
 23 int deep[N],fa[N][17];
 24 
 25 int find(int x)
 26 {
 27     int l=1,r=top;
 28     while(l<=r)
 29     {
 30         int mid=(l+r)>>1;
 31         if (zhi[mid]==x) return mid;
 32         if (zhi[mid]1;
 33         else r=mid-1;
 34     }
 35 }
 36 void add(int u,int v)
 37 {
 38     next[++cnt]=head[u];
 39     head[u]=cnt;
 40     rea[cnt]=v;
 41 }
 42 void dfs(int u)
 43 {
 44     ind++,num[ind]=u,fx[u]=ind;
 45     for (int i=1;i<=16;i++)
 46         fa[u][i]=fa[fa[u][i-1]][i-1];
 47     for (int i=head[u];i!=-1;i=next[i])
 48     {
 49         int v=rea[i];
 50         if (fa[u][0]!=v)
 51         {
 52             deep[v]=deep[u]+1;
 53             fa[v][0]=u;
 54             dfs(v);
 55         }
 56     }
 57 }
 58 int lca(int a,int b)
 59 {
 60     if (deep[a]<deep[b]) swap(a,b);
 61     int i;
 62     for (i=0;(1<);
 63     i--;
 64     for (int j=i;j>=0;j--)
 65         if (deep[a]-(1<=deep[b]) a=fa[a][j];
 66     if (a==b) return a;
 67     for (int j=i;j>=0;j--)
 68         if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];
 69     return fa[a][0];        
 70 }
 71 void change(int l,int r,int x,int &y,int z)
 72 {
 73     y=++sz;
 74     sum[y]=sum[x]+1;
 75     if (l==r) return;
 76     ls[y]=ls[x],rs[y]=rs[x];
 77     int mid=(l+r)>>1;
 78     if (z<=mid) change(l,mid,ls[x],ls[y],z);
 79     else change(mid+1,r,rs[x],rs[y],z);
 80 }
 81 int query(int l,int r,int a,int b,int c,int d,int rank)
 82 {
 83     if (l==r) return zhi[l];
 84     int mid=(l+r)>>1,tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
 85     if (tmp>=rank) return query(l,mid,ls[a],ls[b],ls[c],ls[d],rank);
 86     else return query(mid+1,r,rs[a],rs[b],rs[c],rs[d],rank-tmp);
 87     
 88 }
 89 int que(int x,int y,int rk)
 90 {
 91     int a=x,b=y,c=lca(x,y),d=fa[c][0];
 92     a=root[fx[a]],b=root[fx[b]],c=root[fx[c]],d=root[fx[d]];
 93     int l=1,r=top;
 94     while(l<r)
 95     {
 96         int mid=(l+r)>>1;
 97         int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
 98         if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
 99         else rk-=tmp,l=mid+1,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
100     }
101     return zhi[l];
102 }
103 int main()
104 {
105     memset(head,-1,sizeof(head));
106     n=read(),m=read();
107     for (int i=1;i<=n;i++)
108         a[i]=read(),zhi[i]=a[i];
109     sort(zhi+1,zhi+n+1);
110     top=1;
111     for (int i=2;i<=n;i++)
112         if (zhi[i]!=zhi[i-1]) zhi[++top]=zhi[i];
113     for (int i=1;i<=n;i++)
114         a[i]=find(a[i]);
115     for (int i=1;i)
116     {
117         int x=read(),y=read();
118         add(x,y),add(y,x);
119     }
120     dfs(1);
121     for (int i=1;i<=n;i++)
122     {
123         int t=num[i];//从标号的1开始。 
124         change(1,top,root[fx[fa[t][0]]],root[i],a[t]);
125     }
126     int last=0;
127     for(int i=1;i<=m;i++)
128     {
129         int x=read(),y=read(),rk=read();
130         x^=last;
131         last=que(x,y,rk);
132         printf("%d",last);
133         if(i!=m)printf("
");
134     }
135     /*for (int i=1;i<=m;i++)
136     {
137         int x=read(),y=read(),rank=read();
138         x^=last;
139         int a=root[fx[x]],b=root[fx[y]],c=root[fx[lca(x,y)]],d=root[fx[fa[lca(x,y)][0]]];
140         last=query(1,top,a,b,c,d,rank);
141         printf("%d",last);
142         if (i!=m) cout<143     }*/
144 }

 

Wrong代码

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 
  7 #define N 100007
  8 #define M 3000007
  9 using namespace std;
 10 inline int read()
 11 {
 12     int x=0,f=1;char ch=getchar();
 13     while(ch>'9'||ch<'0'){ if (ch=='-') f=-1;ch=getchar();}
 14     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 
 18 int n,m,top,sz,ind;
 19 int a[N],zhi[N];
 20 int num[N],fx[N];
 21 int cnt,head[N],next[2*N],rea[2*N];
 22 int ls[M],rs[M],sum[M],root[N];
 23 int deep[N],fa[N][17];
 24 
 25 int find(int x)
 26 {
 27     int l=1,r=top;
 28     while(l<=r)
 29     {
 30         int mid=(l+r)>>1;
 31         if (zhi[mid]==x) return mid;
 32         if (zhi[mid]1;
 33         else r=mid-1;
 34     }
 35 }
 36 void add(int u,int v)
 37 {
 38     next[++cnt]=head[u];
 39     head[u]=cnt;
 40     rea[cnt]=v;
 41 }
 42 void dfs(int u)
 43 {
 44     ind++,num[ind]=u,fx[u]=ind;
 45     for (int i=1;i<=16;i++)
 46         fa[u][i]=fa[fa[u][i-1]][i-1];
 47     for (int i=head[u];i!=-1;i=next[i])
 48     {
 49         int v=rea[i];
 50         if (fa[u][0]!=v)
 51         {
 52             deep[v]=deep[u]+1;
 53             fa[v][0]=u;
 54             dfs(v);
 55         }
 56     }
 57 }
 58 int lca(int a,int b)
 59 {
 60     if (deep[a]<deep[b]) swap(a,b);
 61     int i;
 62     for (i=0;(1<);
 63     i--;
 64     for (int j=i;j>=0;j--)
 65         if (deep[a]-(1<=deep[b]) a=fa[a][j];
 66     if (a==b) return a;
 67     for (int j=i;j>=0;j--)
 68         if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];
 69     return fa[a][0];        
 70 }
 71 void change(int l,int r,int x,int &y,int z)
 72 {
 73     y=++sz;
 74     sum[y]=sum[x]+1;
 75     if (l==r) return;
 76     ls[y]=ls[x],rs[y]=rs[x];
 77     int mid=(l+r)>>1;
 78     if (z<=mid) change(l,mid,ls[x],ls[y],z);
 79     else change(mid+1,r,rs[x],rs[y],z);
 80 }
 81 int query(int l,int r,int a,int b,int c,int d,int rank)
 82 {
 83     if (l==r) return zhi[l];
 84     int mid=(l+r)>>1,tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
 85     if (tmp>=rank) return query(l,mid,ls[a],ls[b],ls[c],ls[d],rank);
 86     else return query(mid+1,r,rs[a],rs[b],rs[c],rs[d],rank-tmp);
 87 }
 88 int main()
 89 {
 90     memset(head,-1,sizeof(head));
 91     n=read(),m=read();
 92     for (int i=1;i<=n;i++)
 93         a[i]=read(),zhi[i]=a[i];
 94     sort(zhi+1,zhi+n+1);
 95     top=1;
 96     for (int i=2;i<=n;i++)
 97         if (zhi[i]!=zhi[i-1]) zhi[++top]=zhi[i];
 98     for (int i=1;i<=n;i++)
 99         a[i]=find(a[i]);
100     for (int i=1;i)
101     {
102         int x=read(),y=read();
103         add(x,y),add(y,x);
104     }
105     dfs(1);
106     for (int i=1;i<=n;i++)
107     {
108         int t=num[i];//从标号的1开始。 
109         change(1,top,root[fx[fa[t][0]]],root[i],a[t]);
110     }
111     int last=0;
112     for (int i=1;i<=m;i++)
113     {
114         int x=read(),y=read(),rank=read();
115         x^=last;
116         int a=root[fx[x]],b=root[fx[y]],c=root[fx[lca(x,y)]],d=root[fx[fa[lca(x,y)][0]]];
117         last=query(1,top,a,b,c,d,rank);
118         printf("%d",last);
119         if (i!=m) cout<<endl;
120     }
121 }

 

转载于:https://www.cnblogs.com/fengzhiyuan/p/8034556.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • SAP EWM 代码实现Transportation Unit(TU)的创建

    在EWM中很少有创建或者修改业务对象的BAPI存在，更多的是通过很多面向对象的类方法来实现。 以下这个简单的创建TU应该能很好的体现SCM平台中的OO特性。 REPORT yewm_tu_creation NO STANDARD PAGE HEADING. TYPES:   BEGIN OF lty_key_wrk,     tu_n...

  • linux rm命令

    001.删除不以特定字符串结尾的文件 1.） rm -f `ls | grep -v '.c$'`(删除所有的非c源文件: ls前面" ' "为反向引号, 键盘1前面的键; "." 需要转义) 转载于:https://www.cnblogs.com/itpoorman/p/3858611.html...

  • 相机标定 matlab opencv ROS三种方法标定步骤（2）

    #include #include #include #include #include #include #include

  • 剑指offer：面试题20. 表示数值的字符串

    题目：表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。 解题： 数值错误的形式有多种多样，但是正确的...

  • 数字太大了，计算加法、减法会报错，结果不正确？怎么办？用JavaScript实现大数据（超过20位的数字）相加减运算。

    加法伺候  //超过20位数值相加---------------------------------------- function bigNumAdd(a, b) {if (!(typeof a === "string" && typeof b === "string")) return console.log("传入参数必...

  • Python中使用中文正则表达式匹配指定的中文字符串

    业务场景： 从中文字句中匹配出指定的中文子字符串 .这样的情况我在工作中遇到非常多, 特梳理总结如下. 难点: 处理GBK和utf8之类的字符编码, 同时正则匹配Pattern中包含汉字,要汉字正常发挥作用,必须非常谨慎.推荐最好统一为utf8编码,如果不是这种最优情况,也有酌情处理. 往往一个具有普适性的正则表达式会简化程...

  • Linux 下获取本机所有网卡 以及 网卡对应ip 列表

    简单record 一下 #include // 'struct sockaddr_in' #include #include // 'struct ifreq' and 'struct if_nameindex' #include #inc...

©2024 11GX.COM