很久很久以前，有很多蚂蚁部落共同生活在一片祥和的村庄里。但在某一天，村庄里突然出现了一只食蚁兽，蚂蚁们为了保全性命而决定搬家。
然而这个村庄四面环山，想要离开这个村庄必须要从地洞里离开，村子里一共有 2n2n2n 个地洞，分布在山的左右，一边 nnn 个。左边的任意一个地洞都可以通到右边 nnn 个地洞中的任意的一个，如图所示（两侧地洞从上至下编号为 111 到 nnn）。
对于右边的第 iii 个出口，附近有数量为 wiw_iwi 的食物。
现在前后依次来了 qqq 个蚂蚁部落，第 iii 个部落有 aia_iai 只蚂蚁，它们会从左边第 bib_ibi 个地洞离开，并且选择一个右侧的出口，出口的食物必须大于等于 aia_iai，如果有多个满足要求的出口，则选择距离 bib_ibi 最近的（假设蚂蚁从右边的编号为 kkk 的地洞出来，那么距离定义为 ∣k−bi∣|k-b_i|∣k−bi∣）。如果有多个洞口符合要求，选择编号最小的出口离开，并且占据这个出口数量为 aia_iai 的食物，当前洞口的食物数量减少 aia_iai。
请输出每群蚂蚁会选择哪个出口，如果没有符合要求的出口，输出 −1-1−1，并且忽略这群蚂蚁。
输入格式
第一行两个整数 nnn 和 qqq。
接下来 nnn 行，每行一个整数 wiw_iwi，表示右方第 iii 个洞口的食物数量。
接下来 qqq 行，每行两个整数 aia_iai 和 bib_ibi，表示蚂蚁数量和它们离开的洞口。
输出格式
一共 qqq 行，每行一个整数，表示第 iii 群蚂蚁会选择哪个出口。
数据规模
对于 30%30\%30% 的数据：n,q≤3000n,q \le 3000n,q≤3000。
对于 60%60\%60% 的数据：n,q≤100000n,q \le 100000n,q≤100000。
对于另外 20%20\%20% 的数据保证：ai=1a_i=1ai=1。
对于 100%100\%100% 的数据：n,q≤500000n,q \le 500000n,q≤500000，ai,wi≤109a_i,w_i \le 10^9ai,wi≤109，bi≤nb_i \le nbi≤n。
更多样例
样例解释
原始的剩余食物为 9,8,6,10,59,8,6,10,59,8,6,10,5。
查询 4,54,54,5，选择第 555 个洞口出来，剩下食物为 9,8,6,10,19,8,6,10,19,8,6,10,1。
查询 2,52,52,5，选择第 444 个洞口出来，剩下食物为 9,8,6,8,19,8,6,8,19,8,6,8,1。
查询 8,18,18,1，选择第 111 个洞口出来，剩下食物为 1,8,6,8,11,8,6,8,11,8,6,8,1。
查询 9,39,39,3，这时候没有满足条件的洞口了，忽略之。
查询 3,13,13,1，选择第 222 个洞口出来，剩下食物为 1,5,6,8,11,5,6,8,11,5,6,8,1。
忽略每行输出的末尾多余空格
样例输入
5 5
9 8 6 10 5
4 5
2 5
8 1
9 3
3 1
样例输出
5
4
1
-1
2
对于30%的数据:n≤300直接暴力找就好 对于60%的数据:题目要求相当于找距离bi最近的且大于等于ai的位置
这个可以用二分位置+线段树求区间min实现
复杂度 O(n lg n)
如果没有nb的卡常技巧大概是过不了100分的 对于另外20%的数据:ai =1
相当于找距离i最近的值≥1的点,我们考虑线段树之外的做法
维护两个并查集,分别指向当前点往上第一个不为0的点和往下第一个不为0的点。
复杂度O(nlgn) 。 对于 100% 的数据:
依然考虑用线段树维护,假设现在要找编号小于i的距离i最近的点
我们记录一个数组pos[i]表示代表位置i的线段树的叶子节点的编号,然后从这个节点往上找
如果当前点是fa的左儿子,什么也不做,然后向fa走一步
如果当前点是fa的右儿子,如果fa的左儿子中的最大值≥a[i],那么递归在fa的左儿子中找答案,现
在区间是一整个节点,就可以利用线段树的二分结构往下找。
否则什么也不做,然后向fa走一步。
向右同理
复杂度O(nlgn)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=2e9;
int n,q,w[],c[],L[],R[],pos[];
void pushup(int rt)
{
c[rt]=max(c[rt*],c[rt*+]);
}
void build(int rt,int l,int r)
{
L[rt]=l;R[rt]=r;
if (l==r)
{
c[rt]=w[l];
pos[l]=rt;
return;
}
int mid=(l+r)/;
build(rt*,l,mid);
build(rt*+,mid+,r);
pushup(rt);
}
void update(int rt,int l,int r,int x,int d)
{
if (l==r)
{
c[rt]+=d;
return;
}
int mid=(l+r)/;
if (x<=mid) update(rt*,l,mid,x,d);
else update(rt*+,mid+,r,x,d);
pushup(rt);
}
int take1(int rt,int x)
{
if (L[rt]==R[rt]) return L[rt];
if (c[rt*+]>=x) return take1(rt*+,x);
return take1(rt*,x);
}
int take2(int rt,int x)
{
if (L[rt]==R[rt]) return L[rt];
if (c[rt*]>=x) return take2(rt*,x);
return take2(rt*+,x);
}
int find1(int rt,int x)
{
if (rt==) return inf;
if (rt&)
if (c[rt-]>=x) return take1(rt-,x);
return find1(rt/,x);
}
int find2(int rt,int x)
{
if (rt==) return inf;
if ((rt&)==)
if (c[rt+]>=x) return take2(rt+,x);
return find2(rt/,x);
}
int main()
{int i,x,y,p1,p2;
cin>>n>>q;
for (i=;i<=n;i++)
{
scanf("%d",&w[i]);
}
build(,,n);
while (q--)
{
scanf("%d%d",&x,&y);
if (w[y]>=x) p1=p2=y;
else p1=find1(pos[y],x),p2=find2(pos[y],x);
if (p1==inf&&p2==inf) printf("-1\n");
else
{
if (abs(y-p1)<=abs(p2-y))
{
printf("%d\n",p1);
w[p1]-=x;
update(,,n,p1,-x);
}
else
{
printf("%d\n",p2);
w[p2]-=x;
update(,,n,p2,-x);
}
}
}
}