ivyjiao @ 2024-12-15 20:26:38
感觉能用的卡常方法都用完了啊，大悲
#include<bits/stdc++.h>
using namespace std;
const int N=250001,M=501,Q=60001;
int n,m,b[N],ans[Q],p[M][M],cl,c[M],s[N],sum[M],ccl,cc[N],l,r,u,d;
struct node{
int u,l,d,r,k,id;
}q[Q];
inline int read(){
register int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void build(){
cl=n/pow(m,0.25)/3+1;
ccl=n+1;
for(register int i=1;i<=n;++i) c[i]=(i-1)/cl+1;
for(register int i=1;i<=n*n;++i) cc[i]=(i-1)/ccl+1;
}
inline bool cmp(node x,node y){
if(c[x.u]!=c[y.u]) return x.u<y.u;
if(c[x.l]!=c[y.l]) return c[x.u]&1? x.l<y.l:x.l>y.l;
if(c[x.r]!=c[y.r]) return c[x.l]&1? x.r<y.r:x.r>y.r;
return c[x.r]&1? x.d<y.d:x.d>y.d;
}
inline int query(int x){
register int i=1,cnt=0;
for(;cnt+sum[i]<x&&i<=cc[n*n];++i) cnt+=sum[i];
i=(i-1)*ccl+1;
for(;cnt+s[i]<x&&i<=n*n;++i) cnt+=s[i];
return b[i];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n=read();
m=read();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
p[i][j]=read();
b[++l]=p[i][j];
}
}
sort(b+1,b+1+l);
l=unique(b+1,b+1+l)-b-1;
for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) p[i][j]=lower_bound(b+1,b+1+l,p[i][j])-b;
for(register int i=1;i<=m;++i){
q[i].u=read();
q[i].l=read();
q[i].d=read();
q[i].r=read();
q[i].k=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
s[p[1][1]]++;
sum[cc[p[1][1]]]++;
l=1,r=1,u=1,d=1;
for(register int i=1;i<=m;++i){
for(;r<q[i].r;++r) for(register int i=u;i<=d;++i) ++s[p[i][r+1]],++sum[cc[p[i][r+1]]];
for(;l>q[i].l;--l) for(register int i=u;i<=d;++i) ++s[p[i][l-1]],++sum[cc[p[i][l-1]]];
for(;d<q[i].d;++d) for(register int i=l;i<=r;++i) ++s[p[d+1][i]],++sum[cc[p[d+1][i]]];
for(;u>q[i].u;--u) for(register int i=l;i<=r;++i) ++s[p[u-1][i]],++sum[cc[p[u-1][i]]];
for(;r>q[i].r;--r) for(register int i=u;i<=d;++i) --s[p[i][r]],--sum[cc[p[i][r]]];
for(;l<q[i].l;++l) for(register int i=u;i<=d;++i) --s[p[i][l]],--sum[cc[p[i][l]]];
for(;d>q[i].d;--d) for(register int i=l;i<=r;++i) --s[p[d][i]],--sum[cc[p[d][i]]];
for(;u<q[i].u;++u) for(register int i=l;i<=r;++i) --s[p[u][i]],--sum[cc[p[u][i]]];
ans[q[i].id]=query(q[i].k);
}
for(register int i=1;i<=m;++i) cout<<ans[i]<<'\n';
}by Magus @ 2024-12-15 20:32:51
@ivyjiao
.
哦你好像都卡了？那应该无压力过啊？
给你看看我的代码看看有啥区别/kk
#include<bits/stdc++.h>
#define blk1(i) blk1[i]
#define blk2(i) blk2[i]
#define lft2(i) lft2[i]
#define rgt2(i) rgt2[i]
#define qdrt(i) (sqrt(sqrt(i)))
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 20;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 20;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = (x<<3) + (x<<1)+(c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
const int N=505,M=60005;
int n,m,B1,B2,lsh[N*N],a[N][N],sa[N*N],sb[N],ans[M],blk1[N],blk2[N*N],lft2[N*N],rgt2[N*N];
inline int query(int rk)
{
#define int register int
int pos=1,now=0,tmp;
while(pos<=blk2(n*n)&&now+sb[pos]<rk)now+=sb[pos++];
tmp=pos;
pos=lft2(pos);
while(pos<=rgt2(tmp)&&now+sa[pos]<rk)now+=sa[pos++];
return lsh[pos];
#undef int
}
struct que
{
int u,d,l,r,k,no;
friend inline bool operator<(que a,que b)
{
if(blk1(a.u)==blk1(b.u))
{
if(blk1(a.l)==blk1(b.l))
{
if(blk1(a.r)==blk1(b.r))
{
if(blk1(a.r)&1)return a.d<b.d;
return a.d>b.d;
}
if(blk1(a.l)&1)return a.r<b.r;
return a.r>b.r;
}
if(blk1(a.u)&1)return a.l<b.l;
return a.l>b.l;
}
return a.u<b.u;
}
}q[M];
int main()
{
#define int register int
cin>>n>>m;
B1=n/qdrt(1.0*m)/3+1;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
{
cin>>a[i][j];
lsh[++lsh[0]]=a[i][j];
}
sort(lsh+1,lsh+lsh[0]+1);
lsh[0]=unique(lsh+1,lsh+lsh[0]+1)-lsh-1;
B2=sqrt(lsh[0]);
for(int i=1;i<=n;i++)blk1[i]=(i-1)/B1+1;
for(int i=1;i<=n*n;i++)blk2[i]=(i-1)/B2+1;
for(int i=1;i<=blk2[n*n];i++)
{
lft2[i]=(i-1)*B2+1;
rgt2[i]=i*B2;
}
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)a[i][j]=lower_bound(lsh+1,lsh+lsh[0]+1,a[i][j])-lsh;
for(int i=1;i<=m;++i)
{
cin>>q[i].u>>q[i].l>>q[i].d>>q[i].r>>q[i].k;
q[i].no=i;
}
sort(q+1,q+m+1);
int u=1,d=1,l=1,r=1;
++sa[a[1][1]];++sb[blk2(a[1][1])];
for(int i=1;i<=m;i++)
{
while(r<q[i].r)
{
++r;
for(int i=u;i<=d;++i)
{
++sa[a[i][r]];
++sb[blk2(a[i][r])];
}
}
while(l>q[i].l)
{
--l;
for(int i=u;i<=d;++i)
{
++sa[a[i][l]];
++sb[blk2(a[i][l])];
}
}
while(d<q[i].d)
{
++d;
for(int i=l;i<=r;++i)
{
++sa[a[d][i]];
++sb[blk2(a[d][i])];
}
}
while(u>q[i].u)
{
--u;
for(int i=l;i<=r;++i)
{
++sa[a[u][i]];
++sb[blk2(a[u][i])];
}
}
while(r>q[i].r)
{
for(int i=u;i<=d;++i)
{
--sa[a[i][r]];
--sb[blk2(a[i][r])];
}
--r;
}
while(l<q[i].l)
{
for(int i=u;i<=d;++i)
{
--sa[a[i][l]];
--sb[blk2(a[i][l])];
}
++l;
}
while(d>q[i].d)
{
for(int i=l;i<=r;++i)
{
--sa[a[d][i]];
--sb[blk2(a[d][i])];
}
--d;
}
while(u<q[i].u)
{
for(int i=l;i<=r;++i)
{
--sa[a[u][i]];
--sb[blk2(a[u][i])];
}
++u;
}
ans[q[i].no]=query(q[i].k);
}
for(int i=1;i<=m;++i)cout<<ans[i]<<'\n';
#undef int
}