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}\)
题解
值域很大，传统的线段树无法维护。动态开点线段树根据实现的好坏，需要不同程度的卡常。
考虑使用 std::set 维护操作过的区间。假设一次操作 \((d,l,r)\) 所操作的区间先前未被操作过，则根据等差数列求和公式，本次操作的答案为 \(\frac{d·(r+l)·(r-l+1)}{2}\)。
注意到对于一个相同的区间 \([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)\) 即可。
实现上，使用 std::set 维护保留下的所有区间，按 \(l\) 为第一关键字排序，每次操作时找到所有与 \([l,r]\) 有交的操作然后减去先前操作的影响。
对相交的情况分类讨论即可。
发现如此维护区间后，std::set 内保留的区间两两不交。共有 \(q\) 次询问，每次询问都会插入一个区间，每个区间若导致分裂只会产生 \(O(1)\) 个新区间，覆盖其他区间则直接将其删除，而每个块最多被删除一次。总区间数及其操作数仍在 \(O(q)\) 级别，单次操作时间复杂度为 \(O(\log q)\)，故总复杂度为 \(O(q\log q)\) ，可以通过本题。
代码
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 ;
}