题目大意：

有n个位置，m个操作，提供下列两种操作：

1.在[x,y]区间内每个位置插入一个z

2.查询[x,y]区间内的第k大

注意是第k大不是第k小

来一段《树套树之歌》吧：

树套树 树套树 树套树套树 树套树树套树套树 树套树套树套树套树 树套树树套树套树 树套树套树套树套树套树

BGM：《邮递马车》

树套树摆在这里 关键是怎么套 我一开始想的是权值线段树在内层 结果外层的话树状数区间修改+查询忘记怎么写了 线段树压根不会可持久化标记 最后只能权值线段树开在外面

权值线段树开在外面 内层是区间线段树 记录该权值的覆盖区域

??伤不起啊。。。。

注意这道题的内存空间很不充裕 所以节点能不开就不开 省掉内存就是胜利

把y写成r WA了一下午。。。。。 40%达成 我看来是写不完十道题了。。。。

写完之后无论时间还是空间都和Rank上的神?们差很远 看来我还是去学线段树可持久化标记吧。。。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int n,m; struct Tree{ Tree *ls,*rs; unsigned int num,mark; Tree() { ls=rs=0x0; num=mark=0; } void add(int x,int y,unsigned int z) { num+=(y-x+1)*z; mark+=z; } void update(int x,int y,int l,int r) { int mid=x+y>>1; if(x==l&&y==r) { add(x,y,1u); return ; } if(!ls)ls=new Tree; if(!rs)rs=new Tree; if(mark) { ls->add(x,mid,mark); rs->add(mid+1,y,mark); mark=0; } if(r<=mid) ls->update(x,mid,l,r); else if(l>mid) rs->update(mid+1,y,l,r); else ls->update(x,mid,l,mid),rs->update(mid+1,y,mid+1,r); num=ls->num+rs->num; } unsigned int getans(int x,int y,int l,int r) { int mid=x+y>>1; if(!num) return 0; if(x==l&&y==r) return num; if(!ls)ls=new Tree; if(!rs)rs=new Tree; if(mark) { ls->add(x,mid,mark); rs->add(mid+1,y,mark); mark=0; } if(r<=mid) return ls->getans(x,mid,l,r); if(l>mid) return rs->getans(mid+1,y,l,r); return ls->getans(x,mid,l,mid) + rs->getans(mid+1,y,mid+1,r); } }; struct abcd{ abcd *ls,*rs,; Tree *tree; abcd() { ls=rs=0x0; tree=new Tree; } void update(int x,int y,int l,int r,int val) { int mid=x+y>>1; tree->update(1,n,l,r); if(x==y) return ; if(!ls)ls=new abcd; if(!rs)rs=new abcd; if(val<=mid) ls->update(x,mid,l,r,val); else rs->update(mid+1,y,l,r,val); } int getans(int x,int y,int l,int r,int k) { int mid=x+y>>1; if(x==y) return mid; if(!ls)ls=new abcd; if(!rs)rs=new abcd; int r_sum=rs->tree->getans(1,n,l,r); if(k>r_sum) return ls->getans(x,mid,l,r,k-r_sum); else return rs->getans(mid+1,y,l,r,k); } }root; int main() { //freopen("sequence.in","r",stdin); //freopen("sequence.out","w",stdout); int i,p,x,y,z; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d%d%d",&p,&x,&y,&z); if(p==1) root.update(1,n,x,y,z); else printf("%d\n", root.getans(1,n,x,y,z) ); } }