题目：

第一道线段树套线段树！

第一道标记永久化！

为什么为什么写了两个半小时啊……

本想线段树套平衡树，但想不出怎么合并不同区间上的平衡树（LCT??）。

于是看了一下Zinn的TJ。原来是线段树套线段树呀。原来外层是权值内层是区间呀。原来要动态开点呀。

　　这是因为区间线段树要下传标记什么的，而权值线段树在本题中都是在叶子上修改。所以这样比较方便。

然后手胡了一番pshp，pshd。RE到飞起。

#include
      
       #include
       
        #include
        
         using namespace std;const int N=5e4,M=1e5+5;int n,m,tt1,tt2,rtt,rt[M<<1],ls[M<<1],rs[M<<1],L,R;struct Node{  int ls,rs;long long lazy,sum;//ll!}a[N*380+5];//每个外层点上有logn个节点void pshd2(int cr,int &l,int &r,int lb,int rb){  if(!l)l=++tt2;if(!r)r=++tt2;//!!  if(!a[cr].lazy)return;  int w=a[cr].lazy,mid=lb+rb>>1;  a[cr].lazy=0;a[l].lazy+=w;a[r].lazy+=w;  a[l].sum+=w*(mid-lb+1);a[r].sum+=w*(rb-mid);}void pshp2(int cr){  a[cr].sum=a[a[cr].ls].sum+a[a[cr].rs].sum;}void pshp1(int &cr,int p1,int p2){  if(!cr)cr=++tt2;  a[cr].sum=a[p1].sum+a[p2].sum;  a[cr].lazy=a[p1].lazy+a[p2].lazy;  if(a[p1].ls||a[p2].ls)pshp1(a[cr].ls,a[p1].ls,a[p2].ls);  if(a[p1].rs||a[p2].rs)pshp1(a[cr].rs,a[p1].rs,a[p2].rs);}void mdfy(int l,int r,int &cr){  if(!cr)cr=++tt2;  if(l>=L&&r<=R){a[cr].sum+=(r-l+1);a[cr].lazy++;return;}//r-l+1!!  pshd2(cr,a[cr].ls,a[cr].rs,l,r);int mid=l+r>>1;  if(L<=mid)mdfy(l,mid,a[cr].ls);  if(mid
         
          >1;  if(p<=mid)mdfy(l,mid,ls[cr],p);  else mdfy(mid+1,r,rs[cr],p);  pshp1(rt[cr],rt[ls[cr]],rt[rs[cr]]);  //别pshp了，标记永久化}int query(int l,int r,int cr){  //  printf("l=%d r=%d L=%d R=%d a[%d].sum=%d\n",l,r,L,R,cr,a[cr].sum);  if(l>=L&&r<=R)return a[cr].sum;  pshd2(cr,a[cr].ls,a[cr].rs,l,r);int mid=l+r>>1;  if(L>mid)return query(mid+1,r,a[cr].rs);  if(R<=mid)return query(l,mid,a[cr].ls);  return query(l,mid,a[cr].ls)+query(mid+1,r,a[cr].rs);}int query(int l,int r,int cr,int k){  if(l==r)return l;  int mid=l+r>>1;  int w=query(1,n,rt[rs[cr]]);  //  printf("l=%d r=%d mid=%d w=%d\n",l,r,mid,w);  if(w>=k)return query(mid+1,r,rs[cr],k);  else return query(l,mid,ls[cr],k-w);}int main(){  scanf("%d%d",&n,&m);int op,c;  while(m--)    {      scanf("%d%d%d%d",&op,&L,&R,&c);      if(op==1)      mdfy(-N,N,rtt,c);      else    printf("%d\n",query(-N,N,rtt,c));    }  return 0;}
         
        
       
      

然后又看看Zinn的TJ。原来是标记永久化呀。抄抄抄。

标记永久化就是没有pshp和pshd。在修改的时候往下走的时候就把sum改掉（因为改sum需要知道区间大小，所以需要传L，R），不往下走的时候同样打上lazy。在查询的时候把路径上的lazy累加。细节是累加的lazy需要乘上目标区间的大小，而且因为这种写法，打lazy的时候就不能加sum了。

仍旧数组大小迷茫中。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=5e4+5,M=N*400;//int n,m,tt1,tt2,lm,rtt,ls[N<<1],rs[N<<1],rt[N<<1],lss[M],rss[M];int L,R,op[N],x[N],y[N],c[N],tp[N];ll sum[M],lazy[M];//ll,防止计算时爆intvoid add(int l,int r,int &cr,int L,int R)//传L,R{  if(!cr)cr=++tt2;  if(l==L&&r==R){lazy[cr]++;return;}//==  sum[cr]+=R-L+1;//打了lazy就不要加sum了--看query那里  int mid=l+r>>1;  if(mid
         
          =R)add(l,mid,lss[cr],L,R);  else add(l,mid,lss[cr],L,mid),add(mid+1,r,rss[cr],mid+1,R);}void insert(int l,int r,int &cr,int p){  if(!cr)cr=++tt1;  add(1,n,rt[cr],L,R);  if(l==r)return;int mid=l+r>>1;  if(p<=mid)insert(l,mid,ls[cr],p);  else insert(mid+1,r,rs[cr],p);}//int query(int l,int r,int cr,ll lz)//{//  if(l>=L&&r<=R)return sum[cr]+lz;//  int mid=l+r>>1;int ret=0;//  if(L<=mid)ret+=query(l,mid,lss[cr],lz+lazy[cr]);//  if(mid
          
           >1; if(L>mid)return ret+query(mid+1,r,rss[cr],L,R); if(R<=mid)return ret+query(l,mid,lss[cr],L,R); return ret+query(l,mid,lss[cr],L,mid)+query(mid+1,r,rss[cr],mid+1,R);//仔细想想只加一个ret!!!}int query(int l,int r,int &cr,int k){ if(!cr)cr=++tt1;// if(l==r)return l; ll w=query(1,n,rt[rs[cr]],L,R),mid=l+r>>1; if(w>=k)return query(mid+1,r,rs[cr],k); else return query(l,mid,ls[cr],k-w);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&op[i],&x[i],&y[i],&c[i]); if(op[i]==1)tp[++lm]=c[i];//only op==1!!! } sort(tp+1,tp+m+1);lm=unique(tp+1,tp+m+1)-tp-1; for(int i=1;i<=m;i++) { L=x[i];R=y[i]; if(op[i]==1) { int tmp=lower_bound(tp+1,tp+lm+1,c[i])-tp; insert(1,lm,rtt,tmp); } else printf("%d\n",tp[query(1,lm,rtt,c[i])]); } return 0;}