# P1047 校门外的树 题解(P1047 tree outside the school gate)-其他

## P1047 校门外的树 题解(P1047 tree outside the school gate)

### AC代码

``````#include<bits/stdc++.h>
using namespace std;

int mp[10003];
int suo = -1;
int l,m;
int ans;

signed main()
{
cin >> l >> m;
for(int i=1;i<=m;++i)
{
int u,v;
cin >> u >> v;
mp[u] = v;
}
for(int i=0;i<=l;++i)
{
if(mp[i]&&mp[i]>suo)
{
suo = mp[i];
}
if(i<=suo){}
else ans++;
}
cout << ans << endl;

return 0;
}
``````
————————

This problem is relatively simple. You can do whatever you want, but it’s still a little complicated to look at the problem solution behind Luogu, so you can write it casually.

### Title Description

There is a row of trees on the road with a length of \ (L \) outside the gate of a school, and the interval between each two adjacent trees is 11 meters. We can regard the road as a number axis. One end of the road is at the position of number axis 0 and the other end is at the position of \$l \$; Each integer point on the number axis, that is \ (0,1,2, \ dots, l \), has a tree.

Because there are some areas on the road to build subways. These areas are represented by their starting and ending points on the number axis. It is known that the coordinates of the starting point and ending point of any region are integers, and there may be overlapping parts between regions. Now move the trees in these areas (including the two trees at the end of the area). Your task is to calculate how many trees there are on the road after all these trees are removed.

### Input format

The first line has two integers representing the length of the road \$l \$and the number of areas M

The next M lines, each with two integers u and V, represent the coordinates of the starting and ending points of a region.

### Output format

Output an integer per line, indicating the number of trees remaining on the road after these trees are removed.

### thinking

The simplest is to open an array, plant trees first, then pull them out, and simulate.

Then this problem can also be used as a line segment tree.

There’s also a Kodori tree behind it (I haven’t learned, I can’t).

In fact, this problem only needs to traverse the array with length \ (L \) once, with complexity \ (O (L) \). Firstly, through the array MP, the end position of each area is recorded at the starting position of each area, which can also be regarded as marking the starting position. When traversing the array, a traversal Suo is used to maintain the farthest location of the currently cut tree. The tree must not have been cut down when it did not meet the mark. After the tag is encountered, the variable Suo is updated. If the current position is less than Suo, the tree must be cut, otherwise it is not cut. Therefore, one layer of loop traversal can count the number of remaining trees.

### AC code

``````#include<bits/stdc++.h>
using namespace std;

int mp[10003];
int suo = -1;
int l,m;
int ans;

signed main()
{
cin >> l >> m;
for(int i=1;i<=m;++i)
{
int u,v;
cin >> u >> v;
mp[u] = v;
}
for(int i=0;i<=l;++i)
{
if(mp[i]&&mp[i]>suo)
{
suo = mp[i];
}
if(i<=suo){}
else ans++;
}
cout << ans << endl;

return 0;
}
``````