A simple Blog for wyx I've been down the bottle hoping.
codeforces765F. Souvenirs 莫队 分块 卡常数
发表于: | 分类: Oi | 评论:0 | 阅读:88

考试的时候写了一个复杂度算出来正确但是根本过不了大数据的垃圾算法…………

先来说下这个辣鸡算法吧,虽然这个位置用不上,但是还是不错的想法。

还是莫队,按照$\sqrt{n}$分块,然后容易发现最优的答案必然是一个数字减去他的前去后继得到的答案……

然后我们用一个权值线段树维护离散后的东西,然后每次在权值线段树上二分然后查查查

为了维护答案我们再维护一个同步的堆存所有的答案,然后每次挪指针的时候改改改,改的时候注意要把堆中的元素该删除的删除,保证堆中最多只有$n$个元素,然后堆顶就是答案了,复杂度是 $n\sqrt{n}\log(n)$

然后你发现这个复杂度算出来的数字其实是能过的,但是实际实现的时候挪一下指针实际上需要6个$log$的复杂度,看起来没什么,乘上直接$GG$,比暴力还慢……

【考试直接放弃卡常刚T1然后刚T1失败了 身败名裂

其实也不是非常难卡么……想想办法把那个$log$卡掉就行辣

显然我们需要线性数据结构维护前驱后继,所以拿个链表就行辣

最开始的的时候我们先用$n\sqrt{n}$的复杂度跑个$dp$,得出所有区间小于$\sqrt{n}$的答案,然后现在剩下的就都是跨块的询问辣。对于每个块$[L,R]$,我们先从$R+1$的位置开始向后扫记录$f(i)$表示从$R$扫到$i$位置这部分数字的答案最小是多少,然后把$[R+1,n]$的所有数字扔到链表里面,接下来把询问按照$R$排序,每次把$[q_l,R]$的部分扔到链表里面然后把指针调整到$q_r$的位置,边插入边维护答案,最后再用$f(q_r)$更新一波答案,复杂度显然不超过$n\sqrt{n}$。

高端卡常系列

#include <cmath>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
const int M = 334;
const int N = 1e5+5;
const int inf = 0x3f3f3f3f;
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data {
    int l, r, id;
    bool operator < (const data &z) const {
        return r < z.r;
    }
};

int pre[N], nxt[N], n, m, size, T[N], f[M+5][N], ans[N], F[N], a[N];
pair <int,int> p[N];
vector <data> V[N];

void init() {
    for(int i=1;i<=n;++i) pre[i] = i-1, nxt[i] = i + 1;
    nxt[0] = 1, pre[n+1] = n;
}

inline void del(int x) {
    pre[nxt[x]] = pre[x];
    nxt[pre[x]] = nxt[x];
}

inline int insert(int x) {
    int ans = inf, tmp;
    tmp = nxt[x];
    if(tmp <= n) ans = min(ans,T[tmp]-T[x]);
    tmp = pre[x];
    if(tmp >= 1) ans = min(ans,T[x]-T[tmp]);
    pre[nxt[x]] = x, nxt[pre[x]] = x;
    return ans;
}

int main() {
    n = read(), size = (int) (sqrt(n));
    register int j, i, k;
    for(i=1;i<=n;++i) a[i] = read(), p[i] = mp(a[i],i);
    sort(p+1,p+n+1);
    for(i=1;i<=n;++i) f[1][i] = inf;
    for(i=2;i <M;++i)
        for(j=1;j+i-1<=n;++j) 
            f[i][j] = min(f[i-1][j],min(f[i-1][j+1],abs(a[j]-a[j+i-1])));
    for(i=1;i<=n;++i) a[i] = lower_bound(p+1,p+n+1,mp(a[i],i)) - p;
    for(i=1;i<=n;++i) T[i] = p[i].fir;
    int m = read();
    for(i=1;i<=m;++i) {
        static data tt;
        tt.l = read(), tt.r = read(), tt.id = i;
        if(tt.r-tt.l+1<M) ans[i] = f[tt.r-tt.l+1][tt.l];
        else V[tt.l/size].pb(tt);
    }
    for(i=0;i<M;++i) {
        if(V[i].empty()) continue; init();
        int L = i*size, R = L+size-1;
        for(j=1;j<R;++j) del(a[j]);
        for(j=n;j>R;--j) del(a[j]);
        F[R] = inf;
        for(j=R+1;j<=n;++j) F[j] = min(F[j-1],insert(a[j]));
        for(j=R-1;j>=L;--j) insert(a[j]);
        sort(V[i].begin(),V[i].end());
        for(j=V[i].size()-1,k=n;j>=0;--j) {
            static data tt;
            tt = V[i][j];
            while(k>tt.r) del(a[k--]);
            int tmp = F[k];
            for(int c=L;c<R;++c) del(a[c]);
            for(int c=R-1;c>=tt.l;c--) tmp = min(tmp,insert(a[c]));
            for(int c=tt.l-1;c>=L;c--) insert(a[c]);
            ans[tt.id] = tmp;
        }
    }
    for(int i=1;i<=m;++i) printf("%d\n", ans[i]);
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP