3110: [Zjoi2013]K大数查询
发布时间:2020-12-14 03:25:40 所属栏目:大数据 来源:网络整理
导读:题目大意,带该段的区间第k大。 注意,一个位置上可以有多个数的,更改操作是增加新数,而不是覆盖。 备用知识:标记永久化点击打开链接(不用的话应该也可以,但空间会大) 然后就上权值线段树套区间线段树。 不修改的区间第k小是例题(类似二分),树套树
题目大意,带该段的区间第k大。 注意,一个位置上可以有多个数的,更改操作是增加新数,而不是覆盖。 备用知识:标记永久化点击打开链接(不用的话应该也可以,但空间会大) 然后就上权值线段树套区间线段树。 不修改的区间第k小是例题(类似二分),树套树可以解决修改的问题。 我们可以c+n+1转正,然后把求区间第k大变成(len-k+1)小。 答案再减回来就行了。 要用long long code: #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,int r,int fl,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,c); 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; int mid=(l+r)/2; if(fr<=mid) return findans(tr[x].lc,u+tr[x].u); if(fl>mid) return findans(tr[x].rc,u+tr[x].u); return findans(tr[x].lc,u+tr[x].u)+findans(tr[x].rc,u+tr[x].u); } int bt(int l,int r) { int x=++trlen; if(l!=r) { int mid=(l+r)/2; tr[x].lc=bt(l,mid); tr[x].rc=bt(mid+1,r); } return x; } void change(int x,int k,LL c) { update(root[x],1,n,c); if(l==r) return; int mid=(l+r)/2; if(k<=mid) change(tr[x].lc,k,c); else change(tr[x].rc,c); } int solve(int x,LL k) { if(l==r) return l; int mid=(l+r)/2;LL sum=findans(root[tr[x].lc],0LL); if(k<=sum) return solve(tr[x].lc,k); else return solve(tr[x].rc,k-sum); } int findnum(int l,LL c) { 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)); } } 数据生成器: #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iostream> #define LL long long using namespace std; struct node{ int lc,rc; LL c,u; }tr[400010];int trlen=0; int n,root=0; void update(int &x,u+tr[x].u); } int main() { srand(time(0)); int n=7000,m=5000; printf("%d %dn",m); for(int i=1;i<=m;i++) { 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,1LL); else { LL TMP=findans(root,0); if(TMP==0) tmp=1; else c=rand()%TMP+1; } printf("%d %d %d %dn",tmp,c); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |