一本通1537校门外的树

1537：【例 3】校门外的树

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

原题来自：Vijos P1448

校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：

$K = 1$ ，读入 $l, r$ 表示在 $l$ 到 $r$ 之间种上一种树，每次操作种的树的种类都不同；

$K = 2$ ，读入 $l, r$ 表示询问 $l$ 到 $r$ 之间有多少种树。

注意：每个位置都可以重复种树。

【输入】

第一行 $n, m$ 表示道路总长为 $n$ ，共有 $m$ 个操作；

接下来 $m$ 行为 $m$ 个操作。

【输出】

对于每个 $k = 2$ 输出一个答案。

【输入样例】

【输出样例】

1
2

【提示】

数据范围与提示：

对于 20% 的数据， $1 \leq n, m \leq 100$ ；

对于 60% 的数据， $1 \leq n \leq 10^{3}, 1 \leq m \leq 5 \times 10^{4}$

对于 100% 的数据， $1 \leq n, m \leq 5 \times 10^{4}$ ，保证 l,r>0

要使两个区间有交集，如[a,b]与[s,t] 要满足 a<=t且b>=s

于是根据本题，维护两个BIT即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=50005;
 4 int n,m;
 5 struct BIT
 6 {
 7     int S[N];
 8     inline int lowbit(int x)
 9     {
10         return ((x)&(-x));
11     }
12     inline void Ins(int Pos,int Tag)
13     {
14         while(Pos>0)
15         {
16             S[Pos]+=Tag;
17             Pos-=lowbit(Pos);
18         }
19         return;
20     }
21     inline int Que(int Pos)
22     {
23         int Sum=0;
24         while(Pos<=n)
25         {
26             Sum+=S[Pos];
27             Pos+=lowbit(Pos);
28         }
29         return Sum;
30     }
31 }T1,T2;
32 int main()
33 {
34 //    freopen("tree2.in","r",stdin);
35 //    freopen("my.out","w",stdout);
36     int i;
37     scanf("%d%d",&n,&m);
38     for(i=1;i<=m;i++)
39     {
40         int opt,a,b;
41         scanf("%d%d%d",&opt,&a,&b);
42         if(opt==1)
43         {
44             T1.Ins(b,1);
45             T2.Ins(a,1);
46         }
47         else
48         {
49             printf("%d
",T1.Que(a)-T2.Que(b+1));
50         }
51     }
52     return 0;
53 }
54 /*
55 input
56 5 4
57 1 1 3
58 2 2 5
59 1 2 4
60 2 3 5
61 output
62 1
63 2
64 */

View Code