总差一步。

1833 打地鼠的价值

题意：所有 n(n≤3×105)n(n\le 3\times 10 ^{5}) 只地鼠分布在一条直线上，第 ii 个地鼠洞坐标为 xix _{i}，地鼠只会在 tit _{i} 出现，打到后可获得 wi(0≤xi,ti,wi≤108)w _{i}(0\le x _{i},t _{i},w _{i}\le 10 ^{8}) 的价值。你只能通过机械锤来打地鼠，初始可以将它移到任意位置，它的速度有上限 vmax⁡(0≤vmax⁡≤10)v_{\max}(0\le v _{\max} \le 10) 每单位每秒。你只有在 tit _{i} 时刻将机械锤移动到 xix _{i} 才能打到地鼠并获得价值。请问最大能获得的价值。

解析：首先我们肯定是按 tit _{i} 递增的顺序去打地鼠，然后可以很快推出 DP 式子。

设 fif _{i} 表示最后打的是第 ii 只地鼠时获得的最大价值，那么

fi=max⁡ti≥tj,vmax⁡(ti−tj)≥∣xi−xj∣(fj)+wi f _{i}=\max _{t _{i}\ge t _{j},v _{\max}(t _{i}-t _{j})\ge|x _{i}-x _{j}|}(f _{j})+w _{i}

显然第二个条件已经包含了第一个条件。

对于这个条件，将绝对值去掉后可以化为

{vmax⁡tj+xj≤vmax⁡ti+xivmax⁡tj−xj≤vmax⁡ti−xi \begin{cases} v _{\max}t _{j}+x _{j}\le v _{\max}t _{i}+x _{i}\\ v _{\max}t _{j}-x _{j}\le v _{\max}t _{i}-x _{i} \end{cases}

然后就是一个经典的二维偏序问题了。按照其中一个维度排序后，另一维度用树状数组维护即可。注意要离散化。

代码：

//
// Created by 屋顶上的小丑 on 2023/4/3.
//
#include<cstdio>
#include<cstring>
const int maxn=3e5;
const int mod=1e6+7;
const long long inf=1e8;
int n,v,tot;
long long c[(maxn<<1)+5],f[maxn+5];
long long tr[(maxn<<1)+5];
struct mouse
{
    long long val1;
    long long val2;
    long long w;
}p[maxn+5],tmp[maxn+5];
struct hash_map
{
    struct data
    {
        long long u;
        int v;
        int nex;
    }e[mod+5];
    int head[mod+5],cnt;
    int hash(long long u) { return u%mod; }
    int& operator[](long long u)
    {
        int fir=hash(u);
        for(int i=head[fir];i;i=e[i].nex)
            if(e[i].u==u)
                return e[i].v;
        e[++cnt]={u,-1,head[fir]};
        head[fir]=cnt;
        return e[cnt].v;
    }
    hash_map()
    {
        cnt=0;
        memset(head,0,sizeof(head));
    }
};
bool cmp(mouse a,mouse b)
{
    if(a.val1==b.val1)
        return a.val2<b.val2;
    return a.val1<b.val1;
}
bool cmp1(mouse a,mouse b)
{
    return a.val2<b.val2;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,long long val)
{
    for(int i=x;i<=tot;i+=lowbit(i))
        if(val>tr[i])
            tr[i]=val;
}
long long query(int x)
{
    long long ans=-inf;
    for(int i=x;i;i-=lowbit(i))
        if(tr[i]>ans)
            ans=tr[i];
    return ans;
}
template<class T>
void merge_sort(T x[],T temp[],int l,int r,bool (*comp)(T,T))
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    merge_sort(x,temp,l,mid,comp);
    merge_sort(x,temp,mid+1,r,comp);
    int p1=l,p2=mid+1,now=0;
    while(p1<=mid&&p2<=r)
    {
        if(comp(x[p1],x[p2]))
        {
            temp[++now]=x[p1];
            p1++;
        }
        else
        {
            temp[++now]=x[p2];
            p2++;
        }
    }
    while(p1<=mid)
    {
        temp[++now]=x[p1];
        p1++;
    }
    while(p2<=r)
    {
        temp[++now]=x[p2];
        p2++;
    }
    for(int i=l;i<=r;i++)
        x[i]=temp[i-l+1];
}
long long dp()
{
    f[0]=0;
    long long ans=-inf;
    for(int i=1;i<=n;i++)
    {
        f[i]=p[i].w+query(p[i].val2);
        add(p[i].val2,f[i]);
        if(ans<f[i])
            ans=f[i];
    }
    return ans;
}
hash_map h;
int main()
{
    scanf("%d%d",&n,&v);
    int x,t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%lld",&x,&t,&p[i].w);
        p[i].val1=1ll*v*t+x;
        p[i].val2=1ll*v*t-x;
    }
    merge_sort(p,tmp,1,n,cmp1);
    for(int i=1;i<=n;i++)
    {
        if(~h[p[i].val2])
            p[i].val2=h[p[i].val2];
        else
        {
            h[p[i].val2]=++tot;
            p[i].val2=tot;
        }
    }
    merge_sort(p,tmp,1,n,cmp);
    printf("%lld",dp());
    return 0;
}

1829 神秘的机房

题意：给出两个长度为 nn 的数列 xi,ci(1≤xi≤108,1≤ci≤105)x _{i},c _{i}(1\le x _{i}\le 10 ^{8},1\le c _{i}\le 10 ^{5})，给出 m(n,m≤105)m(n,m\le 10 ^{5}) 个询问，每个询问形如 (a,b)(a,b≤105)(a,b)(a,b\le 10 ^{5})，求出 min⁡{∣xi−xj∣∣ci=a,cj=b}\min\{|x _{i}-x _{j}|\big\vert c _{i}=a,c _{j}=b \}。要求强制在线。

