bzoj3745: [Coci2015]Norma
1509 단어 bzoj
분치 사상을 고려하면 l,r,mid는 왼쪽 단점을 열거할 수 있고 오른쪽 단점이mid 오른쪽에 있는 경우 단조성과 접두사를 이용하여 O(nlogn)에 도달할 수 있다.
디테일 코드 보기: (Pr의 시작은 모두 접두사 및)
#include
#include
#define N 500005
#define ll long long
#define MOD 1000000000
using namespace std;
ll n,a[N],Pr[N],Pr0[N],Pr1[N],Pr2[N],Pr3[N],MAX[N],MIN[N],Px1[N],Px2[N],Px3[N];
ll read()
{
char c=getchar();int x=0;
while (c'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
ll work(ll l,ll r)
{
if (l>r) return 0;
if (l==r) return a[l]*a[r]%MOD;
ll mid=(l+r)>>1,i,j1,j2,Min,Max,Ans=0;
i=mid;j1=j2=mid;Min=Max=a[mid];
MAX[mid]=MIN[mid]=Pr1[mid]=Pr2[mid]=Px1[mid]=Px2[mid]=Px3[mid]=a[mid];
Pr3[mid]=a[mid]*a[mid]%MOD;
Pr[mid]=Pr0[mid]=1;
for (ll i=mid+1;i<=r;i++)
{
MAX[i]=max(MAX[i-1],a[i]);
MIN[i]=min(MIN[i-1],a[i]);
Pr[i]=Pr[i-1]+1;;
Pr0[i]=(Pr0[i-1]+Pr[i])%MOD;
Px1[i]=(Px1[i-1]+MAX[i])%MOD;
Px2[i]=(Px2[i-1]+MIN[i])%MOD;
Px3[i]=(Px3[i-1]+MAX[i]*MIN[i])%MOD;
Pr1[i]=(Pr1[i-1]+MAX[i]*Pr[i])%MOD;
Pr2[i]=(Pr2[i-1]+MIN[i]*Pr[i])%MOD;
Pr3[i]=(Pr3[i-1]+MAX[i]*MIN[i]%MOD*Pr[i])%MOD;
}
for (;i>=l;i--)
{
ll t=mid-i;
Min=min(Min,a[i]);Max=max(Max,a[i]);
while (j1=Min) j1++;
while (j2 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
