首页 > 代码库 > 3110: [Zjoi2013]K大数查询 树状数组套线段树
3110: [Zjoi2013]K大数查询 树状数组套线段树
3110: [Zjoi2013]K大数查询
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 1384 Solved: 629
[Submit][Status]
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
Output
输出每个询问的结果
Sample Input
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
1
2
1
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中abs(c)<=Maxlongint
这道题本来想用线段树套平衡树做，但是即便加了永久lazy标记，还是TLE了，后来改为树状数组套线段树，注意树状数组二分可优化为O(logn)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>using namespace std;#define MAXT 8100000#define MAXN 51009#define lch (now<<1)#define rch (now<<1^1)#define INF 0x3f3f3f3f#define L(x) SBT[x].L#define R(x) SBT[x].R#define S(x) SBT[x].S#define val(x) SBT[x].val#define tot(x) SBT[x].tot#define sum(x) SBT[x].sumtypedef long long qword;int n,m;inline int nextInt(){ register int x=0; register char ch; while (ch=getchar(),ch<‘0‘||ch > ‘9‘); do x=x*10+ch-‘0‘; while (ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x;}int topt;struct SBT_T{ int L,R,S,val,tot,sum;}SBT[MAXT];inline void update(int now){ if (!now)return ; S(now)=S(L(now))+S(R(now))+1; sum(now)=sum(L(now))+sum(R(now))+tot(now);}inline void l_rotate(int &now){ register int t=R(now); R(now)=L(t);update(now); L(t)=now;update(t); now=t;}inline void r_rotate(int &now){ register int t=L(now); L(now)=R(t);update(now); R(t)=now;update(t); now=t;}inline void maintain(int &now){ if (S(L(L(now)))>S(R(now))) { r_rotate(now); //maintain(L(now)); maintain(R(now)); maintain(now); }else if (S(R(R(now)))>S(L(now))) { l_rotate(now); //maintain(R(now)); maintain(L(now)); maintain(now); }else if (S(R(L(now)))>S(R(now))) { l_rotate(L(now)); r_rotate(now); maintain(R(now)); maintain(L(now)); maintain(now); }else if (S(L(R(now)))>S(L(now))) { r_rotate(R(now)); l_rotate(now); maintain(R(now)); maintain(L(now)); maintain(now); }}void Insert(int &now,int v,int t){ if (!now) { // if (topt>MAXT-10)throw 1; now=++topt; L(now)=R(now)=0; val(now)=v; tot(now)=sum(now)=t; return ; } if (v==val(now)) tot(now)+=t; else if (v<val(now)) Insert(L(now),v,t); else if (val(now)<v) Insert(R(now),v,t); update(now); maintain(now);}/*int Get_tot(int &now,int v){ if (!now)return 0; if (val(now)==v) return sum(L(now)); else if (v<val(now)) return Get_tot(L(now),v); else if (val(now)<v) return Get_tot(R(now),v)+sum(L(now))+tot(now); return 0;}*/int Get_tot(int now,int v){ int ret=0; while (now && val(now)!=v) { if (v<val(now)) now=L(now); else if (val(now)<v) ret+=sum(L(now))+tot(now),now=R(now); } if (now && val(now)==v)ret+=sum(L(now)); return ret;}void Scan(int now){ if (!now)return ; Scan(L(now)); printf("%d(%d) ",val(now),tot(now)); Scan(R(now));}struct sgt_node{ int l,r; int rt; int lazy;}sgt[MAXN*4];void Build_sgt(int now,int l,int r){ sgt[now].l=l; sgt[now].r=r; if (l==r)return ; Build_sgt(lch,l,(l+r)>>1); Build_sgt(rch,((l+r)>>1)+1,r);}void Add_val(int now,int l,int r,int v){ Insert(sgt[now].rt,v,r-l+1); if (sgt[now].l==l && sgt[now].r==r) { Insert(sgt[now].lazy,v,1); return ; } int mid=(sgt[now].l+sgt[now].r)>>1; if (r<=mid) { Add_val(lch,l,r,v); }else if (mid<l) { Add_val(rch,l,r,v); }else { Add_val(lch,l,mid,v); Add_val(rch,mid+1,r,v); }}int Qry_tot(int now,int l,int r,int v){ int ret=0; if (sgt[now].l==l && sgt[now].r==r) { return Get_tot(sgt[now].rt,v); } ret=Get_tot(sgt[now].lazy,v)*(r-l+1); int mid=(sgt[now].l+sgt[now].r)>>1; if (r<=mid) ret+=Qry_tot(lch,l,r,v); else if (mid<l) ret+=Qry_tot(rch,l,r,v); else ret+=Qry_tot(lch,l,mid,v)+Qry_tot(rch,mid+1,r,v); return ret;}int Get_size(int now,int l,int r){ if (sgt[now].l==l && sgt[now].r==r) { return sum(sgt[now].rt); } int mid=(sgt[now].l+sgt[now].r)>>1; if (r<=mid) return Get_size(lch,l,r) + sum(sgt[now].lazy)*(r-l+1); else if (mid<l) return Get_size(rch,l,r) + sum(sgt[now].lazy)*(r-l+1); else return Get_size(lch,l,mid)+Get_size(rch,mid+1,r) + sum(sgt[now].lazy)*(r-l+1);}int Qry_kth(int ll,int rr,int rk){ int l,r,mid; l=-n; r=n+1; rk=Get_size(1,ll,rr)-rk; int t=0; if (rk<0)return 1; while (l+1<r) { mid=(l+r)/2; t=Qry_tot(1,ll,rr,mid); if (t<=rk) l=mid; else r=mid; } return l;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,j,k,x,y,z; int rt=0; scanf("%d%d",&n,&m); int opt; Build_sgt(1,1,n); for (i=0;i<m;i++)//50000 { opt=nextInt(); x=nextInt(); y=nextInt(); z=nextInt(); //scanf("%d%d%d%d",&opt,&x,&y,&z); if (opt==1) { Add_val(1,x,y,z); }else { printf("%d\n",Qry_kth(x,y,z)); } }}
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define MAXN 101000#define MAXT 28000000#define lowbit(x) (x&(-x))inline int nextInt(){ register int x=0; register char ch; while (ch=(char)getchar(),ch<‘0‘||ch > ‘9‘); do x=x*10+ch-‘0‘; while (ch=(char)getchar(),ch<=‘9‘ && ch>=‘0‘); return x;}int n,m;struct sgt_node{ int lch,rch; int t,lazy;}sgt[MAXT];int topt=0;void Add_sgt(int &now,int l,int r,int x,int y){ if (!now) { now=++topt; sgt[now].t=sgt[now].lazy=0; } if (l==x && r==y) { sgt[now].t+=r-l+1; sgt[now].lazy++; return ; } int mid=(l+r)>>1; if (sgt[now].lazy) { if (!sgt[now].lch) sgt[now].lch=++topt; if (!sgt[now].rch) sgt[now].rch=++topt; sgt[sgt[now].lch].lazy+=sgt[now].lazy; sgt[sgt[now].rch].lazy+=sgt[now].lazy; sgt[sgt[now].lch].t+=sgt[now].lazy*(mid-l+1); sgt[sgt[now].rch].t+=sgt[now].lazy*(r-mid); sgt[now].lazy=0; } if (y<=mid) { Add_sgt(sgt[now].lch,l,mid,x,y); }else if (mid<x) { Add_sgt(sgt[now].rch,mid+1,r,x,y); }else { Add_sgt(sgt[now].lch,l,mid,x,mid); Add_sgt(sgt[now].rch,mid+1,r,mid+1,y); } sgt[now].t=sgt[sgt[now].lch].t+sgt[sgt[now].rch].t;}int Qry_sgt(int &now,int l,int r,int x,int y){ if (!now || sgt[now].t==0)return 0; if (l==x && r==y) return sgt[now].t; int mid=(l+r)>>1; if (sgt[now].lazy) { if (!sgt[now].lch) sgt[now].lch=++topt; if (!sgt[now].rch) sgt[now].rch=++topt; sgt[sgt[now].lch].lazy+=sgt[now].lazy; sgt[sgt[now].rch].lazy+=sgt[now].lazy; sgt[sgt[now].lch].t+=sgt[now].lazy*(mid-l+1); sgt[sgt[now].rch].t+=sgt[now].lazy*(r-mid); sgt[now].lazy=0; } if (y<=mid) { return Qry_sgt(sgt[now].lch,l,mid,x,y); }else if (mid<x) { return Qry_sgt(sgt[now].rch,mid+1,r,x,y); }else { return Qry_sgt(sgt[now].lch,l,mid,x,mid) +Qry_sgt(sgt[now].rch,mid+1,r,mid+1,y); }}int tarr2[MAXN],tarr3[MAXN];void Add_tarr2(int l,int r){ r++; int a=r; while (r<MAXN) { tarr2[r]--; tarr3[r]-=a; r+=lowbit(r); } a=l; while (l<MAXN) { tarr2[l]++; tarr3[l]+=a; l+=lowbit(l); }}//segma((n-i+1)*a[i])//=(n+1)*segma(a[i]) - segma(i*a[i])int Qry_tarr2(int l,int r){ int ret=0; int v1,v2; int now; v1=0; l--; now=r; v1=v2=0; while (now) { v1+=tarr2[now]; v2+=tarr3[now]; now-=lowbit(now); } ret+=v1*(r+1)-v2; now=l; v1=v2=0; while (now) { v1+=tarr2[now]; v2+=tarr3[now]; now-=lowbit(now); } ret-=v1*(l+1)-v2; return ret;}int tarr[MAXN];void Add_tarr(int pos,int l,int r){ pos+=n+1; Add_tarr2(l,r); while (pos<MAXN) { Add_sgt(tarr[pos],0,n+1,l,r); pos+=lowbit(pos); }}/*int Qry_tarr(int rk,int ll,int rr){ int now=0,t; int i; int l,r,mid; rk=Qry_tarr2(ll,rr)-rk+1; l=-n-1;r=n+1; while (l+1<r) { t=0; mid=(l+r)>>1; now=mid+n+1; while (now) { t+=Qry_sgt(tarr[now],0,n+1,ll,rr); now-=lowbit(now); } if (t<rk) l=mid; else r=mid; } return r==-n ? 1 : r;}*/int Qry_tarr(int rk,int ll,int rr){ int now=0,t; int i; int l,r,mid; rk=Qry_tarr2(ll,rr)-rk+1; for (i=20;i>=0;i--) { if (now+(1<<i)<MAXN && (t=Qry_sgt(tarr[now+(1<<i)],0,n+1,ll,rr))<rk) { rk-=t; now+=(1<<i); } } now=now+1-(n+1); return now;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d",&n,&m); int i; int opt,x,y,z; for (i=0;i<m;i++) { opt=nextInt(); x=nextInt(); y=nextInt(); z=nextInt(); //scanf("%d%d%d%d",&opt,&x,&y,&z); if (opt==1) { Add_tarr(z,x,y); }else { printf("%d\n",Qry_tarr(z,x,y)); } }}
3110: [Zjoi2013]K大数查询 树状数组套线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。