题目链接：点击这里
文章图片
暴力O ( n 2 ) O(n^2) O(n2) 超时。
【牛客 C. 子段乘积（线段树）】用线段树维护区间乘积的余数，然后查询区间[ i , i + k ? 1 ] [i,i+k-1] [i,i+k?1] 即可。其中建树的复杂度是O ( n ) O(n) O(n)，查询的时间复杂度是O ( l o g n ) O(logn) O(logn)。
#include
#include
#include
#include
#include
#includeusing namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 200010;
int n, k;
ll a[N];
struct node {
int l, r;
ll pd;
}tree[4*N];
inline int lc(int p) {return p<<1;
}
inline int rc(int p) {return p<<1|1;
}void build(int i, int l, int r)
{
tree[i].l = l;
tree[i].r = r;
if(l==r)
{
tree[i].pd = a[l];
return ;
}
int mid = (l + r) >> 1;
build(lc(i), l, mid);
build(rc(i), mid+1, r);
tree[i].pd = ( (tree[lc(i)].pd % mod) * (tree[rc(i)].pd % mod) ) % mod;
}ll query(int i, int ql, int qr)
{
if(ql<=tree[i].l&&tree[i].r<=qr)
return tree[i].pd % mod;
int mid = (tree[i].l + tree[i].r) >> 1;
ll res = 1;
if(ql<=mid)
res *= query(lc(i), ql, qr) % mod;
if(qr>mid)
res *= query(rc(i), ql, qr) % mod;
return res % mod;
}int main()
{
scanf("%d%d", &n, &k);
for(int i = 1;
i <= n;
++i)
scanf("%lld", &a[i]);
build(1, 1, n);
//建树
ll ans = -1;
for(int i = 1;
i + k - 1 <= n;
++i)
{
ll tmp = query(1, i, i + k - 1);
ans = max(ans, tmp);
}
printf("%lld\n", ans);
return 0;
}
推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间