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();
}
}
