C.子段乘积

给出一个长度为 n 的数列 a 1, a 2,a 3 . . . a n,求其长度为 k 的连续子段的乘积对 998244353 取模余数的最大值。

输入描述

第一行两个整数n,k。

第二行n个整数,a 1, a 2,a 3 . . . a n

1 <= k <= n <= 2e5

0 <= ai < 998244353

输出描述

输出一个整数,代表最大余数。

示例:

输入

5 3
1 2 3 0 8

输出

6

说明

1∗2∗3 mod 998244353 = 6

题解

题意很简单,求的是区间为k的所有数之积 mod 998244353 的最大值是多少。暴力思路只用将所有长度为k的区间计算一遍纪录最大值就行了,这样时间复杂度为O((n-k)*k), 差不多就是O(n2)。 必然会超时。

正确做法是用线段树储存每个数,线段树查询的时间复杂度O(logn) ,总体来说就是O(nlogn)。

这道题也没有修改什么的,只需要建树,暴力区间查询就可以了。

#include<bits/stdc++.h>
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll N = 2e5+7;
const ll mod = 998244353;
ll mx[N*4];
void build(int node,int l,int r)
{
    if(l==r)
    {
        int x;
        cin>>x;
        mx[node]=x;//当数到达叶子节点输入存入值
        return;
    }
    int mid = MID(l,r);
    build(LC(node),l,mid);
    build(RC(node),mid+1,r);
    mx[node] = mx[LC(node)] * mx[RC(node)] % mod;//父节点是两个子节点的乘积 mod 998244353
}

ll query(int node,int st,int end,int l,int r)
{
    if(end < l || st > r) return 1l; //如果递归到的区间与查询区间没有重合部分,返回1(因为是乘积)
    if(st >= l && end <= r) return mx[node];//如果递归到的区间完全被查询区间包含,返回当前结点的值
    ll lsum = query(LC(node),st,MID(st,end),l,r);//遍历左子树
    ll rsum = query(RC(node),MID(st,end)+1,end,l,r);//遍历右子树
    return lsum*rsum%mod;//
}
int main()
{
    IOS();

    int n,k;
    cin>>n>>k;
    build(1,1,n);//建树
    ll ans = 0;
    for(int i=1,j=k;j<=n;j++,i++) //尺取每个长度为k的区间
        ans = max(ans,query(1,1,n,i,j));
    cout<<ans<<endl;
    return 0;
}

一个好奇的人