当前位置:网站首页>2022杭电多校第二场 Slayers Come

2022杭电多校第二场 Slayers Come

2022-08-06 07:01:21thusloop

预处理计算出每个爆炸点爆炸的范围(可用st表+二分实现)
n 个位置,m 个区间,求选出的区间能够重复覆盖 [1, n] 的方案数。
设 dp[i] 表示恰好覆盖了区间 [1, i] 的方案数。
我们将所有区间按照右端点从小到大进行排序,依次扫描每个区间,考虑一个区间 [l, r] 对 dp 数组的贡献。
dp[r]+ = ∑ dp[j] (j = [l−1 , r])
0 ≤ i ≤ l − 2, dp[i] ∗= 2
初始化dp[0] = 1
用线段树维护这些dp信息(区间乘,单点加,区间求和)

//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yesno if(fg)yes;else no;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
const int mod=998244353;
struct node2
{
    
	int x,l,r;
	int ll,rr;
	bool operator<(const node2&a)const
	{
    
		if(rr==a.rr) return ll<a.ll;
		return rr<a.rr;
	}
} t2[maxn];
int a[maxn],b[maxn],c[maxn],d[maxn];
int st[2][maxn][30];
int lg[maxn];
void init()
{
    
	lg[1]=0;
	for(int i=2; i<maxn; i++)
	{
    
		lg[i]=lg[i/2]+1;
	}
}
int ask(int l,int r,int op)
{
    
	int s=lg[r-l+1];
	return min(st[op][l][s],st[op][r-(1<<s)+1][s]);
}
struct node
{
    
	int l,r;
	int lazy;
	int sum;
} t[maxn*4];
void push_up(int k)
{
    
	if(t[k].l!=t[k].r)
	{
    
		t[k].sum=(t[k<<1].sum+t[k<<1|1].sum)%mod;
	}
}
void push_down(int k)
{
    
	if(t[k].l==t[k].r)
	{
    
		t[k].lazy=1;
		return ;
	}
	if(t[k].lazy>1)
	{
    
		t[k<<1].sum=t[k<<1].sum*t[k].lazy%mod;
		t[k<<1|1].sum=t[k<<1|1].sum*t[k].lazy%mod;
		t[k<<1].lazy=t[k<<1].lazy*t[k].lazy%mod;
		t[k<<1|1].lazy=t[k<<1|1].lazy*t[k].lazy%mod;
		t[k].lazy=1;
	}
}
void build(int l,int r,int k)
{
    
	t[k].l=l;
	t[k].r=r;
	t[k].sum=0;
	t[k].lazy=1;
	if(l==r)return ;
	int mid=(l+r)>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
	push_up(k);
}
void update(int l,int r,int k,int val)
{
    
	if(r<t[k].l||l>t[k].r)return ;
	push_down(k);
	if(l<=t[k].l&&t[k].r<=r)
	{
    
		t[k].sum=(t[k].sum+val)%mod;
		return ;
	}
	update(l,r,k<<1,val);
	update(l,r,k<<1|1,val);
	push_up(k);
}
void mul(int l,int r,int k)
{
    
	if(r<t[k].l||l>t[k].r)return ;
	push_down(k);
	if(l<=t[k].l&&t[k].r<=r)
	{
    
		t[k].lazy=t[k].lazy*2%mod;
		t[k].sum=t[k].sum*t[k].lazy%mod;
		push_down(k);
		return ;
	}
	mul(l,r,k<<1);
	mul(l,r,k<<1|1);
	push_up(k);
}
int query(int l,int r,int k)
{
    
	if(r<t[k].l||l>t[k].r)return 0;
	push_down(k);
	if(l<=t[k].l&&t[k].r<=r)
	{
    
		return t[k].sum;
	}
	int ans=0;
	ans+=query(l,r,k<<1);
	ans%=mod;
	ans+=query(l,r,k<<1|1);
	return ans%mod;
}
signed main()
{
    
	IOS
	init();
	int tt;
	cin>>tt;
	while(tt--)
	{
    
		int n,m;
		cin>>n>>m;
		for(int i=1; i<=n; i++)
		{
    
			cin>>a[i]>>b[i];
			if(i>1)
			{
    
				c[i]=a[i-1]-b[i];
				d[i-1]=a[i]-b[i-1];
			}
		}
		for(int i=1; i<=n; i++)
		{
    
			st[0][i][0]=c[i];
			st[1][i][0]=d[i];
		}
		for(int j=1; j<=lg[n]; j++)
		{
    
			for(int i=1; i+(1<<j)-1<=n; i++)
			{
    
				st[0][i][j]=min(st[0][i][j-1],st[0][i+(1<<(j-1))][j-1]);
				st[1][i][j]=min(st[1][i][j-1],st[1][i+(1<<(j-1))][j-1]);
			}
		}
		for(int i=1; i<=m; i++)
		{
    
			cin>>t2[i].x>>t2[i].l>>t2[i].r;
			int pos=t2[i].x;
			int l=pos+1,r=n;
			while(l<=r)
			{
    
				int mid=(l+r)>>1;
				int tp=ask(pos+1,mid,0);
				if(tp>=t2[i].r)l=mid+1;
				else r=mid-1;
			}
			t2[i].rr=r;

			l=1,r=pos-1;
			while(l<=r)
			{
    
				int mid=(l+r)>>1;
				int tp=ask(mid,pos-1,1);
				if(tp>=t2[i].l)r=mid-1;
				else l=mid+1;
			}
			t2[i].ll=l;
			//cout<<t2[i].ll<<" "<<t2[i].rr<<"\n";
		}
		sort(t2+1,t2+m+1);
		build(1,n,1);
		int st=1;
		for(int i=1; i<=m; i++)
		{
    
			int l=t2[i].ll,r=t2[i].rr;
			int sum=0;
			if(l-1>=1)sum=query(l-1,r,1);
			else sum=st+query(l,r,1);
			update(r,r,1,sum%mod);
			if(l-2>=0)
			{
    
				st=st*2%mod;
				mul(1,l-2,1);
			}
			//cout<<l<<" "<<r<<"\n";
		}
		int ans=query(n,n,1);
		cout<<ans<<"\n";
	}
}
/* 1 4 3 1 4 2 3 3 2 4 1 1 2 -2 2 2 1 3 1 1 */
原网站

版权声明
本文为[thusloop]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_51737737/article/details/126063662

随机推荐