题解：

 

Code：

A. Ascending Rating

#include
     
      const int N=10000010;int T,n,m,k,P,Q,R,MOD,i,a[N],q[N],h,t;long long A,B;int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d%d%d%d%d%d",&n,&m,&k,&P,&Q,&R,&MOD);    for(i=1;i<=k;i++)scanf("%d",&a[i]);    for(i=k+1;i<=n;i++)a[i]=(1LL*P*a[i-1]+1LL*Q*i+R)%MOD;    for(h=1,t=A=B=0,i=n;i;i--){      while(h<=t&&a[q[t]]<=a[i])t--;      q[++t]=i;      if(i+m-1<=n){        while(q[h]>=i+m)h++;        A+=i^a[q[h]];        B+=i^(t-h+1);      }    }    printf("%lld %lld\n",A,B);  }}
     

　　

B. Cut The String

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010,S=26;int T,n,m,i,j,len,x,y,ca,cb,ans;char s[N];struct AP{  int s,d,r,f;  //k*d+s 0<=k<=r  AP(){}  AP(int _s,int _d,int _r,int _f){s=_s,d=_d,r=_r,f=_f;}}a[N],b[N];struct DS{  int all,son[N][S],fail[N],len[N],diff[N],top[N],text[N],last,tot,f[N];  int newnode(int l){    for(int i=0;i
       
        0){      int y=top[x];      q[++cnt]=AP(len[y],diff[x],(len[x]-len[y])/diff[x],len[x]);      //printf("! %d %d %d\n",len[y],len[x],diff[x]);      x=fail[y];    }  }}pre,suf;ll exgcd(ll a,ll b,ll&x,ll&y){  if(!b)return x=1,y=0,a;  ll d=exgcd(b,a%b,x,y),t=x;  return x=y,y=t-a/b*y,d;}inline ll solve(ll a,ll b,ll c,ll xl,ll xr,ll yl,ll yr){  if(xl>xr)return 0;  if(yl>yr)return 0;  if(!a&&!b){    if(c)return 0;    return (xr-xl+1)*(yr-yl+1);  }  if(!b){    swap(a,b);    swap(xl,yl);    swap(xr,yr);  }  if(!a){    if(c%b)return 0;    ll y=-c/b;    if(y
        
         yr)return 0;    return xr-xl+1;  }  ll x,y,d=exgcd((a%abs(b)+abs(b))%abs(b),abs(b),x,y);  if(c%d)return 0;  x=(x%abs(b)+abs(b))%abs(b)*((((-c)%abs(b))+abs(b))%abs(b)/d)%abs(b/d);  d=abs(b/d);  ll kl=(xl-x)/d-3,kr=(xr-x)/d+3;  while(x+kl*d
         
          xr)kr--;  ll A=(-yl*b-a*x-c)/(a*d),B=(-yr*b-a*x-c)/(a*d);  if(A>B)swap(A,B);  kl=max(kl,A-3);  kr=min(kr,B+3);  while(kl<=kr){    ll y=(-c-a*x-a*d*kl)/b;    if(yl<=y&&y<=yr)break;    kl++;  }  while(kl<=kr){    ll y=(-c-a*x-a*d*kr)/b;    if(yl<=y&&y<=yr)break;    kr--;  }  if(kl>kr)return 0;  return kr-kl+1;}int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d%s",&n,&m,s+1);    pre.init();    suf.init();    for(i=1;i<=n;i++)pre.add(s[i]);    for(i=n;i;i--)suf.add(s[i]);    while(m--){      scanf("%d%d",&x,&y);      len=y-x+1;      pre.get(y,a,ca);      suf.get(n-x+1,b,cb);      ans=0;      for(i=1;i<=ca;i++)for(j=1;j<=cb;j++){        if(a[i].s+b[j].s>len)continue;        if(a[i].f+b[j].f
         
        
       
      
     

　　

C. Dynamic Graph Matching

#include
     
      const int N=1<<10,P=1000000007;int T,n,m,all,i,x,y,S,f[N],cnt[N],ans[N];char op[9];inline void add(int&a,int b){a=a+b
      
       =0?a-b:a-b+P;}int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d",&n,&m);    all=1<
      
     

　　

D. Euler Function

