题解：CF2077E Another Folding Strip

· · 题解

线性做法看不太懂，这里是一个 \log 的做法(/kel)。

显然一次折叠会使得若干位置的 a_i 减一，考察这个位置集合的性质。

考虑这个位置集合中相邻的两个元素，它们之间至多只能存在一条折痕，同时由于折痕只能存在于两个相邻格子中间，因此这相邻的两个元素的奇偶性一定是不同的。

同时，只要这个位置集合满足相邻的两个元素的奇偶性都不同，就一定是可以被构造出来的（从前往后依次折叠即可）。

于是问题变成了，每次操作选定一个子序列 -1，满足子序列相邻两项坐标奇偶性不同，用最少的操作次数覆盖完 a。

这个问题就非常类似于积木大赛之类的套路，维护前面偶数结尾位置和奇数结尾位置可以延过来多少个子序列 c_0,c_1，然后对一个 a_i，以 i 为奇数为例（偶数同理）：

这样就可以线性地跑出一个序列的答案。

对所有区间来求，考虑从前面扫描到后面，对每个 a_i 求出它对答案的贡献。

具体来说，每个区间起点 l 到当前位置 i 的时候，其 c_{0,l},c_{1,l} 都是确定的，于是 a_i 的操作就可以写为（以 i,l 的奇偶性相同的情况为例）：

于是多个 l 的操作就可以同时进行，维护四颗权值线段树分别维护所有起点是偶数/奇数的 c_{0/1}。

那么就要维护以下操作：

所有权值 +d 相当于位移，不好操作，所以维护一个基准点表示 0 的位置，这样就变成了基准点的移动。

最后求出 a_i 的贡献之后，区间右端点可以在 [i,n] 中取，因此还要乘上 n-i+1 再加到答案中。

时间复杂度 O(\sum n\log W)(W=\sum a_i)。

好像要卡一下空间。

struct seg_tree{ int rt; ll d; } T[2][2];
inline void pushdown(int now){
    if (tag[now]){
        if (ls[now]) cnt[ls[now]]=sum[ls[now]]=0,tag[ls[now]]=1;
        if (rs[now]) cnt[rs[now]]=sum[rs[now]]=0,tag[rs[now]]=1;
        tag[now]=0;
    }
}
void update(int& now, ll l, ll r, ll x, int y){
    if (!now) now=++tsiz;
    cnt[now]+=y,sum[now]=(sum[now]+1ll*x%mod*y%mod+mod)%mod;
    if (l==r) return;
    ll mid=(l+r)>>1; pushdown(now);
    mid>=x?update(ls[now],l,mid,x,y):update(rs[now],mid+1,r,x,y);
}
pair<int,int> query(int now, ll l, ll r, ll x, ll y){
    if (!now) return make_pair(0,0);
    if (l==x && r==y){
        int d1=cnt[now],d2=sum[now];
        cnt[now]=sum[now]=0,tag[now]=1;
        return {d1,d2};
    }
    ll mid=(l+r)>>1; pushdown(now);
    if (mid>=y){
        auto P=query(ls[now],l,mid,x,y);
        cnt[now]=cnt[ls[now]]+cnt[rs[now]];
        sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
        return P;
    } else
    if (mid<x){
        auto P=query(rs[now],mid+1,r,x,y);
        cnt[now]=cnt[ls[now]]+cnt[rs[now]];
        sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
        return P;
    } else {
        auto P1=query(ls[now],l,mid,x,mid),P2=query(rs[now],mid+1,r,mid+1,y);
        cnt[now]=cnt[ls[now]]+cnt[rs[now]];
        sum[now]=(sum[ls[now]]+sum[rs[now]])%mod;
        return {P1.first+P2.first,(P1.second+P2.second)%mod};
    }
}
//求区间中的权值个数和权值之和，在查询完之后直接删除这部分
int main(){
    for (cin>>Tc; Tc; Tc--){
        scanf("%d",&n); int ans=0;

        for (int i=1; i<=n; i++){
            scanf("%d",&x);
            update(T[i&1][0].rt,-L,L,T[i&1][0].d,1);
            update(T[i&1][1].rt,-L,L,T[i&1][1].d,1);

            int res=0;
            auto P0=query(T[i&1][0].rt,-L,L,T[i&1][0].d,T[i&1][0].d+x);
            int c0=P0.first,s0=P0.second;
            res=(res+1ll*c0*(x+T[i&1][0].d%mod)+mod-s0)%mod;
            T[i&1][1].d-=x; T[i&1][0].d+=x;
            update(T[i&1][0].rt,-L,L,T[i&1][0].d,c0);

            auto P1=query(T[(i&1)^1][1].rt,-L,L,T[(i&1)^1][1].d,T[(i&1)^1][1].d+x);
            int c1=P1.first,s1=P1.second;
            res=(res+1ll*c1*(x+T[(i&1)^1][1].d%mod)+mod-s1)%mod;
            T[(i&1)^1][0].d-=x; T[(i&1)^1][1].d+=x;
            update(T[(i&1)^1][1].rt,-L,L,T[(i&1)^1][1].d,c1);

            ans=(ans+1ll*(res%mod+mod)*(n-i+1))%mod;
        }
        printf("%d\n",ans);

        for (int i=1; i<=tsiz; i++) ls[i]=rs[i]=cnt[i]=sum[i]=tag[i]=0;
        tsiz=T[0][0].d=T[0][0].rt=T[0][1].d=T[0][1].rt=T[1][0].d=T[1][0].rt=T[1][1].d=T[1][1].rt=0;
    }
}