Solution

A.

一共有\(T\)组数据

每次询问你\([l,r]\)中有多少个数能被他的所有数位整除（如果数位中含有\(0\)忽略掉）

数位dp，咕咕咕

B.

题面略

考虑一个个只有两个元素组成的小区间

可以发现若选择\([l,l+1]\)，则必定要选择一个最大的区间包含\([a[l],a[l+1]]\)的区间

每个小区间看成一个点，向它所要求必须要选择的点连边，线段树优化建图

对图进行tarjan缩点，然后拓扑排序即可

全是区间询问，大概要有5棵线段树的样子

其实有简单得多的解法。

为了方便，考虑初始情况线段树的第i个叶子的val值是i

从左到右，如果当前数是\(x\)，位置为\(j\)，且\(x-1\)的位置小于当前位置（假设是\(k\)），那么\([1,k]\)区间加1，\(x+1\)同理

每对相邻数字只会被算一次

这样每次就能维护以左边每个点做左端点，当前点做为右端点，中间能有多少个点连续

找到最大的val值为\(j\)的左端点，就是以该点做右端点的答案了

C.

题面略

经过一波推导可得：\(a_i=x_{i+1}x_i-c_1(c_2-c_1)\)

所以分块+矩阵快速幂就完事了

没开ll会re，虽然到最后也不知道到底是哪里没开ll

Code 