#include
     
      int T,k;int main(){  scanf("%d",&T);  while(T--){    scanf("%d",&k);    if(k==1)puts("5");else printf("%d\n",5+k);  }}
     

　　

E. Find The Submatrix

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=10010;const ll inf=1LL<<60;int T,n,m,X,Y,i,j,k,pool[N];ll a[N],f[4][2][N],g[4][2][N],ans;inline void up(ll&a,ll b){a
       
        >1,dm=dl;  ll ret=-inf;  for(int i=dl;i<=dr&&i<=mid;i++){    ll now=f[o][0][i];    if(mid-i<=m)now+=a[mid-i];    if(now>ret)ret=now,dm=i;  }  up(g[o][0][mid],ret);  if(l
        
         mid)solve1(o,mid+1,r,dm,dr);}void solve2(int o,int l,int r,int dl,int dr){  int mid=(l+r)>>1,dm=dl;  ll ret=-inf;  for(int i=dl;i<=dr&&i<=mid;i++){    ll now=f[o][1][i];    if(mid-i<=m)now+=a[mid-i];    if(now>ret)ret=now,dm=i;  }  up(g[o+1][0][mid],ret);  if(l
         
          mid)solve2(o,mid+1,r,dm,dr);}int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d%d%d",&n,&m,&X,&Y);    clr();    nxt();    f[0][1][0]=0;    while(n--){      for(i=1;i<=m;i++)scanf("%d",&pool[i]);      sort(pool+1,pool+m+1);      a[0]=0;      for(i=1;i<=m;i++)a[0]+=pool[i];      for(i=1;i<=m;i++)a[i]=a[i-1]-pool[i];      clr();      for(i=0;i<=Y;i++)solve1(i,0,X,0,X);      for(i=0;i
         
        
       
      
     

　　

F. Grab The Tree

#include
     
      int T,n,i,x,y,sum;int main(){  scanf("%d",&T);  while(T--){    scanf("%d",&n);    sum=0;    for(i=1;i<=n;i++)scanf("%d",&x),sum^=x;    for(i=1;i
     

　　

G. Interstellar Travel

#include
     
      #include
      
       using namespace std;const int N=200010;int T,n,t,i,f[N];bool must[N];struct P{int x,y,p;}a[N],q[N];inline bool cmp(const P&a,const P&b){  if(a.x!=b.x)return a.x
       
        b.y;  return a.p
        
         1&&a[i].x==a[i-1].x)continue;      while(t>1&&1LL*(q[t].y-q[t-1].y)*(a[i].x-q[t].x)<1LL*(a[i].y-q[t].y)*(q[t].x-q[t-1].x))t--;      q[++t]=a[i];    }    for(i=1;i<=t;i++)must[i]=0;    must[1]=must[t]=1;    for(i=2;i
        
       
      
     

　　

H. Monster Hunter

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int N=100010;int T,n,i,x,y,g[N],v[N<<1],nxt[N<<1],ed,f[N],vis[N],del[N],pos;struct P{  ll a,b;//- a then + b  P(){}  P(ll _a,ll _b){a=_a,b=_b;}  bool operator<(const P&o)const{//true means bigger    int sgn1=a
         
          
           o.a; return b
           
            PI;typedef pair
            
             PII;priority_queue
             
              q;inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x,int y){ f[x]=y; for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x);}int F(int x){return del[f[x]]?f[x]=F(f[x]):f[x];}int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(ed=pos=i=0;i<=n;i++)vis[i]=del[i]=g[i]=0; a[1]=P(0,0); for(i=2;i<=n;i++)scanf("%lld%lld",&a[i].a,&a[i].b); for(i=1;i
              
               1)q.push(PII(a[y],PI(vis[y]=++pos,y))); } printf("%lld\n",a[1].a); }}
              
             
            
           
          
         
        
       
      
     

　　

I. Random Sequence

