卿学姐与基本法

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

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

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

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

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

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

在这个国家总共有

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

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

Input

第一行两个整数

接下来

Output

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

Sample input and output

Sample Input	Sample Output
5 3 1 1 2 1 4 5 2 2 4	1

思路：

一开始不会离散化，直接暴力又TLE，，，好惨==

想到一个不用线段数，离散化什么的做法，

就是每次只记录对区间的修改操作，而不执行。。

用map记录操作，之后好排序什么

然后询问的时候就把询问区间看做线段，用已有线段（就是上面说的对区间的修改操作）进行线段剪裁，把询问区间和排序好的操作区间从左到右一一对比，把询问区间剪裁并执行相应的求和操作；（因为两个线段之间的关系就几种情况，分类讨论就好）

ps：离散化的做法就是对会用到数排个序，然后做个映射就好，再用线段树就不会超内存了

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <vector>
10 #include <cstdlib>
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 
17 map<int,int>q;
18 map<int,int>::iterator it;
19 int query(int x,int y)
20 {
21 //    if(x==31)
22 //    {
23 //        int cds=0;
24 //    }
25     int l=x,r=y,ans=y-x+1;
26     for(it=q.begin();it!=q.end();it++)
27     {
28         int a=it->first,b=it->second;
29         if(a>r)
30             return ans;
31         else if(b<l)
32             continue;
33         else if(a<l&&r<b)
34             return ans-=r-l+1;
35         else
36         {
37             if(a<=l && b<=r)
38                 ans-=b-l+1,l=b+1;
39             else if(a>l && b<=r)
40                 ans-=b-a+1,l=b+1;
41             else
42                 return ans-=r-a+1;
43         }
44     }
45     return ans;
46 }
47 int main (void)
48 {
49 
50     //freopen("test.txt","r",stdin);
51     //freopen("ans1.txt","w",stdout);
52     int t,n,op,x,y;
53     scanf("%d%d",&n,&t);
54     while(t--)
55     {
56         scanf("%d%d%d",&op,&x,&y);
57         if(op==1)
58         {
59             if(q[x]<y) q[x]=y;
60         }
61         else
62             printf("%d
",query(x,y));
63     }
64     return 0;
65 }

View Code