HDU7154多校 - Slayers Come

• 链接：https://acm.hdu.edu.cn/showproblem.php?pid=7154
• 知识点：DP、线段树、组合数学
• 难度：紫

题意

• 给出 $nn$ 个怪物的战力值 $a_{i}a\_i$，抵御值 $d_{i}d\_i$。
• 有 $mm$ 种技能，每种有属性 $x_{i}x\_i$，$L_{i}L\_i$，$R_{i}R\_i$，代表下标为 $x_{i}x\_i$ 的怪物立即死亡。该怪物死亡时会对左边相邻的怪物造成 $a_{xi}-L_{i}a\_\{xi\}-L\_i$ 的伤害，对右边相邻的怪物造成 $a_{xi}-Ria\_\{xi\}-Ri$ 的伤害。会产生连锁反应。
• 下次使用别的技能时，上一次死亡的怪物将重新恢复。
• 问有多少种选择技能的方式，使得每种怪物至少累计死亡一次。每种技能最多使用一次，没有顺序，不分先后。
• 答案对 $998244353998244353$ 取模。

思路

• 首先，我们发现，每种技能会导致某个连续区间的怪物全部死亡。我们可以使用线段树或者并查集，求出这个区间。

从 $mm$ 个区间选出一部分区间，使得这些区间完全覆盖 $[1,n][1,n]$ 的选择方法数。

• 我们用 $dp[i]dp[i]$ 表示对于区间 $[1,i][1,i]$，的方案数。
• 将这些区间，以左端点为第一关键字，右端点为第二关键字，升序排序。

• 这样排序后的一大特征是：对于某个区间，之前一定枚举过覆盖过它左端点左边的区间。

• 初始 $dp[0]=1dp[0]=1$
• 对于每一个排好序的区间
• • $dp[r\mathrm{.}\mathrm{.}\mathrm{.}n]\ast =2dp[r...n]*=2$

• 原因：对于那些从 $11$ 开始的能完全覆盖住当前区间的大区间，选不选当前区间都可以。

• • $dp[r]+={\sum }_{l-1}^{r-1}dp[i]dp[r]\; +=\; \backslash sum\_\{l-1\}^\{r-1\}dp[i]$
• $ans=dp[n]ans=dp[n]$

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N     = 2e5+10;
const int INF 	= 1e14;
const int MOD   = 998244353;
//////////
struct Tree
{
	int dat,l,r,add,mul;
	Tree(int _dat=0,int _l=0,int _r=0,int _add=0,int _mul=1)
	{
		dat=_dat,l=_l,r=_r,add=_add,mul=_mul;
	}
	#define dat(p) tree[(p)].dat
	#define l(p) tree[(p)].l
	#define r(p) tree[(p)].r
	#define add(p) tree[(p)].add
	#define mul(p) tree[(p)].mul
	#define ls(p) ((p)<<1)
	#define rs(p) (((p)<<1)|1)
}tree[N*4+1];
//////////
void init(void);
void build(int p,int l,int r);
void spread(int p);
void change_add(int p,int l,int r,int d);
void change_mul(int p,int l,int r,int d);
int ask(int p,int l,int r);
//////////

void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r){dat(p)=0;return;}
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    dat(p)=(dat(ls(p))+dat(rs(p)))%MOD;
}

void spread(int p)
{
	dat(ls(p))=(dat(ls(p))*mul(p)+add(p)*(r(ls(p))-l(ls(p))+1))%MOD;
	dat(rs(p))=(dat(rs(p))*mul(p)+add(p)*(r(rs(p))-l(rs(p))+1))%MOD;
	mul(ls(p))=(mul(ls(p))*mul(p))%MOD;
	mul(rs(p))=(mul(rs(p))*mul(p))%MOD;
	add(ls(p))=(add(ls(p))*mul(p)+add(p))%MOD;
	add(rs(p))=(add(rs(p))*mul(p)+add(p))%MOD;
	add(p)=0,mul(p)=1;
}
void change_add(int p,int l,int r,int d)
{
	if(l<=l(p) && r(p)<=r){add(p)=(add(p)+d)%MOD,dat(p)=(dat(p)+d*(r(p)-l(p)+1))%MOD;return;}
	spread(p);
	int mid=(l(p)+r(p))>>1;
	if(l<=mid)change_add(ls(p),l,r,d);
	if(r>mid)change_add(rs(p),l,r,d);
	dat(p)=(dat(ls(p))+dat(rs(p)))%MOD;
}
void change_mul(int p,int l,int r,int d)
{
	if(l<=l(p) && r(p)<=r){mul(p)=(mul(p)*d)%MOD,add(p)=(add(p)*d)%MOD,dat(p)=(dat(p)*d)%MOD;return;}
	spread(p);
	int mid=(l(p)+r(p))>>1;
	if(l<=mid)change_mul(ls(p),l,r,d);
	if(r>mid)change_mul(rs(p),l,r,d);
	dat(p)=(dat(ls(p))+dat(rs(p)))%MOD;
}
int ask(int p,int l,int r)
{
	if(l<=l(p) && r(p)<=r)return dat(p)%MOD;
	spread(p);
	int mid=(l(p)+r(p))>>1;
	int val=0;
	if(l<=mid)val=(val+ask(ls(p),l,r))%MOD;
	if(r>mid)val=(val+ask(rs(p),l,r))%MOD;
	return val%MOD;
}
//////////



