[데이터 구조 연습] 구간 K 대 수 를 구 하 는 몇 가지 방법
예 를 들 어 HDOJ 2665, POJ 2104, SOJ 3147, SOJ 3010, SOJ 3102 (한 번 만 계산), POJ 2761 (구간 은 포함 되 지 않 음).
이 문 제 를 해결 하 는 방법 도 매우 많 습 니 다. 여기 서 제 가 흔히 볼 수 있다 고 생각 하 는 몇 가지 방법 에 대해 정 리 를 하고 앞으로 도 계속 보충 할 것 입 니 다.
물론 거의 모든 고급 데이터 구 조 는 구간 K 대 수 를 구 하 는 데 사용 할 수 있 고 나 도 이것 이 데이터 구 조 를 처음 배 울 때 좋 은 연습 이 라 고 생각한다.
고급 데이터 구 조 는 나의 약점 중 하나 입 니 다. 만약 코드 가 좋 지 않 은 부분 이 있다 면 신 번 의 지 도 를 환영 합 니 다 > <.
1. 빠 른 구분
가장 간단 한 방법 은 당연히 빠 른 배열 과 같은 방법 으로 빠 른 구분 을 하 는 것 이다.
매번 무 작위 로 하나의 수 를 '주 원' 으로 선택 하고 '주 원' 을 분계선 으로 현재 구간 의 수 를 두 부분 으로 나 누 어 '주 원' 의 정확 한 위 치 를 찾 은 후에 계속 재 귀 한다.
이 알고리즘 에 대한 설명 은 MIT 의 '알고리즘 서론' 공개 수업 을 볼 수 있다.
어 쩔 수 없 이 제 가 너무 피둥피둥 해서 아무리 해도 TLE 입 니 다. 여러분 잠시 보 세 요.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN=110000;
int a[MAXN],b[MAXN];
char s[2000000];
int quicksort(int p, int q)
{
int k=p+((int)rand()%(q-p+1));
swap(b[k],b[p]);
int i=p;
for(int j=p+1; j<=q; j++)
{
if(b[j]<b[p])
{
i++;
swap(b[i],b[j]);
}
}
swap(b[i],b[p]);
return i-p+1;
}
int solve(int p, int q, int k)
{
int tmp;
while((tmp=quicksort(p,q))!=k)
{
if(tmp<k)
{
p+=tmp;
k-=tmp;
}
else
{
q=p+tmp-1;
}
}
return b[p+tmp-1];
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
memcpy(b,a,n*sizeof(int));
printf("%d
",solve(l-1,r-1,k));
}
}
return 0;
}
2. 이 진 더미
용량 이 K 인 이 진 더미 로 현재 구간 의 요 소 를 모두 쌓 아 올 리 지만 매번 이 더미 의 앞 K 작은 숫자 만 남 겨 두 고 마지막 으로 이 더미 의 꼭대기 요 소 는 원 하 는 것 입 니 다.
이 알고리즘 은 분명히 TLE 의 것 일 것 입 니 다. 저 는 손 으로 써 도 시간 이 지나 지 않 을 것 이 라 고 믿 습 니 다. 여러분 에 게 코드 를 써 서 표 시 를 해 드 리 겠 습 니 다.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN=110000;
int a[MAXN];
priority_queue<int> q;
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
l--;
r--;
while(!q.empty())
{
q.pop();
}
int cot=0;
for(int i=l; i<=r; i++)
{
q.push(a[i]);
cot++;
if(cot>k)
{
q.pop();
cot--;
}
}
printf("%d
",q.top());
}
}
return 0;
}
3. 나무 모양 배열
친구 들 이 즐겨 보 는 나무 모양 의 배열 도 구간 K 대 수 를 구 할 수 있 습 니 다!
트 리 배열 의 + low bit 는 실제 적 으로 '트 리' 에서 부모 노드 / 하위 노드 로 뛰 어 내 리 는 작업 을 실현 합 니 다.
이로써 2 분 의 1 로 K 대 수 를 구 할 수 있다.
clj 의 코드 와 문제 풀이 보고 서 를 참고 하 였 습 니 다. 이것 은 고정 구간 에서 만 구 할 수 있 습 니 다.
물론 임 의 자 구간 에서 구 하 는 것 도 어렵 지 않 고 매번 나 무 를 다시 세우 면 된다.
위 와 마찬가지 로 이 코드 도 도저히 지나 갈 수 없습니다.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXP = 22;
const int MAXN = 2100000;
vector<int> hash;
int a[MAXN], tr[MAXN];
int m;
void add(int x)
{
while(x <= m)
{
tr[x]++;
x+=x&(-x);
}
}
int solve(int k)
{
int cnt = 0, ans = 0;
for (int i = MAXP-1; i >= 0; i--)
{
ans += 1 << i;
if (ans >= m || cnt + tr[ans] >= k)
{
ans -= 1 << i;
}
else
{
cnt += tr[ans];
}
}
return ans + 1;
}
int main()
{
int n,k;
while(scanf("%d%d", &n, &k)==2)
{
hash.clear();
memset(tr, 0, sizeof(tr));
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
hash.push_back(a[i]);
}
sort(hash.begin(), hash.end());
hash.erase(unique(hash.begin(), hash.end()), hash.end());
m = hash.size();
for(int i = 1; i <= n; i ++)
{
a[i] = lower_bound(hash.begin(), hash.end(), a[i]) - hash.begin();
add(a[i]+1);
}
printf("%d
", hash[solve(k)-1]);
}
return 0;
}
--------------------------------------------------------------------------------------------------------------
4. 나무 나 누 기
나 무 를 나 누 는 것 은 일종 의 선분 나무 다.
구간 K 대 를 구 하 는 데 쓸 수 있다.
트 리 벽 이 갈 라 지 는 것 을 배 워 서 HDOJ 4417 을 하 는 것 을 권장 합 니 다. 코드 를 조금 바 꿀 수 있 습 니 다. 구간 K 에서 구간 내 에서 특정한 값 보다 작은 숫자 가 몇 개 (2 점 이 필요 하지 않 습 니 다) 로 바 꿀 수 있 습 니 다.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN=110000;
int tr[MAXN<<2];
int sorted[MAXN],toleft[20][MAXN],val[20][MAXN];
void build(int l, int r, int dep, int rt)
{
if(l==r)
{
return;
}
int mid=(l+r)>>1;
int lnum=mid-l+1;
for(int i=l; i<=r; i++)
{
if(val[dep][i]<sorted[mid])
{
lnum--;
}
}
int lp=l,rp=mid+1;
int cur_lnum=0;
for(int i=l; i<=r; i++)
{
if(i==l)
{
toleft[dep][i]=0;
}
else
{
toleft[dep][i]=toleft[dep][i-1];
}
if(val[dep][i]<sorted[mid])
{
toleft[dep][i]++;
val[dep+1][lp++]=val[dep][i];
}
else if(val[dep][i]>sorted[mid])
{
val[dep+1][rp++]=val[dep][i];
}
else
{
if(cur_lnum<lnum)
{
cur_lnum++;
toleft[dep][i]++;
val[dep+1][lp++]=val[dep][i];
}
else
{
val[dep+1][rp++]=val[dep][i];
}
}
}
build(l,mid,dep+1,rt<<1);
build(mid+1,r,dep+1,rt<<1|1);
}
int query(int l, int r, int L, int R, int k, int dep, int rt)
{
if(l==r)
{
return val[dep][l];
}
int lnum,cur_lnum,rnum,cur_rnum;
int mid=(l+r)>>1;
if(l==L)
{
lnum=toleft[dep][R];
cur_lnum=0;
}
else
{
lnum=toleft[dep][R]-toleft[dep][L-1];
cur_lnum=toleft[dep][L-1];
}
if(lnum>=k)
{
int newL=l+cur_lnum;
int newR=l+lnum+cur_lnum-1;
return query(l,mid,newL,newR,k,dep+1,rt<<1);
}
else
{
int rnum=R-L+1-lnum;
int cur_rnum=L-l-cur_lnum;
int newL=mid+cur_rnum+1;
int newR=mid+cur_rnum+rnum;
return query(mid+1,r,newL,newR,k-lnum,dep+1,rt<<1|1);
}
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
{
scanf("%d",&val[0][i]);
sorted[i]=val[0][i];
}
sort(sorted,sorted+n);
build(0,n-1,0,1);
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
l--;
r--;
printf("%d
",query(0,n-1,l,r,k,0,1));
}
}
return 0;
}
5. 병합 수
나 무 를 병합 하 는 것 과 나 무 를 나 누 는 것 은 좋 은 친구 이다.
근 데 당분간 안 배 울 거 야.
먼저 구 덩이 를 열 어 다른 사람의 문제 풀이 보고 서 를 버리다.
6. 주석 트 리 (지속 가능 한 선분 트 리 / 함수 식 선분 트 리)
주석 트 리 의 핵심 요 지 는 업데이트 할 때마다 업 데 이 트 된 노드 (O (lgn) 개 만 새로 만 들 고 역사 버 전 을 저장 하 는 것 입 니 다.
sd 6001 과 ftiasch 템 플 릿 감사합니다.
배열 판:
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN = 100005;
const int MAXM = 2000005;
vector<int> hash;
int a[MAXN];
int tot;
struct NODE
{
int count;
int left, right;
};
int root[MAXN];
NODE node[MAXM];
int null;
int newnode(int count, int left, int right)
{
node[tot].count=count;
node[tot].left=left;
node[tot].right=right;
return tot++;
}
int insert(int rt, int l, int r, int k)
{
if (l <= k && k <= r)
{
if (l == r)
{
return newnode(node[rt].count + 1, 0, 0);
}
int m = (l + r) >> 1;
return newnode(node[rt].count + 1,
insert(node[rt].left, l, m, k),
insert(node[rt].right, m + 1, r, k));
}
return rt;
}
int query(int p, int q, int l, int r, int k)
{
if (l == r)
{
return hash[l];
}
int m = (l + r) >> 1;
int cot = node[node[q].left].count - node[node[p].left].count;
if (cot >= k)
{
return query(node[p].left, node[q].left, l, m, k);
}
return query(node[p].right, node[q].right, m + 1, r, k - cot);
}
int main()
{
int cas;
scanf("%d", &cas);
while(cas --)
{
int n, q;
scanf("%d%d", &n, &q);
hash.clear();
tot = 0;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
hash.push_back(a[i]);
}
sort(hash.begin(), hash.end());
hash.erase(unique(hash.begin(), hash.end()), hash.end());
int m = hash.size();
null = newnode(0, 0, 0);
root[0] = newnode(0, 0, 0);
for(int i = 1; i <= n; i ++)
{
a[i] = lower_bound(hash.begin(), hash.end(), a[i]) - hash.begin();
root[i] = insert(root[i - 1], 0, m - 1, a[i]);
}
while(q--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d
", query(root[l - 1], root[r], 0, m - 1, k));
}
}
return 0;
}
동적 할당 메모리:
메모: 이 템 플 릿 은 new 만 delete 가 없 기 때문에 모든 케이스 의 신청 메모리 가 겹 쳐 있 음 을 알 수 있 습 니 다. 분 MLE 는 오리 배 가 없습니다.
현재 이 템 플 릿 은 SOJ 3147 을 넘 을 수 밖 에 없다.하지만 싱글 케이스 에서 평가 한 OJ 는 이렇게 쓰 는 것 이 우아 하 다.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
const int MAXN = 100005;
vector<int> hash;
int a[MAXN];
struct node
{
int count;
node *left, *right;
node(int count, node* left, node* right):
count(count), left(left), right(right) {}
node* insert(int k);
node* insert(int l, int r, int k);
};
node* root[MAXN];
node* null = new node(0, NULL, NULL);
node* node::insert(int l, int r, int k)
{
if (l <= k && k <= r)
{
if (l==r)
{
return new node(this->count + 1, null, null);
}
int m = (l + r) >> 1;
return new node(this->count + 1,
this->left->insert(l, m, k),
this->right->insert(m + 1, r, k));
}
return this;
}
int query(node *p, node *q, int l, int r, int k)
{
if (l == r)
{
return hash[l];
}
int m = (l + r) >> 1;
int cot = q->left->count - p->left->count;
if (cot >= k)
{
return query(p->left, q->left, l, m, k);
}
return query(p->right, q->right, m+1, r, k - cot);
}
int main()
{
int cas;
null->left = null->right = null;
scanf("%d", &cas);
while(cas --)
{
int n,q;
scanf("%d%d", &n, &q);
hash.clear();
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
hash.push_back(a[i]);
}
sort(hash.begin(), hash.end());
hash.erase(unique(hash.begin(), hash.end()), hash.end());
int m = hash.size();
root[0] = null;
for(int i = 1; i <= n; i ++)
{
a[i] = lower_bound(hash.begin(), hash.end(), a[i]) - hash.begin();
root[i] = root[i-1]->insert(0,m - 1,a[i]);
}
while(q --)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d
", query(root[l - 1], root[r], 0, m - 1, k));
}
}
return 0;
}
7、Treap
Treap 구간 K 대 수 는 POJ 2761 을 하 는 것 이 가장 좋다. 이 문 제 는 구간 에 포함 되 지 않 는 조건 이 있 기 때문에 그렇지 않 으 면 복잡 도가 많이 올라간다.
이 문 제 는 실제 적 으로 FIFO 대기 열 을 유지 하여 어떤 질문 을 처리 할 때 treap 에는 묻 고 있 는 이 구간 만 포함 되 어 있 습 니 다.
ftiasch 템 플 릿 감사합니다.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define fi first
#define nd second
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 110000;
const int MAXM = 51000;
int treap_size;
int key[MAXN], weight[MAXN], cot[MAXN], size[MAXN], cld[MAXN][2];
pair<PII, PII> query[MAXM];
int ans[MAXM];
int a[MAXN];
bool cmp(const pair<PII, PII> &a, const pair<PII, PII> &b)
{
return a.fi < b.fi;
}
void update(int &x)
{
size[x] = size[cld[x][0]] + size[cld[x][1]] + cot[x];
}
void rotate(int &x, int flg)
{
int y = cld[x][flg];
cld[x][flg] = cld[y][flg ^ 1];
cld[y][flg ^ 1] = x;
update(x);
update(y);
x = y;
}
void insert(int &x, int k)
{
if(x)
{
if(key[x] == k)
{
cot[x] ++;
}
else
{
int flg = key[x] < k;
insert(cld[x][flg], k);
if (weight[cld[x][flg]] < weight[x])
{
rotate(x, flg);
}
}
}
else
{
x = treap_size ++;
key[x] = k;
weight[x] = rand();
cot[x] = 1;
cld[x][0] = cld[x][1] = 0;
}
update(x);
}
void erase (int &x, int k)
{
if(key[x] == k)
{
if(cot[x] > 1)
{
cot[x] --;
}
else
{
if(!cld[x][0] && !cld[x][1])
{
x = 0;
return;
}
rotate(x, ! (weight[cld[x][0]] < weight[cld[x][1]]));
erase(x, k);
}
}
else
{
erase(cld[x][key[x] < k], k);
}
update(x);
}
int calc(int &x, int k)
{
if(size[cld[x][0]] >= k)
{
return calc(cld[x][0], k);
}
if(k <= size[cld[x][0]] + cot[x])
{
return key[x];
}
return calc(cld[x][1], k - (size[cld[x][0]] + cot[x]));
}
void treap_init()
{
treap_size = 1;
size[0] = 0;
weight[0] = INT_MAX;
}
int main()
{
int n, m;
while(scanf("%d %d", &n, &m) == 2)
{
treap_init();
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
for(int i = 0; i < m; i ++)
{
scanf("%d %d %d", &query[i].fi.fi, &query[i].fi.nd, &query[i].nd.fi);
query[i].fi.fi --;
query[i].fi.nd --;
query[i].nd.nd = i;
}
sort(query, query + m, cmp);
int front = 0, rear = 0;
int root = 0;
for(int i = 0; i < m; i ++)
{
while(rear <= query[i].fi.nd)
{
insert(root, a[rear ++]);
}
while(front < query[i].fi.fi)
{
erase(root, a[front ++]);
}
ans[query[i].nd.nd] = calc(root, query[i].nd.fi);
}
for(int i = 0; i < m; i ++)
{
printf("%d
", ans[i]);
}
}
return 0;
}
8. 검 붉 은 나무
이 건 할 수 있어 야 돼.
근 데 정상 인 이 빨 간 검 은 나 무 를 손 으로 쓰 려 고 하 는 건 아니 겠 지?
그래서 무기한 방치.
9、SPLAY
학 교 를 기다리다.
서 두 르 지 마 세 요 > <
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
