Codeforces Round #489 (Div. 2) E. Nastya and King-Shamans
这道题的算法是：
i从1开始，首先求sum(1-i)，然后在[i+1, n]中找到第一个a[j]>=sum(1, i)
如果a[j]==sum(1, i)结束搜索，否则令i=j，循环过程
因为每次做完一次之后sum会至少增大一倍，所以一个查询的复杂度会维持到log(Max(a[i]))
需要维护 区间最大值和区间和 的线段树来实现算法
“`
include
include
include
include
using namespace std;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;
typedef long long ll;
define lson l, m, rt<<1
define rson m+1, r, rt<<1|1
int n, q;
int A[N];
int maxx[N << 2];
ll sum[N << 2];
void Build(int l, int r, int rt) {
if(l == r) {
sum[rt] = A[l];
maxx[rt] = A[l];
return;
}
int m = (l + r) >> 1;
Build(lson);
Build(rson);
sum[rt] = sum[rt << 1] + sum[rt << 1|1];
maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
}
void Update(int pos, int num, int l, int r, int rt) {
if(l == r) {
sum[rt] = num;
maxx[rt] = num;
return;
}
int m = (l + r) >> 1;
if(pos <= m) Update(pos, num, lson);
else Update(pos, num, rson);
sum[rt] = sum[rt << 1] + sum[rt << 1|1];
maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
}
ll Sum(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> 1;
ll ret = 0;
if(L <= m) ret += Sum(L, R, lson);
if(R > m) ret += Sum(L, R, rson);
return ret;
}
pair
}
}
}
}
return 0;}
*/