【Ynoi2014】置身天上之森

Author Avatar
mrsrz 4月 14, 2020

分块。

题目大意：

给定一棵线段树，每个点的值是其覆盖的这段区间的所有数的和，初始全为 $0$。要支持两个操作：

  • 给定 $l,r,a$，将位置在 $[l,r]$ 内的所有数的值加上 $a$，线段树上其他结点的值相应变化。
  • 给定 $l,r,a$，求有多少个线段树结点，被 $[l,r]$ 完全包含，且值小于等于 $a$。

题解：

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

这题要用到线段树的性质。

对于一棵线段树，它同一个高度的所有结点，最多只有 22 种不同的区间大小。

那么整棵线段树只有 $O(\log ⁡n)$ 个不同的区间大小。

我们考虑分开维护这 $O(\log ⁡n)$ 个区间。然后容易将问题转化为这样的一个问题：

给定一个长度为 $n$ 的序列，支持区间加，区间查询一个数的排名。

我们考虑解决这个经典的问题。

考虑序列分块，然后块内元素从小到大排序。设块大小为 $S$。

对于查询操作，区间里的可以直接二分，单次查询时间复杂度 $O(nS\cdot log⁡n)$；边角的暴力查询，单次时间复杂度 $O(S)$。

对于修改操作，区间里的可以直接打修改标记，单次修改时间复杂度 $O(nS)$；边角的可以归并，单次时间复杂度 $O(S)$。

当 $S=\sqrt {n\log n}$ 时，总体最优，为单次 $O(\sqrt{n\log ⁡n})$。空间复杂度 $O(n)$。

考虑回到原问题。我们相当于对每层线段树结点，都要做上面的问题。

那么这样做的时间复杂度是 $O(m\sqrt{n\log n}+m\sqrt{\frac n 2\log\frac n 2}+m\sqrt{\frac n 4\log\frac n 4}+\cdots)=O(m\sqrt {n\log n})$。

目前足以通过此题。

Code：

