NC20507. [ZJOI2013]K大数查询
描述
输入描述
第一行N，M 接下来M行，每行形如1 a b c或2 a b c
输出描述
输出每个询问的结果
示例1
输入:
2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3
输出:
1 2 1
说明:
第1次操作在1,2号集合中分别加入了一个1。C++14(g++5.4) 解法, 执行用时: 603ms, 内存消耗: 76940K, 提交时间: 2019-08-09 17:42:07
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
int root[100005],lc[17000005],rc[17000005],opt[50005],a[50005],b[50005],n,m,cnt,tot,cntn;
int rt,cntt,son[100005][2],lazy[17000005];
long long size[17000005],c[50005],tmp[50005];
inline long long read()
{
long long x=0,f=1;char c=getchar();
for(;c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
return x*f;
}
void seg_insert(int &now,int l,int r,int L,int R)
{
if(!now)now=++cntn;
size[now]+=std::min(R,r)-std::max(L,l)+1;
if(l>=L&&r<=R)
{
lazy[now]++;
return;
}
if(L<=l+r>>1)seg_insert(lc[now],l,l+r>>1,L,R);
if(R>l+r>>1)seg_insert(rc[now],l+r+2>>1,r,L,R);
}
long long seg_query(int now,int l,int r,int L,int R)
{
if(!now)return 0;
if(l>=L&&r<=R)return size[now];
long long sum=lazy[now]*(std::min(R,r)-std::max(L,l)+1);
if(L<=l+r>>1)sum+=seg_query(lc[now],l,l+r>>1,L,R);
if(R>l+r>>1)sum+=seg_query(rc[now],l+r+2>>1,r,L,R);
return sum;
}
void insert(int &now,int l,int r,int k,int L,int R)
{
if(!now)now=++cntt;
seg_insert(root[now],1,n,L,R);
if(l==r)return;
if(k>l+r>>1)insert(son[now][1],l+r+2>>1,r,k,L,R);
else insert(son[now][0],l,l+r>>1,k,L,R);
}
long long query(int now,int l,int r,long long k,int L,int R)
{
if(!now)return 0;
if(l==r)return l;
long long kk=seg_query(root[son[now][0]],1,n,L,R);
if(k<=kk)return query(son[now][0],l,l+r>>1,k,L,R);
else return query(son[now][1],l+r+2>>1,r,k-kk,L,R);
}
inline void work()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
opt[i]=read(),a[i]=read(),b[i]=read(),c[i]=read();
if(opt[i]==1)tmp[++cnt]=-c[i];
}
std::sort(tmp+1,tmp+cnt+1);tot=std::unique(tmp+1,tmp+cnt+1)-tmp-1;tmp[tot+1]=1e18;
for(int i=1;i<=m;i++)
if(opt[i]&1)
{
c[i]=std::lower_bound(tmp+1,tmp+tot+1,-c[i])-tmp;
insert(rt,1,tot,c[i],a[i],b[i]);
}
else printf("%lld\n",-tmp[query(rt,1,tot,c[i],a[i],b[i])]);
}
int main()
{
work();
return 0;
}
C++ 解法, 执行用时: 764ms, 内存消耗: 117112K, 提交时间: 2022-06-24 10:16:22
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
const long long LIM=1e18;
const int INF=0x3f3f3f3f;
const double eps=1e-4;
const double PI=atan(1.0)*4;
const int mod=1e9+7;
int n,m,tot;
long long opt,a,b,c;
int rt[N<<2],ls[N*200],rs[N*200];
long long sum[N*200],lazy[N*200];
void updatey(int& x,int l,int r,int L,int R){
if(!x)x=++tot;
if(L<=l && r<=R){
lazy[x]++;
sum[x]+=(r-l+1);
return;
}
int mid=(l+r)/2;
if(L<=mid)updatey(ls[x],l,mid,L,R);
if(R>mid)updatey(rs[x],mid+1,r,L,R);
sum[x]+=(min(R,r)-max(L,l)+1);
}
void updatex(int x,int l,int r,int L,int R,int pos){
updatey(rt[x],1,n,L,R);
if(l==r)return;
int mid=(l+r)/2;
if(pos<=mid)updatex(x<<1,l,mid,L,R,pos);
else updatex(x<<1|1,mid+1,r,L,R,pos);
}
long long queryy(int x,int l,int r,int L,int R){
if(L<=l && r<=R)return sum[x];
int mid=(l+r)/2;
long long v=0;
if(L<=mid)v+=queryy(ls[x],l,mid,L,R);
if(R>mid)v+=queryy(rs[x],mid+1,r,L,R);
return v+1LL*lazy[x]*(min(r,R)-max(L,l)+1);
}
int queryx(int x,int l,int r,int L,int R,long long v){
if(l==r)return l;
int mid=(l+r)/2;
long long res=queryy(rt[x<<1|1],1,n,L,R);
if(res>=v)return queryx(x<<1|1,mid+1,r,L,R,v);
return queryx(x<<1,l,mid,L,R,v-res);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
while(m--){
cin>>opt>>a>>b>>c;
if(opt==1)updatex(1,1,n,a,b,c);
else cout<<queryx(1,1,n,a,b,c)<<"\n";
}
return 0;
}