回归第六题

这个题关键在于每个ai只是1或-1，也就是总和最大2e6。
有什么用？可以开到数组
再发现这个x一定是存在的，因为1和-1均为连续变化的，所以整个数列是连续的
综上可以用STL里面的vector

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
vector<int>v[N<<1];
signed main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1],v[a[i]+n].push_back(i);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		int val=(a[x]+a[y])/2+n;
		int pos=lower_bound(v[val].begin(),v[val].end(),x)-v[val].begin();
		printf("%d\n",v[val][pos]);
	}
	return 0;
}