hdu 4358 트 리 배열
14224 단어 데이터 구조
데이터 구조 문 제 는 오프라인 에 트 리 배열 을 이용 하여 답 을 통계 한다.
우 리 는 이 문제 의 약화 판 을 고려 합 니 다. N 개 수 를 드 리 겠 습 니 다. 한 구간 에 서로 다른 숫자 가 몇 개 있 는 지 구 합 니 다. 이 문 제 는 모든 가중치 가 지난번 에 나타 난 위 치 를 기록 함으로써 O (N lgN) 의 시간 내 에 해결 할 수 있 습 니 다. 구체 적 인 방법 은 조 회 를 오른쪽 단점 으로 배열 하고 왼쪽 에서 오른쪽으로 매 거 i 를 통 해 나무 모양 의 배열 을 유지 하 는 것 입 니 다.그 k 위 는 k 에서 i 까지 서로 다른 숫자 가 몇 개 인지 나타 낸다. 우 리 는 i 번 째 숫자 를 넣 는 것 을 고려한다. 이때 트 리 배열 에서 변 경 된 것 은 last [v] + 1 에서 i 구간 의 값 일 뿐이다. 그 중에서 v 는 i 번 째 숫자 이 고 last [v] 는 v 라 는 숫자 가 지난번 에 나타 난 위 치 를 나타 내 며 나타 나 지 않 았 다 면 0 이다.그래서 우 리 는 트 리 배열 last [v] + 1 이라는 위치의 값 + 1 을 i + 1 이라는 위치 - 1 로 구 할 때 왼쪽 점 (왼쪽 점 에 대한 구 화) 이 last [v] + 1 이후 (자신 포함) 이면 v 점 을 포함 시 킬 수 있다.그리고 i 를 매 거 한 후에 우 리 는 오른쪽 점 이 i 의 모든 조 회 를 고려 하여 왼쪽 점 이 트 리 배열 에 있 는 값 이 얼마 인지 보면 된다.
그 다음 에 우 리 는 이 문 제 를 고려 하여 나무 구 조 를 선형 구조 로 바 꾸 면 우 리 는 문 제 를 한 구간 으로 바 꿀 수 있다. 마침 K 차 의 가중치 가 몇 가지 가 있 는 지 알 수 있다.우 리 는 트 리 배열 의 k 위 를 기록 하여 k 에서 i 까지 의 답 을 표시 하고 v 가 나타 난 위 치 는 p1 이 라 고 가정 합 니 다.p2; p3; ; pk, 그러면 우 리 는 현재 pk 라 는 위치 에 매 거 되 었 다 고 가정 하고 pk 라 는 위치의 숫자 를 집합 한 후에 p (k - K - 1) + 1 ~ p (k - K) 이 부분 구간 의 가중치 v 가 나타 나 는 횟수 가 K 를 초과 한다. p (k - K) + 1 ~ p (k - K + 1) 이 부분 구간 의 가중치 v 가 나타 나 는 횟수 가 마침 K 에 이 르 렀 기 때문에 우 리 는 나무 모양 배열 의 p (k - K - 1) + 1 ~ p (k - K) 안의 값 을 모두 1 로 줄 였 다. p(k - K) + 1 부터 p (k - K + 1) 까지 의 값 은 모두 1 을 더 합 니 다. 검색 할 때 왼쪽 점 의 앞 수 를 합 친 것 입 니 다. 전체 복잡 도 는 O (N lgN) 입 니 다.
문 제 는 선형 서열 이 되 고 나머지 는 간단 하 다 는 것 이다.
이것 은 핵심 적 이 고 핵심 적 인 코드 이 므 로 잘 체득 해 야 한다.
문 제 를 푸 는 상황 입 니 다. 방금 자신 을 칭찬 하 다가 또 배열 의 크기 에 넘 어 졌 습 니 다. 여 기 는 양 방향 변 을 만 들 었 는데 저 는 단 방향 을 만족 시 키 는 배열 만 열 었 습 니 다. 왜 항 전 은 항상 WA 를 보고 하 는 지 모 르 겠 습 니 다.
그리고 초기 화 입 니 다. L 과 c 는 다시 초기 화해 야 합 니 다. 왜 요? 이전 케이스 의 L 과 c 때문에 이 케이스 에 영향 을 줄 수 있 습 니 다. 왜 요?
그리고 이 문제 의 작법 은 나 를 매우 탄복 하 게 한다. 그러나 나 는 이것 도 고정 적 인 작법 이 라 고 생각한다. 만약 나중에 다시 이런 유형 을 만 나 게 된다 면 아마도 물 문제 일 것 이다.
그리고 두 가지 방법 이 있 습 니 다. 하 나 는 선분 나무 이 고 하 나 는 맵 입 니 다.
선분 트 리 의 작법 은 한 선분 을 삭제 하 는 것 입 니 다. 작법 은 이전의 flowers 와 매우 비슷 합 니 다. 구간 업데이트, 단일 조회.
트 리 배열 핵심 코드:
for (int i=1; i<=n; i++){
int v = val[i]; pl[v].push_back(i);
int g = pl[v].size()-1;
if (g >= k){
if (g > k){
insert(pl[v][g-k-1]+1,-1);
insert(pl[v][g-k]+1,1);
}
insert(pl[v][g-k]+1, 1);
insert(pl[v][g-k+1]+1, -1);
}
while (qn[t].y==i){
ans[qn[t].id]=query(qn[t].x);//
t++;
}
}
선분 트 리 핵심 코드:
for (int i = 1; i <= n; ++i) {
// j [j, i] k
int num = a[i];
vv[num].push_back(i);
int size = vv[num].size();
if (size >= k) {
if (size > k) {
// 1 ~ vv[num][size-k-1] 1,
update(1, n, 1, 1, vv[num][size-k-1], -1);
// vv[num][size-k-1]+1 ~ vv[num][size-k] 1 ,
update(1, n, 1, vv[num][size-k-1] + 1, vv[num][size-k], 1);
} else {
// 1 ,
update(1, n, 1, 1, vv[num][size-k], 1);
}
}
while (Q[idx].r == i) {
ans[Q[idx].id] = query(1, n, 1, Q[idx].l);
idx++;
}
}
트 리 배열:
/*
Pro: 0
Sol:
date:
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 100010
using namespace std;
int n,k,t,a[maxn],Q,head[maxn],esub,linr[maxn],L[maxn],R[maxn],li,ans[maxn];
int c[maxn];
vector < int > pl[maxn];//
bool cmpx(int x, int y){
return a[x] < a[y];
}
void dis(){
int tmp = -1,r[maxn];
for(int i = 1; i <= n; i ++)
r[i] = i;
sort(r + 1, r + 1 + n, cmpx);
int prev = a[r[1]] - 1;// prev ,
for(int i = 1; i <= n; i ++)
if(prev != a[r[i]]) prev = a[r[i]],a[r[i]] = ++ tmp;
else { a[r[i]] = tmp;}
for(int i = 0; i <= tmp; i ++){
pl[i].clear();//
pl[i].push_back(0); // 0
}
}
struct query{
int L,R,id;
bool operator < (const query& cmp) const{
return R < cmp.R;
}
}q[maxn];
struct Edge{
int v,nxt;
}edge[maxn << 1 ];//
void init(){
esub = 0; li = 0;
memset(head,-1,sizeof(head));
memset(c,0,sizeof(c));
memset(L,0,sizeof(L));
}
void add(int u, int v){
edge[esub].v = v;
edge[esub].nxt = head[u];
head[u] = esub ++;
}
void dfs(int rt){
L[rt] = ++li; linr[li] = a[rt];
for(int j = head[rt]; j != -1; j = edge[j].nxt){
if(!L[edge[j].v]) dfs(edge[j].v);
}
R[rt] = li;
}
void modify(int pos, int val){
while(pos <= n){
c[pos] += val;
pos += (pos & (-pos) );
}
}
int getsum(int pos){
int sum = 0;
while(pos){
sum += c[pos];
pos -= (pos & (-pos) );
}return sum;
}
int main(){
scanf("%d",&t);
for(int ca = 1; ca <= t; ca ++){
printf("Case #%d:
",ca);
scanf("%d%d",&n,&k);
init();//
for(int i = 1; i <= n; i ++){
scanf("%d",&a[i]);
}
dis();// , , ,
for(int i = 1; i < n; i ++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1); //
scanf("%d",&Q);
for(int i = 1; i <= Q; i ++){
int x;
scanf("%d",&x);
q[i].L = L[x];
q[i].R = R[x];
q[i].id = i;
} sort(q + 1, q + 1 + n);
int qsub = 1;
for(int i = 1; i <= n; i ++){
int v = linr[i]; pl[v].push_back(i);// linr[i]
int g = pl[v].size() - 1;
if(g >= k){
if(g > k){
modify(pl[v][g - k - 1] + 1, -1);
modify(pl[v][g - k] + 1, 1);
}
modify(pl[v][g - k] + 1, 1);
modify(pl[v][g - k + 1] + 1, -1);
}
while( q[qsub].R == i){
ans[q[qsub].id] = getsum(q[qsub].L);
qsub ++;
}
}
for(int i = 1; i <= Q; i ++)
printf("%d
",ans[i]);
if(ca < t) puts("");
}
return 0;
}
선분 트 리: (붙 인)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 100010;
int t, n, k, q;
int w[maxn], a[maxn];
int L[maxn], R[maxn]; // 、
int ans[maxn], id;
vector<int> vt[maxn]; //
vector<int> vv[maxn];
bool vis[maxn];
map<int, int> mp;
struct Query {
int l, r, id;
}Q[maxn];
// for segment tree:
int add[maxn<<2];
bool cmp(Query q1, Query q2)
{
return q1.r < q2.r;
}
void dfs(int x)
{ //
vis[x] = true;
L[x] = id;
a[id] = w[x];
int size = vt[x].size();
for (int i = 0; i < size; ++i) {
if (!vis[vt[x][i]]) {
id++;
dfs(vt[x][i]);
}
}
R[x] = id;
}
void pushDown(int rt)
{
if (add[rt]) {
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
add[rt] = 0;
}
return ;
}
void build(int l, int r, int rt)
{
add[rt] = 0;
if (l == r) return ;
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
}
void update(int l, int r, int rt, int L, int R, int c)
{
if (L <= l && R >= r) {
add[rt] += c;
return ;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) {
update(l, m, rt << 1, L, R, c);
}
if (R > m) {
update(m + 1, r, rt << 1 | 1, L, R, c);
}
}
int query(int l, int r, int rt, int p)
{
if (l == r) {
return add[rt];
}
pushDown(rt);
int m = (l + r) >> 1;
if (p <= m) {
return query(l, m, rt << 1, p);
} else {
return query(m + 1, r, rt << 1 | 1, p);
}
}
int main()
{
scanf("%d", &t);
for (int cas = 1; cas <= t; ++cas) {
scanf("%d%d", &n, &k);
mp.clear();
id = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &w[i]);
//
if (mp[w[i]] == 0) {
mp[w[i]] = id++;
}
w[i] = mp[w[i]];
}
int u, v;
for (int i = 0; i < maxn; ++i) {
vt[i].clear();
vv[i].clear();
}
for (int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
vt[u].push_back(v);
vt[v].push_back(u);
}
memset(vis, false, sizeof(vis));
id = 1;
dfs(1);
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d", &u);
Q[i].id = i;
Q[i].l = L[u];
Q[i].r = R[u];
}
sort(Q, Q + q, cmp);
build(1, n, 1);
int idx = 0;
for (int i = 1; i <= n; ++i) {
// j [j, i] k
int num = a[i];
vv[num].push_back(i);
int size = vv[num].size();
if (size >= k) {
if (size > k) {
// 1 ~ vv[num][size-k-1] 1
update(1, n, 1, 1, vv[num][size-k-1], -1);
// vv[num][size-k-1]+1 ~ vv[num][size-k] 1
update(1, n, 1, vv[num][size-k-1] + 1, vv[num][size-k], 1);
} else {
// 1
update(1, n, 1, 1, vv[num][size-k], 1);
}
}
while (Q[idx].r == i) {
ans[Q[idx].id] = query(1, n, 1, Q[idx].l);
idx++;
}
}
if (cas != 1) {
printf("
");
}
printf("Case #%d:
", cas);
for (int i = 0; i < q; ++i) {
printf("%d
", ans[i]);
}
}
return 0;
}
맵 으로 쓴 (붙 인):
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define LL long long
//c++ ( ) g++
using namespace std;
const int N=100005;
int head[N];//
struct node
{
int j;
int next;
} side[N*2];
int son[N];//
int f[N];//
int id[N];// map
// i id[i]
int ans[N];//
map<int ,int>str[N];
map<int ,int>:: iterator it,it1;
queue<int>qu;
int K;
void build(int x,int i)
{
side[i].next=head[x];
head[x]=i;
}
void dfs(int x,int pre)// dfs
{
int t=head[x];
f[x]=pre;
while(t!=-1)
{
if(side[t].j!=pre)
{
dfs(side[t].j,x);
++son[x];
}
t=side[t].next;
}
if(son[x]==0)
{
qu.push(x);
}
}
void Add(int I,int i,int j)// map j i ans[I]
{
for(it=str[j].begin(); it!=str[j].end(); ++it) //it map j
{
it1=str[i].find(it->first);// i
if(it1==str[i].end())//
{
str[i][it->first]=it->second;//
if(it->second==K)// K
++(ans[I]);
continue;
}
if(it1->second==K)// i K
// 0 K 1
--(ans[I]);
if((it1->second+=it->second)==K)// K 1
++(ans[I]);
}
}
int main()
{
int T;
scanf("%d",&T);
for(int cas=1; cas<=T; ++cas)
{
memset(head,-1,sizeof(head));
memset(ans,0,sizeof(ans));
memset(son,0,sizeof(son));//
while(!qu.empty())
qu.pop();
int n,q;
scanf("%d %d",&n,&K);
for(int i=1; i<=n; ++i)
{
int a;
str[i].clear();//
id[i]=i;// map
scanf("%d",&a);
str[i][a]=1;//
if(K==1)// K 1
++ans[i];
}
int x,y;
for(int i=1; i<n; ++i) //
{
scanf("%d %d",&x,&y);
side[i].j=y;
build(x,i);
side[i+n].j=x;
build(y,i+n);
}
dfs(1,0);//
while(!qu.empty())
{
int l=qu.front();//
qu.pop();
int fa=f[l];//fa
--son[fa];// 1
if(son[fa]==0)// fa
{
// ( )
qu.push(fa);
}
int li=id[l];// map
int fai=id[fa];
if(str[fai].size()>str[li].size())//
{//
Add(fa,fai,li);
}
else{
ans[fa]=ans[l];// l l ans ans[fa]
// map
id[fa]=li;// map
Add(fa,li,fai);//
}
}
scanf("%d",&q);
printf("Case #%d:
",cas);
while(q--)
{
scanf("%d",&x);
printf("%d
",ans[x]);
}
if(cas<T)
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.