分块大法。。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int maxn=1002333,knum=1023; 8 int sz[knum],l[knum],r[knum],add[knum]; 9 int bel[maxn],mp[maxn];10 int a[knum][1023];11 int i,j,k,n,m,kuai;12  13 int ra;char rx;14 inline int read(){15     rx=getchar(),ra=0;16     while(rx<'0'||rx>'9')rx=getchar();17     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;18 }19 inline int get(int id,int v){20     if(v<=0)return sz[id];21     if(v>a[id][sz[id]])return 0;22     int l=0,r=sz[id]+1,mid;23     while(l
           
            >1)]>=v)r=mid;else l=mid+1;25 return sz[id]-l+1;26 }27 inline void insert(int L,int R,int v){28 register int i;29 if(bel[L]==bel[R]){30 int id=bel[L];31 for(i=L;i<=R;i++)mp[i]+=v;32 memcpy(a[id]+1,mp+1+l[id],sz[id]<<2);33 sort(a[id]+1,a[id]+1+sz[id]);34 return;35 }36 int idl=bel[L],idr=bel[R];37 for(i=L;i<=r[idl];i++)mp[i]+=v;38 memcpy(a[idl]+1,mp+1+l[idl],sz[idl]<<2),39 sort(a[idl]+1,a[idl]+1+sz[idl]);40 41 for(i=l[idr];i<=R;i++)mp[i]+=v;42 memcpy(a[idr]+1,mp+1+l[idr],sz[idr]<<2),43 sort(a[idr]+1,a[idr]+1+sz[idr]);44 45 for(i=idl+1;i
            
             =v;51 return ans;52 }53 for(i=L;i<=r[idl];i++)ans+=mp[i]+add[idl]>=v;54 for(i=l[idr];i<=R;i++)ans+=mp[i]+add[idr]>=v;55 for(i=idl+1;i