# ABC255Ex()-其他

## ABC255Ex()

*2430

### 题意

$$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

std::set

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 ;
}

————————

*2430

### 题意

$$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

std::set

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 ;
}