第二次做这种题目，把人做傻了，没想到是二分，只是隐隐约约感觉到了二分的影子。于是写了两个查找的函数，但是发现查找的函数无法解决求左边最大值和右边最小值的问题。写了一大堆烂代码。
正解只需要在查询的时候不断二分就行了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct Node{
int l, r, minn, maxn;
}node[N << 2];
int n, m, a[N];
void pushup(int root){
node[root].minn = min(node[root << 1].minn, node[root << 1 | 1].minn);
node[root].maxn = max(node[root << 1].maxn, node[root << 1 | 1].maxn);
}
void build(int root, int l, int r){
node[root].l = l;
node[root].r = r;
if(l == r){
node[root].minn = a[l];
node[root].maxn = a[l];
return;
}
int mid = (l + r) >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
pushup(root);
}
void update(int root, int pos, int value){
if(node[root].l == node[root].r){
node[root].minn = value;
node[root].maxn = value;
return;
}
int mid = (node[root].l + node[root].r) >> 1;
if(pos <= mid)
update(root << 1, pos, value);
else
update(root << 1 | 1, pos, value);
pushup(root);
}
/*ll queryleft(int root, int l, int r, int value){
if(node[root].l == node[root].r){
return node[root].l;
}
int mid = (node[root].l + node[root].r) >> 1;
if(node[root].l >= l && node[root].r <= r){
if(node[root].minn > value){
return node[root].l;
}else if(node[root].maxn < value){
return node[root].l - 1;
}else if(node[root].minn < value && node[root].maxn >= value){
if(node[root << 1].minn < value)
return queryleft(root << 1, l, r, value);
else if(node[root << 1 | 1].minn < value)
return queryleft(root << 1 | 1, l, r, value);
}
}
ll ans = -1;
if(l <= mid)
ans = max(ans, queryleft(root << 1, l, r, value));
//cout << "ansleft1 = " << ans << endl;
if(r > mid)
ans = max(ans, queryleft(root << 1 | 1, l, r, value));
//cout << "ansright1 = " << ans << endl;
return ans;
}
int queryright(int root, int l, int r, int value){
if(node[root].l == node[root].r){
return node[root].l;
}
int mid = (node[root].l + node[root].r) >> 1;
if(node[root].l >= l && node[root].r <= r){
if(node[root].minn > value){
//return node[root].r;
return queryright(root << 1 | 1, l, r, value);
}else if(node[root].maxn < value){
return node[root].l - 1;
}else if(node[root].minn < value && node[root].maxn >= value){
if(node[root << 1].minn < value)
return queryright(root << 1, l, r, value);
else if(node[root << 1 | 1].minn < value)
return queryright(root << 1 | 1, l, r, value);
}
}
int ans = 0x3f3f3f3f;
if(l <= mid)
ans = min(ans, queryright(root << 1, l, r, value));
cout << "ansleft2 = " << ans << endl;
if(r > mid)
ans = min(ans, queryright(root << 1 | 1, l, r, value));
cout << "ansright2 = " << ans << endl;
return ans;
}*/
ll query(int root, int l, int r){
if(node[root].l >= l && node[root].r <= r){
return node[root].minn;
}
int mid = (node[root].l + node[root].r) >> 1;
ll ans = 1e9 + 10;
if(l <= mid)
ans = min(ans, query(root << 1, l, r));
if(r > mid)
ans = min(ans, query(root << 1 | 1, l, r));
return ans;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> a[i];
build(1, 1, n);
for(int i = 1; i <= m; i ++){
int op;
cin >> op;
if(op == 1){
int x, y;
cin >> x >> y;
a[x] = y;
update(1, x, y);
}else{
int pos;
cin >> pos;
int value = a[pos];
int l = 1, r = pos;
while(l < r){
int mid = (l + r) >> 1;
if(query(1, mid, pos) >= a[pos])
r = mid;
else
l = mid + 1;
}
int ansleft = pos - l + 1;
l = pos, r = n + 1;
while(l < r){
int mid = (l + r) >> 1;
if(query(1, pos, mid) < a[pos])
r = mid;
else
l = mid + 1;
}
int ansright = l - pos;
cout<< (ll)ansleft * ansright << endl;
}
}
return 0;
}