题解：P4848 崂山白花蛇草水

· · 题解

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

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

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

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

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

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

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

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

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

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

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

因此查询的总复杂度为 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;
}