P9400 「DBOI」Round 1 三班不一般

xiezheyuan · 2023-06-23 18:12:02 · 题解

简要题意

有一个序列 S，第 i 个位置可以取 [l_i,r_i] 中的数，但是不能存在一个长度大于等于 a 且所有数大于 b 的子串。求满足条件的 S 数量，对 998,244,353 取模。

思路

朴素的 dp

这道题不应该评绿吧……我觉得评个紫都不过分……

我们考虑 dp，设 f(i,j) 表示以第 i 个数结尾，构成了一个长度为 j 的所有数大于 b 的子串。

然后分情况讨论。令 g(x,l,r) 表示 [l,r] 中大于 x 的数字数量。当 j=0 时，i-1 构成了长度为多少的子串就无所谓了，也就是说：

当 j\neq 0 时，只有一种转移，也就是 i-1 构成了一个长度为 j-1 的子串。也就是说：

时间复杂度 O(n^2)。你应该可以拿到 40 分。

奇怪的 dp 优化

首先这玩意显然可以滚动数组。

然后考虑这个 dp 的数据结构意义。对于 f(i,0)，本质上是一个区间 [0,a-1] 求和。而 j\neq 0，由于 f(,j) 由 f(,j-1) 转移过来，因此可以看成整体向右平移 1 位（多的一个数直接扔掉），然后区间 [1,a-1] 乘 g(b,l_i,r_i)（注意顺序）。

理一下维护 dp 数组需要支持的操作：

• 区间乘
• 区间求和
• 单点修改
• 区间位移

前三个线段树都可以胜任，但是第四个……我们可以考虑使用文艺平衡树。

（题目主人公叫做 HQ，是不是在提醒我们使用 FHQ-Treap？)

代码

注意 FHQ-Treap 的乘法标记默认值要为 1！

#include <bits/stdc++.h>
#define int long long
using namespace std;

long long n,a,b;
const int N = 2e5+5;
struct student{
    long long l,r;
} s[N];
int SUPER_BIG = -1;
const int mod = 998244353;
typedef int LL;
LL mul(LL a, LL b, LL P=mod){
    LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
    LL R = a * (b & ((1LL << 25) - 1)) % P;
    return (L + R) % P;
}

int M(int x){
    return (x%mod+mod)%mod;
}

int bad_way(int x){
    if(s[x].l>b) return M(s[x].r-s[x].l+1);
    else if(s[x].r<b) return 0;
    else return M(s[x].r-b);
}

namespace FHQTreap{
    const int SIZE = 2e6+5;
    int son[SIZE][2];
    int val[SIZE],rk[SIZE],siz[SIZE],root,points,tag[SIZE],add[SIZE];
    int sumt[SIZE];
    mt19937 randomer(time(0));

#define ls(i) (son[(i)][0])
#define rs(i) (son[(i)][1])

    void pushup(int i){
//      val[ls(i)]=M(val[ls(i)]);add[ls(i)]=M(add[ls(i)]);sumt[ls(i)]=M(sumt[ls(i)]);
//      val[rs(i)]=M(val[rs(i)]);add[rs(i)]=M(add[rs(i)]);sumt[rs(i)]=M(sumt[rs(i)]);
        siz[i]=siz[ls(i)]+siz[rs(i)]+1;
        sumt[i]=M(sumt[ls(i)]+M(sumt[rs(i)]+val[i]));
    }

    void pushdown(int i){
//      val[ls(i)]=M(val[ls(i)]);add[ls(i)]=M(add[ls(i)]);sumt[ls(i)]=M(sumt[ls(i)]);
//      val[rs(i)]=M(val[rs(i)]);add[rs(i)]=M(add[rs(i)]);sumt[rs(i)]=M(sumt[rs(i)]);
        if(add[i]!=1){
            add[i]=M(add[i]);
//          val[ls(i)]=M(val[ls(i)]);add[ls(i)]=M(add[ls(i)]);sumt[ls(i)]=M(sumt[ls(i)]);
//          val[rs(i)]=M(val[rs(i)]);add[rs(i)]=M(add[rs(i)]);sumt[rs(i)]=M(sumt[rs(i)]);
            add[ls(i)]*=add[i];sumt[ls(i)]*=add[i];val[ls(i)]*=add[i];
            add[rs(i)]*=add[i];sumt[rs(i)]*=add[i];val[rs(i)]*=add[i];  
            val[ls(i)]=M(val[ls(i)]);add[ls(i)]=M(add[ls(i)]);sumt[ls(i)]=M(sumt[ls(i)]);
            val[rs(i)]=M(val[rs(i)]);add[rs(i)]=M(add[rs(i)]);sumt[rs(i)]=M(sumt[rs(i)]);
            add[i]=1;
        }
    }

    int newnode(int v,int weight=randomer()){
        val[++points]=M(v);
        rk[points]=weight;
        siz[points]=1;
        add[points]=1;
        return points;
    }

    void split(int p,int v,int &left,int &right){
        if(!p){
            left=right=0;
            return;
        }
        pushdown(p);
        if(siz[ls(p)]<v){
            left=p;
            split(rs(p),v-siz[ls(p)]-1,rs(left),right);
        }
        else{
            right=p;
            split(ls(p),v,left,ls(right));
        }
        pushup(p);
    }

    int merge(int left,int right){
        if(!left||!right){
            if(left)return left;
            else if(right)return right;
            else return 0;
        }
        pushdown(left);
        pushdown(right);
        if(rk[left]<rk[right]){
            ls(right)=merge(left,ls(right));
            pushup(right);
            return right;
        }
        else{
            rs(left)=merge(rs(left),right);
            pushup(left);
            return left;
        }
    }

    void update(int l,int r,int v){
        int left=0,mid=0,right=0;
        split(root,r,left,right);
        split(left,l-1,left,mid);
        v=M(v);
//      add[mid]=M(add[mid]);val[mid]=M(val[mid]);sumt[mid]=M(sumt[mid]);
        add[mid]=mul(add[mid],v);val[mid]=mul(val[mid],v);sumt[mid]=mul(sumt[mid],v);
        add[mid]=M(add[mid]);val[mid]=M(val[mid]);sumt[mid]=M(sumt[mid]);
        root=merge(left,merge(mid,right));
    }

    int query(int l,int r){
        int left=0,mid=0,right=0,ret=0;
        split(root,r,left,right);
        split(left,l-1,left,mid);
        ret=M(sumt[mid]);
        root=merge(left,merge(mid,right));
        return ret;
    }

    void right_move(){
        int A = newnode(0),B,C;
        split(root,a-1,B,C);
        root=merge(A,B);
    }

    void assign(int p,int v){
        int A,B=newnode(v),C,D;
        split(root,p-1,A,C);
        split(C,p,D,C);
        root=merge(A,merge(B,C));
    }
}
using namespace FHQTreap;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b;
    root=merge(root,newnode(1));
    for(int i=2;i<=a;i++) root=merge(root, newnode(0));
    for(int i=1;i<=n;i++) cin>>s[i].l>>s[i].r;
    for(int i=1;i<=n;i++){
        int sum=query(1,a)%mod;
        sum = M(sum * (M(s[i].r-s[i].l+1)-bad_way(i)));
        right_move();
        update(2,a,bad_way(i));
        assign(1,sum);
    }
    int ans = 0;
    for(int i=1;i<=a;i++) ans = M(ans+query(i,i));
    cout<<((long long)(ans%mod));
    return 0;
}