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

Sample Output

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操作中c<=Maxlongint

解题思路：

刚开始把题目看错了，以为是区间加法差点没给我恶心死。

最后发现一个位置上可以有多个数。

那么这道题就是带修改整体二分。

将操作按时间序排序，在二分过程中不要破坏这个序。

二分答案时将操作中的K若大于mid就插入线段树。

在时间序环境下查询区间。

剩下的就是普通整体二分了。

代码：

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #define lll spc<<1  5 #define rrr spc<<1|1  6 typedef long long lnt;  7 const int N=1000000;  8 struct que{  9     bool qu; 10     int t; 11     int l; 12     int r; 13     lnt x; 14 }q[N],sp[N],ss[N]; 15 struct trnt{ 16     lnt val; 17     lnt lzt; 18 }tr[N]; 19 int sek[N]; 20 int ans[N]; 21 lnt num[N]; 22 int n,m; 23 int cnt; 24 int tot; 25 void Add(int spc,int l,int r,lnt v){tr[spc].val+=v*(lnt)(r-l+1);tr[spc].lzt+=v;return ;} 26 void pushup(int spc){tr[spc].val=tr[lll].val+tr[rrr].val;return ;} 27 void pushdown(int spc,int l,int mid,int r) 28 { 29     if(tr[spc].lzt) 30     { 31         Add(lll,l,mid,tr[spc].lzt); 32         Add(rrr,mid+1,r,tr[spc].lzt); 33         tr[spc].lzt=0; 34     } 35     return ; 36 } 37 void update(int l,int r,int ll,int rr,int spc,lnt v) 38 { 39     if(ll>r||l>rr) 40         return ; 41     if(ll<=l&&r<=rr) 42     { 43         Add(spc,l,r,v); 44         return ; 45     } 46     int mid=(l+r)>>1; 47     pushdown(spc,l,mid,r); 48     update(l,mid,ll,rr,lll,v); 49     update(mid+1,r,ll,rr,rrr,v); 50     pushup(spc); 51     return ; 52 } 53 lnt query(int ll,int rr,int l,int r,int spc) 54 { 55     if(l>rr||ll>r) 56         return 0; 57     if(ll<=l&&r<=rr) 58         return tr[spc].val; 59     int mid=(l+r)>>1; 60     pushdown(spc,l,mid,r); 61     return query(ll,rr,l,mid,lll)+query(ll,rr,mid+1,r,rrr); 62 } 63 bool cmp(que a,que b){
    if(a.qu!=b.qu)return b.qu;return a.x
         
          rr) 68         return ; 69     if(l==r) 70     { 71         for(int i=ll;i<=rr;i++) 72             if(q[i].qu) 73                 ans[q[i].t]=l; 74         return ; 75     } 76     int mid=(l+r)>>1; 77     int sta1=0,sta2=0; 78     for(int i=ll;i<=rr;i++) 79     { 80         if(q[i].qu) 81         { 82             lnt sum=query(q[i].l,q[i].r,1,n,1); 83             if(q[i].x<=sum) 84                 ss[++sta2]=q[i]; 85             else{ 86                 q[i].x-=sum; 87                 sp[++sta1]=q[i]; 88             } 89         }else{ 90             if(q[i].x>mid) 91             { 92                 update(1,n,q[i].l,q[i].r,1,1); 93                 ss[++sta2]=q[i]; 94             }else{ 95                 sp[++sta1]=q[i]; 96             } 97         } 98     } 99     for(int i=1;i<=sta2;i++)100         if(ss[i].qu==0)101             update(1,n,ss[i].l,ss[i].r,1,-1);102     int sta=ll-1;103     for(int i=1;i<=sta1;i++)104         q[++sta]=sp[i];105     int midl=sta;106     for(int i=1;i<=sta2;i++)107         q[++sta]=ss[i];108     macrs(l,mid,ll,midl);109     macrs(mid+1,r,midl+1,rr);110     return ;111 }112 int main()113 {114     scanf("%d%d",&n,&m);115     for(int i=1;i<=m;i++)116     {117         int cmd;118         scanf("%d",&cmd);119         sek[i]=cmd;120         scanf("%d%d%lld",&q[i].l,&q[i].r,&q[i].x);121         q[i].qu=(cmd==2);122         q[i].t=i;123     }124     std::sort(q+1,q+m+1,cmp);125     tot=1;126     num[1]=q[1].x;127     q[1].x=1;128     for(int i=2;i<=m&&q[i].qu==0;i++)129     {130         if(q[i].x!=num[tot])131             tot++,num[tot]=q[i].x;132         q[i].x=tot;133     }134     std::sort(q+1,q+m+1,cmq);135     macrs(1,tot,1,m);136     for(int i=1;i<=m;i++)137         if(sek[i]==2)138             printf("%lld\n",num[ans[i]]);139     return 0;140 }