p3863 序列

分析

按照时间为下标分块

块内按照大小排序

每次整块整体修改
半块暴力重构即可

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define int long long
priority_queue<pair<int,int> >p;
int n,m,bl[100100],a[100100],cnt1,cnt2,b,ans[100100];
int val[100100],w[100100],L[100100],R[100100],tag[100100];
struct upd{
    int le,ri,x,t;
};
upd d[100100];
struct ask{
    int pl,x,t,id;
};
ask q[100100];
inline bool cmp(const upd x,const upd y){
    if(x.le==y.le)return x.t<y.t;
    return x.le<y.le;
}
inline bool cmp2(const ask x,const ask y){
    if(x.pl==y.pl)return x.t<y.t;
    return x.pl<y.pl;
}
inline void work(int le,int ri,int x){
    int i,j,k;
    if(bl[le]==bl[ri]){
      for(i=le;i<=ri;i++)val[i]+=x;
      k=bl[le];
      for(i=L[k];i<=R[k];i++)w[i]=val[i];
      sort(w+L[k],w+R[k]+1);
      return;
    }
    for(i=le;i<=R[bl[le]];i++)val[i]+=x;
    for(i=L[bl[le]];i<=R[bl[le]];i++)w[i]=val[i];
    sort(w+L[bl[le]],w+R[bl[le]]+1);
    for(i=L[bl[ri]];i<=ri;i++)val[i]+=x;
    for(i=L[bl[ri]];i<=R[bl[ri]];i++)w[i]=val[i];
    sort(w+L[bl[ri]],w+R[bl[ri]]+1);
    for(i=bl[le]+1;i<bl[ri];i++)tag[i]+=x;
}
inline int go(int wh,int x){
    int k=lower_bound(w+L[wh],w+R[wh]+1,x)-w;
    if(k==R[wh]+1)return 0;
    return R[wh]-k+1;
}
inline int que(int pl,int x){
    int i,j,k,res=0;
    for(i=1;i<bl[pl];i++)res+=go(i,x-tag[i]);
    for(i=L[bl[pl]];i<=pl;i++)if(val[i]>=x-tag[bl[pl]])res++;
    return res;
}
signed main(){
    int i,j,k;
    scanf("%lld%lld",&n,&m);m++;
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=2;i<=m;i++){
      scanf("%lld",&k);
      if(k==1){
          ++cnt2;
          scanf("%lld%lld%lld",&d[cnt2].le,&d[cnt2].ri,&d[cnt2].x);
          d[cnt2].t=i;
      }else {
          ++cnt1;
          scanf("%lld%lld",&q[cnt1].pl,&q[cnt1].x);
          q[cnt1].t=i;
          q[cnt1].id=cnt1;
      }
    }
    b=sqrt((n+1));j=1;
    for(i=1;i<=m;i++)bl[i]=(i-1)/b+1;
    int sum=bl[m];
    for(i=1;i<=sum;i++)L[i]=R[i-1]+1,R[i]=R[i-1]+b;
    R[sum]=min(R[sum],m);
    sort(d+1,d+cnt2+1,cmp);
    sort(q+1,q+cnt1+1,cmp2);
    for(i=1;i<=cnt1;i++){
      while(!p.empty()&&-p.top().fi<q[i].pl){
          int x=p.top().se;
          work(d[x].t,m,-d[x].x);
          p.pop();
      }
      if(q[i].pl!=q[i-1].pl){
          work(1,m,a[q[i].pl]);
          work(1,m,-a[q[i-1].pl]);
      }
      while(j<=cnt2&&d[j].le<=q[i].pl){
          if(d[j].ri<q[i].pl){j++;continue;}
          work(d[j].t,m,d[j].x);
          p.push(mp(-d[j].ri,j));
          j++;
      }
      ans[q[i].id]=que(q[i].t-1,q[i].x);
    }
    for(i=1;i<=cnt1;i++)printf("%lld\n",ans[i]);
    return 0;
}