ABC255Ex()

ABC255Ex

*2430

思路较为简单。

调了一下午加一早上,发现是人眼做 \(10^{18}\) 级整数比大小判错了,抬走。

题意

给定一片 \(N\) 格的农田,从第 \(0\) 天开始,第 \(i\) 格农田每天会长出 \(i\) 的作物。

给出 \(Q\) 个询问,每次询问以 \(D,L,R\) 的格式给出,表示询问在第 \(D\) 天,收割 \([L,R]\) 的农田,会获得多少作物?答案对 \(998244353\) 取模。注意询问相互依赖,即在每一次收割后,\([L,R]\) 的作物应当清零。

\(1\le l_i \le r_i\le n \le 10^{18}\)

\(1\le q \le 2×10^5\)

\(1< d_1 < d_2<…< d_q≤10^{18}\)

题解

值域很大,传统的线段树无法维护。动态开点线段树根据实现的好坏,需要不同程度的卡常。

考虑使用 维护操作过的区间。假设一次操作 \((d,l,r)\) 所操作的区间先前未被操作过,则根据等差数列求和公式,本次操作的答案为 \(\frac{d·(r+l)·(r-l+1)}{2}\)。

std::set

注意到对于一个相同的区间 \([l,r]\),在操作 \((d,l,r)\) 前有操作 \((d_0,l,r)\),则 \((d,l,r)\) 的答案是 \(\frac{(d-d_0)·(r+l)·(r-l+1)}{2}\),其后 \(d_0\) 不再影响接下来的操作,\(d\) 取而代之。

于是在计算答案是可以先计算出不受任何影响的 \(\frac{d·(r+l)·(r-l+1)}{2}\),然后再减去与区间 \([l,r]\) 有交的先前操作的影响,最后由于操作的覆盖性质直接去掉这些相交的区间,并覆盖上 \((d,l,r)\) 即可。

实现上,使用 维护保留下的所有区间,按 \(l\) 为第一关键字排序,每次操作时找到所有与 \([l,r]\) 有交的操作然后减去先前操作的影响。

std::set

对相交的情况分类讨论即可。

发现如此维护区间后, 内保留的区间两两不交。共有 \(q\) 次询问,每次询问都会插入一个区间,每个区间若导致分裂只会产生 \(O(1)\) 个新区间,覆盖其他区间则直接将其删除,而每个块最多被删除一次。总区间数及其操作数仍在 \(O(q)\) 级别,单次操作时间复杂度为 \(O(\log q)\),故总复杂度为 \(O(q\log q)\) ,可以通过本题。

std::set

代码

