卿学姐与基本法 (线段树+离散化)

“做专题也要按照基本法”

离开了诡异的村庄，卿学姐来到了威廉·圣·乱七八糟王国，这里的国王咸鱼王是个智障。

国家涣散，盗贼四起，民不聊生。

见到这样的景象，卿学姐不禁潸然泪下，“悠悠苍天，奈何苦了苍生”。

自幼学习基本法的卿学姐决定向整个国家普及基本法，改善国家法度。

在这个国家总共有 $N$

由于整个国家的人实在是太多了，卿学姐每次只能对一个连续区间的编号的人普及基本法。

同时卿学姐还想知道在某个时刻某个区间还有多少人没有被普及基本法。

Input

第一行两个整数 $N, Q$

接下来 $Q$

$1 \leq N \leq 100000000$

$1 \leq Q \leq 100000$

$1 \leq t \leq 2$

$1 \leq L \leq R \leq N$

Output

输出每个卿学姐想知道的答案

Sample Input

Sample Output

1


//显然，若是对于每个人都当节点来考虑的话，是会爆内存的，
因为操作数比较小，在可接受的范围内，所以，将所有可能用到的 l,r 抽离出来，例如如果只操作 1 5 9 12 ，就将 1 5 9 12 抽出来建树，1代表 [1,5)，9代表[9,12) 这样就是离散化了
但是，有个小问题，比如我要查询 1-5 ,只能查询到 [1,9),显然不对， 所以，需要把右边，+1 后离散建树 
例如，如果上面的输入时是 
1 1 5 
1 9 12
2 5 9
建树的点即为 1 5 6 9 12 13 5 9 10
然后排序去重，即可 1 5 6 9 10 12 13

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <set>
  5 #include <map>
  6 #include <algorithm>
  7 using namespace std;
  8 #define MX 100005
  9 
 10 struct Node
 11 {
 12     int l,r;
 13     int lazy;
 14     int sum;  //已经普法人数
 15     int len;  //实际人数
 16 }node[MX*12];
 17 
 18 struct Op
 19 {
 20     int op;
 21     int l,r;
 22 }opr[MX];
 23 
 24 int n,q;
 25 int point[MX*4];
 26 map<int,int> dex;
 27 
 28 void Init(int l,int r,int k)
 29 {
 30     node[k]=(Node){l,r,0,0,point[r+1]-point[l]}; //区间实际人数
 31     if (l==r) return ;
 32     int mid = (l+r)/2;
 33     Init(l,mid,2*k);
 34     Init(mid+1,r,2*k+1);
 35 }
 36 
 37 void push_down(int k)
 38 {
 39     node[k*2].lazy=1;
 40     node[k*2].sum=node[k*2].len;
 41     node[k*2+1].lazy=1;
 42     node[k*2+1].sum=node[k*2+1].len;
 43     node[k].lazy=0;
 44 }
 45 
 46 void update(int l,int r,int k)
 47 {
 48     if (l==node[k].l&&r==node[k].r)
 49     {
 50         node[k].lazy=1;
 51         node[k].sum=node[k].len;
 52         return;
 53     }
 54     if (node[k].lazy) push_down(k);
 55     int mid = (node[k].l+node[k].r)/2;
 56     if (l>mid) update(l,r,2*k+1);
 57     else if (r<=mid) update(l,r,2*k);
 58     else
 59     {
 60         update(l,mid,2*k);
 61         update(mid+1,r,2*k+1);
 62     }
 63     node[k].sum = node[2*k].sum+node[2*k+1].sum;
 64 }
 65 
 66 int inquery(int l,int r,int k)
 67 {
 68     if (l==node[k].l&&r==node[k].r)
 69     {
 70         return node[k].sum;
 71     }
 72     if (node[k].lazy) push_down(k);
 73     int mid = (node[k].l+node[k].r)/2;
 74     if (l>mid) return inquery(l,r,2*k+1);
 75     else if (r<=mid) return inquery(l,r,2*k);
 76     return inquery(l,mid,2*k)+inquery(mid+1,r,2*k+1);
 77 }
 78 
 79 int main()
 80 {
 81     scanf("%d%d",&n,&q);
 82     int pn=1;
 83     for (int i=0;i<q;i++)
 84     {
 85         scanf("%d%d%d",&opr[i].op,&opr[i].l,&opr[i].r);
 86         point[pn++]=opr[i].l;
 87         point[pn++]=opr[i].r;
 88         point[pn++]=opr[i].r+1; // 很关键
 89     }
 90     pn--;
 91     sort(point+1,point+1+pn);
 92     pn = unique(point+1,point+1+pn)-(point+1);
 93     pn--; //最右边的端点[x,+++) 不会用到，不对它建树
 94     for (int i=1;i<=pn;i++)
 95         dex[point[i]]=i;
 96     Init(1,pn,1);
 97 
 98     for(int i=0;i<q;i++)
 99     {
100         int l=dex[opr[i].l];
101         int r=dex[opr[i].r];
102         if (opr[i].op==1)
103         {
104             update(l,r,1);
105         }
106         else
107         {
108             printf("%d
",opr[i].r-opr[i].l+1-inquery(l,r,1));
109         }
110     }
111     return 0;
112 }

View Code