P5063 置身天上之森

题面

原题链接 click

题解

注意到一棵线段树同一层的区间长度最多相差 \(1\)，所以一共最多只有 \(2\log_2n+O(1)\) 种不同长度的线段，这些线段显然两两无交。
我们把这些线段按照长度拆开，得到 \(O(\log n)\) 组。
组内需要实现区间加区间查询 \(\le x\) 的数的个数，使用分块维护（请注意，实现时块内重构要用），可以做到单次操作 \(O(\sqrt{k\log k})\)，其中 \(k\) 为组内区间数。
这样得到的总复杂度就是 \(O(n\sqrt{n\log n})\)，加一个剪枝即可通过。
Corner case 较多，实现时调试较为费劲。

Code

#include<bits/stdc++.h>
using namespace std;
int n,q,m;
struct block{
    long long a[555]; 
    int p[555],len;
    long long tag;
    int qry1(long long c){
        c-=tag;
        if(a[1]>c) return 0;
        if(a[len]<=c) return len;
        return upper_bound(a+1,a+1+len,c)-a-1;
    }
    int qry2(int l,int r,long long c){
        c-=tag;
        int ans=0;
        for(int i=1;i<=len;i++){
            if(p[i]>=l&&p[i]<=r){
                ans+=a[i]<=c;
            }
        }
        return ans;
    }
    void upd(int l,int r,long long c){
        vector<long long>a1,a2;
        vector<int>p1,p2; 
        for(int i=1;i<=len;i++){
            if(p[i]>=l&&p[i]<=r){
                a1.push_back(a[i]+tag+c); p1.push_back(p[i]);
            }else{
                a2.push_back(a[i]+tag); p2.push_back(p[i]);
            }
        }
        tag=0; len=0; int pos1=0,pos2=0;
        while(pos1<p1.size()&&pos2<p2.size()){
            if(a1[pos1]<a2[pos2]){
                len++; a[len]=a1[pos1]; p[len]=p1[pos1]; pos1++;
            }else{
                len++; a[len]=a2[pos2]; p[len]=p2[pos2]; pos2++;
            }
        }
        while(pos1<p1.size()){
            len++; a[len]=a1[pos1]; p[len]=p1[pos1]; pos1++;
        }
        while(pos2<p2.size()){
            len++; a[len]=a2[pos2]; p[len]=p2[pos2]; pos2++;
        }
    }
};
struct ds{
    int keylen;
    int len,k,m;
    block s[305];
    int p[100005];
    void init(int tt){
        keylen=tt;
        k=sqrt(len+0.5)*1.3;
        m=1;
        for(int i=1;i<=len;i++){
            if(s[m].len==k) m++;
            s[m].len++;
            s[m].p[s[m].len]=i;
        }
        p[0]=-0x3f3f3f3f; p[len+1]=0x3f3f3f3f;
    }
    void update(int l,int r,long long c){
        int u=l,v=r;
        r-=keylen-1;
        l=lower_bound(p+1,p+2+len,l)-p;
        r=upper_bound(p+1,p+2+len,r)-p-1;
        if(l<=r){
            for(int i=1;i<=m;i++){
                if(i*k<l) continue;
                if((i-1)*k>=r) break;
                if(l<=(i-1)*k+1&&i*k<=r) s[i].tag+=c*keylen;
                else s[i].upd(l,r,c*keylen);
            }
        }
        l--; if(l>0&&p[l]+keylen-1>=u){
            s[(l+k-1)/k].upd(l,l,c*(min(p[l]+keylen-1,v)-u+1));
        }
        r++; if(r<=len&&p[r]<=v&&l!=r){
            s[(r+k-1)/k].upd(r,r,c*(v-max(p[r],u)+1));
        }

    }
    int query(int l,int r,long long c){
        r-=keylen-1;
        l=lower_bound(p+1,p+2+len,l)-p;
        r=upper_bound(p+1,p+2+len,r)-p-1;
        if(r<l) return 0;
        int ans=0;
        for(int i=1;i<=m;i++){
            if(i*k<l) continue;
            if((i-1)*k>=r) break;
            if(l<=(i-1)*k+1&&i*k<=r) ans+=s[i].qry1(c);
            else ans+=s[i].qry2(l,r,c);
        }
        return ans;
    }
};
ds c[40];
int lc[40];
void build(int l,int r){
    int len=r-l+1;
    for(int i=1;i<=m;i++){
        if(lc[i]==len){
            c[i].p[++c[i].len]=l;
        }
    }
    if(l==r) return;
    int m=l+r>>1;
    build(l,m); build(m+1,r);
}
void init(){
    int tmp1=n,tmp2=n;
    while(tmp1){
        lc[++m]=tmp1;
        tmp1>>=1;
    }
    while(tmp2!=1){
        lc[++m]=tmp2;
        tmp2++;
        tmp2>>=1;
    }
    sort(lc+1,lc+1+m); m=unique(lc+1,lc+1+m)-lc-1;
    build(1,n);
    for(int i=1;i<=m;i++) c[i].init(lc[i]);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    init();
    while(q--){
        int tp,l,r,d; cin>>tp>>l>>r>>d;
        if(tp==1){
            for(int i=1;i<=m;i++){
                c[i].update(l,r,d);
            }
        }else{
            int ans=0;
            for(int i=1;i<=m;i++){
                ans+=c[i].query(l,r,d);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}