牛客 - 二分(差分)

题目链接：点击查看

题目大意：现在玩猜数字游戏，如果猜的数字比答案要大，就输出 ' + ' ，比答案小，就输出 ' - ' ，猜中了答案，输出 ' . '， 给出这样的 n 条指令，问最多有多少条指令可以同时保证正确性

题目分析：感觉蛮不错的一道差分题目，分类讨论一下：

1. ' . ' ：当前指令只对 pos 位置的数做出了贡献
2. ' + ' ：当前指令对 [ -inf , pos - 1 ] 内的数做出了贡献
3. ' - ' ：当前指令对 [ pos + 1 , inf ] 内的数做出了贡献

因为数据是离散化的，可以用 map 来维护，也可以离散化一下，时间复杂度都是 nlogn 级别的

代码：
 

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<unordered_map>
using namespace std;

typedef long long LL;

typedef unsigned long long ull;

const LL inf=0x3f3f3f3f3f3f3f3f;

const int N=1e5+100;

map<LL,int>mp;

void update(LL l,LL r)
{
	mp[l]++,mp[r+1]--;
}

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int pos;
		char op[5];
		scanf("%d%s",&pos,op);
		if(op[0]=='.')
			update(pos,pos);
		else if(op[0]=='+')
			update(-inf,pos-1);
		else
			update(pos+1,inf);
	}
	int sum=0,ans=0;
	for(auto it:mp)
	{
		sum+=it.second;
		ans=max(ans,sum);
	}
	printf("%d\n",ans);












    return 0;
}