1、HDU 2665
思路：主席树（离线算法）⽹上都有各种详细的解释了，就不多说了。。。主席树的核⼼思想包括前缀和、⼆分查、空间重复利⽤、转化（区间表⽰在此范围内的数的个数，即权值线段树）。时间和空间复杂度为nlogn。氰化亚金钾
代码：
#include<iostream>
西风狂诗曲2
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;石龙二中
int L[20*maxn],R[20*maxn],T[20*maxn],sum[20*maxn],a[maxn],b[maxn];
int tot;
void build(int& rt,int l,int r){///建⽴空树T[0]
rt=++tot;
sum[rt]=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(L[rt],l,mid);
build(R[rt],mid+1,r);
}
///对所有前缀更新树
void update(int& rt,int pre,int l,int r,int pos){
rt = ++tot;
L[rt]=L[pre];
R[rt]=R[pre];
sum[rt]=sum[pre]+1;
if(l==r) return ;
int mid=(l+r)/2;
if(pos<=mid) update(L[rt],L[pre],l,mid,pos);
else update(R[rt],R[pre],mid+1,r,pos);
}
///⼆分查
int query(int s,int e,int l,int r,int k){
if(l==r) return l;
int res=sum[L[e]]-sum[L[s]];
int mid=(l+r)/2;
if(k<=res) return query(L[s],L[e],l,mid,k);
else return query(R[s],R[e],mid+1,r,k-res);
}
int main(){
int t,n,m;
cin>>t;
while(t--){
tot=0;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
///离散化使⽤ sort + unique + lower_bound ⽐较⽅便 map也⾏或者⼆分查
sort(b+1,b+n+1);
int num=unique(b+1,b+n+1)-b-1;
build(T[0],1,num);
for(int i=1;i<=n;i++)
update(T[i],T[i-1],1,num,lower_bound(b+1,b+num+1,a[i])-b);///(先排序)lower_bounder函数返回第⼀个⼤于或者等于该元素的下标
while(m--) {
int s,e,k;
cin>>s>>e>>k;
int ans=query(T[s-1],T[e],1,num,k);
cout<<b[ans]<<endl;
}
}
}
2、The Preliminary Contest for ICPC Asia Nanjing 2019 F. Greedy Sequence
题意：给出n,k，然后给出⼀个长度为n的序列A，构造n个序列Si。要求Si序列的开头必须是Ai，问每个序列的长度。看第⼆组样例，A[1]=3，在前k个和后k个元素中⼀个⼩于A[1]的最⼤的数，到这个数后在这个数前k个到后k个⼩于他的最⼤的数，直到不到为⽌。 第⼆组样例构造的序列：
1
2
3 1
4 3 1
5 2
6 5 2
7 5 2
分析：从⼩到⼤答案，对于答案i开头的序列，通过主席树到[pos[i]-k,pos[i]+k]区间内⼩于i的最⼤值（pos[i]表⽰i的位置），主席树查询的时候，先贪⼼往右查询，如果往右不到，再往左，代码细节要注意。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int t,n,k,a[N],ans[N],pos[N];
int rt[N*20],ls[N*20],rs[N*20],sum[N*20],cnt=0;
void up(int pre,int& o,int l,int r,int pos) {
o=++cnt;
ls[o]=ls[pre];
rs[o]=rs[pre];
sum[o]=sum[pre]+1;
if(l==r) return ;
int m=(l+r)/2;
if(pos<=m) up(ls[pre],ls[o],l,m,pos);
else up(rs[pre],rs[o],m+1,r,pos);
}
int qu(int pre,int o,int l,int r,int kk) {
if(l==r) {
if(l>kk) return -1;
return l;
}
int m=(l+r)/2;
if(kk>m && sum[rs[o]]-sum[rs[pre]]) {
int ans = qu(rs[pre],rs[o],m+1,r,kk);
if(ans==-1) {
if(kk>=l && sum[ls[o]]-sum[ls[pre]])
return qu(ls[pre],ls[o],l,m,kk);
return -1;
}else return ans;
}
if(kk>=l && sum[ls[o]]-sum[ls[pre]])
return qu(ls[pre],ls[o],l,m,kk);
return -1;
}
int main(){
scanf("%d",&t);
while(t--) {
cnt = 0;
网络视听节目内容审核通则scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
pos[a[i]]=i;
up(rt[i-1],rt[i],1,n,a[i]);
}
for(int i=1;i<=n;i++) {
int l=max(1,pos[i]-k),r=min(n,pos[i]+k);
int s1=qu(rt[l-1],rt[pos[i]-1],1,n,i-1);
int s2=qu(rt[pos[i]],rt[r],1,n,i-1);
int res = max(s1,s2);
if(res==-1) ans[i] = 1;
else ans[i] = ans[res]+1;
}
for(int i=1;i<n;i++) printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return 0;
}
3、洛⾕ P2617 Dynamic Rankings
题意：动态区间第k⼤。
分析：树套树，树状数组+主席树，纯模板。
代码（纯模板）：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100007;
鼻咽int n, m, num, n1, n2;
int a[N], b[N << 1], c[N], d[N], e[N], t1[N], t2[N];
int Top, Root[N], val[N * 400], ls[N * 400], rs[N * 400];
inline int lowbit(int x) {
return x & (-x);
}
void Add(int &rt, int l, int r, int ind, int c) {
if (!rt) rt = ++Top;
val[rt] += c;
if (l == r) return;
int m = (l + r) >> 1;
if (ind <= m) Add(ls[rt], l, m, ind, c);
else Add(rs[rt], m+1, r, ind, c);
}
void Change(int ind, int val) {
妇女病普查工作总结int x = lower_bound(b + 1, b + 1 + num, a[ind]) - b;
for (int i = ind; i <= n; i += lowbit(i))
Add(Root[i], 1, num, x, val);
}
int Kth(int l, int r, int k) { ///求第 k ⼤
if (l == r) return l;
int m = (l + r) >> 1, sum = 0;
for (int i = 1; i <= n2; ++i)
sum += val[ls[t2[i]]];
for (int i = 1; i <= n1; ++i)
sum -= val[ls[t1[i]]];
if (sum >= k) {
for (int i = 1; i <= n1; ++i) ///所有树的节点保持对应
t1[i] = ls[t1[i]];
for (int i = 1; i <= n2; ++i)
t2[i] = ls[t2[i]];
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议