bzoj 3110 K大数查询 整体二分
发布时间:2020-12-14 01:21:52 所属栏目:大数据 来源:网络整理
导读:#includecstdio #includeiostream #define maxn 50005 #define LL long long using namespace std; int n, m ;struct Que{ int op,l,r, x ,id; void read () { scanf( " %d %d %d %d " ,op,l,r, x ); if (op== 1 ) x +=n+ 1 ; }} q[50005] ;Que q1[maxn],q2[
#include<cstdio>
#include<iostream>
#define maxn 50005
#define LL long long
using namespace std;
int n,m;
struct Que{
int op,l,r,x,id;
void read()
{
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1) x+=n+1;
}
}q[50005];
Que q1[maxn],q2[maxn];
int ans[maxn];
struct XDS
{
struct xds
{
int l,add;
LL sum;
bool clear;
}tree[maxn<<3];
void build(int x,int l,int r)
{
tree[x].l=l;
tree[x].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(x<<1,mid);
build(x<<1|1,mid+1,r);
}
void init()
{
tree[1].sum=tree[1].add=0;
tree[1].clear=1;
}
int L,R;
int sz(int x)
{return tree[x].r-tree[x].l+1;}
void update(int x)
{tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;}
void spread(int x)
{
if(tree[x].clear)
{
// cout<<x<<endl;
tree[x<<1].sum=tree[x<<1|1].sum=0;
tree[x<<1].add=tree[x<<1|1].add=0;
tree[x<<1].clear=tree[x<<1|1].clear=1;
tree[x].clear=0;
}
if(tree[x].add)
{
tree[x<<1].add+=tree[x].add;
tree[x<<1|1].add+=tree[x].add;
tree[x<<1].sum+=(LL)tree[x].add*sz(x<<1);
tree[x<<1|1].sum+=(LL)tree[x].add*sz(x<<1|1);
tree[x].add=0;
}
}
void Add(int x)
{
if(tree[x].l>=L&&tree[x].r<=R)
{
tree[x].sum+=(LL)sz(x);
tree[x].add++;
return ;
}
spread(x);
int mid=(tree[x].l+tree[x].r)>>1;
if(mid>=L) Add(x<<1);
if(mid<R) Add(x<<1|1);
update(x);
}
LL ask(int x)
{
spread(x);
if(tree[x].l>=L&&tree[x].r<=R)
return tree[x].sum;
int mid=(tree[x].l+tree[x].r)>>1;
LL ans=0;
if(mid>=L) ans+=ask(x<<1);
if(mid<R) ans+=ask(x<<1|1);
return ans;
}
}TR;
void solve(int H,int T,int r)
{
if(H>T) return ;
if(l==r)
{
for(int i=H;i<=T;i++)
if(q[i].op==2)
ans[q[i].id]=l;
return ;
}
TR.init();
int H1=0,H2=0;
int mid=(l+r)>>1;
for(int i=H;i<=T;i++)
{
TR.L=q[i].l;
TR.R=q[i].r;
if(q[i].op==1)
{
if(q[i].x>mid)
{
TR.Add(1);
q2[++H2]=q[i];
}
else q1[++H1]=q[i];
}
else
{
LL tmp=TR.ask(1);
if(tmp<(LL)q[i].x)
{
q[i].x-=tmp;
q1[++H1]=q[i];
}
else q2[++H2]=q[i];
}
}
for(int i=1;i<=H1;i++) q[H+i-1]=q1[i];
for(int i=1;i<=H2;i++) q[H+H1+i-1]=q2[i];
solve(H,H+H1-1,mid);
solve(H+H1,T,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
q[i].read(),q[i].id=i;
TR.build(1,1,n);
solve(1,m,2*n+1);
for(int i=1;i<=m;i++)
if(ans[i]) printf("%dn",ans[i]-n-1);
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |