BZOJ 3110 (zjoi 2013)k大数查询(树套树)
发布时间:2020-12-14 02:46:54 所属栏目:大数据 来源:网络整理
导读:题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=3110 我用的是线段树套线段树 #includecstdio#includecstring#includeiostreamusing namespace std;#define maxn (20000000+5)int N,M;int tot=0;int root[200000+5];int L[maxn],R[maxn],sum[max
题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=3110 我用的是线段树套线段树 #include<cstdio> #include<cstring> #include<iostream> using namespace std; #define maxn (20000000+5) int N,M; int tot=0; int root[200000+5]; int L[maxn],R[maxn],sum[maxn],lazy[maxn]; void pushdown(int k,int l,int r){ if(l==r||lazy[k]==0)return ; if(L[k]==0)L[k]=++tot; if(R[k]==0)R[k]=++tot; lazy[L[k]]+=lazy[k]; lazy[R[k]]+=lazy[k]; int mid=(r+l)>>1; sum[L[k]]+=(mid-l+1)*lazy[k]; sum[R[k]]+=(r-mid)*lazy[k]; lazy[k]=0; } void ADD(int &k,int r,int a,int b){ if(k==0)k=++tot; pushdown(k,l,r); if(l==a&&r==b){ sum[k]+=r-l+1; lazy[k]++; return ; } int mid=(l+r)>>1; if(b<=mid)ADD(L[k],mid,a,b); else if(a>mid)ADD(R[k],mid+1,r,b); else{ ADD(L[k],mid); ADD(R[k],b); } sum[k]=sum[L[k]]+sum[R[k]]; } void adde(int a,int b,int c){ int l=1,r=N,k=1; while(l!=r){ int mid=(l+r)>>1; ADD(root[k],1,N,b); if(c<=mid)r=mid,k=(k<<1); else l=mid+1,k=k<<1|1; } ADD(root[k],b); } int ask(int k,int b){ if(k==0)return 0; pushdown(k,r); if(l==a&&r==b)return sum[k]; int mid=(l+r)>>1; if(b<=mid)return ask(L[k],b); else if(a>mid)return ask(R[k],b); else{ return ask(L[k],mid)+ask(R[k],b); } } int solve(int a,int c){ int k=1,l=1,r=N; while(l!=r){ int mid=(l+r)>>1; int t=ask(root[k<<1],b); if(c<=t)r=mid,k<<=1; else l=mid+1,k=k<<1|1,c-=t; } return l; } void input(){ scanf("%d%d",&N,&M); for(int i=1;i<=M;i++){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); if(a==1){ adde(b,N-d+1); } else{ printf("%dn",N-solve(b,d)+1); } } } int main(){ input(); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |