zcmimi's blog

查看原题

点击跳转

统计方法类似扫描线

lp排序,按顺序枚举

l的时候更新,在r之后还原(p已经不在区间[l,r]中了,不受影响)

以时间为下标,维护某个时间段内大于等于y的数个数

需要一个数据结构维护区间中大于等于某个数的个数(带修改),可以想到分块

#include<bits/stdc++.h>
using std::sort;using std::pair;using std::make_pair;using std::priority_queue;
typedef long long ll;
const int N=100011;
int n,q,blk,c[N],ans[N];
struct node{
    int l,r,v,t;
    bool operator<(const node&x)const{
        return l<x.l||(l==x.l&&t<x.t);
    }
}a[N];
struct que{
    int p,v,t,id;
    bool operator<(const que&x)const{
        return p<x.p||(p==x.p&&t<x.t);
    }
}b[N];
int L[N],R[N],bl[N];
ll s[N],S[N],tag[320];
void init(int k){
    memcpy(S+L[k],s+L[k],(R[k]-L[k]+1)*__SIZEOF_LONG_LONG__);
    // for(int i=L[k];i<=R[k];++i)S[i]=s[i];
    sort(S+L[k],S+R[k]+1);
}
void upd(int l,int r,ll v){
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;++i)s[i]+=v;
        init(bl[l]);return;
    }
    for(int i=l;bl[i]==bl[l];++i)s[i]+=v;
    for(int i=bl[l]+1;i<=bl[r]-1;++i)tag[i]+=v;
    for(int i=r;bl[i]==bl[r];--i)s[i]+=v;
    init(bl[l]);init(bl[r]);    
}
int calc(int i,ll v){
    int x=std::lower_bound(S+L[i],S+R[i]+1,v)-S;
    return R[i]-x+1;
}
int ask(int x,ll v){
    int res=0;
    for(int i=1;i<=bl[x]-1;++i)res+=calc(i,v-tag[i]);
    for(int i=L[bl[x]];i<=x;++i)res+=s[i]+tag[bl[i]]>=v;
    return res;
}
int main(){
    scanf("%d%d",&n,&q);
    int opt,x,y,v,cnt1=0,cnt2=0;
    for(int i=1;i<=n;++i)scanf("%d",c+i);
    for(int i=2;i<=q+1;++i){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)scanf("%d",&v),a[++cnt1]=(node){x,y,v,i};
        else ++cnt2,b[cnt2]=(que){x,y,i,cnt2};
    }
    sort(a+1,a+cnt1+1);
    sort(b+1,b+cnt2+1);
    ++q;
    blk=sqrt(q);
    for(int i=1;i<=q;++i)bl[i]=(i-1)/blk+1;
    for(int i=1;i<=bl[q];++i)
        L[i]=R[i-1]+1,R[i]=R[i-1]+blk;
    R[bl[q]]=q;
    priority_queue<pair<int,int>>Q;
    for(int i=1,j=1;i<=cnt2;++i){
        while(!Q.empty()&&-Q.top().first<b[i].p)
            x=Q.top().second,Q.pop(),
            upd(a[x].t,q,-a[x].v);
        if(b[i].p!=b[i-1].p)
            upd(1,q,c[b[i].p]),
            upd(1,q,-c[b[i-1].p]);
        for(;a[j].l<=b[i].p&&j<=cnt1;++j)
            if(b[i].p<=a[j].r)
                upd(a[j].t,q,a[j].v),
                Q.push(make_pair(-a[j].r,j));
        ans[b[i].id]=ask(b[i].t-1,b[i].v);
    }
    for(int i=1;i<=cnt2;++i)printf("%d\n",ans[i]);
}
LG 3863 序列
comment评论
Search
search