首页分享 2019 10月集训养花（分块）

2019 10月集训养花（分块）

来源：花匠小妙招时间：2025-06-15 04:12

养花

Description

小C" role="presentation">C在家种了n" role="presentation">n盆花，每盆花有一个鲜艳度ai" role="presentation">ai

在接下来的m" role="presentation">m天中，每天早晨他会从一段编号连续的花中选择一盆摆在客厅，并在晚上放回。同时每天有特定的光照强度ki" role="presentation">ki,如果这一天里摆放在客厅的花艳丽度为x" role="presentation">x, 则他能获得的喜悦度为 x" role="presentation">x mod" role="presentation">mod ki" role="presentation">ki.

他希望知道, 每一天他能获得的最大喜悦度是多少.

Input Format

数据第一行包含两个正整数 n" role="presentation">n,m" role="presentation">m.

接下来一行 n" role="presentation">n 个正整数, 第 i" role="presentation">i 个数 ai" role="presentation">ai 表示第 i" role="presentation">i 盆花的艳丽度.

接下来 m" role="presentation">m 行, 每行三个正整数 li" role="presentation">li, ri" role="presentation">ri, ki" role="presentation">ki, 表示选花区间和光照强度.

Solution

考虑当 k" role="presentation">k 确定的时候如何求答案,
显然对于所有形如 [ak,(a+1)k)" role="presentation">[ak,(a+1)k) 的值域区间, 最大值一定是最优的.

进一步观察发现, 这样的区间总个数只有 kln⁡k" role="presentation">kln⁡k 个.
考虑分块, 那么我们可以在 O(n+kln⁡k)" role="presentation">O(n+kln⁡k) 的时间复杂度内处理出一个块对于任意 k" role="presentation">k 的答案.
询问时复杂度是 O(mS)" role="presentation">O(mS) 的, 取 S=kln⁡k" role="presentation">S=kln⁡k 可以达到最优复杂度 O(nkln⁡k)" role="presentation">O(nkln⁡k).

Code

#include<bits/stdc++.h> #define N 100010 using namespace std; int n,m,t; int a[N],s[N],sum[1000][100010]; void prework() { int i,j,k; for(i=1;i<=(n-1)/t+1;i++) {memset(s,0,sizeof(s));for(j=(i-1)*t+1;j<=min(i*t,n);j++) s[a[j]]=a[j];for(j=1;j<=100001;j++) s[j]=max(s[j],s[j-1]);for(j=1;j<=100001;j++) for(k=0;k<=100001;k+=j) sum[i][j]=max(sum[i][j],s[min(k+j-1,100001)]-k); } } int getans(int l,int r,int k) {int i,j,res=0;int lft=(l-1)/t+1;int rht=(r-1)/t+1;for(i=lft+1;i<=rht-1;i++) res=max(res,sum[i][k]);for(i=l;i<=min(lft*t,r);i++) res=max(res,a[i]%k);for(i=max((rht-1)*t+1,l);i<=r;i++) res=max(res,a[i]%k);return res; } int main() { //freopen("flower.in","r",stdin); //freopen("flower.out","w",stdout);int i,j;scanf("%d%d",&n,&m);t=1000;for(i=1;i<=n;i++) scanf("%d",&a[i]);prework();while(m--){int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%dn",getans(l,r,k)); }return 0; }