P10284

· · 题解

讲个笑话，这题过了才发现保证了 a_1\geq a_2\geq \cdots a_n 的性质。

记 x 为两人干草数量的差，每次相当于：

我们可以先做一步预处理，因为 x 在第一次转变正负前是操作固定的，我们可以先二分出第一个转变正负的位置，那么此时必然有 |x|\leq 2\times 10^5，并且之后一直满足。

然后的做法和 P8264 基本相同，我们考虑分块，散块暴力操作，整块维护出每个初始值变成了啥。

我们初始令 [l,r]=[1,2\times 10^5]，表示当前还存在的值，那么当遇到一个 a_i 时，我们发现整体平移等价于平移原点，因此我们维护再维护当前的原点 p。

平移过后，我们考察一下，若两个点关于原点对称，那么他们最终变成的值也只有正负号的区别，因此我们不妨把他们合并成一个，可以把点的个数少的一边向另一边对应的点连边，并把小的一部分删掉，最后只需要遍历一下这个森林就能知道每个点的答案了。

原点的答案需要特殊处理一下，复杂度约为 O(qB+\frac{n}{B}(V+q))，一点不卡常。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=(f?-x:x);
}
int sign(LL x){return x>0;}
int n,m;
const int N = 2e5+7;
int a[N];
LL s[N];
inline LL f(LL x,LL v){return x>0?x-v:x+v;}
int ql[N],qr[N],qx[N];
int bel[N],B;
int fa[N],ans[N],spe[N];
int calc(int x,int l,int r)
{
    for(int i=l;i<=r;i++)x=f(x,a[i]);
    return x;
}
int vis[N],tag=0,tag2=0;
void get(int x)
{
    if(vis[x]==tag||spe[x]==tag2)return;
    vis[x]=tag;
    get(fa[x]);
    if(spe[fa[x]]==tag2)
    {
        ans[x]=ans[fa[x]];
        spe[x]=tag2;
    }
    else
    {
        ans[x]=-ans[fa[x]];
    }
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        s[i]=s[i-1]+a[i];
    }
    read(m);
    for(int i=1;i<=m;i++)
    {
        int L,R;
        LL x;
        read(L);read(R);read(x);
        int l=L,r=R,pos=l-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(sign(x)==sign(f(x,s[mid]-s[L-1])))
            {
                pos=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        x=f(x,s[pos]-s[L-1]);
        ql[i]=pos+1;qr[i]=R;qx[i]=x;
    }
    B=sqrt(n);
    for(int al=1;al<=n;al+=B)
    {
        ++tag;
        ++tag2;
        int ar=min(n,al+B-1);
        int l=1,r=2e5,p=0;
        ans[0]=calc(0,al,ar);vis[0]=tag;spe[0]=tag2;
        for(int i=l;i<=r;i++)fa[i]=i;
        for(int i=al;i<=ar;i++)
        {
            int x=a[i];
            if(p<l)p+=x;
            else if(p>r)p-=x;
            if(p<l||p>r)continue;
            ans[p]=calc(0,i+1,ar);
            vis[p]=tag;spe[p]=tag2;
            if(p-l<r-p)
            {
                for(int i=l;i<p;i++)fa[i]=2*p-i;
                l=p+1;
            }
            else
            {
                for(int i=r;i>p;i--)fa[i]=2*p-i;
                r=p-1;
            }
        }
        for(int i=l;i<=r;i++)ans[i]=i-p,vis[i]=tag;
        for(int i=1;i<=m;i++)
        {
            if(qr[i]<al||ql[i]>ar)continue;
            if(ql[i]<=al&&ar<=qr[i])
            {
                if(qx[i]==0)qx[i]=ans[0];
                else
                {
                    int v=abs(qx[i]);
                    get(v);
                    if(spe[v]==tag2)qx[i]=ans[v];
                    else
                    {
                        if(qx[i]<0)qx[i]=-ans[v];
                        else qx[i]=ans[v];
                    }
                }
                continue;
            }
            for(int j=max(al,ql[i]);j<=min(ar,qr[i]);j++)qx[i]=f(qx[i],a[j]);
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",qx[i]);
    return 0;
}