3110: [Zjoi2013]K大数查询

发布时间：2020-12-14 04:54:01 所属栏目：大数据来源：网络整理

导读：题目大意，带该段的区间第k大。注意，一个位置上可以有多个数的，更改操作是增加新数，而不是覆盖。备用知识：标记永久化点击打开链接（不用的话应该也可以，但空间会大）然后就上权值线段树套区间线段树。不修改的区间第k小是例题（类似二分），树套树

题目大意，带该段的区间第k大。

注意，一个位置上可以有多个数的，更改操作是增加新数，而不是覆盖。

备用知识：标记永久化点击打开链接（不用的话应该也可以，但空间会大）

然后就上权值线段树套区间线段树。

不修改的区间第k小是例题（类似二分），树套树可以解决修改的问题。

我们可以c+n+1转正，然后把求区间第k大变成（len-k+1）小。

答案再减回来就行了。

要用long long

code：

[cpp]? 
      view plain 
      ?copy 
      
 #include<cstdio>??
 #include<cstdlib>??
 #include<cstring>??
 #include<iostream>??
 #define?LL?long?long??
 using?namespace?std;??
 int?n,m,N;??
struct?node{??
 ????int?lc,rc;??
 ????LL?c,u;??
 }tr[20200010];int?trlen=0,root[200010];??
void?update(int?&x,int?l,87); font-weight:bold; background-color:inherit">int?r,87); font-weight:bold; background-color:inherit">int?fl,87); font-weight:bold; background-color:inherit">int?fr,LL?c)??
 {??
 ????if(!x)?x=++trlen;??
 ????if(l==fl&&r==fr){tr[x].u+=c;tr[x].c+=c*(r-l+1);return;}??
 ????int?mid=(l+r)/2;??
if(fr<=mid)?update(tr[x].lc,l,mid,fl,fr,c);??
else?if(fl>mid)?update(tr[x].rc,mid+1,r,c);??
else?update(tr[x].lc,c),update(tr[x].rc,248)"> ????tr[x].c=tr[tr[x].lc].c+tr[tr[x].rc].c+(r-l+1)*tr[x].u;??
 }??
 LL?findans(int?x,LL?u)??
if(!x)?return?u*(LL)(fr-fl+1);??
if(l==fl&&fr==r)?return?tr[x].c+(LL)(r-l+1)*u;??
if(fr<=mid)?return?findans(tr[x].lc,u+tr[x].u);??
if(fl>mid)?return?findans(tr[x].rc,u+tr[x].u);??
 }??
int?bt(int?r)??
 {??
int?x=++trlen;??
if(l!=r)??
 ????{??
 ???????? ????????tr[x].lc=bt(l,mid);??
 ????????tr[x].rc=bt(mid+1,r);??
 ????}??
return?x;??
void?change(int?k,248)"> ????update(root[x],1,n,c);??
if(l==r)?return;??
if(k<=mid)?change(tr[x].lc,k,153); font-weight:bold; background-color:inherit">else?change(tr[x].rc,248)"> int?solve(return?l;??
int?mid=(l+r)/2;LL?sum=findans(root[tr[x].lc],0LL);??
if(k<=sum)?return?solve(tr[x].lc,k);??
return?solve(tr[x].rc,k-sum);??
int?findnum( ????LL?k=(findans(root[1],0)-c+1);??
if(k<=0)?k=1;??
return?solve(1,N,k)-n-1;??
int?main()??
 ????scanf("%d?%d",&n,&m);??
 ????N=2*n+1;bt(1,N);??
for(int?i=1;i<=m;i++)??
 ????{??
 ????????int?tmp,x,y,c;scanf("%d?%d?%d?%d",&tmp,&x,&y,&c);??
 ????????if(tmp==1)?change(1,c+n+1,1LL);??
 ????????else?printf("%dn",findnum(x,(LL)c));??
 ????}??
 }??

数据生成器：

copy

#include<ctime>??

#include<iostream>??
#define?LL?long?long??
namespace?std;??
}tr[400010];int?trlen=0;??
if(!x)?x=++trlen;??
return;}??
int?mid=(l+r)/2;??
????tr[x].c=tr[tr[x].lc].c+tr[tr[x].rc].c+(r-l+1)*tr[x].u;??
LL?findans(return?u*(LL)(fr-fl+1);??
return?tr[x].c+(LL)(r-l+1)*u;??
int?main()??
????srand(time(0));??
int?n=7000,m=5000;??
????printf("%d?%dn",m);??
int?l=rand()%n+1,r=rand()%n+1,c=(rand()%9000-rand()%9000)%n;??
if(l>r)?swap(l,r);??
int?tmp=rand()%2+1;??
if(tmp==1)?update(root,153); font-weight:bold; background-color:inherit">else??
????????{??
????????????LL?TMP=findans(root,0);??
????????????if(TMP==0)?tmp=1;??
????????????else?c=rand()%TMP+1;??
????????}??
????????printf("%d?%d?%d?%dn",tmp,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> } ?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!