提交时间:2024-02-27 16:18:45
运行 ID: 26940
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fr first #define sc second #define mkp make_pair #define lson pos<<1 #define rson pos<<1|1 #define inx int i=h[now];~i;i=edge[i].nx #define y1 y114514 #define x1 x114514 const int MAXN=310,N=18,Maxn=100010,Mod=1000000007,ie9=10000000000000000; inline int read(){char _c=getchar();int _x=0;short _s=1;while(_c<'0'||_c>'9'){if(_c=='-')_s=-1;_c=getchar();}while(_c>='0'&&_c<='9'){_x=_x*10+_c-'0';_c=getchar();}return _x*_s;} int n,m,k,ty,a[MAXN][MAXN],f[MAXN][MAXN][MAXN],rk[MAXN*MAXN][MAXN],e[MAXN*MAXN],ct[MAXN]; struct number{ int id,x,y; bool operator < (const number&G)const{ return id<G.id; } }s[MAXN],q[MAXN*MAXN]; bool cmp(number x,number y){ return x.x<y.x; } inline void slv(){ scanf("%d%d%d%d",&n,&m,&k,&ty); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); q[(i-1)*m+j]={a[i][j],i,j}; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ s[j]={j,a[i][j]}; } sort(s+1,s+m+1,cmp); for(int j=1,o=0;j<=m;j++){ if(j==1||s[j].x!=s[j-1].x)o++; s[j].y=o; } sort(s+1,s+m+1); for(int j=1;j<=m;j++){ f[i][j][s[j].y]++; } for(int j=1;j<=m;j++){ for(int o=1;o<=m+1;o++){ f[i][j][o]+=f[i][j-1][o]; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int o=1;o<=m+1;o++){ f[i][j][o]+=f[i][j][o-1]; } } } sort(q+1,q+n*m+1); for(int i=1,o=0;i<=n*m;i++){ if(i==1||q[i].id!=q[i-1].id){ o++; e[o]=q[i].id; } ct[q[i].x]++; for(int j=1;j<=n;j++){ rk[o][j]=ct[j]; } } int lstans=0; while(k--){ int x1=read(),y1=read(),x2=read(),y2=read(),s=read(),t=read(); if(ty){ x1^=lstans;y1^=lstans;x2^=lstans;y2^=lstans;s^=lstans;t^=lstans; } x1=(x1-1+n)%n+1,x2=(x2-1+n)%n+1,y1=(y1-1+m)%m+1,y2=(y2-1+m)%m+1; if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);if(s>t)swap(s,t); int l=0,r=n*m,T=0,S=0; while(l<r){int mid=(l+r+1)>>1;if(e[mid]<s)l=mid;else r=mid-1;} // cout<<l<<endl; for(int i=x1;i<=x2;i++){ S+=f[i][y2][rk[l][i]]-f[i][y1-1][rk[l][i]]; // cout<<i<<","<<y2<<","<<rk[l][i]<<":"<<f[i][y2][rk[l][i]]<<" "<<i<<","<<y1-1<<","<<rk[l][i]<<":"<<f[i][y1-1][rk[l][i]]<<endl; } l=0;r=n*m; while(l<r){int mid=(l+r+1)>>1;if(e[mid]<=t)l=mid;else r=mid-1;} for(int i=x1;i<=x2;i++){ T+=f[i][y2][rk[l][i]]-f[i][y1-1][rk[l][i]]; // cout<<i<<","<<y2<<","<<rk[l][i]<<":"<<f[i][y2][rk[l][i]]<<" "<<i<<","<<y1-1<<","<<rk[l][i]<<":"<<f[i][y1-1][rk[l][i]]<<endl; } printf("%lld\n",T-S); lstans=T-S; } } signed main(){ slv(); return 0; }