校门外的树（3）

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

这道题暴力线段树无法维护，因为每个时刻只有一种树，所以想到直接管树的种类即可。其实对于一个区间查询（x， y），它的值就是树的总种类减去（1，x-1）的树的种类再减去（y+1，n）的树的种类。两颗线段树暴力维护即可。

 1 #include <cstdio>
 2 using namespace std;
 3 #define debug
 4 
 5 #ifdef debug
 6 const int maxn=55, maxm=55;
 7 #else
 8 const int maxn=50005, maxm=50005;
 9 #endif
10 
11 int n, m, flag;
12 int segl[maxn*4], segr[maxn*4];
13 int makl[maxn*4], makr[maxn*4];
14 
15 void swap(int &x, int &y){
16     int t=x;
17     x=y;
18     y=t;
19 }
20 
21 void pushdown(int x){
22     segl[x<<1]+=makl[x], segl[x<<1|1]+=makl[x];
23     makl[x<<1]+=makl[x], makl[x<<1|1]+=makl[x];
24     makl[x]=0;
25     segr[x<<1]+=makr[x], segr[x<<1|1]+=makr[x];
26     makr[x<<1]+=makr[x], makr[x<<1|1]+=makr[x];
27     makr[x]=0;
28 }
29 
30 void add(int pos, int l, int r, int L, int R){
31     if (l>r) return;
32     if (l>R||r<L) return;
33     if (l>=L&&r<=R){
34         if (flag==1) segl[pos]+=1, makl[pos]+=1;
35         else segr[pos]+=1, makr[pos]+=1;
36         return;
37     }
38     pushdown(pos);
39     int mid=(l+r)>>1;
40     add(pos<<1, l, mid, L, R);
41     add(pos<<1|1, mid+1, r, L, R);
42     if (flag==1) segl[pos]=segl[pos<<1]+segl[pos<<1|1];
43     else segr[pos]=segr[pos<<1]+segr[pos<<1|1];
44 }
45 
46 int query(int pos, int l, int r, int POS){
47     if (l>r) return 0;
48     if (l>POS||r<POS) return 0;
49     if (l==r) return flag==1?segl[pos]:segr[pos];
50     pushdown(pos);
51     int mid=(l+r)>>1;
52     return query(pos<<1, l, mid, POS)+query(pos<<1|1, mid+1, r, POS);
53 }
54 
55 int main(){
56     scanf("%d%d", &n, &m);
57     int op, x, y, cnttree=0;
58     for (int i=0; i<m; ++i){
59         scanf("%d%d%d", &op, &x, &y);
60         if (x>y) swap(x, y);
61         if (op==1){
62             ++cnttree;
63             flag=1;
64             add(1, 1, n, y+1, n);
65             flag=2;
66             add(1, 1, n, 1, x-1);
67         }
68         else{
69             flag=1;
70             int q1=query(1, 1, n, x);
71             flag=2;
72             int q2=query(1, 1, n, y);
73             printf("%d
",cnttree-q1-q2);
74         }
75     }
76     return 0;
77 }