和不带修的没啥区别,就把数换一换就好了。
#include<cstdio>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=7e4+5;
const int inf=1e9+5;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node{int op,x,y,z;}q[N],lq[N],rq[N];
int ans[N],c[N],n,a[N];
inline void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
/*
若修改操作在查询操作前,那么入队时,修改操作在查询操作前
若查询操作在修改操作前,则没有影响
*/
void solve(int l,int r,int st,int ed)
{
if(l==r){for(int i=st;i<=ed;i++)if(q[i].op>0)ans[q[i].op]=l;return ;}
int mid=l+r>>1,ls=0,rs=0;
for(int i=st;i<=ed;i++)
{
if(q[i].op<=0)
{
if(q[i].y<=mid)add(q[i].x,q[i].z),lq[++ls]=q[i];
else rq[++rs]=q[i];
}
else
{
int cnt=ask(q[i].y)-ask(q[i].x-1);
if(cnt>=q[i].z)lq[++ls]=q[i];
else q[i].z-=cnt,rq[++rs]=q[i];
}
}
for(int i=1;i<=ls;i++)if(lq[i].op<=0)add(lq[i].x,-lq[i].z);
for(int i=1;i<=ls;i++)q[st+i-1]=lq[i];
for(int i=1;i<=rs;i++)q[st+i+ls-1]=rq[i];//按值域排
if(ls)solve(l,mid,st,st+ls-1);
if(rs)solve(mid+1,r,st+ls,ed);
}
int main()
{
int T;qr(T);
while(T--)
{
int m;qr(n),qr(m);
for(int i=1;i<=n;i++)
{
q[i].op=0,q[i].z=1,q[i].x=i;qr(q[i].y);
a[i]=q[i].y;
}
int t=0,sz=n;
for(int i=n+1;i<=n+m;i++)
{
char op[3];scanf("%s",op);
if(op[0]=='Q')q[++sz].op=++t,qr(q[sz].x),qr(q[sz].y),qr(q[sz].z);
else
{
q[++sz].op=-1,qr(q[sz].x),q[sz].y=a[q[sz].x],q[sz].z=-1;
q[++sz].op=0,qr(q[sz].y),q[sz].x=q[sz-1].x,q[sz].z=1;
a[q[sz].x]=q[sz].y;
}
}
solve(-inf,inf,1,sz);
for(int i=1;i<=t;i++)qw(ans[i]),puts("");
}
return 0;
}
主席树做法:
开个树状数组记录增减信息就好了。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=6e4+5;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node{int op,l,r,k;}q[N];
int a[N],arr[N],n,len,b[N];
void disc()
{
sort(arr+1,arr+len+1);int sz=0;
for(int i=1;i<=len;i++)
if(i==1||arr[i]!=arr[i-1])arr[++sz]=arr[i];
len=sz;
}
inline int get(int d)
{
int l=1,r=len;
while(l<r)
{
int mid=l+r>>1;
if(arr[mid]<d)l=mid+1;
else r=mid;
}
return l;
}
struct HJTSeg{int l,r,sum;}t[N*50];int cnt,root[N];
int c[N],c1[N],c2[N],l1,l2;
void update(int l,int r,int &x,int y,int pos)
{
t[x=++cnt]=t[y];++t[x].sum;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
else update(mid+1,r,t[x].r,t[y].r,pos);
}
void change(int l,int r,int &x,int pos,int ad)
{
if(!x)x=++cnt,t[x]=(HJTSeg){0,0,0};
t[x].sum+=ad;
if(l==r)return ;
int mid=l+r>>1;
if(pos<=mid)change(l,mid,t[x].l,pos,ad);
else change(mid+1,r,t[x].r,pos,ad);
}
void change(int k,int val)
{
int x=a[k],y=get(val);a[k]=y;
for(;k<=n;k+=k&-k)change(1,len,c[k],x,-1),change(1,len,c[k],y,1);
}
int query(int l,int r,int x,int y,int k)
{
if(l==r)return l;
int mid=l+r>>1,sum=t[t[x].l].sum-t[t[y].l].sum;
for(int i=1;i<=l1;i++)sum+=t[t[c1[i]].l].sum;
for(int i=1;i<=l2;i++)sum-=t[t[c2[i]].l].sum;
if(sum>=k)
{
for(int i=1;i<=l1;i++)c1[i]=t[c1[i]].l;
for(int i=1;i<=l2;i++)c2[i]=t[c2[i]].l;
return query(l,mid,t[x].l,t[y].l,k);
}
else
{
for(int i=1;i<=l1;i++)c1[i]=t[c1[i]].r;
for(int i=1;i<=l2;i++)c2[i]=t[c2[i]].r;
return query(mid+1,r,t[x].r,t[y].r,k-sum);
}
}
void query(int l,int r,int k)
{
l1=l2=0;
for(int i=r;i;i-=i&-i)if(c[i])c1[++l1]=c[i];
for(int i=l-1;i;i-=i&-i)if(c[i])c2[++l2]=c[i];
int ans=query(1,len,root[r],root[l-1],k);
qw(arr[ans]);puts("");
}
int main()
{
//freopen("a.in","r",stdin);
int T;qr(T);
while(T--)
{
qr(n);int m;qr(m);memset(c,0,sizeof(c));
root[0]=0;
for(int i=1;i<=n;i++)qr(a[i]),arr[i]=a[i];
len=n;cnt=0;
for(int i=1;i<=m;i++)
{
char op[3];scanf("%s",op);
if(op[0]=='Q')q[i].op=1,qr(q[i].l),qr(q[i].r),qr(q[i].k);
else q[i].op=2,qr(q[i].l),qr(q[i].r),arr[++len]=q[i].r;
}
if(T==0)
T--,++T;
disc();
for(int i=1;i<=n;i++)
{
a[i]=get(a[i]);
update(1,len,root[i],root[i-1],a[i]);
}
for(int i=1;i<=m;i++)
{
if(q[i].op==1)query(q[i].l,q[i].r,q[i].k);
else change(q[i].l,q[i].r);
}
}
return 0;
}
最后一次更新于2019-10-13
0 条评论