解析：这道题强制在线，不能很好用常规方法直接处理，考虑根号分治。

对于某种颜色 pp，如果 ci=pc _{i}=p 的点大于 n\sqrt{n}，那么我们可以直接将颜色 pp 到其他颜色的距离预处理出来。设 fp(ci)f _p(c _{i}) 表示颜色 cic _{i} 到颜色 pp 的距离，显然它要么是点 ii 到左边第一个颜色 xx 的点的距离，或到右边第一个颜色 xx 点的距离。我们分两遍处理，顺着扫一遍再逆着扫一遍，每次即可处理出左边最近的或右边最近的颜色 xx 点的位置，然后即可预处理出 ff，在回答时如果 cac _{a} 和 cbc _{b} 中有一个数量大于 n\sqrt{n} 即可 O(1)O(1) 回答。由于颜色数量大于 n\sqrt{n} 的颜色不会超过 n\sqrt{n} 种，所以整个预处理的复杂度为 O(nn)O(n\sqrt{n})。

剩下的则是对于 ca,cbc _{a},c _{b} 均小于 n\sqrt{n} 的情况。我们把这两种颜色的点单独取出，按照 xx 坐标排序，然后用双指针扫一遍求出答案（类似归并），此时排序复杂度为 O(nlog⁡n)O(\sqrt{n}\log n)，双指针为 O(n)O(\sqrt{n})。我们可以一开始把所有点的都排好然后再取出即可（或者先拿个数组存下，询问时直接双指针扫）。故这部分的询问复杂度为 O(mn)O(m\sqrt{n})。

因此总复杂度为 O(nn+mn)O(n\sqrt{n}+m\sqrt{n})。

代码：

//
// Created by 屋顶上的小丑 on 2023/4/3.
//
#include<cstdio>
#include<cmath>
const int maxn=1e5;
const int maxb=350;
const int inf=2e8;
int n,m,num[maxn+5];
int num1,num2;//大，小
int id[maxn+5],col[maxb+5];
int dis[maxb+5][maxn+5];
int p[maxn+5][maxb+5];
struct company
{
    int x;
    int c;
}e[maxn+5],tmp[maxn+5];
bool cmp(company a,company b)
{
    return a.x<b.x;
}
template<class T>
void merge_sort(T data[],T temp[],int l,int r,bool (*comp)(T,T))
{
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    merge_sort(data,temp,l,mid,comp);
    merge_sort(data,temp,mid+1,r,comp);
    int p1=l,p2=mid+1,now=0;
    while(p1<=mid&&p2<=r)
    {
        if(comp(data[p1],data[p2]))
        {
            temp[++now]=data[p1];
            p1++;
        }
        else
        {
            temp[++now]=data[p2];
            p2++;
        }
    }
    while(p1<=mid)
    {
        temp[++now]=data[p1];
        p1++;
    }
    while(p2<=r)
    {
        temp[++now]=data[p2];
        p2++;
    }
    for(int i=l;i<=r;i++)
        data[i]=temp[i-l+1];
}
int main()
{
    scanf("%d%d",&n,&m);
    int mid=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&e[i].x,&e[i].c);
        num[e[i].c]++;
    }
    merge_sort(e,tmp,1,n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(num[e[i].c]>=mid)
        {
            if(id[e[i].c])
                continue;
            id[e[i].c]=++num1;
            col[num1]=e[i].c;
        }
        else
        {
            if(!id[e[i].c])
                id[e[i].c]=++num2;
            int now=id[e[i].c];
            p[now][++p[now][0]]=e[i].x;
        }
    }
    for(int i=1;i<=num1;i++)
    {
        int now=col[i],las=0;
        for(int j=1;j<=n;j++)
            dis[i][j]=inf;
        for(int j=1;j<=n;j++)
        {
            if(e[j].c==now)
            {
                las=e[j].x;
                continue;
            }
            if(las&&e[j].x-las<dis[i][e[j].c])
                dis[i][e[j].c]=e[j].x-las;
        }
        las=0;
        for(int j=n;j>=1;j--)
        {
            if(e[j].c==now)
            {
                las=e[j].x;
                continue;
            }
            if(las&&las-e[j].x<dis[i][e[j].c])
                dis[i][e[j].c]=las-e[j].x;
        }
    }
    int las=0,a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        a^=las;
        b^=las;
        if((!num[a])||(!num[b]))
        {
            printf("invalid\n");
            las=0;
            continue;
        }
        if(num[a]>=mid)
            printf("%d\n",las=dis[id[a]][b]);
        else if(num[b]>=mid)
            printf("%d\n",las=dis[id[b]][a]);
        else
        {
            a=id[a],b=id[b];
            int p1=1,p2=1;
            las=inf;
            while(p1<=p[a][0]&&p2<=p[b][0])
            {
                int now=p[b][p2]-p[a][p1];
                if(now<0) now=-now;
                if(p[a][p1]<=p[b][p2])
                {
                    if(las>now) las=now;
                    p1++;
                }
                else
                {
                    if(las>now) las=now;
                    p2++;
                }
            }
            while(p1<=p[a][0])
            {
                int now=p[b][p2-1]-p[a][p1];
                if(now<0) now=-now;
                if(las>now) las=now;
                p1++;
            }
            while(p2<=p[b][0])
            {
                int now=p[a][p1-1]-p[b][p2];
                if(now<0) now=-now;
                if(las>now) las=now;
                p2++;
            }
            printf("%d\n",las);
        }
    }
    return 0;
}