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

Solution

整体二分板子题哪来的题解，笔记又懒得写这样子。

线段树写错不做人了。爆$int$了不做人了。懒得一个一个改$long~long$直接$define$了……慢点就慢点吧……

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #define N (50009) 5 #define int long long 6 using namespace std; 7  8 struct Que{
   int opt,a,b,c,pos;}Q[N],q1[N],q2[N]; 9 struct Sgt{
   int val,add;}Segt[N<<2];10 int n,m,cnt,ans[N];11 12 inline int read()13 {14     int x=0,w=1; char c=getchar();15     while (c<'0' || c>'9') {
   if (c=='-') w=-1; c=getchar();}16     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();17     return x*w;18 }19 20 void Pushdown(int now,int l,int r)21 {22     if (Segt[now].add)23     {24         int mid=(l+r)>>1;25         Segt[now<<1].add+=Segt[now].add;26         Segt[now<<1|1].add+=Segt[now].add;27         Segt[now<<1].val+=Segt[now].add*(mid-l+1);28         Segt[now<<1|1].val+=Segt[now].add*(r-mid);29         Segt[now].add=0;30     }31 }32 33 void Update(int now,int l,int r,int l1,int r1,int k)34 {35     if (l>r1 || r
        
         >1; Pushdown(now,l,r);43     Update(now<<1,l,mid,l1,r1,k); Update(now<<1|1,mid+1,r,l1,r1,k);44     Segt[now].val=Segt[now<<1].val+Segt[now<<1|1].val;45 }46 47 int Query(int now,int l,int r,int l1,int r1)48 {49     if (l>r1 || r
         
          >1; Pushdown(now,l,r);52     return Query(now<<1,l,mid,l1,r1)+Query(now<<1|1,mid+1,r,l1,r1);53 }54 55 void Solve(int l,int r,int L,int R)56 {57     if (l>r || L>R) return;58     if (l==r)59     {60         for (int i=L; i<=R; ++i) if (Q[i].opt==2) ans[Q[i].pos]=l;61         return;62     }63     int mid=(l+r)>>1,cnt1=0,cnt2=0;64     for (int i=L; i<=R; ++i)65         if (Q[i].opt==1)66         {67             if (Q[i].c>mid) Update(1,1,n,Q[i].a,Q[i].b,1), q2[++cnt2]=Q[i]; 68             else q1[++cnt1]=Q[i];69         }70         else71         {72             int now=Query(1,1,n,Q[i].a,Q[i].b);73             if (now>=Q[i].c) q2[++cnt2]=Q[i];74             else Q[i].c-=now, q1[++cnt1]=Q[i];75         }76     for (int i=L; i<=R; ++i) if (Q[i].opt==1 && Q[i].c>mid) Update(1,1,n,Q[i].a,Q[i].b,-1);77     for (int i=1; i<=cnt1; ++i) Q[L+i-1]=q1[i];78     for (int i=1; i<=cnt2; ++i) Q[L+cnt1+i-1]=q2[i];79     Solve(l,mid,L,L+cnt1-1); Solve(mid+1,r,L+cnt1,R);80 }81 #undef int82 int main()83 #define int long long84 {85     n=read(); m=read();86     for (int i=1; i<=m; ++i)87     {88         int opt=read(),a=read(),b=read(),c=read();89         if (opt==2) ++cnt;90         Q[i]=(Que){opt,a,b,c,cnt};91     }92     Solve(1,n,1,m);93     for (int i=1; i<=cnt; ++i) printf("%lld\n",ans[i]);94 }