CHOJ 4301 [선분 수 + 구간 최대 부분 과]
주어진 길이 가 N 인 수열 A 및 M 개 명령 (N ≤ 500000, M ≤ 100000), 각 명령 은 다음 과 같은 두 가지 중 하나 일 수 있 습 니 다. "2 x y ", A [x] 를 y 로 바 꿉 니 다.“1 x y ", 조회 구간 [x, y] 중의 최대 연속 서브 세그먼트 와, 즉 max (x ≤ l ≤ r ≤ y) * 8289 ℃ {> (i = l ~ r) A [i]}.모든 질문 에 정 수 를 출력 하여 답 을 표시 합 니 다.
입력 형식
첫 줄 두 정수 N, M
두 번 째 줄 N 개 정수 Ai
다음 M 줄 당 3 개의 정수 k, x, y, k = 1 은 조회 (이때 x > y 라면 x, y 를 교환 하 십시오), k = 2 는 수정 을 표시 합 니 다.
출력 형식
모든 질문 출력 에 대해 정 수 를 표시 합 니 다.
샘플 입력
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
샘플 출력
2
-1
데이터 범위 와 약속
4. 567917. 100% 의 데이터 에 대해: N≤500000, M≤100000, |Ai|<=1000
문제 풀이:
#include
#include
#include
#include
#include
#define INF -0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn = 500010;
int n, m;
int a[maxn];
struct SegmentTree{
int l, r;
int dat, sum, lmax, rmax;
}t[maxn<<2];
void init(SegmentTree &tree, int x){
tree.dat=tree.lmax=tree.rmax=tree.sum=x;
}
void push_up(int p){
t[p].sum = t[2*p].sum + t[2*p+1].sum;
t[p].lmax = max(t[2*p].lmax, t[2*p].sum+t[2*p+1].lmax);
t[p].rmax = max(t[2*p+1].rmax, t[2*p+1].sum+t[2*p].rmax);
t[p].dat = max(t[2*p].dat, max(t[2*p+1].dat, t[2*p].rmax+t[2*p+1].lmax));
}
void build(int p, int l, int r){
t[p].l = l, t[p].r = r;
if(l == r){
init(t[p], a[l]);
return;
}
int mid = (l+r)/2;
build(2*p, l, mid);
build(2*p+1, mid+1, r);
push_up(p);
}
void change(int p, int x, int val){
if(t[p].l == t[p].r){
init(t[p], val);
return ;
}
int mid = (t[p].l+t[p].r)/2;
if(x <= mid) change(2*p, x, val);
else change(2*p+1, x, val);
push_up(p);
}
SegmentTree ask(int p, int l, int r){
if(l <= t[p].l && r >= t[p].r){
return t[p];
}
int mid = (t[p].l+t[p].r)/2;
SegmentTree a, b, c;
init(a, INF), init(b, INF);
c.sum = 0;
if(l <= mid) {
a = ask(2*p, l, r);
c.sum += a.sum;
}
if(r > mid) {
b = ask(2*p+1, l, r);
c.sum += b.sum;
}
c.dat = max(max(a.dat, b.dat), a.rmax+b.lmax);
c.lmax = max(a.lmax, b.lmax+a.sum);
c.rmax = max(b.rmax, a.rmax+b.sum);
return c;
}
int main()
{
int k, x, y;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
build(1,1,n);
while(m--){
cin >> k >> x >> y;
if(k == 1){
if(x > y) swap(x, y);
printf("%d
", ask(1,x,y).dat);
}else change(1,x,y);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ACM - 계산 기하학 적 Pick - up sticks -- poj 2653Description Stan has n sticks of various length. The data for each case start with 1 <= n <= 100000, the number of stick...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.