【JZOJ6091】唐时月夜

本文主要是介绍【JZOJ6091】唐时月夜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Solution

因为后面的矩阵总会包含前面的矩阵，所以对于每个$(x,y)$的变换是由一段后缀操作实现的。
同时每个操作都是线性变换，即满足$(x,y)$经过变换后会到达$(ax+by+c,dx+ey+f)$。那么只要复合后缀的变换即可。
还有一种做法是四向链表，1操作就是交换左右指针，2操作就是交换上下指针，3操作交换左上和右下指针。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef unsigned int uint;
const int N=4050,M=2e5+10;
uint F[N][N];
int op[M];
struct P{int x,y;P(int _x=0,int _y=0) {x=_x,y=_y;}
}r1[M],r2[M];
struct node{int a,b,c,d,e,f;node(int _a=1,int _b=0,int _c=0,int _d=0,int _e=1,int _f=0){a=_a,b=_b,c=_c,d=_d,e=_e,f=_f;}friend node operator+(node x,node y){node z(y.a*x.a+y.b*x.d,y.a*x.b+y.b*x.e,y.a*x.c+y.b*x.f+y.c,y.d*x.a+y.e*x.d,y.d*x.b+y.e*x.e,y.d*x.c+y.e*x.f+y.f);return z;}P get(int x,int y){return P(a*x+b*y+c,d*x+e*y+f);}
};
node solve(int now){int tp=op[now];P p=r1[now],q=r2[now];node z;if(tp==1) z=node(1,0,0,0,-1,p.y+q.y);else if(tp==2) z=node(-1,0,p.x+q.x,0,1,0);else z=node(0,1,p.x-p.y,1,0,p.y-p.x);return z;
}
uint calc(int x,int y,node z){P p=z.get(x,y);return F[x][y]*F[p.x][p.y];
}
int main()
{int tp,n,m,q;scanf("%d %d %d %d",&tp,&n,&m,&q);uint A,B,C;scanf("%u %u %u",&A,&B,&C);fo(i,1,n)fo(j,1,m) C=A*C+B,F[i][j]=C;fo(i,1,q) scanf("%d %d %d %d %d",&op[i],&r1[i].x,&r1[i].y,&r2[i].x,&r2[i].y);node t;int u=1,d=n,l=1,r=m;uint ans=0;fd(i,q,1){for(;u<r1[i].x;++u) fo(j,l,r) ans+=calc(u,j,t);for(;d>r2[i].x;--d) fo(j,l,r) ans+=calc(d,j,t);for(;l<r1[i].y;++l) fo(j,u,d) ans+=calc(j,l,t);for(;r>r2[i].y;--r) fo(j,u,d) ans+=calc(j,r,t);t=solve(i)+t;}fo(i,u,d)fo(j,l,r) ans+=calc(i,j,t);printf("%u",ans);
}

这篇关于【JZOJ6091】唐时月夜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---