BZOJ 3110 [ZJOI2013] K大数查询 【树套树】
学了学树套树,大概就是,外层是一棵权值线段树,内层是一棵普通线段树,然后对于第一种询问,在外层找到权值为c的线段树,在内层的a-b上加;对于第二种询问,外层线段树处理后内层再搞即可。
附上代码
# include <stdio.h> # include <algorithm> using namespace std; const int M=300010,MM=20000005; int root[M],ch[MM][2],s[MM],lazy[MM],cnt=0,n,m; inline void update(int &rt,int l,int r,int ql,int qr) { if(rt==0) rt=++cnt; if(ql<=l && r<=qr) { lazy[rt]++; s[rt]+=r-l+1; return ; } int mid=l+r>>1; if(ql<=mid) update(ch[rt][0],l,mid,ql,qr); if(qr>mid) update(ch[rt][1],mid+1,r,ql,qr); s[rt]=s[ch[rt][0]]+s[ch[rt][1]]+lazy[rt]*(r-l+1); } inline void Update(int x,int l,int r,int ql,int qr,int qc) { update(root[x],1,n,ql,qr); if(l==r) return; int mid=l+r>>1; if(qc<=mid) Update(x*2,l,mid,ql,qr,qc); else Update(x*2+1,mid+1,r,ql,qr,qc); } inline int query(int rt,int l,int r,int ql,int qr) { if(!rt) return 0; if(ql<=l && r<=qr) return s[rt]; int mid=l+r>>1; int ret=0; if(ql<=mid) ret+=query(ch[rt][0],l,mid,ql,qr); if(qr>mid) ret+=query(ch[rt][1],mid+1,r,ql,qr); return ret+lazy[rt]*(min(qr,r)-max(ql,l)+1); } inline int Query(int x,int l,int r,int ql,int qr,int qc) { if(l==r) return l; int mid=l+r>>1; int ret=query(root[x*2],1,n,ql,qr); if (qc<=ret) return Query(x*2,l,mid,ql,qr,qc); qc=qc-ret; return Query(x*2+1,mid+1,r,ql,qr,qc); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { int buf,a,b,c; scanf("%d%d%d%d",&buf,&a,&b,&c); if(buf==1) c=n-c+1,Update(1,1,n,a,b,c); else printf("%d\n",n-Query(1,1,n,a,b,c)+1); } return 0; }