题解：CF717F Heroes of Making Magic III

· · 题解

思维好题，在 duel 的时候击杀了此题。

假设没有区间修改，只问一次是否可以击杀 [1,n] 内所有小怪。

容易发现“从区间一端走到另一端”完全可以变成从左边走到右边，因为路径是可逆的。

假定我们的路径出发点是 0（因为要先走到 1），终点是 n。容易发现角色行走的路径是 S 形。我们可以把每次拐弯的点记录下来，这样，每段直走的路径，除了这段路径的出发点，每个位置都会打一次怪。

我们把这个对每段路径，做区间 +1 的操作改为在差分数组上处理，那么就会变成这样：

其中最左边是 0，最右边是 n+1，图中是 n=4，a=\{2,3,2,1\} 的一种合法路径。

容易发现：除了 1 位置会额外 +1，n+1 位置额外 -1（不过 n+1 位置在对差分做前缀和的时候一般是无效的），其余的都是形如对相邻两个位置 \pm 1。

进一步发现，一组 +1 和一组 -1 是成对出现的，且 +1 的位置在 -1 之前。

我们考虑对于一个位置 i，给 i,i+1 位置 +1，给 i+1,i+2 位置 -1，这样 i+1 位置的操作抵消，就相当于可以给 i,i+2 位置分别 +1,-1。

所以问题变为：对 a 求差分数组 b，在将 b_1 减去额外 1 的贡献之后，能否通过给 i,i+2 位置分别 +1,-1 的操作，让 b 变为全 0。

显然可以对位置的奇偶情况讨论，然后处理。

回到原问题，会发现线段树很好维护这些操作。特判 l=r 即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=3e5+5;
int n,a[N],q;
namespace sgm{
    int m[2];
    struct sgm{
        #define lc (x<<1)
        #define rc (x<<1|1)
        #define mid ((l+r)>>1)
        int v[N],mn[N<<2],tag[N<<2];
        void build(int x,int l,int r){
            if (l==r){
                mn[x]=v[l];
                return;
            }
            build(lc,l,mid);
            build(rc,mid+1,r);
            mn[x]=min(mn[lc],mn[rc]);
        }
        void modify(int x,int l,int r,int ql,int qr,int k){
            if (ql<=l&&r<=qr){
                mn[x]+=k,tag[x]+=k;
                return;
            }
            mn[lc]+=tag[x],mn[rc]+=tag[x];
            tag[lc]+=tag[x],tag[rc]+=tag[x];
            tag[x]=0;
            if (ql<=mid)
                modify(lc,l,mid,ql,qr,k);
            if (qr>mid)
                modify(rc,mid+1,r,ql,qr,k);
            mn[x]=min(mn[lc],mn[rc]);
        }
        int query(int x,int l,int r,int ql,int qr){
            if (ql<=l&&r<=qr)
                return mn[x];
            mn[lc]+=tag[x],mn[rc]+=tag[x];
            tag[lc]+=tag[x],tag[rc]+=tag[x];
            tag[x]=0;
            int rt=1e18;
            if (ql<=mid)
                rt=min(rt,query(lc,l,mid,ql,qr));
            if (qr>mid)
                rt=min(rt,query(rc,mid+1,r,ql,qr));
            return rt;
        }
    }f[2];
}
using namespace sgm;
namespace bit{
    int c[N];
    void add(int x,int k){
        for (;x<=n;x+=(x&-x))
            c[x]+=k;
    }
    int query(int x){
        int rs=0;
        for (;x;x-=(x&-x))
            rs+=c[x];
        return rs;
    }
}
using namespace bit;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    fo(i,1,n)
        cin>>a[i];
    ro(i,n,1){
        a[i]-=a[i-1];
        add(i,a[i]);
    }
    fo(i,1,(n+1)/2){
        f[1].v[i]=a[i*2-1];
        f[1].v[i]+=f[1].v[i-1];
    }
    fo(i,1,n/2){
        f[0].v[i]=a[i*2];
        f[0].v[i]+=f[0].v[i-1];
    }
    m[0]=n/2,m[1]=(n+1)/2;
    f[0].build(1,1,m[0]);
    f[1].build(1,1,m[1]);
    cin>>q;
    while (q--){
        int op;
        cin>>op;
        if (op==1){
            int l,r,k;
            cin>>l>>r>>k;
            l++,r++;
            int l0=l,r0=r;
            l0+=(l0&1),r0-=(r0&1);
            l0/=2,r0/=2;
            int l1=l,r1=r;
            l1+=(l1&1^1),r1-=(r1&1^1);
            l1=(l1+1)/2,r1=(r1+1)/2;
            if (l&1)
                f[1].modify(1,1,m[1],l1,m[1],k);
            else f[0].modify(1,1,m[0],l0,m[0],k);
            if (r&1){
                if (r0<m[0])
                    f[0].modify(1,1,m[0],r0+1,m[0],-k);
            }
            else if (r1<m[1])
                f[1].modify(1,1,m[1],r1+1,m[1],-k);
            add(l,k),add(r+1,-k);
        }
        else{
            int l,r;
            cin>>l>>r;
            l++,r++;
            if (l==r){
                if (query(l)<=1)
                    cout<<"1\n";
                else cout<<"0\n";
                continue;
            }
            int l0=l,r0=r;
            l0+=(l0&1),r0-=(r0&1);
            l0/=2,r0/=2;
            int l1=l,r1=r;
            l1+=(l1&1^1),r1-=(r1&1^1);
            l1=(l1+1)/2,r1=(r1+1)/2;
            int lm0=0,lm1=0;
            if (l>1){
                if (l&1^1){
                    lm0-=f[1].query(1,1,m[1],l1-1,l1-1);
                    lm1+=f[1].query(1,1,m[1],l1-1,l1-1);
                }
                else{
                    lm0+=f[0].query(1,1,m[0],l0-1,l0-1);
                    lm1-=f[0].query(1,1,m[0],l0-1,l0-1);
                }
            }
            bool sb=1;
            sb&=(f[0].query(1,1,m[0],l0,r0)>=lm0+(l&1^1));
            sb&=(f[1].query(1,1,m[1],l1,r1)>=lm1+(l&1));
            if (r&1^1)
                sb&=(f[0].query(1,1,m[0],r0,r0)==lm0+(l&1^1));
            else sb&=(f[1].query(1,1,m[1],r1,r1)==lm1+(l&1));
            cout<<sb<<'\n';
        }
    }
    return 0;
}