A

一个暴力的想法是找出这条链,暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。

于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点,首先跳 $2^0$ 步可以二分预处理,然后直接转移就好了。

但是这只能处理往上的,往下怎么做呢?

一种方法是直接树链剖分,就变成了若干个链的问题,但是这是 $O(\log^2n)$ 的,又难写又难调。

我们可以观察到对于一条链,如果满血开始的话正着走和倒着走的答案是一样的(考场上可以对拍证明),一个有理有据的证明是考虑这个操作其实是遇到 $\geq k$ 的地方就分段,而我们发现这个贪心其实是解决将这个链分为最多的段,每段要求 $\geq k$,正着做和倒着做答案都是一样的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

const int MAXN = 2e5 + 5;
const int MAXM = 17;
int f[MAXN][MAXM+1],F[MAXN][MAXM+1];

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;
int n,k;

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}

LL sm[MAXN];
int st[MAXN],tp;
int dep[MAXN];

inline void dfs(int v,int fa=0){
    st[++tp] = v;dep[v] = dep[fa]+1;
    int l = 1,r = tp,ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(sm[v]-sm[st[mid]] >= k) ans = mid,l = mid+1;
        else r = mid-1;
    }
    f[v][0] = st[ans];F[v][0] = fa;
    FOR(i,1,MAXM){
        f[v][i] = f[f[v][i-1]][i-1];
        F[v][i] = F[F[v][i-1]][i-1];
    }
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        sm[e[i].to] = sm[v]+e[i].w;dfs(e[i].to,v);
    }
    --tp;
}

inline int lca(int x,int y){
    if(dep[x]^dep[y]){
        if(dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x]-dep[y];
        FOR(i,0,MAXM) if((d>>i)&1) x = F[x][i];
    }
    if(x == y) return x;
    ROF(i,MAXM,0){
        if(!(F[x][i]^F[y][i])) continue;
        x = F[x][i],y = F[y][i];
    }
    return F[x][0];
}

int main(){
    read(n);read(k);
    FOR(i,2,n){
        int u,v,w;read(u);read(v);read(w);
        add(u,v,w);
    }
    dfs(1);
    int q;read(q);
    while(q--){
        int x,y;read(x);read(y);
        int l = lca(x,y);
        int ans = 0;
        ROF(i,MAXM,0) if(dep[f[x][i]] >= dep[l]) x = f[x][i],ans |= (1<<i);
        // x 是刚刚回满血的位置
        int r = k-(sm[x]-sm[l]);
//        assert(r > 0);
        int v = y;
        ROF(i,MAXM,0){
            if(dep[F[v][i]] < dep[l]) continue;
            if(sm[F[v][i]]-sm[l] < r) continue;
            v = F[v][i];
        }
        if(sm[v]-sm[l] >= r) ++ans;
        ROF(i,MAXM,0) if(dep[f[y][i]] >= dep[v]) y = f[y][i],ans += (1<<i);
        printf("%d\n",ans);
    }
    return 0;
}

B

看到所有区间的和,要么数据结构要么分治。

考虑分治,每次处理所有经过 $mid$ 的区间。对左边处理一个 $f_{i,0/1}$ 表示 $[i,mid-1]$ 区间,是否选 $mid-1$ 的答案,右边倒着类似处理一下。对于区间 $[l,r]$,答案就是 $\max(f_{l,0}+f_{r,0},f_{l,1}+f_{r,0},f_{l,0}+f_{r,1})$。

发现这个东西本质上是 $f_{l,0}+f_{r_0}+max(f_{l,1}-f_{l,0},f_{r,1}-f_{r,0},0)$,也就是 $f_{l,0}+f_{r_0}+max(max(f_{l,1}-f_{l,0},0),max(f_{r,1}-f_{r,0},0))$,设 $g_i = max(f_{i,1}-f_{i,0},0)$,相当于是对于一对 $(i,j)$,我们要统计 $\max(g_i,g_j)$,排序双指针即可。

考试被降智了。。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int ha = 998244353;
int n,a[MAXN],ans;

inline void work(int l,int r){
    if(l > r) return;
    auto add = [&](int &x,int y){
        x += y-ha;x += x>>31&ha;
    };
    if(l == r) return add(ans,a[l]%ha);
    int mid = (l + r) >> 1;
    work(l,mid);work(mid+1,r);
    static LL f[MAXN][2][2],g[MAXN][2];
    // 最后一个选不选  当前选不选
    f[mid][0][1] = f[mid][1][0] = -1e18;
    f[mid][0][0] = 0;f[mid][1][1] = a[mid];
    f[mid+1][0][1] = f[mid+1][1][0] = -1e18;
    f[mid+1][0][0] = 0;f[mid+1][1][1] = a[mid+1];
    ROF(i,mid-1,l){
        FOR(j,0,1){
            f[i][j][0] = std::max(f[i+1][j][0],f[i+1][j][1]);
            f[i][j][1] = f[i+1][j][0]+a[i];
        }
    }
    FOR(i,mid+2,r){
        FOR(j,0,1){
            f[i][j][0] = std::max(f[i-1][j][0],f[i-1][j][1]);
            f[i][j][1] = f[i-1][j][0]+a[i];
        }
    }
    FOR(i,l,r) FOR(j,0,1) g[i][j] = std::max(f[i][j][0],f[i][j][1]);
    FOR(i,l,mid) add(ans,1ll*g[i][0]%ha*(r-mid)%ha);
    FOR(i,mid+1,r) add(ans,1ll*g[i][0]%ha*(mid-l+1)%ha);
    std::vector<LL> v1,v2;
    FOR(i,l,mid) v1.pb(std::max(0ll,g[i][1]-g[i][0]));
    FOR(i,mid+1,r) v2.pb(std::max(0ll,g[i][1]-g[i][0]));
    std::sort(all(v1));std::sort(all(v2));
    int tp = -1;
    FOR(i,0,(int)v1.size()-1){
        while(tp+1 < v2.size() && v2[tp+1] <= v1[i]) ++tp;
        add(ans,1ll*v1[i]%ha*(tp+1)%ha);
    }
    tp = -1;
    FOR(i,0,(int)v2.size()-1){
        while(tp+1 < v1.size() && v1[tp+1] < v2[i]) ++tp;
        add(ans,1ll*v2[i]%ha*(tp+1)%ha);
    }
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    work(1,n);
    printf("%d\n",ans);
    return 0;
}

