题解 P3730 【曼哈顿交易】

· · 题解

用权值树状数组卡了半天没卡过/kk

然后用分块随便过了。。。

这道题很明显的莫队套一个求第 k 小的数据结构

但是如果用权值树状数组/线段树是 O(n^{1.5}\log n) 的

那么考虑一种增加/减少均是 O(1) 的数据结构就很容易想到分块了。

然后每次查询时 O(\sqrt n) 的可以接受。

所以用分块的复杂度是 O(n^{1.5}+m\sqrt n)。

因为这道题的分块很特殊所以可以用一个珂技。

int t[10005];
int t2[100005];
int len;
void insert(int w,int v)
{
    if(w==0) return;
    t[w/len]+=v;
    t2[w]+=v;
}
int que(int k)
{
    int i;
    for(i=0;k>t[i];i++)
        k-=t[i];
    for(i=i*len;k>t2[i];i++)
        k-=t2[i];
    return i;
}

常数巨小。