ABC255 Ex. Range Harvest Query
Difficulty:2430
問題
長さ$ Nの数列がある。はじめ、すべての項は0である。
毎日の朝に各$ i(1 \leq i \leq N)項目に$ iが加算される。
以下のクエリを処理せよ。
$ D日目の夜時点の$ L_i項目から$ R_i項目までの和を出力し、$ L_i項目から$ R_i項目までを0にする。
※ただし出力時は極めて大きい値になることがあるので、$ 998244353で割ったあまりを出力すること。
解法
区間をsetで管理するテクを少し応用する。区間ごとに「最後に0になった時間」を保存しておけばよい。
はじめは区間[0,N] 0があり、例えばクエリD=5,L = 3, R = 4が与えられたとき、
区間[0,2] 0,[3,4] 5,[5,N] 0に分割する。
クエリで増える区間の数は高々2個であり、区間に含まれていた区間はすべて削除されるため、総じて区間の増減は$ O(Q)回となる。区間の追加と削除、および区間が含む区間の先頭を取得する操作はsetのサイズを$ Nとして$ O(\log N)で可能なので、$ O(Q \log Q)でこの問題を解くことができた。
実装
code:cpp
bool solve(){
LL(n,q);
set<tuple<ll,ll,ll>>s;
s.insert({0,n,0});
ll pre{};
auto f = [](mint l,mint r){
return (l+r)*(r-l+1)/2;
};
rep(i,q){
LL(d,l,r);
auto it = s.upper_bound({l,0,0});
it--;
queue<tuple<ll,ll,ll>>qu,equ;
mint ret{};
while(it!=s.end()){
//範囲外
if(l2>r)break;
equ.push({l2,r2,d2});
if(l2<l){
qu.push({l2,l-1,d2});
}
if(r2>r){
qu.push({r+1,r2,d2});
}
// deb(i,l2,r2,d2);
// deb(ret);
ret += f(max(l2,l),min(r2,r))*(d-d2);
it++;
}
qu.push({l,r,d});
while(equ.size()){
equ.pop();
s.erase({l2,r2,d2});
}
while(qu.size()){
qu.pop();
s.insert({l2,r2,d2});
}
O(ret.val());
}
return true;
}