링크:https://ac.nowcoder.com/acm/contest/892/D 우 객 망
제목: 따뜻 한 출석 체크
n 길이 의 서열 을 드 리 겠 습 니 다. 처음에는 1, 2, 3... n 으로 m 번 조작 합 니 다.작업 은 두 가지 가 있 습 니 다. 1 l r 는 구간 [l, r] 을 [1, 2... r - l + 1] 로 2 l r 조회 [l, r] 의 구간 과 입력 설명 을 표시 합 니 다. 첫 번 째 줄 은 2 개의 숫자, n, m (1 < = n, m < = 1e5) 를 포함 합 니 다.
다음은 m 줄 을 포함 합 니 다. 형식 은 문제 면 에서 보 여 준 출력 설명 과 같 습 니 다. 각 조작 2 에 대해 한 줄 의 정 수 를 출력 하여 답 을 표시 합 니 다.
입력
복사 10, 5, 2, 1, 10, 1, 3, 6, 2, 1, 10, 1, 10, 2, 1, 10.
출력
55 47 55
제목 은 따뜻 한 출석 문제 라 고 하 는데 저 는 짙 은 악 의 를 느 꼈 습 니 다. 경기 할 때 선분 나무 로 해 야 한 다 는 것 을 알 았 습 니 다. 그러나 자신의 선분 나 무 는 기본 적 인 것 만 할 수 있 습 니 다. 구간 수정 과 게 으 른 노드 는 자신 이 할 줄 모 릅 니 다. 배 운 선분 나무 모델 은 왼쪽 에서 열 고 오른쪽 에서 닫 으 면 실수 하기 쉽 습 니 다. 이 문 제 를 틈 타 선분 나 무 를 잘 풀 어서 bug 를 오래 조정 하면 복잡 하고 실수 하기 쉽 습 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll s[4 * maxn], f[4 * maxn];//s ， f
int n, m, Q; //Q
void init(int k, int l, int r) //
{
if (l == r)
{
s[k] = r;
return;
}
int mid = (l + r) / 2;
init(k * 2, l, mid);
init(k * 2 + 1, mid + 1, r);
s[k] = s[k * 2] + s[k * 2 + 1];// pushup， ， pushdown 。
}
ll cal(ll t, int len)// ，
{
return (t + t + len - 1)* len / 2;
}
void pushdown(int k, int l, int r)//
{
if (f[k] == 0) return;
int mid = (l + r) /2;
f[k * 2] = f[k];
s[k * 2] = cal(f[k], mid - l + 1);
f[k * 2 + 1] = f[k] + mid - l + 1;
s[k * 2 + 1] = cal(f[k * 2 + 1], r - mid);
f[k] = 0;// ，
}
void update(int a, int b, int k, int l, int r)
{
if (l >= a && r <= b)
{
f[k] = Q;//l Q k Q
s[k] = cal(Q, r - l + 1);
Q += (r - l + 1);//Q
return;
}
pushdown(k, l, r);
int mid = (l + r) / 2;
if (a <= mid) update(a, b, k * 2, l, mid);
if (b > mid) update(a, b, k * 2 + 1, mid + 1, r);
s[k] = s[k * 2] + s[k * 2 + 1];
}
ll sum(int a, int b, int k, int l, int r)
{
if (l >= a && r <= b)
return s[k];
pushdown(k, l, r);//
ll left = 0, right = 0;
int mid = (l + r) / 2;;
if (a <= mid) left = sum(a, b, k * 2, l, mid);
if (b > mid) right = sum(a, b, k * 2 + 1, mid + 1, r);
s[k] = s[k * 2] + s[k * 2 + 1];
return left + right;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
init(1, 1, n);
for (int i = 0; i < m; i++)
{
int x, l, r;
cin >> x >> l >> r;
if (x == 1)
Q = 1, update(l, r, 1, 1, n);// Q 1
else
cout << sum(l, r, 1, 1, n) << endl;
}
}
더 성숙 한 코드 업데이트
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll s[maxn * 4], f[maxn * 4];
int n, m, Q;
void pushup(int k)
{
s[k] = s[k * 2 + 1] + s[k * 2];
}
void init(int k, int l, int r)
{
if (l == r) s[k] = r;
else
{
int mid = (l + r) >> 1;
init(k * 2, l, mid);
init(k * 2 + 1, mid + 1, r);
pushup(k);
}
}
ll cal(ll a, int len)
{
return (a + a + len - 1)* len / 2;
}
void pushdown(int k, int l, int r)
{
if (!f[k]) return;
int mid = (l + r) >> 1;
f[k * 2] = f[k];
s[k * 2] = cal(f[k], mid - l + 1);
f[k * 2 + 1] = f[k] + mid - l + 1;
s[k * 2 + 1] = cal(f[k * 2 + 1], r - mid);
f[k] = 0;
}
void update(int a, int b, int k, int l, int r)
{
if (l >= a && r <= b)
{
f[k] = Q;
s[k] = cal(Q, r - l + 1);
Q += (r - l + 1);
}
else
{
pushdown(k, l, r);
int mid = (l + r) >> 1;
if (a <= mid) update(a, b, k * 2, l, mid);
if (b > mid) update(a, b, k * 2 + 1, mid + 1, r);
pushup(k);
}
}
ll sum(int a, int b, int k, int l, int r)
{
if (l >= a && r <= b) return s[k];
pushdown(k, l, r);
int mid = (l + r) >> 1;
ll left = 0, right = 0;
if (a <= mid) left = sum(a, b, k * 2, l, mid);
if (b > mid) right = sum(a, b, k * 2 + 1, mid + 1, r);
return left + right;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
init(1, 1, n);
for (int i = 0; i < m; i++)
{
int x, l, r;
cin >> x >> l >> r;
if (x == 1)
{
Q = 1;
update(l, r, 1, 1, n);
}
else
cout << sum(l, r, 1, 1, n) << endl;
}
}
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전
Udemy 에서 공부 한 것을 중얼거린다
Chapter3【Integer Reversal】
(예)
문자열로 숫자를 반전 (toString, split, reverse, join)
인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