C

观察移动方式,设 $L_{t,i}$ 表示 $t$ 时刻 $i$ 行的左端点是啥,$R_{t,i}$ 表示右端点,显然答案是最小的 $t'$ 满足 $L_{t',i} > R_{t',i}$。

显然有转移:$L_{t,i} = \max(L_{t-1,i},L_{t,i}+1,L_{t,i+1})$ 和 $R_{t,i} = \max(R_{t-1,i},R_{t,i}-1,R_{t,i+1})$。

我们设 $i$ 行的答案为 $f_i$,可以发现一个事实是 $|f_i - f_{i-1}| \leq 1$,并且 $f_1 = 1$,于是确定了 $i$ 后,可以暴力枚举得到 $i+1$。(二分不行的时候就想想答案之间有什么联系)

现在我们需要快速求出某个 $L_{t,i}$ 和 $R_{t,i}$。我们将转移画到二维平面上,可以发现相当于斜着走代价为 $0$,竖着走代价为 $1$,所以我们可以直接统计出第 $0$ 行对这个格子的贡献系数是加上一个横向的距离,所以转化为了求区间 $[i-f(i),i+f(i)]$的 RMQ 问题

可以用 $O(n)-O(1)$ RMQ 但是常数巨大,一种更好的方式是注意到无论如何左端点只会左移,因为 $i$ 至少 $+1$,$f(i)$ 最多 $-1$。所以单调队列就行了。这里边界有问题,要用边角暴力去询问(反正只有 $O(1)$ 个边角)

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;

typedef unsigned long long u64;

u64 xorshift128p(u64 &A, u64 &B) {
    u64 T = A, S = B;
    A = S;
    T ^= T << 23;
    T ^= T >> 17;
    T ^= S ^ (S >> 26);
    B = T;
    return T + S;
}

int n,l[MAXN],r[MAXN];

void gen(){
    int L,X,Y;u64 A,B;
    scanf("%d%d%d%d%llu%llu",&n,&L,&X,&Y,&A,&B);
    for (int i = 1; i <= n; i ++) {
        l[i] = xorshift128p(A, B) % L + X;
        r[i] = xorshift128p(A, B) % L + Y;
        if (l[i] > r[i]) std::swap(l[i], r[i]);
    }
}

const int ha = 998244353;

struct Node{
    std::deque<int> q;
    int val[MAXN],l,r;
    Node(){l = r = 0;}

    inline int query(int L,int R){
        int ans = -1e9;
        for(auto x:q) if(x >= L) {ans = val[x];break;}
        FOR(i,r,R) ans = std::max(ans,val[i]);
        return ans;
    }

    inline void move(int ll,int rr){
        while(r <= rr){
            while(!q.empty() && val[q.back()] <= val[r]) q.pop_back();
            q.pb(r);++r;
        }
        l = ll;
        while(!q.empty() && q[0] < l) q.pop_front();
    }
}q1,q2,q3,q4;

int main(){
    gen();
    int ans = 0,bs = 1;
    auto answer = [&](int x){
        (ans += 1ll*bs*x%ha) %= ha;
        bs = 3ll*bs%ha;
    };
    static int f[MAXN];
    f[1] = 1;
    FOR(i,1,n){
        q1.val[i] = l[i]+i;q2.val[i] = l[i]-i;
        q3.val[i] = -(r[i]-i);q4.val[i] = -(r[i]+i);
    }
    l[0] = l[n+1] = 1e9;
    r[0] = r[n+1] = -1e9;
    q1.move(0,1);q3.move(0,1);
    q2.move(2,2);q4.move(2,2);
    answer(1);
    FOR(i,2,n){
        FOR(j,f[i-1]-1,f[i-1]+1){
            int ll = i-j,rr = i+j;
            int L = std::max(q1.query(ll,i)-ll,q2.query(i+1,rr)+i+j);
            int R = std::min(-q3.query(ll,i)+ll,-q4.query(i+1,rr)-i-j);
            if(L > R){
                f[i] = j;break;
            }
        }
        assert(f[i] > 0);
        q1.move(i-f[i],i);q2.move(i+1,i+f[i]);
        q3.move(i-f[i],i);q4.move(i+1,i+f[i]);
        answer(f[i]);
    }
    printf("%d\n",ans);
    return 0;
}
Last modification:July 11th, 2022 at 06:09 pm
如果觉得我的文章对你有用,请随意赞赏