NC213989. Sequence
描述
Given an array a consisting of n integers, on which you are to perform m operations of two types.
1.Given two integers x,y, replace the number of index x with number y. That is ax:=y.
2.Given one integer x, print the number of consecutive subsequences of a, whose minimum value equals to ax.
It's guaranteed that there are no duplicated value in array a at any moment.
输入描述
The first line contains two intergers n,m(1≤n,m≤105)，where n is the size of the array and m is the number of operations to perform.The second line contains n integer, the ith integer is ai (1≤ai≤231-1)Then,m lines follow, describing m operation you are to perform in order.
If opt=1,two integers x, y (1≤x≤n,1≤y≤231-1) follows,mentioned above.
Each line start with an integer opt∈[1,2], meaning the type of operation to perform.If opt=2,one integers x (1≤x≤n) follows, mentioned above.
输出描述
For each operation of type 2, print one integer on one line as the answer.
示例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
C++ 解法, 执行用时: 65ms, 内存消耗: 1888K, 提交时间: 2022-03-27 16:20:42
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int a[100005];
int main()
{
int n,m;
ll minn = INF;
ll max = 0;
ll minx;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(minn>a[i])
{
minn=a[i];
minx = i;
}
if(max<a[i])
max = a[i];
}
int c,x,y;
for(int i=0;i<m;i++)
{
scanf("%d",&c);
ll cnt1=0;
ll cnt2=0;
if(c==1)
{
scanf("%d%d",&x,&y);
a[x] = y;
}
else
{
scanf("%d",&x);
if(a[x]==minn)
{
printf("%lld\n",(n-minx+1)*minx);
}
else if(a[x]==max)
printf("1\n");
else
{
for(int j=x+1;a[j]>=a[x]&&j<=n;j++)
cnt1++;
for(int j=x;a[j]>=a[x]&&j>0;j--)
cnt2++;
printf("%lld\n",(cnt1*cnt2)+cnt2);
}
}
}
}