主席树
暂时小结
1.查询区间有多少个不同的数//可以用树状数组，线段树，莫队算法
3.动态求区间的第k大//全部修改后查询 //修改同时查询
4.查询某区间比指定的数大的个数//小的个数
5.数上路径点权第k大
静态区间第k大
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn =200010;
int n, m;
int cnt;
struct node//存树
{
int L, R;//分别指向左右子树
int sum;//该节点所管辖区间范围内数的个数
}Tree[maxn * 20];
struct value//值 //离散化
{
int x;//值的大小
int id;//离散之前在原数组中的位置
} Value[maxn];
bool cmp(value v1, value v2)//排序从到小
{
return v1.x < v2.x;
}
int root[maxn];//多颗线段树的根节点
int yy[maxn];//原数组离散之后的数组
void update(int num, int &rt, int l, int r)
{
Tree[cnt++] = Tree[rt];
rt = cnt - 1;
Tree[rt].sum++;
if(l == r) return;
int mid = (l + r)>>1;
if(num <= mid)
update(num,Tree[rt].L,l,mid);
else
update(num,Tree[rt].R,mid+1,r);
}
int query(int i,int j,int k,int l,int r)
{
int d=Tree[Tree[j].L].sum-Tree[Tree[i].L].sum;
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=d)
return query(Tree[i].L,Tree[j].L,k,l,mid);
else return query(Tree[i].R, Tree[j].R,k-d,mid+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%d",&Value[i].x);
Value[i].id=i;
}
//进行离散化
sort(Value + 1,Value+n+1, cmp);
for(int i=1; i<=n; i++)
{
yy[Value[i].id]=i;
}
// init();//初始化
cnt=1;
for(int i=1; i<=n; i++)
{
root[i]=root[i - 1];
update(yy[i],root[i],1,n);
}
int left, right,k;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &left, &right, &k);
printf("%d\n", Value[query(root[left - 1], root[right], k, 1, n)].x);
}
return 0;
}
数组形式 静态区间第k大
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int MM=200010;
int node,n,m;
int sum[MM*5],rt[MM],lc[MM*5],rc[MM*5];
int a[MM],b[MM];
int p;
void build(int &t,int l,int r)//建树
{
t=++node;
if(l==r)
return;
int mid=((l+r)>>1);
build(lc[t],l,mid);
build(rc[t],mid+1,r);
}
int update(int o,int l,int r)//更新
{
int rt=++node;
lc[rt]=lc[o];
rc[rt]=rc[o];
sum[rt]=sum[o]+1;
if(l==r)
return rt;
int mid=((l+r)>>1);
if(p<=mid)
lc[rt]=update(lc[rt],l,mid);
else
rc[rt]=update(rc[rt],mid+1,r);
return rt;
}
int query(int u,int v,int l,int r,int k)//查询
{
int ans,mid=((l+r)>>1),x=sum[lc[v]]-sum[lc[u]];//前缀和
if(l==r)
return l;
if(x>=k)//说明在左子树
ans=query(lc[u],lc[v],l,mid,k);//
else
ans=query(rc[u],rc[v],mid+1,r,k-x);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);//离散化
int q=unique(b+1,b+n+1)-b-1;//
build(rt[0],1,q);
for(register int i=1; i<=n; i++)
{
p=lower_bound(b+1,b+q+1,a[i])-b;//二分
rt[i]=rt[i-1];
rt[i]=update(rt[i],1,q);
}
int l,r,k,ans;
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
ans=query(rt[l-1],rt[r],1,q,k);
printf("%d\n",b[ans]);
}
return 0;
}
//动态求第k大的值（ZO2112)
Q查询
C改变第i个的值为val
树状数组套主席树
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 6e4+5;
const int maxm = 1e4+5;
int T[maxn],S[maxn],L[maxn*32],R[maxn*32],sum[maxn*32];
/*n是原序列个数 T[i]表示第i棵线段树的根节点编号 S[i]表示树状数组思维建的第i棵线段树的根节点编号 L[i]表示节点i的左子节点编号 R[i]表示节点i的右子节点编号 sum[i]表示节点i对应区间中数的个数。*/
char str[60];
int sz[maxn],h[maxn];
int ul[maxn],ur[maxn];
int tot,num,n,q;
struct node
{
int l,r,k;
bool flag; //ture代表Q，false代表C
} Q[maxm*4]; //存储询问
void build(int& rt,int l,int r)//建树
{
rt = ++tot;
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 x,int val)//更新
{
rt = ++tot;
L[rt] = L[pre];
R[rt] = R[pre];
sum[rt] = sum[pre]+val;//加val
if(l==r)
return;
int mid =(l+r)>>1;
if(x<=mid)
update(L[rt],L[pre],l,mid,x,val);
else
update(R[rt],R[pre],mid+1,r,x,val);
}
int lowbit(int x)//树状数组
{
return x&(-x);
}
void add(int x,int val)
{
int res = lower_bound(h+1,h+1+num,sz[x])-h;//
while(x<=n)
{
update(S[x],S[x],1,num,res,val);
x += lowbit(x);
}
}
int Sum(int x,bool flag)
{
int res=0;
while(x>0)
{
if(flag) res += sum[L[ur[x]]];//
else res += sum[L[ul[x]]];
x -= lowbit(x);
}
return res;
}
int query(int s,int e,int ts,int te,int l,int r,int k)
{
if(l==r) return l;
int mid = (l+r)>>1;
int res = Sum(e,true)-Sum(s,false)+sum[L[te]]-sum[L[ts]];//前缀和
if(k<=res)
{
for(int i=e; i; i-=lowbit(i))
ur[i] = L[ur[i]];
for(int i=s; i; i-=lowbit(i))
ul[i] = L[ul[i]];
return query(s,e,L[ts],L[te],l,mid,k);
}
else
{
for(int i=e; i; i-=lowbit(i))
ur[i] = R[ur[i]];
for(int i=s; i; i-=lowbit(i))
ul[i] = R[ul[i]];
return query(s,e,R[ts],R[te],mid+1,r,k-res);
}
}
//树状数组 前缀和
int main()
{
int yy;
scanf("%d",&yy);
while(yy--)
{
scanf("%d%d",&n,&q);
num=0;
for(int i=1; i<=n; i++)
scanf("%d",sz+i),h[++num]=sz[i];
for(int i=1; i<=q; i++)
{
scanf("%s",str);
if(str[0]=='Q')//查询
{
scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
Q[i].flag=true;
}
else
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].flag=false;
h[++num]=Q[i].r;
}
}
sort(h+1,h+1+num);
int tmp = unique(h+1,h+1+num)-h-1;//离散化
num = tmp;
tot=0;
build(T[0],1,num);
for(int i=1; i<=n; i++)
{
update(T[i],T[i-1],1,num,lower_bound(h+1,h+1+num,sz[i])-h,1);
}
for(int i=1; i<=n; i++)
S[i] = T[0];
for(int i=1; i<=q; i++)
{
if(Q[i].flag)//查找
{
for(int j=Q[i].r; j; j-=lowbit(j))
ur[j] = S[j];
for(int j=Q[i].l-1; j; j-=lowbit(j))
ul[j] = S[j];
printf("%d\n",h[query(Q[i].l-1,Q[i].r,T[Q[i].l-1],T[Q[i].r],1,num,Q[i].k)]);
}
else//改变
{
add(Q[i].l,-1);
sz[Q[i].l] = Q[i].r;
add(Q[i].l,1);
}
}
}
return 0;
}
京公网安备 11010502036488号