선분 수 문제 몇 개
13847 단어 선분 수
다음은 초급 라인 트 리 입 니 다. 업데이트 점 만 있 고 delay 작업 이 없습니다.
1. HDU 1166 적군 포진
이 문 제 는 선분 트 리 나 트 리 배열 로 모두 풀 수 있 는데, HDU 의 데이터 가 매우 약 한 것 같 아서, 시 뮬 레이 션 을 모두 통과 할 수 있다.
우선 선분 트 리 판 입 니 다. 선분 트 리 에 있 는 정 보 는 현재 구간 의 모든 점 의 값 과
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int a[MAXN];
struct node
{
int left, right, mid;
int sum;
}tree[4 * MAXN];
int ans;
void up(int C)
{
tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) / 2;
tree[C].sum = 0;
if(s == e)
{
tree[C].sum = a[s];
return;
}
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
up(C);
}
void update(int C, int p, int v)
{
if(tree[C].left == p && tree[C].right == p)
{
tree[C].sum += v;
return;
}
if(p <= tree[C].mid)
update(L(C), p, v);
else update(R(C), p, v);
up(C);
}
void search(int s, int e, int C)
{
if(s <= tree[C].left && tree[C].right <= e)
{
ans += tree[C].sum;
return;
}
if(tree[C].mid >= e) search(s, e, L(C));
else if(tree[C].mid < s) search(s, e, R(C));
else
{
search(s, tree[C].mid, L(C));
search(tree[C].mid + 1, e, R(C));
}
}
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
char s[20];
int t, n, i, cas = 0, x, y;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
make_tree(1, n, 1);
printf("Case %d:
", ++cas);
while(scanf("%s", s) != EOF)
{
if(s[0] == 'E') break;
else if(s[0] == 'Q')
{
ans = 0;
scanf("%d%d", &x, &y);
search(x, y, 1);
printf("%d
", ans);
}
else if(s[0] == 'A')
{
scanf("%d%d", &x, &y);
update(1, x, y);
}
else if(s[0] == 'S')
{
scanf("%d%d", &x, &y);
update(1, x, -y);
}
}
}
return 0;
}그리고 트 리 배열 판.
/*
ID: sdj22251
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
using namespace std;
int a[50005], n, b[50005];
int lowbit(int x)
{
return x & -x;
}
void modify(int x)
{
for(int i = x; i <= n; i += lowbit(i))
a[i] += b[x];
}
void modify2(int x, int y)
{
for(int i = x; i <= n; i += lowbit(i))
a[i] += y;
}
int sum(int x)
{
int ans = 0;
for(int i = x; i >= 1; i -= lowbit(i))
ans += a[i];
return ans;
}
int main()
{
#ifdef LOCAL
freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);
#endif
int t, cas = 0, i, x, y;
char s[15];
scanf("%d", &t);
while(t--)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
modify(i);
}
printf("Case %d:
", ++cas);
while(scanf("%s", s) != EOF)
{
if(s[0] == 'E')
break;
else if(s[0] == 'Q')
{
scanf("%d%d", &x, &y);
printf("%d
", sum(y) - sum(x - 1));
}
else if(s[0] == 'A')
{
scanf("%d%d", &x, &y);
modify2(x, y);
}
else if(s[0] == 'S')
{
scanf("%d%d", &x, &y);
modify2(x, -y);
}
}
}
return 0;
}2.HDU 1754 I Hate It
같은 점 업데이트 에 up 작업 을 추가 하면 됩 니 다. 선분 트 리 에 있 는 정 보 는 현재 구간 의 최대 값 입 니 다.
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 200005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct node
{
int left, right, mid;
int l, mx;
} tree[4 * MAXN];
int ans, num[MAXN];
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = ((s + e) >> 1);
tree[C].l = tree[C].right - tree[C].left + 1;
tree[C].mx = 0;
if(s == e) {tree[C].mx = num[s]; return;}
make_tree(s, tree[C].mid, (C << 1));
make_tree(tree[C].mid + 1, e, (C << 1) | 1);
tree[C].mx = max(tree[C << 1].mx, tree[(C << 1) + 1].mx);
}
void update(int s, int v, int C)
{
if(tree[C].left == s && tree[C].right == s)
{
tree[C].mx = v;
return;
}
if(s > tree[C].mid)
{
update(s, v, (C << 1) | 1);
}
else update(s, v, C << 1);
tree[C].mx = max(tree[C << 1].mx, tree[(C << 1) + 1].mx);
}
void search(int s, int e, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
if(tree[C].mx > ans)
ans = tree[C].mx;
return;
}
if(s > tree[C].mid)
{
search(s, e, (C << 1) | 1);
}
else if(e <= tree[C].mid)
{
search(s, e, C << 1);
}
else
{
search(s, tree[C].mid, C << 1);
search(tree[C].mid + 1, e, (C << 1) | 1);
}
}
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
int n, m, i, x, y;
char s[5];
while(scanf("%d%d", &n, &m) != EOF)
{
for(i = 1; i <= n; i++)
scanf("%d", &num[i]);
make_tree(1, n, 1);
while(m--)
{
scanf("%s %d %d", s, &x, &y);
if(s[0] == 'Q')
{
ans = 0;
search(x, y, 1);
printf("%d
", ans);
}
else
{
update(x, y, 1);
}
}
}
return 0;
}3.HDU 1394Minimum Inversion Number
문 제 는 바로 역순 수 를 구 한 다음 에 현재 서열 의 첫 번 째 수 를 서열 끝 에 놓 고 역순 수 를 구 하 는 것 이다. 모두 n 번 으로 그 중에서 가장 작은 역순 수 를 구 하 는 것 이다.
사실은 최초의 역순 수 를 구하 면 됩 니 다. 그 다음 의 역순 수 는 유도 할 수 있 기 때문에 모두 n 개의 수, 0 에서 n - 1 까지 있 습 니 다. a [i] 보다 작은 수 는 a [i] 개 이 고 큰 수 는 n - 1 - a [i] 개 입 니 다.
역순 수 를 구 할 때 사용 하 는 방법 은 먼저 조회 하고 업데이트 하 는 것 이다. 이미 존재 하 는 자신 보다 큰 수의 개 수 를 조회 하 는 것 이 고, 선분 수 에 있 는 정 보 는 바로 이 구간 에 몇 개의 수가 존재 하 는 것 이다.
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
int sum;
}tree[4 * MAXN];
int tmp, a[MAXN];
void up(int C)
{
tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) / 2;
tree[C].sum = 0;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void search(int s, int e, int C)
{
if(s <= tree[C].left && e >= tree[C].right)
{
tmp += tree[C].sum;
return;
}
if(tree[C].mid >= e) search(s, e, L(C));
else if(tree[C].mid < s) search(s, e, R(C));
else
{
search(s, tree[C].mid, L(C));
search(tree[C].mid + 1, e, R(C));
}
}
void update(int p, int s, int e, int C)
{
if(s == e && s == p) {tree[C].sum++; return;}
if(tree[C].mid >= p) update(p, s, tree[C].mid, L(C));
else update(p, tree[C].mid + 1, e, R(C));
up(C);
}
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
int n, i;
while(scanf("%d", &n) != EOF)
{
make_tree(0, n - 1, 1);
int sum = 0;
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
tmp = 0;
search(a[i], n - 1, 1);
sum += tmp;
update(a[i], 0, n - 1, 1);
}
int ret = sum;
for(i = 0; i < n; i++)
{
sum = sum + n - a[i] - a[i] - 1;
ret = min(ret, sum);
}
printf("%d
", ret);
}
return 0;
}4.HDU 2795 Billboard
문 제 는 높이 가 h 너비 가 w 인 널 빤 지 를 주 고 높이 가 1, 너비 와 이 를 붙 이 는 것 이다. 매번 댓 글 에서 가장 높 은 댓 글 을 먼저 찾 고 높이 가 같은 것 은 가능 한 한 왼쪽으로 붙 여야 한 다 는 뜻 이다.
사실 판 자 를 가로로 놓 으 면 이해 하기 쉽 습 니 다. 가로 좌 표 는 h 이 고 최대한 왼쪽으로 쪽 지 를 붙 입 니 다.
데이터 범위 가 매우 큰 것 같 지만 사실은 크 지 않다. 왜냐하면 n 은 20 만 위안 밖 에 안 되 기 때문이다. 즉, 선분 나무의 범 위 는 1 만 에서 20 만 위안 이면 충분 하 다.
그 다음 에 선분 나무의 추가 정 보 는 이 구간 에 있 는 모든 h 의 남 은 공간의 최대 치 입 니 다. 조회 할 때 최종 적 으로 잎 노드 를 찾 아 소모 하 는 길 이 를 줄 이면 됩 니 다.
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 200005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int h, w, n;
struct node
{
int left, right, mid;
int mx;
}tree[4 * MAXN];
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) / 2;
tree[C].mx = w;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
int insert(int C, int v)
{
if(tree[C].mx < v) return -1;
if(tree[C].left == tree[C].right)
{
tree[C].mx -= v;
return tree[C].left;
}
int ans = -1;
if(v <= tree[L(C)].mx)
ans = insert(L(C), v);
else if(v <= tree[R(C)].mx)
ans = insert(R(C), v);
tree[C].mx = max(tree[L(C)].mx, tree[R(C)].mx);
return ans;
}
int main()
{
#ifdef LOCAL
freopen("d:/data.in","r",stdin);
freopen("d:/data.out","w",stdout);
#endif
int i, x;
while(scanf("%d%d%d", &h, &w, &n) != EOF)
{
if(h > n) h = n;
make_tree(1, h, 1);
for(i = 0; i < n; i++)
{
scanf("%d", &x);
printf("%d
", insert(1, x));
}
}
return 0;
}그 다음 에 이 몇 가지 초급 문 제 를 풀 었 는데 조 회 를 발 견 했 을 때 하 나 는 사용자 정의 조회 범 위 를 필요 로 하 는 것 이 고 다른 하 나 는 사용자 정의 조회 범 위 를 필요 로 하지 않 고 조상 부터 직접 조사 한 것 으로 조회 함수 의 매개 변 수 는 자 연 스 럽 게 다르다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
