牛客练习赛 115 记录

/*
1. 根据山峰数列的定义，用排列组合知识去计算即可。
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int t,n;
int a[maxn];
ll ans;
const int MOD=998244353;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans=1ll;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		int e=n;
		while(a[e]==a[n]) e--;
		int cnt=0,s=0;
		for(int i=1;i<=e;i++)
		{
			if(a[s]!=a[i])
			{
				ans=(cnt+1)*ans%MOD;
				s=i,cnt=1;
			}
			else cnt++;
		}
		ans=(cnt+1)*ans%MOD;
		printf("%lld\n",ans);
	}
}

/*
1. 模拟+贪心的水题。
*/
#include<bits/stdc++.h>
using namespace std;
int t,l,r,cnt;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&l,&r,&cnt);
		int pos;
		while(cnt&&l<=r)
		{
			pos=(l+r)>>1;
			if(r-pos>pos-l) l=pos+1;
			else r=pos-1;
			cnt--;
		}
		if(cnt) printf("-1\n");
		else printf("%d\n",pos);
	}
	return 0;
}

/*
1. 突破点在于发现，$\max\limits_{i\ne j}\{|\frac{a_i-a_j}{i-j}|\}$ 一定在当 $j=i+1$ 时取到（可以用**反证法**证明），故只需计算相邻元素的差的最大值。
2. 对于 $a$ 的差分数组 $d$，要求满足**单点修改**和**求区间最大值**的操作。本题中，由于区间一直是 $[2,n]$，故可直接用 $L$ 维护区间最大值，然后每次修改 $d$ 数组时，更新 $L$。
3. 代码中用了线段树，是因为当时没有注意到区间一直是 $[2,n]$（nt 了）。
*/
#include<bits/stdc++.h>
#define ld long double
#define lson i<<1
#define rson i<<1|1
using namespace std;
const int maxn=5e5+100;
int n,q,a[maxn];
struct ST
{
	int mx,mi;
}t[maxn<<2];
void build(int i,int L,int R)
{
	if(L==R) 
	{
		t[i].mx=t[i].mi=a[R+1]-a[R];
		return;
	}
	int mid=(L+R)>>1;
	build(i<<1,L,mid),build(i<<1|1,mid+1,R);
	t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);
	t[i].mi=min(t[i<<1].mi,t[i<<1|1].mi);
	return;
}
void merge(int i,int l,int r,int pos,int k)
{
	if(l==r&&l==pos)
	{
		t[i].mx+=k,t[i].mi+=k;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) merge(lson,l,mid,pos,k);
	else merge(rson,mid+1,r,pos,k);
	t[i].mx=max(t[i<<1].mx,t[i<<1|1].mx);
	t[i].mi=min(t[i<<1].mi,t[i<<1|1].mi);
	return;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	build(1,1,n-1);
	printf("%lf\n",1.0*max(abs(t[1].mx),abs(t[1].mi)));
	while(q--)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		if(l-1)merge(1,1,n-1,l-1,k);
		if(r<n)merge(1,1,n-1,r,-k);
		printf("%lf\n",1.0*max(abs(t[1].mx),abs(t[1].mi)));
	}
	return 0;
}