AcWing 1913. 公平摄影（前缀和+STL）

题目连接

https://www.acwing.com/problem/content/1915/

思路

对于这个牛牛的位置和不同牛牛我们可以用一个pair存储，然后我们实际上要求的答案是

• 连续同种牛牛的最长距离
  • 连续荷斯坦牛的最长距离
  • 连续根西岛牛的最长距离
• 连续两种牛牛但是两种牛牛的数量都是相同的

因为位置是乱序的，所以我们先把牛牛按照位置信息排个序 那么对于第一种情况，我们直接O(N)扫过去即可，对于第二种情况，我们先对当前得序列求一个前缀和，我们假定H牛牛是正数、G牛牛是负数，那么我们在循环得时候，如果当前这个前缀和出现了两次，那么说明这个区间内的两牛牛数量是相等的，于是我们就使用一个map存储一下第一次出现这个前缀和的位置，记得初始化0

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
int n,m,q,pre[N];
PII a[N];
map vis;

int main()
{
	cin>>n;
	int x;
	char b;
	int lasth = 0,lastg = 0;
	for(int i = 1;i >x>>b;
		a[i] = {x,b};
	}
	sort(a+1,a+1+n);
	for(int i = 1;i