二维离线莫队求卡常技巧

TLE，只有60pts

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=250005;
int n,q,a[N][N],xa[M],zs,cd,fk[M],b,c,d,e,k,cnt[M],js[M],ans[60005],lsh[M];
namespace io
{
    const int __SIZE = (1 << 21) + 1;
    char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
    #define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
    inline void gc (char &x) { x = Gc(); }
    inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
    inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
        for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
    template <class I> inline bool gi (I &x) { _eof = 0;
        for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
        for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
    template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
struct XW
{
    int l1,r1,l2,r2,k,id;
}xw[M];
bool cmp(XW x,XW y)
{
    if(fk[x.l1]==fk[y.l1])
    {
        if(fk[x.r1]==fk[y.r1])
        {
            if(fk[x.l2]==fk[y.l2])
            {
                if(fk[x.l2]&1) return x.r2<y.r2;
                return x.r2>y.r2;
            }
            if(fk[x.r1]&1) return x.l2<y.l2;
            return x.l2>y.l2;
        }
        if(fk[x.l1]&1) return x.r1<y.r1;
        return x.r1>y.r1;
    }
    return x.l1<y.l1;
}
inline int ls(int x)
{
    return (x-1)*cd+1;
}
inline int rs(int x)
{
    return x*cd;
}
inline int Q(int ks)
{
    int zh=0;
    zh+=js[0];
    if(ks==1&&zh) return 0;
    for(int i=1;i<=fk[n*n];i++)
    {
        zh+=cnt[i];
        if(zh>=ks)
        {
            zh-=cnt[i];
            for(int j=ls(i);j<=rs(i);j++)
            {
                zh+=js[j];
                if(zh>=ks) return j;
            }
        }
    }
}
int main()
{
    gi(n);
    gi(q);
    cd=n/pow(q,0.25)/3+1;
    for(register int i=1;i<=n;++i)
    {
        for(register int j=1;j<=n;++j)
        {
            int dq=(i-1)*n+j;
            gi(a[i][j]);
            xa[++zs]=a[i][j];
            fk[dq]=(dq-1)/cd+1;
        }
    }
    sort(xa+1,xa+zs+1);
    int len=unique(xa+1,xa+zs+1)-(xa+1);
    for(register int i=1;i<=n;++i)
    {
        for(register int j=1;j<=n;++j)
        {
            int t=a[i][j];
            a[i][j]=lower_bound(xa+1,xa+len+1,a[i][j])-xa;
            lsh[a[i][j]]=t;
        }
    }
    for(register int i=1;i<=q;++i)
    {
        gi(xw[i].l1);
        gi(xw[i].r1);
        gi(xw[i].l2);
        gi(xw[i].r2);
        gi(xw[i].k);
        xw[i].id=i;
    }
    sort(xw+1,xw+q+1,cmp);
    int zuo=1,you=1,sha=1,xia=1;
    js[a[1][1]]=1;
    cnt[fk[a[1][1]]]=1;
    for(register int kk(1);kk<=q;++kk)
    {
        int l1=xw[kk].r1,l2=xw[kk].r2,r1=xw[kk].l1,r2=xw[kk].l2,xy=xw[kk].k;
        while(zuo>l1)
        {
            --zuo;
            for(int i=sha;i<=xia;++i)
            {
                ++js[a[i][zuo]];
                ++cnt[fk[a[i][zuo]]];
            }
        }
        while(you>l2)
        {
            for(int i=sha;i<=xia;++i)
            {
                --js[a[i][you]];
                --cnt[fk[a[i][you]]];
            }
            --you;
        }
        while(sha>r1)
        {
            sha--;
            for(int i=zuo;i<=you;++i)
            {
                ++js[a[sha][i]];
                ++cnt[fk[a[sha][i]]];
            }
        }
        while(xia>r2)
        {
            for(int i=zuo;i<=you;++i)
            {
                --js[a[xia][i]];
                --cnt[fk[a[xia][i]]];
            }
            --xia;
        }
        while(zuo<l1)
        {
            for(int i=sha;i<=xia;++i)
            {
                --js[a[i][zuo]];
                --cnt[fk[a[i][zuo]]];
            }
            ++zuo;
        }
        while(you<l2)
        {
            ++you;
            for(int i=sha;i<=xia;++i)
            {
                ++js[a[i][you]];
                ++cnt[fk[a[i][you]]];
            }
        }
        while(sha<r1)
        {
            for(int i=zuo;i<=you;++i)
            {
                --js[a[sha][i]];
                --cnt[fk[a[sha][i]]];
            }
            ++sha;
        }
        while(xia<r2)
        {
            ++xia;
            for(int i=zuo;i<=you;++i)
            {
                ++js[a[xia][i]];
                ++cnt[fk[a[xia][i]]];
            }
        }
        ans[xw[kk].id]=Q(xy);
    }
    for(register int i=1;i<=q;++i) printf("%d\n",lsh[ans[i]]);
    return 0;
}