#include
     
      const int N=110,M=1500,P=1000000007;int T,n,m,i,j,k,x,y,cnt,gcd[N][N],v[N],a[N],id[N][N][N],g[M][N],w[M][N],f[N][M],ans;int getgcd(int a,int b){return b?getgcd(b,a%b):a;}int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}inline void up(int&a,int b){a=a+b
     

　　

J. Rectangle Radar Scanner

#include
     
      #include
      
       using namespace std;const int N=100010,M=1000010,E=262150,inf=~0U>>1;int T,n,m,K,i,a[N],b[N],vma[E],vmi[E],vprod[E];int xl[M],xr[M],yl[M],yr[M],ansma[M],ansmi[M],ansprod[M],q[M],pool[M],e[M];int A,B,U,C,D;inline bool cmpl(int x,int y){return xl[x]>xl[y];}inline bool cmpr(int x,int y){return xr[x]
       
        b?(a=b):0;}void dfs(int x,int a,int b){  if(!vma[x])return;  vma[x]=0,vmi[x]=inf,vprod[x]=1;  if(a==b)return;  int mid=(a+b)>>1;  dfs(x<<1,a,mid),dfs(x<<1|1,mid+1,b);}void add(int x,int a,int b){  umax(vma[x],D);  umin(vmi[x],D);  vprod[x]=1LL*vprod[x]*D%K;  if(a==b)return;  int mid=(a+b)>>1;  if(C<=mid)add(x<<1,a,mid);else add(x<<1|1,mid+1,b);}void ask(int x,int a,int b){  if(C<=a&&b<=D){    umax(A,vma[x]);    umin(B,vmi[x]);    U=1LL*U*vprod[x]%K;    return;  }  int mid=(a+b)>>1;  if(C<=mid)ask(x<<1,a,mid);  if(D>mid)ask(x<<1|1,mid+1,b);}void solve(int l,int r,int L,int R){  if(l>r||L>R)return;  int mid=(l+r)>>1,i,j,k,cL=L-1,cR=R+1,ce=0;  for(i=L;i<=R;i++){    j=q[i];    if(xr[j]
        
         mid)pool[--cR]=j;    else e[++ce]=j;  }  for(i=L;i<=R;i++)q[i]=pool[i];  sort(e+1,e+ce+1,cmpl);  for(i=1,j=mid;i<=ce;i++){    k=e[i];    while(j>=xl[k]){      C=a[j],D=b[j];      add(1,1,n);      j--;    }    C=yl[k],D=yr[k],A=ansma[k],B=ansmi[k],U=ansprod[k];    ask(1,1,n);    ansma[k]=A,ansmi[k]=B,ansprod[k]=U;  }  dfs(1,1,n);  sort(e+1,e+ce+1,cmpr);  for(i=1,j=mid+1;i<=ce;i++){    k=e[i];    while(j<=xr[k]){      C=a[j],D=b[j];      add(1,1,n);      j++;    }    C=yl[k],D=yr[k],A=ansma[k],B=ansmi[k],U=ansprod[k];    ask(1,1,n);    ansma[k]=A,ansmi[k]=B,ansprod[k]=U;  }  dfs(1,1,n);  solve(l,mid-1,L,cL);  solve(mid+1,r,cR,R);}int main(){  for(i=0;i
        
       
      
     

　　

K. Transport Construction

#include
     
      #include
      
       using namespace std;typedef long long ll;typedef pair
       
        E;const int N=100010;const ll inf=1LL<<60;int T,n,i,j,k,m,c[N],q[N],st[N],en[N],qx[N],qk[N],stq[N],enq[N],tmp[N];int hull[N],on[N],f[N];E e[N];ll ans;struct P{int x,y;}a[N];inline bool cmpc(int x,int y){return c[x]
        
         l1&&a[qx[i]].x==a[qx[i-1]].x)continue;    //while(t>1&&slope(tmp[t],tmp[t-1])>slope(qx[i],tmp[t]))t--;    while(t>1&&1LL*(a[tmp[t]].y-a[tmp[t-1]].y)*(a[qx[i]].x-a[tmp[t]].x)>1LL*(a[qx[i]].y-a[tmp[t]].y)*(a[tmp[t]].x-a[tmp[t-1]].x))t--;    tmp[++t]=qx[i];  }  for(i=1;i<=t;i++){    if(i==1||i==t)hull[++cnt]=i;    //else if(slope(tmp[i],tmp[i-1])!=slope(tmp[i+1],tmp[i]))hull[++cnt]=i;    else if(1LL*(a[tmp[i]].y-a[tmp[i-1]].y)*(a[tmp[i+1]].x-a[tmp[i]].x)!=1LL*(a[tmp[i+1]].y-a[tmp[i]].y)*(a[tmp[i]].x-a[tmp[i-1]].x))hull[++cnt]=i;  }  for(i=1;i
         
          dot(a[x],a[hull[j+1]]))j++;    ll now=dot(a[x],a[hull[j]]);    if(j
          
           >1; solve(l,mid); solve(mid+1,r); work(l,mid+1); work(mid+1,l); int l1=stq[l],r1=enq[l]; int l2=stq[mid+1],r2=enq[mid+1]; int k=l1-1; while(l1<=r1&&l2<=r2)tmp[++k]=cmpx(qx[l1],qx[l2])?qx[l1++]:qx[l2++]; while(l1<=r1)tmp[++k]=qx[l1++]; while(l2<=r2)tmp[++k]=qx[l2++]; for(int i=stq[l];i<=k;i++)qx[i]=tmp[i]; l1=stq[l],r1=enq[l]; l2=stq[mid+1],r2=enq[mid+1]; k=l1-1; while(l1<=r1&&l2<=r2)tmp[++k]=cmpk(qk[l1],qk[l2])?qk[l1++]:qk[l2++]; while(l1<=r1)tmp[++k]=qk[l1++]; while(l2<=r2)tmp[++k]=qk[l2++]; for(int i=stq[l];i<=k;i++)qk[i]=tmp[i]; enq[l]=r2;}int F(int x){return f[x]==x?x:f[x]=F(f[x]);}inline void merge(int x,int y,ll z){if(F(x)!=F(y))ans+=z,f[f[x]]=f[y];}int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); c[i]=q[i]=i; } ans=0; while(1){ sort(q+1,q+n+1,cmpc); for(m=0,i=1;i<=n;i=j){ for(j=i;j<=n&&c[q[i]]==c[q[j]];j++); m++; for(k=i;k
          
         
        
       
      
     

　　

L. Visual Cube

#include
     
      const int N=200;int T,a,b,c,n,m,i,j;char f[N][N];int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d%d",&a,&b,&c);    n=b*2+c*2+1;    m=a*2+b*2+1;    for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]='.';    for(i=1;i<=b;i++)for(j=1;j<=a;j++){      f[i*2-1][j*2+1+b*2-i*2]='+';      f[i*2-1][j*2+2+b*2-i*2]='-';      f[i*2-1][j*2+3+b*2-i*2]='+';      f[i*2][j*2+b*2-i*2]='/';      f[i*2][j*2+2+b*2-i*2]='/';    }    for(i=1;i<=c;i++)for(j=1;j<=a;j++){      f[i*2+b*2-1][j*2-1]='+';      f[i*2+b*2-1][j*2]='-';      f[i*2+b*2-1][j*2+1]='+';      f[i*2+b*2][j*2-1]='|';      f[i*2+b*2][j*2+1]='|';      f[i*2+b*2+1][j*2-1]='+';      f[i*2+b*2+1][j*2]='-';      f[i*2+b*2+1][j*2+1]='+';    }    for(i=1;i<=c;i++)for(j=1;j<=b;j++){      f[i*2+b*2-j*2][a*2+j*2+1]='|';      f[i*2+b*2-j*2+1][a*2+j*2+1]='+';      f[i*2+b*2-j*2+2][a*2+j*2]='/';    }    for(i=1;i<=n;i++){      for(j=1;j<=m;j++)putchar(f[i][j]);      puts("");    }  }}
     

　　

M. Walking Plan

#include
     
      #define rep(i) for(int i=0;i
      
       b)a=b;}inline void mul(int a[][N],int b[][N],int c[][N]){  static int f[N][N];  rep(i)rep(j){    f[i][j]=inf;    rep(k)up(f[i][j],a[i][k]+b[k][j]);  }  rep(i)rep(j)c[i][j]=f[i][j];}int main(){  scanf("%d",&T);  while(T--){    scanf("%d%d",&n,&m);    rep(i)rep(j)g[i][j]=inf;    while(m--){      scanf("%d%d%d",&x,&y,&z);      x--,y--;      up(g[x][y],z);    }    rep(i)rep(j)a[0][i][j]=b[0][i][j]=i==j?0:inf;    for(int i=1;i
       
        =inf)z=-1;      printf("%d\n",z);    }  }}