Sequence(二分 + 线段树)
H-Sequence_2020ICPC 江西省大学生程序设计竞赛（重现赛）@Joanh_Lan (nowcoder.com)
题目描述
给定一个包含n个整数的数组a，你要对它执行两种类型的m个操作。1.给定两个整数x,y，将索引x的个数替换为数字y，即ax:=y。2.给定一个整数x，打印a的连续子序列的个数，其最小值为ax。它保证数组a在任何时候都没有重复的值。
输入描述:
第一行包含两个整数n,m(1Sn,mS105)，其中n是数组的大小，m是要执行的操作的数量。第二行包含n个整数，第i个整数是ai (1SaiS231-1)然后是m行，依次描述m个你要执行的操作。每行以一个整数optE[1,2]开始，表示要执行的操作类型。如果opt=1，则会出现两个整数x, y (1Sxsn,1Sys231-1)，如上所述。如果opt=2，一个整数x (1sxsn)紧随其后，如上所述。
输出描述:
对于类型2的每个操作，在一行上打印一个整数作为答案。
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
示例1
输入
复制
10 5 8 3 6 2 10 9 5 7 1 4 2 2 1 9 11 1 5 12 2 4 1 8 18
输出
复制
4 28
题解:
(反思:写题时越是有思路,越应该仔细推敲,看能不能以更简单的代码实现,本来已经想到二分了,确想了一直及其傻逼的实现,为啥不直接用二分???)!!!
题意很容易理解,看有多少子串最小值是a[p],暴力的解法就是每次向所求的下标左右遍历,直到找到比他小的,这样我们就知道最左和最右的下标l,r,输出(p - l + 1)*(r - l + 1)即可
可是每次遍历的话,时间复杂度肯定会超
所以我们利用线段树可以求每一段最小值,并且可以进行单点修改
那我们如何求左右边界?
利用两次二分,左右check
L,p p,R是最小值是否a[p]
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
//#define int long long
ll mod = 998244353;
struct node
{int l,r;int mi;
}tre[400060];
int a[100050];
void pushup(int rt)
{tre[rt].mi = min(tre[rt*2].mi,tre[rt*2 + 1].mi);
}
void build(int rt,int l,int r)
{tre[rt].l = l;tre[rt].r = r;if(l == r){tre[rt].mi = a[l];return ;}int mid = (l + r)/2;build(rt*2,l,mid);build(rt*2+1,mid + 1,r);pushup(rt);
}
void updata(int rt,int l,int r,int pos)
{if(tre[rt].l == l&& tre[rt].r == r){tre[rt].mi = pos;return;}int mid=(tre[rt].l+tre[rt].r)/2;if(l<=mid){updata(2*rt,l,r,pos);} if(r>mid){updata(2*rt+1,l,r,pos);}pushup(rt);
}
int ask(int rt,int l,int r)
{if(tre[rt].l >= l&&tre[rt].r <= r){return tre[rt].mi;}int ans = (1 << 31) - 1;int mid = (tre[rt].l + tre[rt].r)/2;if(l <= mid){ans = min(ans,ask(rt*2,l,r));}if(r > mid){ans = min(ans,ask(rt*2 + 1,l,r));}return ans;
}
void solve()
{int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);}build(1,1,n); while(m--){int op;scanf("%d",&op);if(op == 1){int x,pos;scanf("%d%d",&x,&pos);updata(1,x,x,pos); a[x] = pos;}else{int p;scanf("%d",&p);int l = 1,r = p;while(l <= r){int mid = (l + r)/2;if(ask(1,mid,p) == a[p]){r = mid - 1;}else{l = mid + 1;}}ll L = l;l = p,r = n;while(l <= r){int mid = (l + r)/2;if(ask(1,p,mid) == a[p]){l = mid + 1;}else{r = mid - 1;}}ll R = r;printf("%lld\\n",(ll)(p - L + 1)*(r - p + 1));}}
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}
