【清华集训2014】玄学 | Mrsrz's blog

线段树

题目大意：

给定一个长度为 $n$ 的数组 $x_1,x_2,\ldots,x_n$ 和 $m$，有 $q$ 个操作，分为如下两种：

1. 给定 $s,t,a,b$，如果这是第 $i$ 个 $1$ 操作，就称其为第 $i$ 个计划。
2. 给定 $l,r,k$，令 $x=x_k$，依次考虑第 $l$ 到第 $r$ 个计划，若 $s\leq k\leq t$，则令 $x=(ax+b)\bmod m$。输出最终的 $x$。

强制在线。保证最多 $10^5$ 个计划。

题解：

考虑对所有计划建线段树。

对线段树的每个结点，我们记录若干个三元组 $(k,a,b)$，并按照 $k$ 从小到大排序。其中，第 $i$ 个三元组 $(k_i,a_i,b_i)$ 表示 $[k_{i-1},k_i]$ 这些编号的数 $x$，经过这个结点后会变成 $a_ix+b_i$（规定 $k_0=0$）。

查询比较简单，直接在线段树上按时间顺序找到对应的结点，然后在结点上二分即可。

考虑新加入一个计划，每次暴力地将这个计划到线段树根路径上所有点都更新一遍显然是不可行的。

注意到一个线段树结点上的值用于询问时，这个结点代表的区间的计划一定都已经插入过了，因此对每个线段树结点，我们只在它最后一个元素插入的时候更新它的信息即可。

更新信息的时候采用归并即可。

设修改次数为 $k$，时间复杂度 $O(q\log^2 k)$，常数较小。

空间复杂度 $O(k\log k)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=6e5+5,D=1e5;
int tim,n,m,md,a[N],lst,T;
struct data{
    int r,a,b;
    inline bool operator<(const data&rhs)const{return r<rhs.r;}
    inline int get(int x){return((LL)a*x+b)%md;}
};
typedef vector<data>VD;
VD v[N<<2];
void merge(VD&V,VD&X,VD&Y){
    int itX=0,itY=0;
    while(itX!=(int)X.size()&&itY!=(int)Y.size()){
        int a=X[itX].a*(LL)Y[itY].a%md;
        int b=((LL)Y[itY].a*X[itX].b+Y[itY].b)%md;
        V.push_back((data){min(X[itX].r,Y[itY].r),a,b});
        if(X[itX].r<Y[itY].r)++itX;
        else if(X[itX].r>Y[itY].r)++itY;
        else ++itX,++itY;
    }
}
void add(int l,int r,int o,const int&p,const int&L,const int&R,const int&a,const int&b){
    if(l==r)
    v[o].push_back((data){L-1,1,0}),v[o].push_back((data){R,a,b}),v[o].push_back((data){n+1,1,0});
    else{
        const int mid=(l+r)>>1;
        if(p<=mid)add(l,mid,o<<1,p,L,R,a,b);
        else add(mid+1,r,o<<1|1,p,L,R,a,b);
        if(p==r)merge(v[o],v[o<<1],v[o<<1|1]);
    }
}
void query(int l,int r,int o,const int&L,const int&R,const int&id,int&res){
    if(L<=l&&r<=R){
        res=lower_bound(v[o].begin(),v[o].end(),(data){id})->get(res);
        return;
    }
    const int mid=(l+r)>>1;
    if(L<=mid)query(l,mid,o<<1,L,R,id,res);
    if(mid<R)query(mid+1,r,o<<1|1,L,R,id,res);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T>>n>>md;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(cin>>m;m--;){
        int op;
        cin>>op;
        if(op==1){
            int l,r,a,b;
            cin>>l>>r>>a>>b;
            ++tim;
            add(1,D,1,tim,l^lst,r^lst,a,b);
        }else{
            int l,r,id;
            cin>>l>>r>>id;
            l^=lst,r^=lst,id^=lst;
            int res=a[id];
            query(1,D,1,l,r,id,res);
            lst=res;
            cout<<res<<'\n';
        }
        if(!(T&1))lst=0;
    }
    return 0;
}