首页 > 代码库 > Vijos1448校门外的树 题解
Vijos1448校门外的树 题解
Vijos1448校门外的树 题解
描述：
校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）
输入格式：
第一行n,m表示道路总长为n，共有m个操作
接下来m行为m个操作
输出格式：
对于每个k=2输出一个答案
样例输入：
5 4
1 1 3
2 2 5
1 2 4
2 3 5
样例输出：
1
2
数据范围：
20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000
原题地址：https://vijos.org/p/1448
~~~~~~~~~~~~~~~~~~~~~~~~~~~分割线~~~~~~~~~~~~~~~~~~~~~~~~~~~
分析：
这道题是一个典型的区间问题，考虑到数据量较大，使用线段树完成这个操作。由于树的种类很多，不难想到用线段树暴力维护的方法。但是暴力维护一定会超时，那么这么解决这个问题呢？
这里介绍一种十分机智的想法——括号序列。
假设有一个长度为10的数轴，我们要将区间[ 2 , 5 ]中种树，这时，我们将 2 处放一个左括号 " ( " ,5处放一个 " )" ，表示区间 [ 2 , 5 ]种了树。
查询某个区间树的种类，如区间[ 3 , 10]，只需统计10之前（包括10）有多少个‘（’，统计3之前有多少个‘）’，（不包括3）。
如下图所示：
以上就是括号序列的过程。简单的说，就是更新区间[a,b]时，点a记录左括号数，点b记录右括号数，查询区间[a,b]时，即为b之前（包括b）的左括号数-a之前的右括号数。
下面贴注释代码：
1 #include "bits/stdc++.h" 2 #define maxN 50010 3 4 using namespace std ; 5 typedef long long QAQ ; 6 7 struct Tree 8 { 9 int l , r ;10 QAQ liml , limr ;//左括号右括号11 };12 13 Tree tr[maxN << 2];14 15 void Build_Tree ( int x , int y , int i )//建树16 {17 tr[i].l = x ;18 tr[i].r = y ;19 if( x == y )return ;20 else21 {22 QAQ mid = (tr[i].l + tr[i].r) >> 1 ;23 Build_Tree ( x , mid , i << 1);24 Build_Tree ( mid + 1 , y , i << 1 | 1);25 return ;26 }27 }28 29 void Update_left ( int w , int i )30 {31 if( w == tr[i].l && w == tr[i].r )tr[i].liml++;//找到目标节点32 else33 {34 QAQ mid = (tr[i].l + tr[i].r) >> 1 ;35 if( w > mid )Update_left( w , i << 1 | 1);//找右儿子36 else if( w <= mid)Update_left( w , i << 1 );//找左儿子37 tr[i].liml = tr[i << 1].liml + tr[i << 1 | 1].liml ;//回溯更新38 }39 }40 41 void Update_right ( int w , int i )//同Update_left42 {43 if( w == tr[i].l && w == tr[i].r )tr[i].limr++;44 else45 {46 QAQ mid = (tr[i].l + tr[i].r) >> 1 ;47 if( w > mid )Update_right( w , i << 1 | 1);48 else if( w <= mid)Update_right( w , i << 1 );49 tr[i].limr = tr[i << 1].limr + tr[i << 1 | 1].limr ;50 }51 }52 53 QAQ Query_left ( int q , int w , int i )//同Query_right54 {55 if( q <= tr[i].l && w >= tr[i].r )return tr[i].liml ;56 else57 {58 QAQ mid = (tr[i].l + tr[i].r) >> 1 ;59 if ( q > mid )return Query_left ( q , w , i << 1 | 1);60 else if ( w <= mid ) return Query_left ( q , w , i << 1);61 else return Query_left ( q , w , i << 1 | 1) + Query_left ( q , w , i << 1);62 }63 }64 65 QAQ Query_right ( int q , int w , int i )66 {67 if( q <= tr[i].l && w >= tr[i].r )return tr[i].limr ;//找到目标区间直接返回68 else69 {70 QAQ mid = (tr[i].l + tr[i].r) >> 1 ;71 if ( q > mid )return Query_right ( q , w , i << 1 | 1);//找右儿子72 else if ( w <= mid ) return Query_right ( q , w , i << 1);//找左儿子73 else return Query_right ( q , w , i << 1 | 1) + Query_right ( q , w , i << 1);//左右儿子都查找74 }75 }76 77 int main()78 {79 int N, M, op, ll, rr ;80 scanf("%d %d", &N, &M);81 Build_Tree ( 1 , N , 1 ) ;//建树82 while(M--)83 {84 scanf("%d%d%d", &op, &ll, &rr);85 if( op == 1 )86 {87 Update_left ( ll , 1);//添加左括号88 Update_right ( rr , 1 );//添加右括号89 }90 else91 {92 QAQ ans = Query_left( 1 , rr , 1);93 if (ll != 1)ans -= Query_right(1 , ll - 1 , 1);//当ll不等于1时再相减，否则栈会炸94 printf("%I64d\n", ans);95 }96 }97 return 0 ;98 }
PS: 本题也可以用树状数组完成，代码量较少，容易实现。
（完）
Vijos1448校门外的树 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。