T1.矩阵游戏

　考试时去了个厕所顿时豁然开朗想明白了80分算法最后得到了wa0的令人羡慕的好成绩，神tm鬼知道我为什么等差数列求和公式“歇逼”了QAQ（话说lu li < 数学老师 > 知道了一定会干死我嘤.

　一百分没啥好说的大家都A了.现在让性感Smily在线描述自己的SB经历.

　看看右边，板儿逼敲起了T3;

　看看左边，lyl打起了暴力;

　抉择：正解还是暴力？

　　　依稀记得某年某月某日 starsing soul Smily 三人结义，许下海誓山盟约定

　　　　曰：“吾三人擅敢打正解者，必有另二人将其头按键盘上摩擦蹂躏”

　三思后qnmd约定，我选择了打正解，最后，我死在了lu li手里等差数列上？？？？

　在此提醒：好好打暴力学数学.

　lyl式题解法：直接糊代码.

#include <cstdio>
#define re register
#define QAQ 10000010
#define int long long
#define fup(i,a,b) for(re int i=a;i<=b;++i)
const int MOD=1e9+7;
using namespace std;
int n,m,k,ans,s,d,R[QAQ],S[QAQ];
inline int Get_num(re int x,re int y) {return (1ll*m*(x-1)%MOD+y)%MOD;}
main() {
    scanf("%lld%lld%lld",&n,&m,&k);
    re int top=m>n?m:n;fup(i,1,top) R[i]=1,S[i]=1; 
    fup(i,1,k) {
        re char ch[3];scanf("%s",ch);
        re int id,up;scanf("%lld%lld",&id,&up);
        switch (ch[0]){
            case 'R' : R[id]=1ll*R[id]*up%MOD;break;
            case 'S' : S[id]=1ll*S[id]*up%MOD;break;
        }
    }
    fup(i,1,n) s=(s+Get_num(i,1)*R[i]%MOD)%MOD,d=(d+R[i])%MOD;
    fup(i,1,m) ans=(ans+S[i]*s%MOD)%MOD,s=(s+d)%MOD;
    printf("%lld",ans);
}

数学题

T2.跳房子（考场以为自己骗到分系列 + 多测不清系列.

　话说给的正解是分块儿思想（我喜欢。

　查询不用说吧，处理出 jump 后可以直接跑了

　那修改呢？假如修改（x , y）它造成的影响是给（x+1 , y-1）, ( x , y-1 ) , ( x-1 , y-1 )的.以此类推就会发现它影响着的第一列是一个区间，正如题解所说，处理上下界，就可以快速修改（只考虑向外扩，因为外边被影响的话，里边也会被影响，里外指以（x , y）为起点的向第一列的喇叭形区域）.

　然而听说有200多行，王某人就打了线段树嘤

　线段树的话建一棵下标区间为m $m$

$m$ r-l+1步到达的行数。

　　显然置换是满足结合律，也就是说，它可以进行快速幂。

