bzoj 4540: [Hnoi 2016] 시퀀스 (모 팀 + ST 표 + 단조 스 택 | 선분 트 리)
전송 문
제목: 주어진 길이 n 의 서열: a1, a2,..., an, a [1: n] 로 기록 합 니 다.유사 하 게 a [l: r] (1 ≤ l ≤ r ≤ N) 는 서열: al, al + 1,..., ar - 1, ar 를 가리킨다.만약 1 ≤ l ≤ s ≤ t ≤ r ≤ n 이 라면 a [s: t] 는 a [l: r] 의 하위 서열 이 라 고 부른다.현재 q 개의 질문 이 있 습 니 다. 각 질문 은 두 개의 수 l 과 r, 1 ≤ l ≤ r ≤ n 을 정 하고 a [l: r] 의 서로 다른 하위 서열 의 최소 값 의 합 을 구 합 니 다.예 를 들 어 주어진 순서 가 5, 2, 4, 1, 3 이 고 주어진 두 개의 수 는 1 과 3 이 라 고 묻는다. 그러면 a [1: 3] 는 6 개의 서열 a [1: 1], a [2: 2], a [3: 3], a [2: 3], a [1: 3] 가 있 는데 이 6 개의 서열 의 최소 치 의 합 은 5 + 2 + 4 + 2 + 2 + 2 = 17 이다.
해제
모 팀 + 단조 스 택 + ST 표 시간 복잡 도 O (N √) 는 각 점 이 최소 값 이 되 는 구간 이 어떤 특징 이 있 는 지 고려 하여 현재 위 치 를 x 로 설정 한 다음 에 l 로 가장 왼쪽 에 있 는 것 이 x 와 같은 위 치 를 나타 낸다 (가장 오른쪽 에 있 는 x 보다 작은 위치 라 고 할 수 있다). r 표 는 가장 오른쪽 에 있 는 것 이 x 와 같은 위 치 를 나타 낸다.그러면 구간 의 최소 값 이 x 라면 구간 의 왼쪽 끝 점 은 반드시 [l, x] 에 있 고 오른쪽 끝 점 은 반드시 [x, r] 에 있 습 니 다. 각 점 의 l, r 에 대해 우 리 는 단조 로 운 스 택 O (n) 의 구 해 를 통 해 구 할 수 있 습 니 다.현재 질문 구간 이 [ls, rs - 1] 이 라 고 가정 하면 저 는 rs 가입 에 어떤 영향 을 미 치 는 지 고려 합 니까?우 리 는 실제로 (r - l + 1) 구간 에 가 입 했 는데, 지금 우 리 는 이 구간 의 최소 값 이 각각 무엇 인지 알 아야 한다.먼저 [ls, rs] 에서 가장 작은 값 의 위치 x 를 확인 합 니 다. 이것 은 ST 표를 만 든 다음 에 매번 O (1) 의 조 회 를 할 수 있 습 니 다.그러면 출발점 은 [ls, x] 이 고 종점 은 rs 구간 에 있 으 며 최소 치 는 반드시 a [x] 입 니 다. 이것 은 문제 가 없 으 며 O (1) 로 계산 할 수 있 습 니 다.그러면 출발점 이 [x + 1, rs] 에 있 는 구간 에 대해 어떻게 계산 합 니까?사실은 모든 점 에서 통제 하 는 것 은 반드시 연속 적 인 구간 이 고 지금까지 미리 처리 한 l, r 는 도움 이 될 수 있다.시작 점 이 [rs, r [rs] 구간 의 최소 값 은 rs 입 니 다. 그러면 우 리 는 접두사 와 비슷 한 것 을 유지 할 수 있 습 니 다.sumr [x] = sumr [r [x] + (x - r [x]) * a [x], 그러면 새로 추 가 된 구간 의 총액 은 sumr [rs] - sumr [mn] mn 이 구간 의 최소 가치 위 치 를 나타 낸다.l 의 가입 에 도 비슷 한 방법 으로 완벽 하 게 해결 할 수 있 습 니 다.
코드 1
#include0; stack[++top]=1;
for (int i=2;i<=n;i++) {
while (top&&a[stack[top]]>=a[i]) top--;
last[i]=stack[top]; stack[++top]=i;
}
top=0; stack[0]=n+1; stack[++top]=n; nxt[n]=n+1;
for (int i=n-1;i>=1;i--) {
while (top&&a[stack[top]]>=a[i]) top--;
nxt[i]=stack[top]; stack[++top]=i;
}
for (int i=1;i<=n;i++) sumr[i]=sumr[last[i]]+(LL)(i-last[i])*a[i];
for (int i=n;i>=1;i--) suml[i]=suml[nxt[i]]+(LL)(nxt[i]-i)*a[i];
}
int query(int x,int y)
{
int k=l[y-x];
if (a[st[k][x]]<=a[st[k][y-(1<1]]) return st[k][x];
else return st[k][y-(1<1];
}
void changer(int x,int y,int val)
{
int mn=query(x,y); LL sum=(LL)(mn-x+1)*a[mn];
sum+=sumr[y]-sumr[mn]; ans+=(LL)val*sum;
}
void changel(int x,int y,int val)
{
int mn=query(x,y); LL sum=(LL)(y-mn+1)*a[mn];
sum+=suml[x]-suml[mn]; ans+=(LL)val*sum;
}
int main()
{
freopen("a.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),st[0][i]=i;
for (int i=1;i<=17;i++)
for (int j=1;j<=n;j++)
if (j+(1<1<=n) {
if (a[st[i-1][j]]<=a[st[i-1][j+(1<1))]]) st[i][j]=st[i-1][j];
else st[i][j]=st[i-1][j+(1<1))];
}
int j=0;
for (int i=1;i<=n;i++) {
if (1<1)<=i) j++;
l[i]=j;
}
int block=ceil(sqrt(n));
for (int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
init();
int l=1; int r=1; ans=a[1];
for (int i=1;i<=m;i++) {
while (q[i].r>r) changer(l,++r,1);
while (q[i].l1);
while (q[i].l>l) changel(l++,r,-1);
while (q[i].r1);
c[q[i].id]=ans;
}
for (int i=1;i<=m;i++) printf("%I64d
",c[i]);
} 해제
라인 트 리 시간 복잡 도 O (nlogn) 하지만 상수 가 커 위 에 O (N √) 보다 더 느 려 요...우 리 는 오프라인 질문 을 한 다음 에 종점 에 따라 순 서 를 매 긴 다음 에 1 부터 n 까지 모든 위 치 를 순서대로 옮 겨 다 니 며 동시에 답 을 계산 할 것 이다.현재 우리 가 옮 겨 다 니 는 위 치 를 x 라 고 가정 하면 모든 위치 에 대해 우 리 는 두 개의 값 sum [now], val [now] (x 뒤의 점 초기 값 은 0) 을 유지 합 니 다. 다음은 sum 과 val 의 정 의 를 내 립 니 다.val[now]=min{a[k]} k * 8712 ° [now, x] 는 구간 [now, x] 의 최소 값 을 의미한다.sum [now] = ∑ xi = 1val [now] 는 모든 역사 버 전의 val [now] 의 합 을 나타 낸다. 다시 말 하면 출발점 은 now 이 고 종점 은 [now, x] 의 모든 최소 값 의 합 이다.그러면 모든 질문 l, r 에 있어 x = r 시 ans = ＞ ri = lsum [i].자, 이제 우리 의 문 제 는 어떻게 빨리 ans 를 구 하 느 냐 하 는 것 입 니 다. 이런 구간 의 지식 문 제 는 선분 나무 로 유지 하 는 것 을 생각 하기 쉽 습 니 다.우 리 는 현재 모든 위치의 정 의 를 선분 트 리 로 확장 합 니 다. 각 점 now 는 [l, r] 구간 을 대표 합 니 다.Val [now] = ∑ ri = lval [now], Sum [now] = ∑ xi = 1Val [now], 우 리 는 한 위치 에 새로 가입 한 후에 앞의 값 을 어떻게 업데이트 하 는 지 를 고려한다.a [x] 를 추가 하면 x 의 가장 왼쪽 에 있 는 x 와 같은 위치 L, L 에서 x 구간 의 val 값 은 모두 a [x] 가 되 고 모든 선분 나무의 구간 으로 Val 을 수정 할 수 있 습 니 다.좋 을 것 같 아.4 개의 태그 a, b, c, d Val ′ = Val ∗ a + b ∗ (r - l + 1) Sum ′ = Sum ′ + c ∗ Val ′ + d ∗ (r - l + 1) 유지 보수
[lenValSum] * * 9121 ° 9123 ° 100 ba0dc 1 * 9124 ° 9126 ° 9125 ° 구간 의 길이 가 len 이 변 하지 않 기 때문에 행렬 을 곱 한 결 과 는 위의 두 가지 식 입 니 다.두 표지 의 문제 에 대해 행렬 의 결합 율 을 활용 하면 된다.100 x. bx. a0x. dx. cx. c1 은 100 y. by. by. dy. dy. c1 은 100 y. by. by. dy. dy. c1 은 100 y. b + x. b + x. b. x. b. x. b. b. x. b. b. x. b. b. x. b. b. x. b. b. x. x. a. x. d + x. d + x. d + x. b: x. b: 9125 = = 9123 이 100 y. b + x. b + x. b * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 24. 9126. 9125. 그러나 우리 에 게 있어 서 행렬 을 진정 으로 유지 할 필요 가 없다. a, b, c, d 의 값 만 유지 하면 된다. 표지 가 겹 칠 때마다 위의 행렬 의 계산 방식 으로 합병 하면 된다.초기 에 모든 위치의 네 개의 표 시 된 값 은 a = 1, b = c = d = 0 이 었 습 니 다. 구간 Val 의 수정 에 대해 우 리 는 대응 하 는 구간 에서 a = 0, b = a [x], c = 0, d = 0 을 내 려 놓 았 습 니 다. 전역 적 인 Sum 의 업데이트 에 대해 서 는 a = 1, b = 0, c = 1, d = 0 을 내 려 놓 았 습 니 다.
코드 2
#includeint now)
{
val[now]=val[now<<1]+val[now<<1|1];
sum[now]=sum[now<<1]+sum[now<<1|1];
}
void build(int now,int l,int r)
{
val[now]=sum[now]=0; delta[now].clear();
if (l==r) return;
int mid=(l+r)/2;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
update(now);
}
void add(int now,int l,int r,node t){
LL len=(LL)(r-l+1);
sum[now]+=t.c*val[now]+t.d*len;
val[now]=t.a*val[now]+t.b*len;
delta[now]=delta[now]+t;
}
void pushdown(int now,int l,int r)
{
int mid=(l+r)/2; node t=delta[now];
if (t.a!=1||t.b||t.c||t.d) {
add(now<<1,l,mid,t); add(now<<1|1,mid+1,r,t);
delta[now].clear();
}
}
void qjchange(int now,int l,int r,int ll,int rr,node t)
{
if (ll<=l&&r<=rr) {
add(now,l,r,t);
return;
}
int mid=(l+r)/2;
pushdown(now,l,r);
if (ll<=mid) qjchange(now<<1,l,mid,ll,rr,t);
if (rr>mid) qjchange(now<<1|1,mid+1,r,ll,rr,t);
update(now);
}
LL qjsum(int now,int l,int r,int ll,int rr)
{
if (ll<=l&&r<=rr) return sum[now];
int mid=(l+r)/2; pushdown(now,l,r);
LL ans=0;
if (ll<=mid) ans+=qjsum(now<<1,l,mid,ll,rr);
if (rr>mid) ans+=qjsum(now<<1|1,mid+1,r,ll,rr);
return ans;
}
int main()
{
freopen("a.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
top=0; build(1,1,n); int j=1;
for (int i=1;i<=n;i++) {
while (top&&a[st[top]]>=a[i]) top--;
node tmp=(node){0,a[i],0,0};
qjchange(1,1,n,st[top]+1,i,tmp);
tmp=(node){1,0,1,0}; st[++top]=i;
add(1,1,n,tmp);
while (j<=m&&q[j].r==i) ans[q[j].id]=qjsum(1,1,n,q[j].l,q[j].r),j++;
}
for (int i=1;i<=m;i++) printf("%I64d
",ans[i]);
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