#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
#define bel(x)((x-1)/B+1)
#define _L(x)(((x)-1)*B+1)
#define _R(x)((x)*B)
using namespace std;
typedef long long LL;
const int N=1e5+5;
inline int readint(){
    int c=getchar(),d=0,f=0;
    for(;!isdigit(c);c=getchar())f=c=='-';
    for(;isdigit(c);c=getchar())d=d*10+(c^'0');
    return f?-d:d;
}
int topA,topB;
pair<LL,int>A[N],C[N];
struct DataStructure{
    int*d,n,B,blocks,tp,lth;
    LL*tag;
    pair<LL,int>*b;
    inline void init(){
        B=sqrt(n*log(n))+1;B*=0.2;
        if(B<10)B=10;
        blocks=bel(n);
        b=new pair<LL,int>[n+2],d=new int[n+2];
        tag=new LL[blocks+2],tp=0;
        for(int i=0;i<=n+1;++i)d[i]=0,b[i]=make_pair(0LL,i);
        for(int i=0;i<=blocks+1;++i)tag[i]=0;
    }
    inline void merge(pair<LL,int>*t){
        int it0=1,it1=1;
        while(it0<=topA&&it1<=topB)if(A[it0].first<C[it1].first)*t++=A[it0++];else*t++=C[it1++];
        while(it0<=topA)*t++=A[it0++];
        while(it1<=topB)*t++=C[it1++];
    }
    void modify_(int l,int r,LL x){
        const int L=_L(bel(l)),R=min(_R(bel(r)),n);
        topA=topB=0;
        for(int i=L;i<=R;++i)
        if(l<=b[i].second&&b[i].second<=r)A[++topA]=make_pair(b[i].first+x,b[i].second);
        else C[++topB]=b[i];
        merge(b+L);
    }
    inline void modify_ALL(int l,int r,LL x){
        const int bL=bel(l),bR=bel(r);
        if(bL==bR)modify_(l,r,x);else{
            modify_(l,_R(bL),x);
            modify_(_L(bR),r,x);
            for(int i=bL+1;i<bR;++i)tag[i]+=x;
        }
    }
    inline void modify_one(int t,LL x){
        const int L=_L(bel(t)),R=min(_R(bel(t)),n);
        pair<LL,int>k;bool ok=0;
        if(x>=0){
            for(int i=L;i<=R;++i)if(!ok){
                if(b[i].second==t)ok=1,k=make_pair(b[i].first+x,b[i].second),--i;
            }else if(i==R||b[i+1].first>k.first){b[i]=k;break;}else b[i]=b[i+1];
        }else{
            for(int i=R;i>=L;--i)if(!ok){
                if(b[i].second==t)ok=1,k=make_pair(b[i].first+x,b[i].second),++i;
            }else if(i==L||b[i-1].first<k.first){b[i]=k;break;}else b[i]=b[i-1];
        }
    }
    void modify(int l,int r,int a){
        int L=upper_bound(d+1,d+n+1,l)-d-1;
        int R=lower_bound(d+1,d+n+1,r-lth+1)-d;
        if(L+1<=R-1)modify_ALL(L+1,R-1,(LL)a*lth);
        if(L&&R<=n&&L==R&&d[L]+lth-1>=l&&d[R]<=r){
            modify_one(L,(LL)a*(r-l+1));
        }else{
            if(L&&d[L]+lth-1>=l)modify_one(L,(LL)a*(d[L]+lth-l));
            if(R<=n&&d[R]<=r)modify_one(R,(LL)a*(r-d[R]+1));
        }
    }
    inline int query_(int l,int r,int x){
        const int bl=bel(l),L=_L(bl),R=min(_R(bl),n);
        if(b[L].first+tag[bl]>x)return 0;
        int res=0;
        for(int i=L;i<=R;++i)
        if(l<=b[i].second&&b[i].second<=r&&b[i].first+tag[bl]<=x)++res;
        return res;
    }
    inline int query_ALL(int l,int r,int x){
        const int bl=bel(l);
        if(b[l].first+tag[bl]>x)return 0;
        if(b[r].first+tag[bl]<=x)return r-l+1;
        int it=upper_bound(b+l,b+r+1,make_pair(x-tag[bl],114514))-b-l;
        return it;
    }
    int query(int l,int r,int x){
        int L=lower_bound(d+1,d+n+1,l)-d;
        int R=upper_bound(d+1,d+n+1,r-lth+1)-d-1;
        if(L<=R){
            int res=0;
            const int bL=bel(L),bR=bel(R);
            if(bL==bR)res=query_(L,R,x);else{
                res=query_(L,_R(bL),x)+query_(_L(bR),R,x);
                for(int i=bL+1;i<bR;++i)res+=query_ALL(_L(i),min(_R(i),n),x);
            }
            return res;
        }else return 0;
    }
}G[40];
int n,m,bid[N],nod;
inline void __(int l,int r){
    if(!bid[r-l+1])bid[r-l+1]=++nod,G[nod].lth=r-l+1;
    ++G[bid[r-l+1]].n;
    if(l<r){
        const int mid=l+r>>1;
        __(l,mid),__(mid+1,r);
    }
}
inline void build(int l,int r){
    G[bid[r-l+1]].d[++G[bid[r-l+1]].tp]=l;
    if(l<r){
        const int mid=l+r>>1;
        build(l,mid),build(mid+1,r);
    }
}
int main(){
    ios::sync_with_stdio(0),cout.tie(0);
    n=readint(),m=readint();
    __(1,n);
    for(int i=1;i<=nod;++i)G[i].init();
    build(1,n);
    while(m--){
        int op=readint(),l=readint(),r=readint(),a=readint();
        if(op==1){
            for(int i=1;i<=nod;++i)
            G[i].modify(l,r,a);
        }else{
            int ans=0;
            for(int i=1;i<=nod;++i)
            ans+=G[i].query(l,r,a);
            cout<<ans<<'\n';
        }
    }
    return 0;
}
Powered by Hexo
Theme - Material