　　对于修改操作，直接修改线段树上叶节点的置换，之后将置换上传。(By skyh

 1 #include <queue>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 #define QAQ 2333
 7 #define re register
 8 #define mp(a,b) make_pair(a,b)
 9 #define fup(i,a,b) for(re int i=a;i<=b;++i)
10 #define fdn(i,a,b) for(re int i=a;i>=b;--i)
11 using namespace std;
12 int n,m,q,len;
13 int nowx,nowy;
14 int jump[2001];
15 int map[2001][2001];
16 inline int read() {
17     re int x(0),f(1);re char ch=getchar();
18     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
19     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
20     return x*f;
21 }
22 struct node {
23     int map[2001];
24     node () {
25         fup(i,1,n) map[i]=i;
26     }
27     node operator * (const node &b) {
28         node c;
29         fup(i,1,n) c.map[i]=b.map[map[i]];
30         return c;
31     }
32 }nxt[QAQ],a[QAQ<<2];
33 inline int cal(int x,int up) {
34     return x>up?1:(x==0?up:x);
35 }
36 node qpow(node a,int b) {
37     node ans;
38     for(;b;b>>=1) {
39         if(b&1) ans=ans*a;
40         a=a*a;
41     }
42     return ans;
43 }
44 void change(int x,int y) {
45     re int max_v=0;
46     x=cal(x,n),y=cal(y,m);
47     fup(i,-1,1) {
48         re int tox=cal(x+i,n);
49         re int toy=cal(y+1,m);
50         if(max_v<map[tox][toy]) {
51             max_v=map[tox][toy];
52             nxt[y].map[x]=tox;
53         }
54     }
55 }
56 void build(int k,int l,int r) {
57     if(l==r) { a[k]=nxt[l]; return ;}
58     re int mid=l+r>>1;
59     build(k<<1,l,mid);
60     build(k<<1|1,mid+1,r);
61     a[k]=a[k<<1]*a[k<<1|1];
62 }
63 void modify(int k,int l,int r,int id) {
64     if(l==r) { a[k]=nxt[id]; return ; }
65     re int mid=l+r>>1;
66     if(id<=mid) modify(k<<1,l,mid,id);
67     else modify(k<<1|1,mid+1,r,id);
68     a[k]=a[k<<1]*a[k<<1|1];
69 }
70 inline void move(int &x,int &y,int mv) {
71     while(mv --> 0) x=nxt[y].map[x],y=cal(y+1,m);
72 }
73 int main() {
74     n=read(),m=read();nowx=1,nowy=1;
75     fup(i,1,n) fup(j,1,m) map[i][j]=read();
76     fup(i,1,n) fup(j,1,m) change(i,j);
77     build(1,1,m);q=read();
78     while(q --> 0) {
79         re char ch[10];scanf("%s",ch);
80         switch (ch[0]) {
81             case 'm' : {
82                re int mv=read(),res=min(mv,m-nowy+1);
83                move(nowx,nowy,res);mv-=res;
84                if(mv) nowx=qpow(a[1],mv/m).map[nowx],mv%=m,move(nowx,nowy,mv);
85                printf("%d %d
",nowx,nowy);break;
86             }
87             case 'c' : {
88                int x=read(),y=read(),dat=read();map[x][y]=dat;
89                change(x-1,y-1),change(x,y-1),change(x+1,y-1);
90                modify(1,1,m,cal(y-1,m));break;
91             }
92         }
93     }
94 }

Code

T3.优美序列

　我只解释一下分块的优秀.

　我原以为（你身为汉朝老臣，来到阵前必有高论）分块优化的是预处理，YY+SY一晚上才发现它优化的是询问嘤？？

　由于n范围很小所以预处理拉不开什么差距，而我们发现询问有好多while跳来跳去特别慢，我们就要想如何优化。

　考虑分块优化询问，即预处理出每两个块L，R的 L的l端点和 R的r端点所构成区间的合法且最优区间。询问时先判断Belong[l]+1的左端点与Belong[r]-1的右端点的合法且最优区间的左右端点minp,maxp与询问区间l,r的关系,即l=min(minp,l),r=max(r,maxp)

　它只会比普通ST表快而不会慢，因为它没用普通分块的爆扫。

  1 #include <map>
  2 #include <cmath>
  3 #include <queue>
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <iostream>
  7 #include <algorithm>
  8 #define re register
  9 #define QAQ 1000110
 10 #define fup(i,a,b) for(re int i=a;i<=b;++i)
 11 #define fdn(i,a,b) for(re int i=a;i>=b;--i)
 12 using namespace std;
 13 int n,m,t;
 14 int Lg[QAQ];
 15 int dat[QAQ],pos[QAQ];
 16 int Be[QAQ],L[QAQ],R[QAQ];
 17 int l_[555][555],r_[555][555];
 18 int max_dat[50][QAQ],min_dat[50][QAQ];
 19 int max_pos[50][QAQ],min_pos[50][QAQ];
 20 //map< pair< int, int > , pair< int, int > >mmp;
 21 const int LL=1<<20|1;
 22 char buffer[LL],*S,*TT;
 23 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,LL,stdin),S==TT))?EOF:*S++)
 24 int read() {
 25     re int x(0);re char ch=getchar();
 26     while(ch<'0'||ch>'9'){ch=getchar();}
 27     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
 28     return x;
 29 }
 30 inline int query_max_dat(re int l,re int r) {
 31     const int len=r-l+1;
 32     return max(max_dat[Lg[len]][l],max_dat[Lg[len]][r-(1<<Lg[len])+1]);
 33 }
 34 inline int query_min_dat(re int l,re int r) {
 35     const int len=r-l+1;
 36     return min(min_dat[Lg[len]][l],min_dat[Lg[len]][r-(1<<Lg[len])+1]);
 37 }
 38 inline int query_max_pos(re int l,re int r) {
 39     const int len=r-l+1;
 40     return max(max_pos[Lg[len]][l],max_pos[Lg[len]][r-(1<<Lg[len])+1]);
 41 }
 42 inline int query_min_pos(re int l,re int r) {
 43     const int len=r-l+1;
 44     return min(min_pos[Lg[len]][l],min_pos[Lg[len]][r-(1<<Lg[len])+1]);
 45 }
 46 void calc_ans(re int l,re int r) {
 47     re int mind=query_min_dat(l,r);
 48     re int maxd=query_max_dat(l,r);
 49     while(maxd-mind!=r-l) {
 50         l=query_min_pos(mind,maxd);
 51         r=query_max_pos(mind,maxd);
 52         if(Be[r]-1>=Be[l]+1) {
 53             const int tmp=l;
 54             l=min(l_[Be[tmp]+1][Be[r]-1],l);
 55             r=max(r_[Be[tmp]+1][Be[r]-1],r);
 56         }
 57         mind=query_min_dat(l,r);
 58         maxd=query_max_dat(l,r);
 59     }
 60     printf("%d %d
",l,r);
 61 }
 62 main() {
 63     //freopen("sequence1.in","r",stdin);
 64     n=read();  t=pow(1.0*n,0.666); Lg[0]=-1;
 65     fup(i,1,n) {
 66         dat[i]=read(),pos[dat[i]]=i;
 67         max_dat[0][i]=min_dat[0][i]=dat[i];
 68         //cout<<max_dat[0][i]<<" ";
 69         max_pos[0][dat[i]]=min_pos[0][dat[i]]=i;
 70         Lg[i]=Lg[i>>1]+1;Be[i]=(i-1)/t+1;
 71     }
 72     //fup(i,1,n) cout<<Be[i]<<endl;
 73     fup(i,1,Lg[n]) for(re int j=1;j<=n-(1<<i)+1;++j) {
 74         min_dat[i][j]=min(min_dat[i-1][j],min_dat[i-1][j+(1<<i-1)]);
 75         //cout<<min_dat[i][j]<<" ";
 76         max_dat[i][j]=max(max_dat[i-1][j],max_dat[i-1][j+(1<<i-1)]);
 77         //cout<<max_dat[i][j]<<" ";
 78         min_pos[i][j]=min(min_pos[i-1][j],min_pos[i-1][j+(1<<i-1)]);
 79         //cout<<min_pos[i][j]<<" ";
 80         max_pos[i][j]=max(max_pos[i-1][j],max_pos[i-1][j+(1<<i-1)]);
 81         //cout<<max_pos[i][j]<<" ";
 82         //puts("");
 83     }
 84     fup(i,1,Be[n]) fdn(j,Be[n],i) {
 85         //cout<<i<<" "<<j<<endl;
 86         re int l=(i-1)*t+1,r=min(j*t,n);
 87         re int mind=query_min_dat(l,r);
 88         re int maxd=query_max_dat(l,r);
 89         //cout<<mind<<" "<<maxd<<endl;
 90         //int q=0;
 91         while(maxd-mind!=r-l) {
 92             //if(++q==5) return 0;
 93             //cout<<l<<" "<<r<<endl;
 94             l=query_min_pos(mind,maxd);
 95             r=query_max_pos(mind,maxd);
 96             if(Be[r]-1>j&&Be[l]+1<i) {
 97                 const int tmp=l;
 98                 //cout<<i<<" "<<j<<" "<<l<<" "<<r<<endl;
 99                 l=min(l_[Be[tmp]+1][Be[r]-1],l);
100                 r=max(r_[Be[tmp]+1][Be[r]-1],r);
101             }
102             mind=query_min_dat(l,r);
103             maxd=query_max_dat(l,r);
104             //cout<<mind<<" "<<maxd<<endl;
105         }
106         l_[i][j]=l,r_[i][j]=r;
107         //cout<<i<<" "<<j<<" "<<l_[i][j]<<" "<<r_[i][j]<<endl;
108     }
109     m=read();
110     //double st=clock();
111     while(m --> 0) {
112         re int l,r;
113         l=read(),r=read();
114         calc_ans(l,r);
115     }
116     //double ed=clock();
117     //printf("%.4lf",(ed-st)/1e6);
118 }

　（完了太潦草了我不想女装啊喂

　等下一场花开.