BZOJ4303：数列

浅谈\(K-D\) \(Tree\)：https://www.cnblogs.com/AKMer/p/10387266.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4303

把每个元素看成点\((i,a_i)\)即可，然后裸的正交范围打标记和查询。由于膜的是\(2^{29}\)，所以任由其自然溢出最后与\(2^{29}-1\)按位和输出即可。

时间复杂度：\(O(n\sqrt{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=5e4+5,inf=2e9,mo=(1<<29)-1;

int n,m,pps,opt,l,r,x,y,ans;

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct kd_tree {
    int root;

    struct TAG {
        int mul,add;

        TAG() {}

        TAG(int _mul,int _add) {
            mul=_mul,add=_add;
        }

        TAG operator+(const TAG &a)const {
            return TAG(mul*a.mul,add*a.mul+a.add);
        }
    };

    struct point {
        TAG tag;
        int c[2],mn[2],mx[2];
        int val,sum,cnt,ls,rs;

        bool operator<(const point &a)const {
            return c[pps]<a.c[pps];
        }
    }p[maxn];

    int build(int l,int r,int d) {
        int mid=(l+r)>>1,u=mid;pps=d;
        nth_element(p+l,p+mid,p+r+1);
        if(l<mid)p[u].ls=build(l,mid-1,d^1);
        if(r>mid)p[u].rs=build(mid+1,r,d^1);
        p[u].tag=TAG(1,0);
        int ls=p[u].ls,rs=p[u].rs;
        p[u].cnt=p[ls].cnt+1+p[rs].cnt;
        for(int i=0;i<2;i++) {
            int mn=min(p[ls].mn[i],p[rs].mn[i]);
            p[u].mn[i]=min(p[u].c[i],mn);
            int mx=max(p[ls].mx[i],p[rs].mx[i]);
            p[u].mx[i]=max(p[u].c[i],mx);
        }
        return u;
    }

    void prepare() {
        p[0].mn[0]=p[0].mn[1]=inf;
        p[0].mx[0]=p[0].mx[1]=-inf;
        for(int i=1;i<=n;i++)
            p[i].c[0]=i,p[i].c[1]=read();
        root=build(1,n,0);
    }

    void update(int u) {
        int ls=p[u].ls,rs=p[u].rs;
        p[u].sum=p[ls].sum+p[u].val+p[rs].sum;
    }

    void make_tag(int u,TAG a) {
        p[u].tag=p[u].tag+a;
        p[u].val=p[u].val*a.mul+a.add;
        p[u].sum=p[u].sum*a.mul+p[u].cnt*a.add;
    }

    void push_down(int u) {
        if(p[u].tag.mul==1&&p[u].tag.add==0)return;
        if(p[u].ls)make_tag(p[u].ls,p[u].tag);
        if(p[u].rs)make_tag(p[u].rs,p[u].tag);
        p[u].tag=TAG(1,0);
    }

    void change(int u) {
        if(r<p[u].mn[opt]||l>p[u].mx[opt])return;
        if(l<=p[u].mn[opt]&&p[u].mx[opt]<=r) {
            make_tag(u,TAG(x,y));return;
        }
        push_down(u);
        if(l<=p[u].c[opt]&&p[u].c[opt]<=r)
            p[u].val=p[u].val*x+y;
        if(p[u].ls)change(p[u].ls);
        if(p[u].rs)change(p[u].rs);
        update(u);
    }

    void query(int u) {
        if(r<p[u].mn[opt]||l>p[u].mx[opt])return;
        if(l<=p[u].mn[opt]&&p[u].mx[opt]<=r) {
            ans+=p[u].sum;return;
        }
        push_down(u);
        if(l<=p[u].c[opt]&&p[u].c[opt]<=r)ans+=p[u].val;
        if(p[u].ls)query(p[u].ls);
        if(p[u].rs)query(p[u].rs);
    }
}T;

int main() {
    n=read(),m=read();
    T.prepare();
    for(int i=1;i<=m;i++) {
        ans=0,opt=read(),l=read(),r=read();
        if(opt<2)x=read(),y=read(),T.change(T.root);
        else opt-=2,T.query(T.root),printf("%d\n",ans&mo);
    }
    return 0;
}

BZOJ4303：数列

原文：https://www.cnblogs.com/AKMer/p/10391894.html