P9069 [Ynoi Easy Round 2022] 堕天作战题解

许多 · 2023-04-21 19:30:14 · 题解
倍增值域分块模板题，~~但因为我太菜了，调了好长时间~~。
分析题意可知，当 a_i\leq 0 时，无论 x 取何值，它都必定会减 x，这一点很好分析。所以我们单独用一棵线段树维护这种情况。
倍增值域分块的核心就在于对于值域在 [len^{i-1}+1,len^i] 中的数分为一个块，用线段树维护每一个块，不难看出，我们一共需要 \log_{len}n 棵线段树。
对于修改操作，我们进行以下判断:
当当前最大值 <v 时，将其全部删去，插入到维护负数的线段树中。
当当前最小值 >v 时，暴力枚举所有会掉出当前块的数，进行暴力删除。
更多细节见代码。
code

#include<bits/stdc++.h>
#include<cstdio>
#define N 555555
#define M 8
#define inf 1e12
#define mod (1<<20)
#define LL long long
#define ULL unsigned long long
#define len 22 
inline LL read() {
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
using namespace std;
LL n,m,lastans=0;
LL a[N],la[N];//这是初始时的值（之后就没用到了
inline void init(){
    la[0]=1;
    for(int i=1;i<M;i++)la[i]=la[i-1]*len;
    return ;
}
struct two {
    LL smin;//最小值
    LL xw;//最小值位置
};
struct node {
    LL sum,smax,tag;//分别是：区间数字个数，区间最大值，懒标记
    LL ans,summin;//区间和，区间最小值个数 
    two in;
} tree[M][N<<2]; //tree[s][now]s为第几颗线段树，now为当前节点
inline void sum(LL now,LL s) { //上传（很多人把这个写成pushup
    tree[s][now].ans=tree[s][now<<1].ans+tree[s][now<<1|1].ans;//个数上传
    tree[s][now].sum=tree[s][now<<1].sum+tree[s][now<<1|1].sum;//总和上传
    tree[s][now].smax=max(tree[s][now<<1].smax,tree[s][now<<1|1].smax);//区间最大值上传
    if(tree[s][now<<1].in.smin<tree[s][now<<1|1].in.smin) {
        tree[s][now].in=tree[s][now<<1].in;
        tree[s][now].summin=tree[s][now<<1].summin;
    } else if(tree[s][now<<1].in.smin>tree[s][now<<1|1].in.smin){
        tree[s][now].in=tree[s][now<<1|1].in;
        tree[s][now].summin=tree[s][now<<1|1].summin;
    }
    else {
        tree[s][now].in=tree[s][now<<1].in;
        tree[s][now].summin=tree[s][now<<1].summin+tree[s][now<<1|1].summin;
    }
    return ;
}
inline void SW(LL now,LL s) {//这个是删除当前节点 
    tree[s][now].tag=0;
    tree[s][now].sum=0;
    tree[s][now].smax=-inf;
    tree[s][now].in.smin=inf;
    tree[s][now].ans=0;
    tree[s][now].summin=0;
    return ;
}
inline void build(LL l,LL r,LL now,LL s) { //建树，这里的s及下面函数的s 表示第几棵线段树
    if(l==r) {
        //特判s=0的情况，防止出现玄学错误
        if((s==0&&a[l]==0)||(s!=0&&(la[s-1])<=a[l]&&a[l]<(la[s]))) {
            tree[s][now].sum=1;
            tree[s][now].smax=tree[s][now].ans=tree[s][now].in.smin=a[l];
            tree[s][now].in.xw=l;
            tree[s][now].summin=1;
        } else 
            SW(now,s);
        return ;
    }
    LL mid=l+r>>1;
    build(l,mid,now<<1,s);
    build(mid+1,r,now<<1|1,s);
    sum(now,s);
    return ;
}//对于不会线段树的，我只能说：您真勇 
inline void add(LL l,LL r,LL now,LL s,LL v) {//区间加（我知道操作是减，自己看其他函数。 
    if(tree[s][now].sum==0)return ;
    tree[s][now].tag+=v;
    tree[s][now].in.smin+=v;
    tree[s][now].smax+=v;
    tree[s][now].ans+=tree[s][now].sum*v;//这里用sum*v，不是(r-l+1)*v 
    return ;
}
inline void pushdown(LL l,LL r,LL now,LL s) {//下传懒标记 
    if(tree[s][now].smax==-inf) {//特判点已经被删了的情况 
        SW(now<<1,s),SW(now<<1|1,s);
        return ;
    }
    if(!tree[s][now].tag)return ;
    LL mid=l+r>>1;
    add(l,mid,now<<1,s,tree[s][now].tag);
    add(mid+1,r,now<<1|1,s,tree[s][now].tag);
    tree[s][now].tag=0;
    return ;
}
inline void modify_j(LL l,LL r,LL now,LL s,LL x,LL y,LL v) {
    if(tree[s][now].sum==0)return ;//防止出现玄学错误 
    if(l>=x&&r<=y)return add(l,r,now,s,-v);//细节，这里是-v 
    pushdown(l,r,now,s);
    LL mid=l+r>>1;
    if(x<=mid)modify_j(l,mid,now<<1,s,x,y,v);
    if(y>mid)modify_j(mid+1,r,now<<1|1,s,x,y,v);
    return sum(now,s);
}
inline two query_min(LL l,LL r,LL now,LL s,LL x,LL y) {
    if(l>=x&&r<=y)return tree[s][now].in;//我们直接返回这个东东，方便我们删除 
    pushdown(l,r,now,s);
    LL mid=l+r>>1;
    two cnt;
    cnt.smin=inf;
    if(x<=mid) {
        two linshi=query_min(l,mid,now<<1,s,x,y);
        cnt=linshi;
    }
    if(y>mid) {
        two linshi=query_min(mid+1,r,now<<1|1,s,x,y);
        if(linshi.smin<cnt.smin)cnt=linshi;
    }
    return cnt;
}
inline LL query_max(LL l,LL r,LL now,LL s,LL x,LL y) {
    if(tree[s][now].sum==0)return -inf;//注意细节 
    if(l>=x&&r<=y)return tree[s][now].smax;
    pushdown(l,r,now,s);
    LL mid=l+r>>1,cnt=-inf;
    if(x<=mid)cnt=query_max(l,mid,now<<1,s,x,y);
    if(y>mid)cnt=max(cnt,query_max(mid+1,r,now<<1|1,s,x,y));
    return cnt;
}
inline void tree_push(LL l,LL r,LL now,LL s,LL x,LL v) {//加入新点 
    if(l==r) {
        tree[s][now].sum=1;
        tree[s][now].smax=tree[s][now].ans=tree[s][now].in.smin=v;
        tree[s][now].in.xw=l;tree[s][now].summin=1;
        return ;
    }
    pushdown(l,r,now,s);
    LL mid=l+r>>1;
    if(x<=mid)tree_push(l,mid,now<<1,s,x,v);
    else tree_push(mid+1,r,now<<1|1,s,x,v);
    return sum(now,s);
}
inline void del_all(LL l,LL r,LL now,LL s,LL x,LL y,LL v) {//区间删除，这个时候必定是出现了负数，要插入到线段树0的情况  
    if(tree[s][now].sum==0)return ;//至于我为什么不暴力枚举，一个一个用del删除 ，主要原因是怕被卡常 
    if(l==r) {
        tree_push(1,n,1,0,l,tree[s][now].smax-v);
        SW(now,s);
        return ;
    }
    LL mid=l+r>>1;
    pushdown(l,r,now,s);
    if(x<=mid)del_all(l,mid,now<<1,s,x,y,v);
    if(y>mid)del_all(mid+1,r,now<<1|1,s,x,y,v);
    return sum(now,s);
}
inline void del(LL l,LL r,LL now,LL s,LL x,LL v) {//删除单点 
    if(l==r) {
        LL nowv=tree[s][now].smax-v;
        SW(now,s);
        if(nowv<0) {
            tree_push(1,n,1,0,x,nowv);
            return ;
        }
        for(LL i=1; i<s; i++)//查看被减之后调到了什么块中 
            if((la[i-1])<=nowv&&nowv<(la[i])) {
                tree_push(1,n,1,i,x,nowv);
                break;
            }
        return ;
    }
    LL mid=l+r>>1;
    pushdown(l,r,now,s);
    if(x<=mid)del(l,mid,now<<1,s,x,v);
    else del(mid+1,r,now<<1|1,s,x,v);
    return sum(now,s);
}
inline void modify_all(LL l,LL r,LL now,LL s,LL x,LL y,LL v) {
    if(tree[s][now].sum==0)return ;
    if(l>=x&&r<=y) {
        if(tree[s][now].smax<v)return del_all(1,n,1,s,l,r,v);
        if(tree[s][now].in.smin>v) {
            while(tree[s][now].in.smin-v<(la[s-1]))del(1,n,1,s,tree[s][now].in.xw,v);
            add(l,r,now,s,-v);
            return; 
        }
        if(tree[s][now].in.smin==v&&tree[s][now].summin==tree[s][now].sum)return ;//不写这句会被卡 
        if(l==r) {
            if(tree[s][now].ans==v)return ;
            if(tree[s][now].ans<v)return del_all(1,n,1,s,l,r,v);
            if(tree[s][now].ans-v<(la[s-1]))return del(1,n,1,s,l,v);
            return add(l,r,now,s,-v);
        }
        LL mid=l+r>>1;
        pushdown(l,r,now,s);
        modify_all(l,mid,now<<1,s,x,y,v);
        modify_all(mid+1,r,now<<1|1,s,x,y,v);
        return sum(now,s);
    }
    pushdown(l,r,now,s);
    LL mid=l+r>>1;
    if(x<=mid)modify_all(l,mid,now<<1,s,x,y,v);
    if(y>mid)modify_all(mid+1,r,now<<1|1,s,x,y,v);
    return sum(now,s);
}
inline ULL query_ans(LL l,LL r,LL now,LL s,LL x,LL y) {
    if(tree[s][now].sum==0)return 0ll;
    if(l>=x&&r<=y)return tree[s][now].ans;
    pushdown(l,r,now,s);
    LL mid=l+r>>1;
    ULL aans=0;
    if(x<=mid)aans=query_ans(l,mid,now<<1,s,x,y);
    if(y>mid) aans+=query_ans(mid+1,r,now<<1|1,s,x,y);
    return aans;
}
int main() {
    n=read();m=read();
    init();
    for(LL i=1; i<=n; i++)
        a[i]=read();
    for(LL i=0; i<M; i++) //i=0时 ，这棵线段树维护0及负数。 因为修改的x>=0 ,而等于0时没有任何影响。
        build(1,n,1,i);//i!=0时，这棵线段树维护的值域为2^(i-1)——(2^i)
    while(m--) {
        LL op=read();
        if(op==1) {
            LL l=read()^lastans,r=read()^lastans,x=read()^lastans;
            if(!x)continue;
            modify_j(1,n,1,0,l,r,x);
            for(LL j=1; j<M; j++) 
                modify_all(1,n,1,j,l,r,x);
                //太毒瘤了！
        }
        if(op==2) {
            LL l=read()^lastans,r=read()^lastans;
            ULL ANS=0;
            for(LL j=0; j<M; j++)
                ANS+=query_ans(1,n,1,j,l,r);
            lastans=(long long)(ANS%mod);
            printf("%llu\n",ANS);
        }
    }
    return 0;
}
P9069 [Ynoi Easy Round 2022] 堕天作战 题解

code

P9069 [Ynoi Easy Round 2022] 堕天作战题解
