【LittleXi】Crying 与 404

写在前前面

出题人思路：主席树qwq 这里提供一份莫队思路 upd：2023/12/29 22:16

写在前面

个人觉得这题出得没什么意思，感觉像中高级算法杂糅硬套（轻喷，其他题都出地很好，保命~）

算法

莫队+分块

思路

这题是m次询问区间问题，其实很容易想到莫队的莫队算法，如下：

算法最先可以在名次树中插入[0,n-1]（C++中对应的是pbds，当然也可以手搓平衡二叉树）。

最普通的莫队 维护区间的转移，然后我们在每一步转移的时候，可以在名次树中插入或者删除，查询的时候查询order是k的值就行了，k大于n的话，区间内的数字肯定都跨越过了，答案是r-l+k

然后发现每次转移是O(lgn)的，时间复杂度肯定不能接受

如何做到O(1)转移呢，可以利用vis[500000]数组和block[1000]数组，vis数组存这个区间下，某个位置的数字是否在区间内，block数组i表示[i*block_size,i * block_size-1]中不在区间内的数字的数量，转移的时候，维护这两个数组就行了，O(1)

然后查询答案的时候，根据上面的分块数组，步长为1000地跳，知道跳到一个块内，使得可以在这个块内找到答案，因为只需要查询m次，每次查询sqrt(n)，时间完全可以接受

总的时间复杂度

实现代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

int vis[500005]={0};
int blocksz = 700;
int block[800];
vector<int> a;

struct node
{
    int l,r,id;
    long long k;
};

void move(int l,int r,int op){
    if(op==1){
        vis[a[l-1]] = 1;
        block[a[l-1]/blocksz]--;
    }
    else if(op==2){
        vis[a[r+1]] = 1;
        block[a[r+1]/blocksz]--;
    }else if(op==3){
        vis[a[l]] = 0;
        block[a[l]/blocksz]++;
    }else{
        vis[a[r]] = 0;
        block[a[r]/blocksz]++;
    }
}

void solve(){
    int n,m;
    cin>>n>>m;
    a = vector<int> (n,0);
    for(int&x:a) cin>>x;
    for(int i=0;i<800;i++){
        block[i] = blocksz;
    }
    vector<node> vp(m);

    for(int i=0;i<m;i++){
        cin>>vp[i].l>>vp[i].r>>vp[i].k;vp[i].id = i; 
        vp[i].l--;vp[i].r--;
    }
    int unit = int(ceil(pow(n,0.5)));
    //分块+奇偶优化
    sort(vp.begin(),vp.end(),[&](node&n1,node&n2){
        if (n1.l / unit != n2.l / unit) return n1.l < n2.l;
        if ((n1.l / unit) & 1) return n1.r <n2.r;  // 注意这里和下面一行不能写小于（大于）等于，否则会出错（详见下面的小细节）
        return n2.r > n1.r;
    });

    vis[a[0]] = 1;block[a[0]/blocksz]--;
    vector<long long> ansv(m);
    for (int i = 0, l = 0, r = 0; i < m; ++i) {
        auto q  = vp[i];
        while (l > q.l) move(l,r,1),l--;
        while (r < q.r) move(l,r,2),r++;
        while (l < q.l) move(l,r,3),l++;
        while (r > q.r) move(l,r,4),r--;
        
        if(q.k > 1000000){
            ansv[q.id] = r-l+1-1+q.k;
            continue;
        }

        int k = q.k;
        int mxblock = n/blocksz;
        int arrblock = -1;
        int ans = k;
        for(int j = 0;j<mxblock;j++){
            if(block[j]<k){
                k-=block[j];
            }else{
                arrblock = j;break;
            }
        }
        if(arrblock == -1) arrblock = mxblock;
        for(int j = arrblock*blocksz;j<n;j++){
            if(vis[j]) continue;
            k--;
            if(k==0){
                ans = j;break;
            } 
        }
        if(k) ans =  n-1+k;
        ansv[q.id] = ans;
    }
    for(auto x:ansv)
        cout<<x<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    while(t--){
        solve();
    }
}

写在最后