本文主要是介绍【bzoj 3110】[Zjoi2013]K大数查询|树套树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
开始打算自己yy写了半天 弃疗
采用权值线段树套主席树
BZOJ没A 数据被加强 各种无果后 弃疗
UPD 3.16： 要来了数据 负数的没问题 。。。
tmd 居然真给 MAX_LONG_INT
吓死我 改LL TLE
又改 卡时过 被fqk大爷无情嘲讽
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 50010
int n,m;
struct H
{int sum;int mark;int L,R;
}seg[MAXN*600];
int tot=0;
int root[MAXN*2*40];void Pushdown(int now,int l,int r)
{if(seg[now].mark==0||l==r) return ;int mid=(l+r)/2;if(seg[now].L==0) seg[now].L=++tot;{seg[seg[now].L].sum+=(mid-l+1)*seg[now].mark;seg[seg[now].L].mark+=seg[now].mark;}if(seg[now].R==0) seg[now].R=++tot;{seg[seg[now].R].sum+=(r-mid)*seg[now].mark;seg[seg[now].R].mark+=seg[now].mark;}seg[now].mark=0;
}void Add2(int now,int l,int r,int a,int b)
{if(a<=l&&r<=b){seg[now].mark+=1;seg[now].sum+=(r-l+1);return ;}Pushdown(now,l,r);int mid=(l+r)/2;if(a<=mid){if(seg[now].L==0) seg[now].L=++tot;Add2(seg[now].L,l,mid,a,b);}if(mid+1<=b){if(seg[now].R==0) seg[now].R=++tot;Add2(seg[now].R,mid+1,r,a,b);}seg[now].sum=seg[seg[now].L].sum + seg[seg[now].R].sum;
}void Add1(int now,int l,int r,int a,int b,int c)
{if(root[now]==0) root[now]=++tot;Add2(root[now],1,n,a,b);if(l==r) return ;int mid=(l+r)/2;if(c<=mid) Add1(now*2,l,mid,a,b,c);else Add1(now*2+1,mid+1,r,a,b,c);
}int Q2(int now,int l,int r,int a,int b)
{if(now==0) return 0;if(a<=l&&r<=b){return seg[now].sum;}Pushdown(now,l,r);int mid=(l+r)/2;int sum=0;if(a<=mid) sum+=Q2(seg[now].L,l,mid,a,b);if(mid+1<=b) sum+=Q2(seg[now].R,mid+1,r,a,b);return sum;
}int Q1(int now,int l,int r,int s,int t,int a,int b)
{if(s<=l&&r<=t){return Q2(root[now],1,n,a,b); }int mid=(l+r)/2;int sum=0;if(s<=mid) sum+=Q1(now*2,l,mid,s,t,a,b);if(mid+1<=t) sum+=Q1(now*2+1,mid+1,r,s,t,a,b);return sum;
}int Solve(int a,int b,int c)
{int L=1,R=n*2+1;while(L<R){int mid=(L+R)/2;int tmp=Q1(1,1,2*n+1,mid+1,2*n+1,a,b);if(tmp>=c) L=mid+1;else R=mid;}return L;
}int main()
{cin >>n >>m;for(int i=1;i<=m;i++){int opt,a,b,c;scanf("%d %d %d %d",&opt,&a,&b,&c);if(opt==1){Add1(1,1,2*n+1,a,b,c+n+1);if(tot>MAXN*600-10) return 1;}else{printf("%d\n",Solve(a,b,c)-n-1);if(tot>MAXN*600-10) return 1;}}return 0;
}
这篇关于【bzoj 3110】[Zjoi2013]K大数查询|树套树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
