数据结构练习-白红宇

数据结构练习

阅读量：5742 次

发布时间：2019-06-18

本文共 5176 字，大约阅读时间需要 17 分钟。

P2320 - 【长郡模拟赛】数据结构练习

Description

费了一番功夫，神犇 CJK 终于完成了前三道题目。“不错，不愧是新一代神犇啊！” JesseLiu 满意地说道，“不过，你在算法方面的功底固然不错。对于数据结构的运用，你又掌握地如何呢？”

听到“数据结构”这四个字，就连身为神犇的 CJK 也不禁吓出一身冷汗。“年轻人，现在，对于我给定一棵树，你需要完成以下操作：

1.修改某个点的权值；

2.查询某两点间路径上所有点的权值和；

3.查询某点子树的权值和。”

CJK 脸上闪过一丝不屑：不就是道链剖裸题吗？

“这只是第一问。”JesseLiu 似乎也觉得这道题太水了，于是补充道：“完成以上所有操作后，我还会有以下几种询问：

1. 询问某个点子树上有多少个点的权值小于等于 k；

2. 询问某两点之间的路径上有多少点的权值小于等于 k；”

尽管 CJK 是神犇，但遇到这种题，也不禁感到一丝恐惧。还好，通过自己的玄学力量，他联系到了他的同学——你。现在，就请你 A 掉这最后一道水题。

Input

第一行一个数 n，表示点的总数。接下来 n-1 行，一行两个整数 x 和 y，表示 x 和 y 之间有边相连。接下来一个整数 m1，表示第一问中操作的数量。接下来 m1 行表示操作，格式如下：

“1 x y”将点 x 的权值修改为 y；

“2 x y”询问 x 到 y 路径上的点权之和（包括 x 和 y）；

“3 x”询问 x 的子树上的点权和（包括 x）；

接下来一行 m2，表示第二问中操作的数量。接下来 m2 行描述操作，格式如下：

“1 x y z”询问 x 到 y 的路径上有多少个点的权值小于等于 z；

“2 x y”询问 x 的子树上有多少个点的权值小于等于 y；

每个点的初始权值为 0,默认树根为 1 号节点。

Output

对于每一次询问，输出一个整数表示询问的答案。

Sample Input

样例①：

1 2

1 3

1 1 3

1 3 1

3 1

2 1 2

1 1 3 1

样例②：

1 2

1 3

3 4

3 5

3 1

1 3 1

2 4 5

1 4 -1

3 3

1 1 5 0

2 3 -1

Sample Output

样例①：

样例②：

Hint

对于 30%的数据，n<=100,m1<=100,m2<=100。剩下的数据保证 n<=50000；

对于另外 30%的数据，m2=0。其中有 1 组数据，树退化为链;

对于 100%的数据，保证 n<=50000,m1<=50000,m2<=50000，保证题目中所有输入、输出、中间运算不超过 int 范围。

Source

叶闻捷出题 NOIP 模拟测试T4

第二问：离线做法。

我们可以与第一问类比一下：对于第一问，所有对答案有贡献的点只有一个约束条件：该点在给定两点的路径上（或在给定点的子树上）。而一个点对答案的贡献就是它的权值，所以用树链剖分区间求和即可。

再看看第二问：一个点要对答案有贡献，必须满足两个条件：（1）该点在给定两点的路径上（或在给定点的子树上）；（2）该点的权值小于等于一个给定的值k。而每个点对于答案的贡献是1。

如果只要求满足第一个条件，那么我们只需要像第一问一样区间求和就可以了。但是，还有第二个条件的约束。所以，我们需要保证：在询问时，只有权值小于等于k（k的意义见上）的点能对答案产生贡献。也就是说，只有权值小于等于k的点对应的dfs序在线段树中对应的点为1，其它都是0。

所以，我们可以把树上的每一个点当做一次修改操作（把对应的

dfs序在线段树中对应的值修改为1），每一个询问操作就是统计路径（子树）上有多少个1（其实就是一次区间求和，和第一问一模一样）。我们只需要在进行操作之前，对于所有的操作，以权值为关键字（修改操作的权值是对应的点权，询问操作的权值为对应的k）由小到大排序，权值相同的把修改放到查询之前。然后和第一问一样地跑就可以了。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #include
                 12 #include
                 
                   13 #define rep(i,a,b) for(register int i=a;i<=b;i++) 14 #define il inline 15 #define ll long long 16 #define RG register 17 #define ls o<<1 18 #define rs (o<<1)|1 19 #define mimi RG int mid=(L+R)>>1; 20 using namespace std; 21 const int N=50010,M=50010; 22 struct E { 23 int to,net; 24 }e[N*2]; 25 struct ASK{ 26 int x,y,k; 27 int f; 28 }a[M],dig[M]; 29 int head[N],top[N],tid[N],pos[N],siz[N],dep[N],son[N],fa[N],oh[N],idx,num_e,n,m1,m2; 30 int W[N],sum[N]; 31 int gi(); 32 void add(int x,int y) { 33 e[++num_e].to=y , e[num_e].net=head[x] , head[x] = num_e; 34 } 35 int comp(const ASK& a,const ASK& b) { 36 if(a.k
                  
                   b.k) return 0; 38 return a.f>b.f; 39 } 40 void dfs1(int x,int fu) { 41 siz[x]=1; 42 dep[x]=dep[fu]+1; 43 fa[x]=fu; 44 for(RG int i=head[x];i;i=e[i].net) { 45 int to=e[i].to; 46 if(to==fu) continue; 47 dfs1(to,x); 48 siz[x] += siz[to]; 49 if(siz[to]>siz[son[x]]) son[x]=to; 50 } 51 } 52 void dfs2(int x,int tp) { 53 tid[x]=++idx; 54 pos[idx]=x; 55 top[x]=tp; 56 oh[x]=idx; 57 if(!son[x]) return; 58 dfs2(son[x],tp);// bug 59 oh[x]=oh[son[x]]; 60 for(RG int i=head[x];i;i=e[i].net) { 61 int to=e[i].to; 62 if(to!=fa[x]&&to!=son[x]) dfs2(to,to),oh[x]=max(oh[x],oh[to]); 63 } 64 } 65 void Update(int o,int L,int R,int p,int x) { 66 if(L==R&&p==L) { 67 sum[o]=x;return; 68 } 69 mimi; 70 if(p<=mid) Update(ls,L,mid,p,x); 71 else Update(rs,mid+1,R,p,x); 72 sum[o]=sum[ls]+sum[rs]; 73 } 74 int querysum(int o,int L,int R,int l,int r) { 75 if(l<=L&&R<=r) return sum[o]; 76 mimi; 77 int he=0; 78 if(l<=mid) he += querysum(ls,L,mid,l,r); 79 if(r>mid) he += querysum(rs,mid+1,R,l,r); 80 return he; 81 } 82 int solve(int x,int y) { 83 int he=0; 84 // rep(i,1,n) printf("top=%d ",top[i]);puts("\n"); 85 while(top[x]!=top[y]) { 86 if(dep[top[x]]>dep[top[y]]) swap(x,y); 87 he += querysum(1,1,n,tid[top[y]],tid[y]); 88 y=fa[top[y]]; 89 } 90 if(dep[x]>dep[y]) swap(x,y); 91 he += querysum(1,1,n,tid[x],tid[y]); 92 return he; 93 } 94 void ONE() { 95 n=gi(); 96 RG int x,y; 97 rep(i,1,n-1) { 98 x=gi(),y=gi();add(x,y),add(y,x); 99 }100 dfs1(1,0);101 dfs2(1,1);102 m1=gi();RG int k;103 while(m1--) {104 k=gi(),x=gi();105 if(k==1) y=gi(),Update(1,1,n,tid[x],y),W[tid[x]]=y;// val[x]106 else if(k==2) y=gi(),printf("%d\n",solve(x,y));107 else printf("%d\n",querysum(1,1,n,tid[x],oh[x]));108 }109 return;110 }111 void TWO() {112 m2=gi();113 memset(sum,0,sizeof(sum));114 RG int x,y,k;// ghost115 rep(i,1,m2) {116 k=gi(),x=gi(),y=gi();117 if(k==1) a[i].x=x,a[i].y=y,a[i].k=gi();118 else a[i].x=x,a[i].y=pos[oh[x]],a[i].k=y;119 }120 int num=m2;121 rep(i,1,n) a[++num].x=i,a[num].k=W[tid[i]],a[num].f=1;122 sort(a+1,a+num+1,comp);123 rep(i,1,num) printf("%d %d %d\n",a[i].x,a[i].y,a[i].f);124 rep(i,1,num) {125 if(a[i].f==0) printf("%d\n",solve(a[i].x,a[i].y));126 else Update(1,1,n,tid[a[i].x],1);127 }128 return;129 }130 int main() {131 freopen("datastruct.in","r",stdin);132 freopen("datastruct.out","w",stdout);133 ONE();134 TWO();135 return 0;136 }137 int gi() {138 int res=0,f=1;139 char ch=getchar();140 while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();141 if(ch=='-') ch=getchar(),f=-1;142 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();143 return res*f;144 }