【题解】Cutting Woods

题目链接: Cutting Woods

题意:

题意很简单，给我们一个长度为N的区间，有M次询问，每次询问是两种操作之一：1.在x坐标处，将x所在区间一分为二。2.询问x点在哪个区间。

思路:

• 这道题我开始思路没错，有序存下每个点，每次询问x所在区间时取分别第一个小于x点和第一个大于x点的坐标（从题意看询问x所在区间时不会与区间边重合，否则会产生歧义——左右区间都符合条件）。
• 但是我第一思路居然是 sort(vector)＋二分，果不其然超时。估计是在询问时每添加一个数都要sort排序严重拖慢时间。
• 于是想到会不会是线段树，写了一会发觉不太对劲，这个题用线段树写起来着实有些费劲。
• 最后终于发现，原来用set可以轻松解决。

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>

using namespace std;
typedef pair<int, int > PII;

const int N = 2e5 + 10;

int n, m;
set<int>p;//大意了，没有想到set居然速度这么快，居然傻傻二分

int main()
{
	scanf("%d%d", &n, &m);

	p.insert(0), p.insert(n);//初始条件
	while (m--)
	{
		int c, x;
		scanf("%d%d", &c, &x);
		
		if (c == 1)p.insert(x);
		else
		{
			auto t = p.lower_bound(x);
			printf("%d\n", *t - *(--t));
		}
	}

	return 0;
}

错误示范：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;
typedef pair<int, int > PII;


const int N = 2010;

int n, m;
vector<int>p;

int erfen(int x)
{
	int l = 0, r = (int)p.size() - 1;
	while (l < r)
	{
		int mid = (l + r+1) / 2;
		if (p[mid] < x)l = mid;
		else r = mid - 1;
	}

	return l;
}
int main()
{
	scanf("%d%d", &n, &m);

	p.push_back(0), p.push_back(n);

	int flag = 1;
	while (m--)
	{
		int c, x;
		scanf("%d%d", &c, &x);
		if (c == 1)p.push_back(x), flag = 1;
		else
		{
			if(flag==1)sort(p.begin(), p.end());
			int k = erfen(x);
			printf("%d\n", p[k+1] - p[k]);
			flag = 2;
		}
	}
	return 0;
}