P6325 [COCI2006-2007#4] ISPITI 题解

lzqy_ · 2021-07-31 15:30:45 · 题解

提供一种 O(n^2) 的纯分块做法。暴力碾标算

思路

要维护一些奇怪的东西，首先想到分块。

先看操作一。插入操作对于分块来说是比较复杂的，考虑到最多插入 n 个二元组，所以提前处理出长度为 n 的分块，每个二元组都是 (0,0)，这样，就把插入变成了单点修改。

再看操作二。如果要求的东西和数值的大小关系有关时，一种很套路的做法就是将每个块进行排序，即按 B 作为第一关键字、A 作为第二关键字排序。

然后就可以具体对每个操作来处理了。

操作一：

设修改的是第 x 个二元组，那么暴力扫描 x 所在的块，找到 x 进行修改，然后再对整个块重新排序。时间复杂度 O(\sqrt n\,log\sqrt n)。

操作二：

设询问的是第 x 个二元组 (A,B)，那么对于每一个块，先二分出第一个 B' 大于等于 B 的元素的位置（首先满足第一关键字），然后在块的剩下部分暴力搜索找到第一个 A' 大于等于 A 的元素，那么这个元素便是当前块的答案。对每个块执行这个操作，总的极限时间复杂度 O(n)。

这样我们就拥有了一个常数极小的 O(n^2) 算法。但是我们需要剪枝。

• 对于每一个块，如果其最左边元素的 B 值（即最大的 B）小于要比较的 B 值，那么直接跳过整个块。

• 可以发现，这个算法的瓶颈在于二分完遍历块的时间。所以可以适当缩短块长，牺牲二分的时间来减短遍历块的时间（使二分可以过滤掉更多没必要遍历的部分）。块长取 222 时速度最快（比正常块长短一半）。

• 在遍历块找答案时，目前 B 值必须小于已找出答案的 B 值，否则这个块的剩余部分不会存在最终答案。

• 以及一些普遍的卡常小技巧。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
inline int read()
{
    register int x=0;
    register char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
struct node
{
    int A,B,id;
}a[maxn];
bool operator <(node a,node b)
{
    if(a.B==b.B) return a.A<b.A;
    return a.B<b.B;
}
int Y[maxn],L[maxn],R[maxn];
int n,m,qn;
void change(int x,int A,int B)
{
    register int k=Y[x];
    for(register int i=L[k];i<=R[k];i++)
        if(a[i].id==x)
        {
            a[i].A=A,a[i].B=B;
            break;//找到就跳出
        }
    sort(a+L[k],a+1+R[k]);//对块内元素进行排序
}
pair<int,int> getsum(int x)
{
    register int k=Y[x];
    for(register int i=L[k];i<=R[k];i++)
        if(a[i].id==x)
            return make_pair(a[i].A,a[i].B);
}
int getnum(int A,int B,int x)
{
    pair<int,int>Min;
    Min.first=INT_MAX,Min.second=INT_MAX;
    register int l,r,h=-1,mid,ll,rr,lll,rrr;
    for(register int i=1;i<=Y[n];i++)
    {
        if(a[R[i]].B<B) continue;//当前块没有答案,跳过
        l=L[i],r=R[i];
        while(r>l)
        {
            mid=l+r>>1;
            if(a[mid].B<B) l=mid+1;
            else r=mid;
        }
        for(register int j=l;j<=R[i]&&a[j].B<=Min.first;j++)
            if(a[j].A>=A&&a[j].id!=x)
                if(make_pair(a[j].B,a[j].A)<Min)
                {
                    Min=make_pair(a[j].B,a[j].A),h=a[j].id;
                    break;//取到当前块的答案就跳出
                }

    }
    return h;
}
int main()
{
    n=m=read(),qn=222;//手动定义块长
    for(register int i=1;i<=n;i++)
        Y[i]=(i-1)/qn+1,a[i].id=i;
    for(register int i=1;i<=Y[n];i++)
        L[i]=(i-1)*qn+1,R[i]=min(i*qn,n);
    register int x,y,ii=0;
    pair<int,int>t;
    register char c; 
    while(m--)
    {
        getchar(),c=getchar();//用getchar节省时间
        if(c=='D')
            x=read(),y=read(),change(++ii,x,y);
            //ii为下一个插入的元素的编号
        else
        {
            x=read(),t=getsum(x),y=getnum(t.first,t.second,x);
            if(y==-1) puts("NE");
            else printf("%d\n",y);
        }

    }
    return 0;
}

算是一种思维简单的方法吧，祝AC！