Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
26962 | baka24 | 【BJ】T1 | C++ | 通过 | 100 | 636 MS | 221760 KB | 3466 | 2024-02-27 17:01:19 |
#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;j<=m;j++){ s[j].y=j; } 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 o=1;o<=m+1;o++){ // cout<<o<<" "; for(int j=1;j<=m;j++){ f[i][j][o]+=f[i][j][o-1]; // cout<<f[i][j][o]<<" "; } // cout<<endl;; } // cout<<endl; } sort(q+1,q+n*m+1); int num=0; for(int i=1;i<=n*m;i++){ if(i==1||q[i].id!=q[i-1].id){ num++; e[num]=q[i].id; } ct[q[i].x]++; for(int j=1;j<=n;j++){ rk[num][j]=ct[j]; } } // for(int i=1;i<=n*m;i++){ // cout<<i<<" "; // for(int j=1;j<=n;j++){ // cout<<rk[i][j]<<" "; // } // cout<<endl; // } //cout<<endl; 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); // cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<" "<<s<<" "<<t<<endl; int l=0,r=num,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=num; 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<<l<<" "<<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; }