用主席树吊打CDQ
其实这道题是整体二分,像CDQ而已。
考虑一个询问$l_i,r_i$,只有前$i-1$个修改(把赋值当成修改)对其可能产生贡献。
那么第一维是时间,第二维是值域,第三维是位置。
第二维的意思也就是数的值,第三维是数的位置。
如果当前修改的值在值域$[l,r]$上小于等于$mid$,就意味着这个修改,会对询问产生贡献,因此在相应位置上$+1$,并将其推入值域$[l,mid]$上,继续对左半区询问产生贡献。反之则由于其大于$mid$,对于询问不会产生贡献,因此推入右区间。
那么这道题也就解决了。
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=11e4+10;
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[5050],c[N],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)
{
int mid=l+r>>1;
if(l==r){for(int i=st;i<=ed;i++)ans[q[i].op]=l;return ;}
int ls=0,rs=0;
for(int i=st;i<=ed;i++)
{
if(!q[i].op)
{
if(q[i].y<=mid)add(q[i].x,1),lq[++ls]=q[i];
else rq[++rs]=q[i];
}
else
{
int cnt=ask(q[i].y)-ask(q[i].x-1);//统计[l,r]区间‘1’的数量
if(cnt>=q[i].z)lq[++ls]=q[i];
else q[i].z-=cnt,rq[++rs]=q[i];//[q[i].x,q[i].y]有cnt个数小于mid ,减去cnt,再进入[mid+1,r]值域 ,说明这个询问的区间第k小的值大于mid
}
}
for(int i=1;i<=ls;i++)if(!lq[i].op)add(lq[i].x,-1);
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()
{
qr(n);int m;qr(m);
for(int i=1;i<=n;i++)q[i].op=0,q[i].x=i,qr(q[i].y);
for(int i=n+1;i<=n+m;i++)q[i].op=i-n,qr(q[i].x),qr(q[i].y),qr(q[i].z);
solve(-inf,inf,1,n+m);
for(int i=1;i<=m;i++)qw(ans[i]),puts("");
return 0;
}
附上一个主席树做法:
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1e5+10;
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);
}
int a[N],arr[N],n,len;
void disc()
{
sort(arr+1,arr+n+1);len=0;
for(int i=1;i<=n;i++)
if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
}
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 HGTSeg{int l,r,s;}t[N*20];int cnt,root[N];
void update(int l,int r,int &x,int y,int pos)
{
t[x=++cnt]=t[y];++t[x].s;
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);
}
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].s-t[t[y].l].s;
if(k<=sum)return query(l,mid,t[x].l,t[y].l,k);
else return query(mid+1,r,t[x].r,t[y].r,k-sum);
}
int main()
{
int m;qr(n),qr(m);
for(int i=1;i<=n;i++)qr(a[i]),arr[i]=a[i];
disc();
for(int i=1;i<=n;i++)a[i]=get(a[i]);
for(int i=1;i<=n;i++)update(1,len,root[i],root[i-1],a[i]);
for(int i=1,l,r,k;i<=m;i++)
{
qr(l),qr(r),qr(k);
qw(arr[query(1,len,root[r],root[l-1],k)]);puts("");
}
return 0;
}
最后一次更新于2019-10-13
0 条评论