[文章目录]
Description
给你一段长度为n的序列，给出m次操作：Q l,r,k表示查询区间[l,r]的第k大值。C i,t表示将原序列第i位改为t。
就是带修改的区间第k大值啊。
我们知道主席树求区间第k大，实际上是维护了一个前缀权值线段树，说白了等价于前缀和，然后由于前缀维护的是线段树，所以各种操作都多了个log。查询：O(logn)，修改O(nlogn)。
考虑其他维护序列的想法：
差分？？？
发现每个节点就维护一个数，查询O(nlogn),修改O(logn),（还不如暴力排序滚粗呢。。。）。
回忆起了当年解决前缀问题能将查询+修改兼容的神级操作：树状数组。
树状数组说白了就是将原序列分成n组，使得每个数出现在不到logn组里，任意的一个前缀和最多用logn组的并集表示的一种分组方法。
那么我们依然按照树状数组的分组方式在每一组维护一颗主席树。
发现每个数只在logn个主席树中被统计，每一个前缀和至多由logn个主席树的并集表示。
所以修改就可以直接修改logn个主席树O()，查询的时候，直接logn个主席树同时走，O()。
然后1A啦哈哈哈。（汗。还好有EdwardFrog提前告知天坑）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010
int n,m,a[N],b[N<<1],c[N<<1],tot,cnt;
int ql[N],qr[N],qk[N];
char st[20];
int ls[N*680],rs[N*680],sum[N*680],root[N];
void hash_id()
{
sort(b+1,b+tot+1);
int tmp=1; c[1]=b[1];
for(int i=2;i<=tot;i++)
if(b[i]!=b[i-1]) c[++tmp]=b[i];
tot=tmp;
}
int hash(int x)
{
int l=1,r=tot+1,mid;
while(l<r)
{
mid=l+r>>1;
if(c[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
void update(int l,int r,int &x,int y,int z,int w)
{
x=++cnt; sum[x]=sum[y]+w;
if(l==r) return ;
int mid=l+r>>1;
if(z<=mid) rs[x]=rs[y],update(l,mid,ls[x],ls[y],z,w);
else ls[x]=ls[y],update(mid+1,r,rs[x],rs[y],z,w);
}
void build()
{
int i,j;
for(i=1;i<=n;i++)
{
a[i]=hash(a[i]);
for(j=i;j<=n;j+=-j&j)
update(1,tot,root[j],root[j],a[i],1);
}
}
void Query(int x)
{
static int zr[30],zl[30];
int tr=0,tl=0,l,r,k=qk[x],mid,num,i;
for(r=qr[x];r>0;r-=-r&r) zr[++tr]=root[r];
for(l=ql[x]-1;l>0;l-=-l&l) zl[++tl]=root[l];
l=1,r=tot;
while(l!=r)
{
mid=l+r>>1; num=0;
for(i=1;i<=tr;i++) num+=sum[ls[zr[i]]];
for(i=1;i<=tl;i++) num-=sum[ls[zl[i]]];
if(k<=num)
{
for(i=1;i<=tr;i++) zr[i]=ls[zr[i]];
for(i=1;i<=tl;i++) zl[i]=ls[zl[i]];
r=mid;
}
else
{
k-=num;
for(i=1;i<=tr;i++) zr[i]=rs[zr[i]];
for(i=1;i<=tl;i++) zl[i]=rs[zl[i]];
l=mid+1;
}
}
printf("%d\n",c[r]);
}
void Fix(int x)
{
int w=hash(qk[x]); x=qr[x];
for(int i=x;i<=n;i+=-i&i)
{
update(1,tot,root[i],root[i],a[x],-1);
update(1,tot,root[i],root[i],w,1);
}
a[x]=w;
}
int main()
{
scanf("%d%d",&n,&m); tot=n;
for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
for(int i=1;i<=m;i++)
{
scanf("%s",st);
if(st[0]=='Q') scanf("%d%d%d",ql+i,qr+i,qk+i);
else scanf("%d%d",qr+i,qk+i),b[++tot]=qk[i];
}
hash_id(); build();
for(int i=1;i<=m;i++)
{
if(ql[i]) Query(i);
else Fix(i);
}
return 0;
}
讲真感觉内存好像可以回收的吧。。。以后有时间再研究一下。