CF453E Little Pony and Lord Tirek（题解）
Leap_Frog
2021-04-12 10:22:34
### P.S.
前情回顾：
去年 9 月份，@[$\color{gray}\text{leapfrog}$](https://www.luogu.com.cn/user/44805) 刚学 Chtholly Tree，Chtholly 没什么好题，都被毒瘤初题人卡光了。
这句话被经过的 @[$\color{black}\text{F}\color{red}\text{lying2018}$](https://www.luogu.com.cn/user/52902) 神仙听到了，就给 @[$\color{gray}\text{leapfrog}$](https://www.luogu.com.cn/user/52902) 推了这道神仙题。
然后菜菜的 @[$\color{gray}\text{leapfrog}$](https://www.luogu.com.cn/user/44805) 不会做，只能加入收藏计划。
当时还是黑题，现在回来一看，发现紫了，@[$\color{gray}\text{leapfrog}$](https://www.luogu.com.cn/user/44805) 看了题解才会做。
~~求赞~~
### Description.
有 $n$ 个数，每秒第 $i$ 个数 $x_i$ 会变成 $\min(m_{i},x_i+k_i)$。
每次操作询问区间和，并把区间 $x_i$ 清零。
### Solution.
我们考虑一个子问题，每次操作都针对整个序列。
我们可以按照 $x_i$ 是否等于 $m_i$ 分类。
$x_i$ 等于 $m_i$ 的一类，我们可以直接统计区间 $m_i$ 和。
$x_i$ 不等于 $m_i$ 的一类，我们直接统计区间 $k_i$ 和，乘上时间差就好了。
问题是怎么分类。~~这不是有手就行~~
按照 $\frac{m_i}{k_i}$ 排序，然后每次肯定是一个前缀 $x_i$ 不等于 $m_i$，后缀都等于。
直接二分找到第一个 $k_i=x_i$ 的位置。
然后前缀和计算 $\sum k_i$，后缀和计算 $\sum m_i$ 即可。
但是现在是对某个子区间进行操作。
我们并不能对整个序列排序求前缀和。
我们现在相当于要求 $\frac{m_i}{k_i}\le qwq,pos\in[l,r]$ 的所有 $k_i$ 和。
我们可以按照 $\frac{m_i}{k_i}$ 排序并离散化，然后一位一位加入主席树。
这样就相当于查询主席树上一个前缀的和了。
这边还有一个 tips，就是一颗主席树可以同时维护那两个值。
还有另外一个问题，就是因为修改并不对于整个序列。
所以每次询问所有的上一次时间是不一定一样的。
而上一次时间是决定了某一个数应该贡献入 $k$ 还是 $m$ 的。
相当于上面的 $qwq$ 和上一次时间是有关系的。
所以我们只能暴力维护，直接上 Chtholly Tree。
而因为这题每次询问之后会对询问区间区间覆盖，所以 Chtholly Tree 时间复杂度正确。
证明就考虑，每次修改至多多 $O(1)$ 个区间，每次查询遍历到的所有区间都会被删除。
所以时间复杂度正确。
这边还有一个小 tips，有些小马初始有权值，可以当做上一次修改是负时间。
### Coding.
```cpp
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}/*}}}*/
int n,Q,K[100005],M[100005],id[100005];
struct data{ll k,b;inline data operator+(data x) const {return(data){k+x.k,b+x.b};}};
struct node{int ls,rs;data vl;}T[2000005];int tt,rt[100005];
inline void pushup(int x) {T[x].vl=T[T[x].ls].vl+T[T[x].rs].vl;}
inline void build(int &x,int l,int r)
{
int md=(l+r)>>1;x=++tt;if(l==r) return T[x].vl=(data){K[l],0},void();
build(T[x].ls,l,md),build(T[x].rs,md+1,r),pushup(x);
}
inline void modif(int &x,int y,int l,int r,int dw)
{
T[x=++tt]=T[y];if(l==r) return T[x].vl=(data){0,M[l]},void();
if(dw<=((l+r)>>1)) modif(T[x].ls,T[y].ls,l,(l+r)>>1,dw),pushup(x);
else modif(T[x].rs,T[y].rs,((l+r)>>1)+1,r,dw),pushup(x);
}
inline data query(int x,int l,int r,int dl,int dr)
{
if(l>dr||dl>r) return(data){0,0};else if(dl<=l&&r<=dr) return T[x].vl;
return query(T[x].ls,l,(l+r)>>1,dl,dr)+query(T[x].rs,((l+r)>>1)+1,r,dl,dr);
}
struct Chtholly{int l,r;mutable double v;char operator<(Chtholly b) const {return l<b.l;}};
typedef set<Chtholly>::iterator IT;set<Chtholly>S;
inline IT split(int wh)
{
IT it=S.lower_bound((Chtholly){wh,114,514});
if(it!=S.end()&&it->l==wh) return it;else it--;
int l=it->l,r=it->r;double v=it->v;S.erase(it);
return S.insert((Chtholly){l,wh-1,v}),S.insert((Chtholly){wh,r,v}).first;
}
inline data calc(double vl,int l,int r)
{
int le=1,ri=n,rs=0;
while(le<=ri) {int md=(le+ri)>>1;if(M[id[md]]<=vl*K[id[md]]) rs=md,le=md+1;else ri=md-1;}
return query(rt[rs],1,n,l,r);
}
set<pair<int,int> >s;
inline char cmp(int a,int b) {return 1ll*M[a]*K[b]<1ll*M[b]*K[a];}
int main()
{
read(n);for(int i=1,x;i<=n;i++)
{
read(x),read(M[i]),read(K[i]),id[i]=i;
if(!M[i]&&!K[i]) M[i]=1;
if(K[i]) S.insert((Chtholly){i,i,-1.0*x/K[i]});
else S.insert((Chtholly){i,i,0}),s.insert(make_pair(i,x));
}
s.insert(make_pair(n+1,0)),build(rt[0],1,n),sort(id+1,id+n+1,cmp);
for(int i=1;i<=n;i++) modif(rt[i],rt[i-1],1,n,id[i]);
for(read(Q);Q--;)
{
set<pair<int,int> >::iterator it;int t,l,r;ll res=0;read(t),read(l),read(r);
while(s.size()>1ull&&(it=s.lower_bound(make_pair(l,0)))->first<=r) res+=it->second,s.erase(it);
IT ir=split(r+1),il=split(l);for(IT i=il;i!=ir;i++)
{data x=calc(t-i->v,i->l,i->r);res+=x.b+(ll)(x.k*(t-i->v)+0.5);}
S.erase(il,ir),S.insert((Chtholly){l,r,1.0*t}),printf("%lld\n",res);
}
return 0;
}
```