int tree_min[3][N*4];
int arr[3][N];
void Build(int num,int cur,int l,int r)
{
	if(l==r)
	{
		tree_min[num][cur] = arr[num][l];
		return;
	}
	int mid=(l+r)/2;
	Build(num, cur*2, l, mid);
	Build(num, cur*2+1, mid+1, r);
	
	tree_min[num][cur] = min(tree_min[num][cur*2], tree_min[num][cur*2+1]);
}

int QRY1(int cur,int l,int r,int ql,int qr,int lim)
{
	//printf("l=%d,r=%d(%d,%d), min=%d(%d)\n",l,r,ql,qr, tree_min[0][cur],lim);

	if(r<ql || l>qr || tree_min[0][cur]>=lim)
	{
		return -1;
	}
	if(l==r)
	{
		return l;
	}
	int mid=(l+r)/2;
	int res = QRY1(cur*2, l, mid, ql, qr, lim);
	if(res==-1)return QRY1(cur*2+1, mid+1, r, ql, qr, lim);
	return res;
}

int QRY2(int cur,int l,int r,int ql,int qr,int lim)
{
	if(r<ql || l>qr || tree_min[1][cur]>=lim)
	{
		return -1;
	}
	if(l==r)
	{
		return l;
	}
	int mid=(l+r)/2;
	int res = QRY2(cur*2+1, mid+1, r, ql, qr, lim);
	if(res==-1)return QRY2(cur*2, l, mid, ql, qr, lim);
	return res;
}

int ai[N],di[N];
int xi[N],Li[N],Ri[N];

struct Vec
{
	int l,r;
	bool operator < (const Vec & item) const
	{
		return l==item.l ? r<item.r : l<item.l;
	}
};
//bool cmp(Vec a,Vec b){if(a.r==b.r)return a.l<b.l;return a.r<b.r;}
vector< Vec >vec;

int T,n,m;

void Sol()
{
	memset(arr, 0, sizeof(arr));
	memset(tree, 0, sizeof(tree));
	memset(tree_min, 0, sizeof(tree_min));
	
	vec.clear();
	
	for (int i=1; i<=n-1; i++)
	{
		arr[0][i] = ai[i] - di[i+1];
	}
	arr[0][n] = -INF;
	
	for (int i=n; i>=2; i--)
	{
		arr[1][i] = ai[i] - di[i-1];
	}
	arr[1][1] = -INF;
	
	
	build(1, 1, n+1);
	Build(0, 1, 1, n);
	Build(1, 1, 1, n);
	
//	for (int i=1; i<=n; i++)
//	{
//		printf("%d,",arr[0][i]);
//	}
//	printf("\n");
	//printf("[%d]",m);
	for (int i=1; i<=m; i++)
	{
		int r = QRY1(1, 1, n, xi[i], n, Ri[i]);
		int l = QRY2(1, 1, n, 1, xi[i], Li[i]);
		vec.push_back({l,r});
	}
	
	sort(vec.begin(), vec.end());
	
	printf("\n");
	
	change_add(1, 0+1, 0+1, 1);
	
	for (auto item : vec)
	{
		int l = item.l, r = item.r;
		change_mul(1, r+1, n+1, 2);
		int res = ask(1, l-1+1, r-1+1);
		change_add(1, r+1, r+1, res);
	}
	int ans = ask(1, n+1, n+1);
	printf("%lld\n",ans);
}


signed main()
{
	scanf("%lld",&T);
	while (T--)
	{
		scanf("%lld %lld",&n,&m);
		for (int i=1; i<=n; i++)
		{
			scanf("%lld %lld",&ai[i],&di[i]);
		}
		for (int i=1; i<=m; i++)
		{
			scanf("%lld %lld %lld",&xi[i],&Li[i],&Ri[i]);
		}
		Sol();
	}
	
	return 0;
}