Sequence 线段树+二分

本题目出自2020江西省ICPC省赛 题目地址

给定序列，支持两个操作：

1. Replace(x, y)单点修改，将 a x a_x ax​修改为 y y y；
2. Query(x) 序列查询，查询对于整个序列，子序列最小值小于等于 a x a_x ax​的序列个数。

单点修改+区间查询，首先考虑线段树维护区间最小值，然后考虑对于序列查询操作如何进行。

首先我们找到 a x a_x ax​的位置，查询 a x a_x ax​左右区间序列最小值不小于 a x a_x ax​的长度，设为 s u m l , s u m r sum_l, sum_r suml​,sumr​，则根据组合数学可以知道此时满足条件的子序列个数为 s u m l + s u m r + 1 + s u m l × s u m r sum_l + sum_r + 1 + sum_l \times sum_r suml​+sumr​+1+suml​×sumr​。那么只需要在查询的时候略作修改即可。

考虑如何查询左右元素个数。由于线段树维护的是区间最小值，因此从根节点到叶节点是满足元素大小不递减，也就是满足有序性。因此可以二分 a x a_x ax​左右区间，查询区间最小值检验。此种方法容易理解，但是每次需要进行两次查询，复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。

#include 
//#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m, a[N], tree[N