/*    B 2019/3/18 */#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=1e5+5;int N,Q,a[MN],b[MN],ls[MN*3],rs[MN*3],tt,root,minb[MN<<2],maxb[MN<<2];struct edge{int to,nex;}e[MN<<4];int en,hr[MN*3];inline void ins(int f,int t){e[++en]=(edge){t,hr[f]};hr[f]=en;} inline void build(int &x,int l,int r){    if(l==r){x=l;return;}register int mid=(l+r)>>1;    x=++tt;build(ls[x],l,mid);build(rs[x],mid+1,r);    ins(x,ls[x]);ins(x,rs[x]);}inline void Build(int x,int l,int r){    if(l==r){minb[x]=maxb[x]=b[l];return;}int mid=(l+r)>>1;    Build(x<<1,l,mid);Build(x<<1|1,mid+1,r);    minb[x]=min(minb[x<<1],minb[x<<1|1]);    maxb[x]=max(maxb[x<<1],maxb[x<<1|1]);}inline int qmi(int x,int l,int r,int a,int b){    if(a==l&&b==r)return minb[x];int mid=(l+r)>>1;    if(b<=mid) return qmi(x<<1,l,mid,a,b);    else if(a>mid) return qmi(x<<1|1,mid+1,r,a,b);    return min(qmi(x<<1,l,mid,a,mid),qmi(x<<1|1,mid+1,r,mid+1,b)); }inline int qma(int x,int l,int r,int a,int b){    if(a==l&&b==r)return maxb[x];int mid=(l+r)>>1;    if(b<=mid) return qma(x<<1,l,mid,a,b);    else if(a>mid) return qma(x<<1|1,mid+1,r,a,b);    return max(qma(x<<1,l,mid,a,mid),qma(x<<1|1,mid+1,r,mid+1,b));}inline void Insert(int x,int l,int r,int a,int b,int t){    if(l==a&&r==b){ins(t,x);return;}    int mid=(l+r)>>1;    if(b<=mid) Insert(ls[x],l,mid,a,b,t);    else if(a>mid) Insert(rs[x],mid+1,r,a,b,t);    else Insert(ls[x],l,mid,a,mid,t),Insert(rs[x],mid+1,r,mid+1,b,t); }int bel[MN*3],Mi[MN*3],Ma[MN*3],dfn[MN*3],low[MN*3],dind,st[MN*3],tp,bl;int getv(int x){if(x>N)return 0;return x;}bool in[MN*3];inline void rwi(int &x,int y){if(y
     
      x)x=y;}void tj(int x){    dfn[x]=low[x]=++dind;st[tp++]=x;in[x]=true;    register int i;    for(i=hr[x];i;i=e[i].nex)     {        if(!dfn[e[i].to]) tj(e[i].to),low[x]=min(low[x],low[e[i].to]);        else if(in[e[i].to])low[x]=min(low[x],low[e[i].to]);    }    if(low[x]==dfn[x])    {        ++bl;        for(;st[tp]!=x;in[st[--tp]]=false)bel[st[tp-1]]=bl,rwi(Mi[bl],st[tp-1]),rwa(Ma[bl],getv(st[tp-1]));    }}inline void Built(int x,int l,int r){    if(l==r){minb[x]=Mi[bel[l]];maxb[x]=Ma[bel[l]];return;}    register int mid=(l+r)>>1;    Built(x<<1,l,mid);Built(x<<1|1,mid+1,r);    minb[x]=min(minb[x<<1],minb[x<<1|1]);    maxb[x]=max(maxb[x<<1],maxb[x<<1|1]);}edge E[MN<<4];int En=0,Hr[MN*3],rd[MN*3];inline void Ins(int f,int t){++rd[t];E[++En]=(edge){t,Hr[f]};Hr[f]=En;}std::queue
      
        q;void jt(){    register int i,j,I,J;    memset(Hr,0,sizeof Hr);    for(i=1;i<=tt;++i) for(j=hr[i];j;j=e[j].nex)        if(bel[i]^bel[e[j].to]) Ins(bel[e[j].to],bel[i]);    for(i=1;i<=bl;++i) if(!rd[i]) q.push(i);    while(!q.empty())    {        int u=q.front();q.pop();        for(i=Hr[u];i;i=E[i].nex)        {            if(Ma[u]) rwa(Ma[E[i].to],Ma[u]);            if(Mi[u]
       
        r) std::swap(l,r);        mi=qmi(1,1,N,l,r);ma=qma(1,1,N,l,r);--ma;        if(mi
        
         i) Insert(root,1,N-1,i+1,ma,i);    }    memset(Mi,0x3f,sizeof Mi);    for(i=1;i<=tt;++i) if(i!=N&&!dfn[i]) tj(i);jt();    memset(minb,0,sizeof minb);memset(maxb,0,sizeof maxb);    Built(1,1,N-1);Q=read();    while(Q--)    {        int l=read(),r=read(),mi,ma;--r;        if(l>r){printf("%d %d\n",l,l);continue;}        mi=qmi(1,1,N-1,l,r);ma=qma(1,1,N-1,l,r);        printf("%d %d\n",mi,ma+1);    }    return 0;}
        
       
      
     
    

/*    C 2019/3/18*/ #include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define reg registerll N,M,P,Q,_1,_2;std::map
     
       mp;const ll MN=2e5+5;struct matrix{    ll a[3][3];    matrix(){memset(a,0,sizeof a);}    matrix operator *(const matrix o)    {        reg int i,j,k;matrix c;        for(k=0;k<2;++k)for(i=0;i<2;++i)for(j=0;j<2;++j)            (c.a[i][j]+=(1ll*o.a[i][k]*a[k][j])%P)%=P;        return c;    }}L[MN],R[MN],ep,_;ll ans[MN<<1],dec;ll Cal(ll num){    ll x=(num-1)/M,y=(num-1)%M+1;    matrix t;    t=L[x]*R[y];    ll xi=(1ll*t.a[0][0]*_1%P+1ll*t.a[0][1]*_2%P)%P;    ll xi_=(1ll*t.a[1][0]*_1%P+1ll*t.a[1][1]*_2%P)%P;    return (1ll*xi_*xi%P+dec)%P;}ll cal(ll x,ll y){    if(mp.count(1ll*(x-1)*M+y)) return (Cal(mp[1ll*(x-1)*M+y])+P)%P;    else return (Cal(1ll*(x-1)*M+y)+P)%P;}signed main(){    ll x,y,i,j;    N=read(),M=read();Q=read();P=read();_1=read();_2=read();    dec=1ll*_1*((_2-_1+P)%P)%P;dec=1ll*(P-dec)%P;    while(Q--)    {        x=read();y=read();        i=mp.count(x)?mp[x]:x;j=mp.count(y)?mp[y]:y;        mp[x]=j;mp[y]=i;    }    ep.a[0][0]=ep.a[1][1]=1;ep.a[0][1]=ep.a[1][0]=0;    _.a[0][1]=_.a[1][0]=_.a[1][1]=1;_.a[0][0]=0;    R[0]=ep;for(i=1;i<=M;++i)R[i]=R[i-1]*_;    L[0]=ep;for(i=1;i<=N;++i)L[i]=L[i-1]*R[M];    ans[1]=cal(1,1);    for(i=1,j=1;i<=N&&j<=M;)    {        if(i
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！