自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 22:48:01，当前版本为作者最后更新于2023-06-23 18:12:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

简要题意

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

$1 \leq n \leq 2\times10^5,1 \leq l_i,r_i,b \leq 10^9$

思路

朴素的 dp

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

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

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

$$f(i,0)=(r_i-l_i+1-g(b,l_i,r_i))\cdot\sum_{k=0}^{a-1}f(i-1,k) $$

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

$$f(i,j)=f(i-1,j-1)\cdot g(b,l_i,r_i)$$

时间复杂度 $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;
}