【ZJOI2013】bzoj3110 K大数查询【解法一】
发布时间:2020-12-14 03:16:47 所属栏目:大数据 来源:网络整理
导读:Description 有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。 Input 第一行N,M 接下来M行,每行形如1 a b c或2 a b
整体二分做法见【这里】。 #include<cstdio>
#include<algorithm>
using namespace std;
int rd()
{
int x=0,f=1;
char c=getchar();
while (c<'0'||c>'9')
{
if (c=='-') f=-1;
c=getchar();
}
while (c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
unsigned int rdu()
{
unsigned int x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
unsigned int sum[25000010],tag[25000010],K[50010];
int root[25000010],son[25000010][2],opt[50010],L[50010],R[50010],tem[50010],ord[50010],n,m,q,clo;
void down(int p,int L,int R)
{
if (tag[p])
{
sum[p]+=tag[p]*(R-L+1);
if (L==R)
{
tag[p]=0;
return;
}
if (!son[p][0]) son[p][0]=++clo;
tag[son[p][0]]+=tag[p];
if (!son[p][1]) son[p][1]=++clo;
tag[son[p][1]]+=tag[p];
tag[p]=0;
}
}
void up(int p,int R)
{
sum[p]=0;
int mid=L+R>>1;
if (son[p][0])
{
down(son[p][0],L,mid);
sum[p]+=sum[son[p][0]];
}
if (son[p][1])
{
down(son[p][1],mid+1,R);
sum[p]+=sum[son[p][1]];
}
}
void modify(int &p,int R,int l,int r)
{
if (!p) p=++clo;
down(p,R);
if (l<=L&&R<=r)
{
tag[p]++;
down(p,R);
return;
}
int mid=L+R>>1;
if (l<=mid) modify(son[p][0],mid,l,r);
if (r>mid) modify(son[p][1],R,r);
up(p,R);
}
void Modify(int p,int x,int r)
{
modify(root[p],1,r);
if (L==R) return;
int mid=L+R>>1;
if (x<=mid) Modify(p<<1,x,r);
else Modify(p<<1|1,r);
}
unsigned int query(int p,int r)
{
if (!p) return 0;
down(p,R);
if (l<=L&&R<=r) return sum[p];
int mid=L+R>>1;
unsigned int ret=0;
if (l<=mid) ret+=query(son[p][0],r);
if (r>mid) ret+=query(son[p][1],r);
return ret;
}
int Query(int p,unsigned int x,int r)
{
if (L==R) return L;
int mid=L+R>>1;
unsigned int y=query(root[p<<1|1],r);
if (y>=x) return Query(p<<1|1,r);
return Query(p<<1,x-y,r);
}
int main()
{
/*freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);*/
n=rd();
q=rd();
for (int i=1;i<=q;i++)
{
opt[i]=rd();
L[i]=rd();
R[i]=rd();
if (opt[i]==1) tem[i]=ord[++m]=rd();
else K[i]=rdu();
}
sort(ord+1,ord+m+1);
m=unique(ord+1,ord+m+1)-ord-1;
for (int i=1;i<=q;i++)
if (opt[i]==1)
K[i]=lower_bound(ord+1,ord+m+1,tem[i])-ord;
for (int i=1;i<=q;i++)
if (opt[i]==1)
Modify(1,K[i],L[i],R[i]);
else
printf("%dn",ord[Query(1,R[i])]);
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |