1351:面朝大海 春暖花开 [ 数据加强版 ]

题目描述：

依然选择那些大晴天的日子,再一次行走在孤单的海岸线,静静地种更多的花给自己看~

我们假设把海岸线分为n块,每块的分别标记为1…n,每块都可以种花,每次种花可以选择某个[left,right]的闭区间,每块种上一朵花.经过m次种花操作后,根据输入的区间,求该区间内花的总数.
输入描述：

多组输入

对每组输入，第一行有两个整数n m,分别代表总块数和种花的次数.(1 <= n, m <= 100000)

接下来的m行, 每行两个整数 L,R 代表[L,R]区间内每块种上一朵花.(1 <= L <= R <= n)

最后一行,输入两个整数 a,b 代表最后要查询的花的总数的区间.(1 <= a <= b <= n)
输出描述：

对每组输入，输出区间[a,b]内花的总数
样例输入：

5 2

1 5

1 2

2 3
样例输出：

3

对于该题，由于数据量的扩大，通过数组模拟的方法来解已经不可行了，因为在模拟种花过程中，会嵌套两个for循环，时间复杂度为n^2，将会超时。由于每次种花只会在一片花田次数加1，所以可以先用一个100000行2列的二维数组存储下种花区间，其长度就代表了该区间种花增加的次数。读取了需要查询的区间后，遍历二维数组，将在查询区间内的次数加上，最后得出结果。由于只需要做n次判断和加法操作，所以大大降低了时间复杂度。

#include<stdio.h>int main(){int n;int m;int L;int R;int a;int b;int i=0;int k=0;while(scanf("%d",&n)!=EOF){int sum=0;int block[100000][2];for(i=0;i<100000;i++){for(k=0;k<2;k++){block[i][k]=0;}}scanf("%d",&m);
//记录下种花区间。for(i=0;i<m;i++){scanf("%d %d",&L,&R);block[i][0]=L;block[i][1]=R;}scanf("%d %d",&a,&b);
//根据条件判断需查询区间增加的种花次数。for(i=0;i<m;i++){if(block[i][1]<a);if(block[i][1]>=a&&block[i][1]<=b){if(block[i][0]<a){sum=sum+(block[i][1]-a+1);}if(block[i][0]>=a){sum=sum+(block[i][1]-block[i][0]+1);    }}if(block[i][1]>b){if(block[i][0]<a){sum=sum+(b-a+1);}if(block[i][0]>=a&&block[i][0]<=b){sum=sum+(b-block[i][0]+1);}if(block[i][0]>b);}}printf("%d\n",sum);}return 0;
}