const ll maxn=2e5+5,mod=998244353,inv=499122177;
struct node{
	ll l,r,d;
	friend bool operator < (const node &x,const node &y){
		return x.l==y.l?x.r<y.r:x.l<y.l;
	}
};
set<node>s;
ll ins(ll l,ll r,ll d){
	ll res=((r+l)%mod*((r-l+1)%mod)%mod)*(d%mod)%mod*inv%mod;//计算原始答案
	auto it=s.lower_bound((node){l,0,d});
	while(it!=s.end()&&it->l<=r){//左端点落在区间内
		if(it->r<=r){//完全被区间包含
			res=(res+mod-((it->r+it->l)%mod*((it->r-it->l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
			s.erase(*it);
		}
		else{//右端点在区间外
			node tmp=*it;
			res=(res+mod-((r+it->l)%mod*((r-it->l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
			s.erase(*it);
			s.insert((node){r+1,tmp.r,tmp.d});
		}
		it=s.lower_bound((node){l,0,d});
	}
	if(it!=s.begin()){
		it--;
		if(it->r>=l){//要求有交
			if(it->r<=r){//左端点在区间外
				node tmp=*it;
				res=(res+mod-((it->r+l)%mod*((it->r-l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
				s.erase(*it);
				s.insert((node){tmp.l,l-1,tmp.d});
			}
			else {//区间完全被包含
				node tmp=*it;
				res=(res+mod-((r+l)%mod*((r-l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
				s.erase(*it);
				s.insert((node){tmp.l,l-1,tmp.d});
				s.insert((node){r+1,tmp.r,tmp.d});
			}
		}
		
	}
	s.insert((node){l,r,d});
	return res;
}
ll n,m;
void solve(){
	n=R,m=R;
	while(m--){
		ll d=R,l=R,r=R;
		we(ins(l,r,d));
	}
	return ;
}
————————

ABC255Ex

*2430

思路较为简单。

调了一下午加一早上,发现是人眼做 \(10^{18}\) 级整数比大小判错了,抬走。

题意

给定一片 \(N\) 格的农田,从第 \(0\) 天开始,第 \(i\) 格农田每天会长出 \(i\) 的作物。

给出 \(Q\) 个询问,每次询问以 \(D,L,R\) 的格式给出,表示询问在第 \(D\) 天,收割 \([L,R]\) 的农田,会获得多少作物?答案对 \(998244353\) 取模。注意询问相互依赖,即在每一次收割后,\([L,R]\) 的作物应当清零。

\(1\le l_i \le r_i\le n \le 10^{18}\)

\(1\le q \le 2×10^5\)

\(1< d_1 < d_2<…< d_q≤10^{18}\)

题解

值域很大,传统的线段树无法维护。动态开点线段树根据实现的好坏,需要不同程度的卡常。

考虑使用 维护操作过的区间。假设一次操作 \((d,l,r)\) 所操作的区间先前未被操作过,则根据等差数列求和公式,本次操作的答案为 \(\frac{d·(r+l)·(r-l+1)}{2}\)。

std::set

注意到对于一个相同的区间 \([l,r]\),在操作 \((d,l,r)\) 前有操作 \((d_0,l,r)\),则 \((d,l,r)\) 的答案是 \(\frac{(d-d_0)·(r+l)·(r-l+1)}{2}\),其后 \(d_0\) 不再影响接下来的操作,\(d\) 取而代之。

于是在计算答案是可以先计算出不受任何影响的 \(\frac{d·(r+l)·(r-l+1)}{2}\),然后再减去与区间 \([l,r]\) 有交的先前操作的影响,最后由于操作的覆盖性质直接去掉这些相交的区间,并覆盖上 \((d,l,r)\) 即可。

实现上,使用 维护保留下的所有区间,按 \(l\) 为第一关键字排序,每次操作时找到所有与 \([l,r]\) 有交的操作然后减去先前操作的影响。

std::set

对相交的情况分类讨论即可。

发现如此维护区间后, 内保留的区间两两不交。共有 \(q\) 次询问,每次询问都会插入一个区间,每个区间若导致分裂只会产生 \(O(1)\) 个新区间,覆盖其他区间则直接将其删除,而每个块最多被删除一次。总区间数及其操作数仍在 \(O(q)\) 级别,单次操作时间复杂度为 \(O(\log q)\),故总复杂度为 \(O(q\log q)\) ,可以通过本题。

std::set

代码

const ll maxn=2e5+5,mod=998244353,inv=499122177;
struct node{
	ll l,r,d;
	friend bool operator < (const node &x,const node &y){
		return x.l==y.l?x.r<y.r:x.l<y.l;
	}
};
set<node>s;
ll ins(ll l,ll r,ll d){
	ll res=((r+l)%mod*((r-l+1)%mod)%mod)*(d%mod)%mod*inv%mod;//计算原始答案
	auto it=s.lower_bound((node){l,0,d});
	while(it!=s.end()&&it->l<=r){//左端点落在区间内
		if(it->r<=r){//完全被区间包含
			res=(res+mod-((it->r+it->l)%mod*((it->r-it->l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
			s.erase(*it);
		}
		else{//右端点在区间外
			node tmp=*it;
			res=(res+mod-((r+it->l)%mod*((r-it->l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
			s.erase(*it);
			s.insert((node){r+1,tmp.r,tmp.d});
		}
		it=s.lower_bound((node){l,0,d});
	}
	if(it!=s.begin()){
		it--;
		if(it->r>=l){//要求有交
			if(it->r<=r){//左端点在区间外
				node tmp=*it;
				res=(res+mod-((it->r+l)%mod*((it->r-l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
				s.erase(*it);
				s.insert((node){tmp.l,l-1,tmp.d});
			}
			else {//区间完全被包含
				node tmp=*it;
				res=(res+mod-((r+l)%mod*((r-l+1)%mod)%mod*(it->d%mod)%mod*inv%mod)%mod)%mod;
				s.erase(*it);
				s.insert((node){tmp.l,l-1,tmp.d});
				s.insert((node){r+1,tmp.r,tmp.d});
			}
		}
		
	}
	s.insert((node){l,r,d});
	return res;
}
ll n,m;
void solve(){
	n=R,m=R;
	while(m--){
		ll d=R,l=R,r=R;
		we(ins(l,r,d));
	}
	return ;
}