BZOJ 3110: [Zjoi2013]K大数查询|线段树套线段树
发布时间:2020-12-14 02:02:55 所属栏目:大数据 来源:网络整理
导读:这个题貌似有很多姿势都可以做。 我用的是线段树套线段树。 因为存在区间插入操作,所以我们可以让外层的线段树为权值线段树,内层的线段树为这个权值区间的数在原序列中的位置数量。 这样插入操作就相当于外层的线段树单点修改,内层的区间修改。 然后由于
这个题貌似有很多姿势都可以做。 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<iostream>
#define N 50050
#define M 7000001
using namespace std;
int sc()
{
int i=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
return i*f;
}
int ch[M][2],sum[M],tag[M];
int root[N*8],n,m,cnt;
void add(int &x,int L,int R,int l,int r)
{
if(!x)x=++cnt;
sum[x]+=r-l+1;
if(L==l&&R==r)
{
tag[x]++;
return;
}
int mid=L+R>>1;
if(r<=mid) add(ch[x][0],L,mid,l,r);
else if(l>mid) add(ch[x][1],mid+1,R,r);
else add(ch[x][0],mid),add(ch[x][1],r);
}
void insert(int x,int r,int f)
{
add(root[x],1,r);
if(L==R)return;
int mid=L+R>>1;
if(f<=mid)insert(x<<1,r,f);
else insert(x<<1|1,f);
}
int ask(int x,int a)
{
if(L==l&&R==r)return sum[x]+(r-l+1)*a;
int mid=L+R>>1;
if(r<=mid)return ask(ch[x][0],a+tag[x]);
else if(l>mid)return ask(ch[x][1],a+tag[x]);
else return ask(ch[x][0],a+tag[x])+ask(ch[x][1],a+tag[x]);
}
int query(int l,int f)
{
int x=1,L=1,R=n;
while(L!=R)
{
int sum=ask(root[x<<1|1],0);
int mid=L+R>>1;
if(f<=sum)
x=x<<1|1,L=mid+1;
else
x=x<<1,R=mid,f-=sum;
}
return L;
}
int main()
{
n=sc(),m=sc();
for(int i=1;i<=m;i++)
{
int opt=sc();
if(opt==1)
{
int l=sc(),r=sc(),x=sc();
insert(1,x);
}
else
{
int l=sc(),x=sc();
printf("%dn",query(l,x));
}
}
return 0;
}
第二种方法,2000W数组,12+s #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<iostream>
#define N 50050
#define M 20000001
using namespace std;
int sc()
{
int i=0,cnt;
void push_down(int x,int R)
{
if(L==R)return;
if(!ch[x][0])ch[x][0]=++cnt;
if(!ch[x][1])ch[x][1]=++cnt;
int l=ch[x][0],r=ch[x][1],mid=R+L>>1;
tag[l]+=tag[x];
tag[r]+=tag[x];
sum[l]+=tag[x]*(mid-L+1);
sum[r]+=tag[x]*(R-mid);
tag[x]=0;
}
void add(int &x,int r)
{
//if(tag[x])push_down(x,R);可有可无
if(!x)x=++cnt;
sum[x]+=r-l+1;
if(L==l&&R==r)
{
tag[x]+=1;
return;
}
int mid=L+R>>1;
if(r<=mid) add(ch[x][0],int r)
{
if(tag[x])push_down(x,R);
if(L==l&&R==r)return sum[x];
int mid=L+R>>1;
if(r<=mid)return ask(ch[x][0],r);
else if(l>mid)return ask(ch[x][1],r);
else return ask(ch[x][0],mid)+ask(ch[x][1],r);
}
int query(int l,r);
int mid=L+R>>1;
if(f<=sum)
x=x<<1|1,x));
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |