题解：P10284 [USACO24OPEN] Splitting Haybales P

· · 题解

首先根据题目的意思若 x\le 0，则 x=x+a_i，否则 x=x-a_i。

首先这个 x 是吓唬人的，可以先二分一次将范围缩成 2\times 10^5。

考虑分块，假设我们可以求出每一个 x 在经过一个整块后的值，我们就可以在 O(n\sqrt n) 的复杂度内查询。

而求这个东西正是 ARC149D，即对于一个值域区间 [l,r] 如果中间有 0，那么离 x 的端点可以往相反数建边并扔掉，因为可以通过相反数求得，直接打一个 tag 维护即可，最后 dfs 即可，注意 0 的一些细节。

这题卡空间，所以我们要离线处理所有询问然后一个块一个块处理，具体的可以看代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
const int N=2e5+10,len=447;
int a[N],n,m,tot;ll s[N];
inline ll get(int l,int r){return s[r]-s[l-1];}
struct node{int l,r,x;}q[N]; 
vector<int>xw[N],g[N];
int bl[N],L[N],R[N],mp[N],vis[N];
inline int get(int l,int r,int x){
    int tmpl=l,tmp=r,ans=-1;
    while(l<=r){int mid=l+r>>1;if (get(tmpl,mid)<=x) ans=mid,l=mid+1;else r=mid-1;}
    return ans;
}
inline void build(){
    tot=n/len;if (n%len) tot++;
    for (int i=1;i<=tot;i++) L[i]=R[i-1]+1,R[i]=i*len;R[tot]=n;
    for (int i=1;i<=n;i++) bl[i]=(i-1)/len+1;
}
void dfs(int u){for (auto v:g[u]){if (vis[u]) mp[v]=mp[u],vis[v]=1;else mp[v]=-mp[u];dfs(v);}}
inline void solve(){
    for (int k=1;k<=tot;k++){
        for (int i=0;i<N;i++) mp[i]=vis[i]=0,g[i].clear(); 
        int l=1,r=N-1,tag=0;
        for (int i=L[k];i<=R[k];i++) if (mp[0]>0) mp[0]-=a[i];else mp[0]+=a[i]; 
        for (int i=L[k];i<=R[k];i++){
            if (r+tag<=0) tag+=a[i];else tag-=a[i];
            if (l<=-tag&&-tag<=r){
                for (int j=i+1;j<=R[k];j++) if (mp[-tag]>0) mp[-tag]-=a[j];else mp[-tag]+=a[j];vis[-tag]=1;
                if (-tag-l<r+tag){
                    for (int i=l;i<-tag;i++) g[-tag*2-i].push_back(i);
                    l=-tag+1;
                }
                else{
                    for (int i=-tag+1;i<=r;i++) g[-tag*2-i].push_back(i);
                    r=-tag-1;
                }
            }
        } 
        for (int i=l;i<=r;i++){if (!mp[i]) mp[i]=i+tag;dfs(i);}
        for (int i=1;i<l;i++) if (vis[i]) dfs(i);for (int i=r+1;i<N;i++) if (vis[i]) dfs(i);
        for (auto id:xw[k]) if (q[id].x<0&&vis[-q[id].x]) q[id].x=mp[-q[id].x];else if (q[id].x<0&&!vis[-q[id].x]) q[id].x=-mp[-q[id].x];else q[id].x=mp[q[id].x];
    }
}
main(){
    n=read();
    for (int i=1;i<=n;i++) s[i]=s[i-1]+(a[i]=read());
    m=read();
    build();
    for (int i=1;i<=m;i++){
        int l=read(),r=read(),x=read();
        int tmp=get(l,r,abs(x));
        if (tmp!=-1){if (x<0) x+=get(l,tmp);else x-=get(l,tmp);l=tmp+1;}
        if (l<=r){
            if (bl[l]==bl[r]) for (int i=l;i<=r;i++) if (x>0) x-=a[i];else x+=a[i];
            else{
                for (int i=l;i<=R[bl[l]];i++) if (x>0) x-=a[i];else x+=a[i];
                for (int j=bl[l]+1;j<bl[r];j++) xw[j].push_back(i); 
            }
        }
        q[i]={l,r,x};
    }
    solve();
    for (int i=1;i<=m;i++){
        int l=q[i].l,r=q[i].r,x=q[i].x;
        if (l<=r&&bl[l]!=bl[r]) for (int i=L[bl[r]];i<=r;i++) if (x>0) x-=a[i];else x+=a[i];
        printf("%d\n",x);
    }
    return 0;
}