题解：P17180 Canines Canines Paws Claws

· · 题解

简单题，但是赛时饭堂以为必须得使用矩阵加速就开摆了。

首先我们充分理解题意以后发现如果 k=0 的时候答案为 1，k>1 的时候答案为 2，k=1 的时候方案数我们考虑这样算。

我们让 d_i=A_i-A_{i-1}，初始时 \forall i,d_i=1。操作 0 等价于对于所有的 i\in[l,r],d_i=-d_i。现在我们来思考一下 50 分的做法。考虑 O(nm)，修改可以直接暴力修改，查询直接上一个线性 dp 就完事了。我们不妨设 dp_{i,0} 表示第 i 个位置选择 A_i+1 的方案数，dp_{i,1} 表示第 i 个位置选择 A_i-1 的方案数。我们注意到当 d_i=1 的时候，dp_{i,1} 可以从 dp_{i-1,0} 和 dp_{i-1,1} 转移过来，不懂的同学可以稍微自己画一下图。

总结一下转移式大概长这样：

\begin{cases} dp_{i,0}=dp_{i-1,0}+[d_i=-1]dp_{i-1,1}\\ dp_{i,1}=[d_i=1]dp_{i-1,0}+dp_{i-1,1} \end{cases}

接下来怎么优化？矩阵加速显然是一种好办法。但是赛后我经过深思后我决定使用动态开点线段树大法 （其实是因为不太会矩阵加速）。具体地，我们要怎么做呢？发现对于每个 i，只有两个 dp 值，为了方便，我们暂且就叫做 a 和 b。现在我们通过线段树维护区间 [l,r]，要维护以下信息：首先，我们肯定知道假如以 l 开始，a_l=b_l=1，我们考虑维护 a_r 和 b_r。但是区间该如何合并呢？这里有一个想法，将 a_r 和 b_r 的含义继续进行拆分，a_r 拆成 x_1 和 y_1，代表 a_r 含有 x_1 个 a_l，含有 y_1 个 b_l，x_2 和 y_2 含义为 b_r 的组成。这样两个区间合并时，我们发现右区间的 a_l 和 b_l 不再是原本的 1，而是变成了左区间的 a_r 和 b_r，所以我们就可以得出以下递推式（记左区间的 x_1 为 x_{l1}，右区间的 x_1 为 x_{r1}，其他的同理）：

\begin{cases} x_1=x_{r1}\times x_{l1}+y_{r1}\times x_{l2}\\ x_2=x_{r2}\times x_{l1}+y_{r2}\times x_{l2}\\ y_1=x_{r1}\times y_{l1}+y_{r1}\times y_{l2}\\ y_2=x_{r2}\times y_{l1}+y_{r2}\times y_{l2}\\ \end{cases}

意思大家自己体味一下吧，把定义搞懂这些就是显然的了。

需要注意一下的是我们还需要根据右区间的 d_l 来对左区间的 x_1、y_1、x_2、y_2 进行一次转移。

总结来说，就是前面的拆分成四个变量有点绕，稍微花点时间就能想通了，实现上有一些小细节，并且这道题目的空间卡得巨紧，你必须尽可能地压空间（其实我卡 80 分卡了老久 /ll）。

然后操作 0 等价于区间翻转，这一部分交给大家自行思考：区间反转后 x_1、y_1、x_2、y_2 会出现什么变化？

先展示一下一个线段树节点需要维护的有哪些东西：

struct node{
    int x1,y1,x2,y2;//分别表示 a_r 和 b_r 的含义（由几个 a_l、几个 b_l 组成）
    bool len,s,tag;//长度是否等于 1（push_up 时有边界需要特判），d_l 是 1 还是 -1，懒标记
}

还有这道题目不能全开 long long，空间卡得特别紧！！！特别特别紧！

时空复杂度都是 O(m\log n)，有常数。

upd：观察了一下矩阵加速的解法，发现我这种做法的本质就是矩阵加速。 :::success[code]


#include <bits/stdc++.h>
using namespace std;
using LL=long long;
#define mid (l+r>>1) 
const int mod=19990721,N=17000005;
struct node{int x1,y1,x2,y2;bool len,s,tag;}tree[N];
int m,op,ans,k,lh[N],rh[N],cnt;
LL n,l,r;
inline void push_up(node &p,node L,node R){
    node t=L;
    if(R.s==1) (t.x1+=t.x2)%=mod,(t.y1+=t.y2)%=mod; 
    else (t.x2+=t.x1)%=mod,(t.y2+=t.y1)%=mod;
    if(R.len!=1)
        p.x1=(1ll*R.x1*t.x1+1ll*R.y1*t.x2)%mod,p.x2=(1ll*R.x2*t.x1+1ll*R.y2*t.x2)%mod,
        p.y1=(1ll*R.x1*t.y1+1ll*R.y1*t.y2)%mod,p.y2=(1ll*R.x2*t.y1+1ll*R.y2*t.y2)%mod;
    else p=t;
    p.s=L.s,p.tag=p.len=0;
}
inline void f(node &p){swap(p.x1,p.x2),swap(p.y1,p.y2),swap(p.x1,p.y1),swap(p.x2,p.y2),p.s=p.s^1,p.tag=p.tag^1;}
inline void push_down(int p){
    if(!tree[p].tag) return;
    f(tree[lh[p]]);
    f(tree[rh[p]]);
    tree[p].tag=0;
}
inline void update(int p,LL l,LL r,LL nl,LL nr){
    if(l>nr||r<nl) return;
    if(l>=nl&&r<=nr){
        f(tree[p]);
        return;
    }
    if(!lh[p]) lh[p]=++cnt,tree[cnt]={1,mid-l,0,1,mid==l,1,0};
    if(!rh[p]) rh[p]=++cnt,tree[cnt]={1,r-mid-1,0,1,mid+1==r,1,0};
    push_down(p);
    update(lh[p],l,mid,nl,nr);
    update(rh[p],mid+1,r,nl,nr);
    push_up(tree[p],tree[lh[p]],tree[rh[p]]);
}
inline node query(int p,LL l,LL r,LL ql,LL qr){
    if(l>=ql&&r<=qr) return tree[p];
    if(!lh[p]) lh[p]=++cnt,tree[cnt]={1,mid-l,0,1,mid==l,1,0};
    if(!rh[p]) rh[p]=++cnt,tree[cnt]={1,r-mid-1,0,1,mid+1==r,1,0};
    push_down(p);
    if(mid>=qr) return query(lh[p],l,mid,ql,qr);
    if(mid<ql) return query(rh[p],mid+1,r,ql,qr);
    node res;
    push_up(res,query(lh[p],l,mid,ql,qr),query(rh[p],mid+1,r,ql,qr));
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    cnt=1;
    tree[1]={1,n-1,0,1,n,1,0};
    while(m--){
        cin>>op>>l>>r;
        l+=ans,r+=ans;
        if(op==0){
            l%=n,r%=n,l+=2,r+=2;
            if(r>n) r--;
            if(l<=r) update(1,1,n,l,r);
        }
        else{
            l%=n,r%=n,l++,r++,cin>>k;
            if(!k){
                cout<<(ans=1)<<'\n';
                continue;
            }
            if(k>1){
                cout<<(ans=2)<<'\n';
                continue;
            }
            node res=query(1,1,n,l,r);
            // cout<<res.x1<<' '<<res.y1<<' '<<res.x2<<' '<<res.y2<<'\n';;
            cout<<(ans=(1ll*res.x1+res.x2+res.y1+res.y2)%mod)<<'\n';
        }
    }
    return 0;
}