【CF765F】Souvenirs

向右看齐 2023-10-11 11:20 10阅读 0赞

[题目][Link 1]

仔细思考发现我会\\(O((n+m)\\sqrt\{n\}\\log n)\\)，不难发现这显然过不了

考虑一下这道题的答案是某一个点对产生的贡献，考虑强行转数点，我们将\\(x,y\\)搞成\\((x,y,|a\_x-a\_y|)\\)

点对的个数高达\\(n^2\\)，但一些点对显然没有什么用，比如说\\((x\_1,y\_1,v\_1)\\)和\\((x\_2,y\_2,v\_2)\\)，如果存在\\(x\_1\\leq x\_2 \\leq y\_2\\leq y\_2\\)，并且\\(v\_2\\leq v\_1\\)，那么\\((x\_1,y\_1,v\_1)\\)显然没什么用，因为能覆盖到\\((x\_1,y\_1)\\)的询问都能覆盖到\\((x\_2,y\_2)\\)，并且\\((x\_2,y\_2)\\)的答案更小

于是考虑只求出有用的点对

一个直观的想法，对于每一个\\(i\\)，先找到其前面第一个大于等于它的\\(j\\)，\\((j,i,a\_j-a\_i)\\)是一个有用的点对，再找在\\(j\\)前面第一个比\\(a\_j\\)小但大于\\(a\_i\\)的位置，计入这个点对；之后将这个位置作为新的\\(j\\)如此反复

这样并没有什么复杂度的保证，但是不难发现这中间加入了很多没有意义的点对

比如说我们找到了在\\(j\\)前面第一个小于\\(a\_j\\)的\\(k\\)，如果\\(a\_j-a\_k\\leq a\_k-a\_i\\)，那么\\((k,i)\\)这个点对并没有什么用，显然\\((k,j)\\)更容易被统计而且绝对答案还小

所以我们需要找的\\(a\_k\\)，不仅要小于\\(a\_j\\)，而且还得相对\\(a\_j\\)更靠近\\(a\_i\\)，也就是说\\(a\_k\\in \[a\_i,a\_j-\\frac\{a\_j-a\_i\}\{2\}\]\\)，不难发现这样每往前多形成一个点对\\(a\_j-a\_i\\)至少要除以\\(2\\)，也就是说一个点最多形成\\(\\log \\max(a\_i)\\)个点对

于是我们每次用一棵值域线段树找到\\(a\_j\\)前第一个在\\(\[a\_i,a\_j-\\frac\{a\_j-a\_i\}\{2\}\]\\)的\\(a\_k\\)，计入\\((k,i)\\)这个点对，把\\(k\\)作为新的\\(j\\)继续往前找

这样只会形成\\(O(n\\log \\max(a\_i))\\)个点对，之后把询问和点对离线，扫描线+线段树统计答案即可

复杂度\\(O(n\\log n\\log max(a\_i))\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=3e5+5;const int M=maxn*40;
    inline int max(int a,int b) {return a>b?a:b;}
    inline int min(int a,int b) {return a<b?a:b;}
    struct pt{int x,y,v;}p[M<<1];
    struct Ask{int l,r,rk;}q[maxn];
    int n,m,cnt,rt,a[maxn],L,R,top,b[maxn],c[maxn],st[maxn],Ans[maxn];
    inline int cmp(const pt &A,const pt &B) {return A.x>B.x;}
    inline int ctp(const Ask &A,const Ask &B) {return A.l>B.l;}
    struct Segment_Tree {
        int l[M],r[M],tot,d[M];
        inline int ins(int now,int x,int y,int pos,int v) {
            if(!now) now=++tot;d[now]=v;
            if(x==y) return now;
            int mid=x+y>>1;
            if(pos<=mid) l[now]=ins(l[now],x,mid,pos,v);
                else r[now]=ins(r[now],mid+1,y,pos,v);
            return now;
        }
        inline int query(int now,int x,int y,int lx,int ry) {
            if(!now) return 0;
            if(lx<=x&&ry>=y) return d[now];
            int mid=x+y>>1;int t=0;
            if(lx<=mid) t=max(t,query(l[now],x,mid,lx,ry));
            if(ry>mid) t=max(t,query(r[now],mid+1,y,lx,ry));
            return t;
        }
    }T;
    struct Min_Segment_Tree {
        int l[maxn*3],r[maxn*3],pos[maxn],d[maxn*3];
        void build(int x,int y,int i) {
            l[i]=x,r[i]=y;d[i]=R;
            if(x==y) {pos[x]=i;return;}
            int mid=x+y>>1;
            build(x,mid,i<<1),build(mid+1,y,i<<1|1);
        }
        void add(int x,int v) {
            x=pos[x];
            for(;x;x>>=1) if(d[x]<=v) return;else d[x]=v;
        }
        int ask(int x,int y,int i) {
            if(x<=l[i]&&y>=r[i]) return d[i];
            int mid=l[i]+r[i]>>1;int t=R;
            if(x<=mid) t=min(t,ask(x,y,i<<1));
            if(y>mid) t=min(t,ask(x,y,i<<1|1));
            return t;
        }
    }S;
    int main() {
        n=read();for(re int i=1;i<=n;i++) a[i]=read();
        L=R=a[1];for(re int i=2;i<=n;i++) L=min(L,a[i]),R=max(R,a[i]);
        for(re int i=n;i;i--) {
            while(top&&a[i]>=a[st[top]]) b[st[top]]=i,top--;
            st[++top]=i;
        }top=0;
        for(re int i=n;i;--i) {
            while(top&&a[i]<=a[st[top]]) c[st[top]]=i,top--;
            st[++top]=i;
        }
        for(re int i=1;i<=n;i++) {
            if(b[i]) {
                p[++cnt]=(pt){b[i],i,a[b[i]]-a[i]};
                int k=a[b[i]];
                while(k>a[i]) {
                    int t=k-std::ceil((double)(k-a[i])/2.0);
                    int x=T.query(rt,L,R,a[i],t);
                    if(!x) break;k=a[x];
                    p[++cnt]=(pt){x,i,a[x]-a[i]};
                }
            }
            if(c[i]) {
                p[++cnt]=(pt){c[i],i,a[i]-a[c[i]]};
                int k=a[c[i]];
                while(k<a[i]) {
                    int t=k+std::ceil((double)(a[i]-k)/2.0);
                    int x=T.query(rt,L,R,t,a[i]);
                    if(!x) break;k=a[x];
                    p[++cnt]={x,i,a[i]-a[x]};
                }
            }
            rt=T.ins(rt,L,R,a[i],i);
        }
        m=read();for(re int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].rk=i;
        std::sort(q+1,q+m+1,ctp);std::sort(p+1,p+cnt+1,cmp);
        int now=1;S.build(1,n,1);
        for(re int i=1;i<=m;i++) {
            while(now<=cnt&&p[now].x>=q[i].l) S.add(p[now].y,p[now].v),now++;
            Ans[q[i].rk]=S.ask(q[i].l,q[i].r,1);
        }
        for(re int i=1;i<=m;i++) printf("%d\n",Ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11379812.html

[Link 1]: https://www.luogu.org/problem/CF765F