自动搬运

查看原文

来自洛谷，原作者为

	xxseven 所有梦想，终有绽放之时

搬运于2025-08-24 22:04:33，当前版本为作者最后更新于2025-06-18 16:37:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

纪念一下首次独自做出数据结构黑题！

提供一种分块结合线段树的做法，时间复杂度为 $O(q\sqrt{q\log n})$，目前（截至 2025/6/18）在没有刻意卡常的情况下，拿到了本题的最优解。

首先考虑静态问题，即所有查询在修改之后的版本怎么做。

把所有点按 $v$ 升序排序，之后对其进行分块。块内构建可持久化线段树，用于查询一个矩形内有多少个点。

查询时，从最后一块向前扫描整块，累加当前在查询矩形内的点数，直到找到累加后点数不小于 $k$ 的第一个块，在块内暴力找到答案即可。

接着考虑扩展至动态。最直观的想法就是定期重构，查询时暴力统计新加入的点的贡献，当加入的点达到一个阈值时就暴力重构。

接下来是时间复杂度分析，记分块长度为 $B$，重构阈值为 $lim$，则各部分的时间复杂度如下：

加入新点，共 $O(q)$ 次，单次复杂度 $O(lim)$，用于维护散点序列 $v$ 值的有序性。

重构，共 $O(\frac{q}{lim})$ 次，由以下部分组成：

• 排序所有的点，使用归并排序复杂度为 $O(q)$。
• 构建线段树，复杂度为 $O(q\log n)$。

因此重构的总复杂度为 $O(\frac{q^2\log n}{lim})$。

查询，共 $O(q)$ 次，由以下部分组成：

• 查询整块矩形内点的个数，有 $O(\frac{q}{B})$ 块，总复杂度为 $O(\frac{q \log n}{B})$。
• 暴力处理所有散点和最终答案落在的块，复杂度 $O(lim+B)$。

因此查询的总复杂度为 $O(\frac{q^2\log n}{B}+q(lim+B))$。

最终的总复杂度为 $O(\frac{q^2\log n}{B}+\frac{q^2\log n}{lim}+q(lim+B))$，取 $lim=B=\sqrt{q\log n}$ 即可得到 $O(q\sqrt{q\log n})$。

我的代码实现如下，取了 $lim=B=2500$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6,B=2500;
int n,q;

struct sgt_node{
    int l,r,val;
}t[N<<5];
int idx,rt[50][B+5];
#define mid (L+R>>1)
void upd(int &pos,int pre,int L,int R,int x){
    pos=++idx; t[pos]=t[pre]; t[pos].val++;
    if(L==R) return;
    if(x<=mid) upd(t[pos].l,t[pre].l,L,mid,x);
    else upd(t[pos].r,t[pre].r,mid+1,R,x);
}
int qry(int pos,int L,int R,int x,int y){
    if(x>R||y<L||!pos) return 0;
    if(x<=L&&R<=y) return t[pos].val;
    return qry(t[pos].l,L,mid,x,y)+qry(t[pos].r,mid+1,R,x,y);
}

int cntB,bl[B+5],br[B+5],mn[B+5];

struct point{
    int x,y,k;
    bool operator < (const point &b)const{
        return x<b.x;
    }
}a[N],b[B+5],S[N]; int m,top;
void rebuild(){
    int p=1,q=1;
    for(int i=1;i<=m+top;++i) {
        if(q>top||(p<=m&&a[p].k<b[q].k)) S[i]=a[p++];
        else S[i]=b[q++];
    } 
    m+=top; top=0;
    for(int i=1;i<=m;++i) a[i]=S[i];

    for(int i=1;i<=idx;++i) t[i].l=t[i].r=t[i].val=0;
    for(int i=1;i<=cntB;++i) for(int j=1;j<=B;++j) rt[i][j]=0; idx=0;
    cntB++; bl[cntB]=br[cntB-1]+1; br[cntB]=m;

    for(int i=1;i<=cntB;++i) {
        for(int j=bl[i];j<=br[i];++j) S[j]=a[j];
        sort(S+bl[i],S+br[i]+1);
        mn[i]=a[bl[i]].k;
        for(int j=bl[i];j<=br[i];++j) upd(rt[i][j-bl[i]+1],rt[i][j-bl[i]],1,n,S[j].y);
    }
}
int qryb(int B,int x,int y,int y2){
    int pos=upper_bound(S+bl[B],S+br[B]+1,(point){x,0,0})-S-bl[B];
    return qry(rt[B][pos],1,n,y,y2);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>q; int lst=0;
    while(q--) {
        int op,x,y,x2,y2,k;
        cin>>op;
        if(op==1) {
            cin>>x>>y>>k;
            x^=lst; y^=lst; k^=lst;
            b[++top]=(point){x,y,k}; 
            int pos=top;
            while(pos!=1&&b[pos-1].k>b[pos].k) {
                swap(b[pos-1],b[pos]);
                pos--;
            }
            if(top==B) rebuild();
        }
        else {
            cin>>x>>y>>x2>>y2>>k;
            x^=lst; y^=lst; x2^=lst; y2^=lst; k^=lst;

            int pos=top,tot=0;
            for(int i=cntB;i>=0;--i) {
                if(i==0) {
                    assert(tot<k);
                    int ans=-1,q=pos;
                    while(q!=0) {
                        ans=b[q].k;
                        if(x<=b[q].x&&b[q].x<=x2&&y<=b[q].y&&b[q].y<=y2) tot++;
                        q--;
                        if(tot==k) break;
                    }

                    if(tot<k) {
                        cout<<"NAIVE!ORZzyz.\n";
                        lst=0;
                    } 
                    else {
                        lst=ans;
                        cout<<ans<<'\n';
                    }
                    break;
                }
                int now=0,tmp=pos;
                now+=qryb(i,x2,y,y2)-qryb(i,x-1,y,y2);
                while(tmp!=0&&mn[i]<=b[tmp].k) {
                    if(x<=b[tmp].x&&b[tmp].x<=x2&&y<=b[tmp].y&&b[tmp].y<=y2) now++;
                    tmp--;
                }
                if(tot+now>=k) {
                    int p=br[i],q=pos,ans=-1;
                    while(tot<k) {
                        if(q==tmp-1||(p!=bl[i]-1&&a[p].k>b[q].k)) {
                            ans=a[p].k;
                            if(x<=a[p].x&&a[p].x<=x2&&y<=a[p].y&&a[p].y<=y2) tot++;
                            p--;
                        }
                        else {
                            ans=b[q].k;
                            if(x<=b[q].x&&b[q].x<=x2&&y<=b[q].y&&b[q].y<=y2) tot++;
                            q--;
                        }
                    } 
                    lst=ans;
                    cout<<ans<<'\n';
                    break;
                }
                tot+=now; pos=tmp;
            }
        }
    }
    return 0;
}