【解题报告】VijosP1448校门外的树（困难版）

原题：

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）

输入样例：

5 4
1 1 3
2 2 5
1 2 4
2 3 5

样例输出：

1
2

曾经，校门外的树是几行的暴力染色

然后，校门外的树是长长的线段树

后来啊，校门外的树是几行的树状数组

判断询问的区间与之前多少个已知区间有交集

如果将之前的已知区间双关键字排序

再做二分查找

很快就能得到有交集的区间数量

那么现在只有两个事情要办：

1、排序，要让已知的区间始终是有序的

2、查找，以logn的效率迅速找有交集的已知区间

可以用来联系线段树，也能作为树状数组的尝试

步骤（原来在写线段树的，写到一半突然发现树状数组可解，于是直接删代码写树状数组）：

1：如果当前根不为空：得到一个区间信息，从根开始，如果该区间比根小，则把左子节点当成根做下一次操作的根，比根大则把右子节点作为下一次操作的根

2：如果当前根为空：愉快地将该区间信息放在根位置上

3：返回第一步

我的程序：

 #include <stdio.h>

 int h[],t[];

 int n,k;

 void add(int a[],int k)

 {

     while(k<=n){

         a[k]++;

         k+=k&(-k);

     }

 }

 int search(int a[],int k)

 {

     int tot=;

     while(k){

         tot+=a[k];

         k-=k&(-k);

     }

     return tot;

 }

 int main()

 {

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

     for(int i=;i<=k;i++)

     {

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         if(a==){

             add(h,b);

             add(t,c);

         }

         else printf("%d\n",search(h,c)-search(t,b-));

     }

 }

PS：博客园第一文

巴特西

【解题报告】VijosP1448校门外的树（困难版）

最新文章

热门文章