成功把这道小清新题做成了一道大数据结构题，我的评价是我是小丑。
首先显然要离散化对时间轴扫描线。这个除以 \(2\) 下取整的操作显然启示我们往势能的方向思考，也就是我们希望能够找到某个变量，使得这个变量的均摊变化次数在可接受范围内。但是直接以每个元素的值为势能好像也不太对，因为一次全局除以 \(2\) 之后肯定还会通过全局加 \(1\) 加回去，因此一次操作所变化的势能。但是我们发现全局加 \(1\) 不改变的是数组的差分数组，而一次全局除以 \(2\) 的操作对差分数组的影响大体上也是让差分数组中每个元素除以 \(2\)。因此以差分数组的值为势能求解是可取的。
因此大体思路就出来了：用平衡树维护差分数组，每次插入/删除一个元素时直接暴力处理其对差分数组的影响（显然是 \(O(1)\) 的），对于一个时间区间：
- 如果原数组的变化还没有进入周期的状态，就暴力算出全局加多少次 \(1\) 以后数组之和 \(>b\)，然后暴力处理全局除以 \(2\) 对差分数组的影响，具体来说，类似于线段树 beats，如果一个点子树里存在某个差分元素的值 \(\ge 2\)，或者存在某个差分元素的值 \(=1\)，且其原数组中这个数对应的数是奇数，说明这个子树内有可以操作的点，就暴力递归，否则直接返回。
- 否则显然这个时候全局除以 \(2\) 不改变差分数组，也就是说全局除以 \(2\) 这个操作相当于全局加上一个负数，可以 \(O(1)\) 计算出这段时间区间对答案的贡献。
细节很多。下面的代码已经调得不成样子了，大家看看笑笑我这个傻逼就好（
不过好像有比这个做法简单很多的做法。总之感觉这个题思维难度倒不太大，重点在于找到合适的方法实现。
const int MAXN=2e5;
const int MAXP=6e5;
mt19937 rng(114514);
int n,b,l[MAXN+5],r[MAXN+5],t[MAXN+5],key[MAXN*2+5],cnt,uni[MAXN*2+5],num;
int rt,ncnt,curc,ID[MAXN+5],RID[MAXP+5];
struct node{
int ch[2],siz,val,f,key,flg[2];
ll sum,sumv;
}s[MAXP+5];
vector<pii>ins[MAXN*2+5],del[MAXN*2+5];
void pushup(int k){
int ls=s[k].ch[0],rs=s[k].ch[1];
s[k].siz=s[ls].siz+s[rs].siz+1;
s[k].sum=s[ls].sum+s[rs].sum+s[k].val;
s[k].sumv=s[ls].sumv+s[rs].sumv+(s[ls].sum+s[k].val)*s[rs].siz+s[k].val+s[ls].sum;
s[k].flg[0]=s[ls].flg[0]+s[rs].flg[(s[ls].sum+s[k].val)&1];
s[k].flg[1]=s[ls].flg[1]+s[rs].flg[((s[ls].sum+s[k].val)&1)^1];
if(s[k].val==1)s[k].flg[(s[k].val+s[ls].sum)&1]++;
else if(s[k].val>1)s[k].flg[0]++,s[k].flg[1]++;
}
int newnode(int v){
int id=++ncnt;s[id].siz=1;s[id].val=v;
s[id].key=rng();s[id].sum=s[id].sumv=v;
if(v==1)s[id].flg[1]=1;
else if(v>1)s[id].flg[0]=s[id].flg[1]=1;
return id;
}
void split(int k,int siz,int &a,int &b){
if(!k)return a=b=0,void();
if(siz<=s[s[k].ch[0]].siz){
b=k;split(s[k].ch[0],siz,a,s[k].ch[0]);
if(s[k].ch[0])s[s[k].ch[0]].f=k;
pushup(k);
}else{
a=k;split(s[k].ch[1],siz-s[s[k].ch[0]].siz-1,s[k].ch[1],b);
if(s[k].ch[1])s[s[k].ch[1]].f=k;
pushup(k);
}
}
int merge(int a,int b){
if(!a||!b)return a+b;
if(s[a].key<s[b].key){
s[a].ch[1]=merge(s[a].ch[1],b);
s[s[a].ch[1]].f=a;pushup(a);return a;
}else{
s[b].ch[0]=merge(a,s[b].ch[0]);
s[s[b].ch[0]].f=b;pushup(b);return b;
}
}
int findlst(int k,int lim){
if(!k)return 0;int ls=s[k].ch[0],rs=s[k].ch[1];
if(s[ls].sum+s[k].val<=lim)return s[ls].siz+1+findlst(rs,lim-s[ls].sum-s[k].val);
else return findlst(ls,lim);
}
void inc(int k,int p){
if(!s[k].ch[0])s[k].val+=p;
else inc(s[k].ch[0],p);
pushup(k);
}
ll res=0;
void work(int k,int presum){
if(!k||!s[k].flg[(presum&1)^1])return;
int tmp=s[s[k].ch[0]].sum+s[k].val;
s[k].val=(presum+tmp)/2-(presum+tmp-s[k].val)/2;
work(s[k].ch[0],presum);work(s[k].ch[1],presum+tmp);
pushup(k);
}
int findmn(){int k=rt;while(s[k].ch[0])k=s[k].ch[0];return s[k].val;}
signed main(){
scanf("%lld%lld",&n,&b);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&l[i],&r[i],&t[i]),++r[i];
for(int i=1;i<=n;i++)key[++cnt]=l[i],key[++cnt]=r[i];
sort(key+1,key+cnt+1);
for(int i=1;i<=cnt;i++)if(key[i]!=key[i-1])uni[++num]=key[i];
for(int i=1;i<=n;i++){
l[i]=lower_bound(uni+1,uni+num+1,l[i])-uni;
r[i]=lower_bound(uni+1,uni+num+1,r[i])-uni;
ins[l[i]].pb(mp(t[i],i));del[r[i]].pb(mp(t[i],i));
}
for(int i=1;i<num;i++){
for(pii p:ins[i]){
int id=p.se,val=p.fi,pos=findlst(rt,val);
if(pos==curc){
int z=newnode(val-s[rt].sum);
ID[id]=z;RID[z]=id;rt=merge(rt,z);
}else{
int a,b,c;split(rt,pos+1,a,c);split(a,pos,a,b);
int z1=newnode(val-s[a].sum),z2=newnode(s[a].sum+s[b].val-val);
ID[RID[b]]=z2;RID[z2]=RID[b];ID[id]=z1;RID[z1]=id;
rt=merge(merge(a,z1),merge(z2,c));
}
curc++;
}
for(pii p:del[i]){
int id=p.se,nd=ID[id],pos=s[s[nd].ch[0]].siz+1;
while(nd!=rt){
int fa=s[nd].f;
if(s[fa].ch[1]==nd)pos+=s[s[fa].ch[0]].siz+1;
nd=fa;
}
if(pos==curc){int a,b;split(rt,curc-1,a,b);rt=a;}
else{
int a,b,c,d;split(rt,pos-1,a,b);split(b,1,b,c);split(c,1,c,d);
int z=newnode(s[b].val+s[c].val);ID[RID[c]]=z;RID[z]=RID[c];
rt=merge(merge(a,z),d);
}
curc--;
}
if(!s[rt].siz)continue;
int len=uni[i+1]-uni[i],cur=1;
while(cur<=len){
int l=0,r=1e9,p=0;
while(l<=r){
int mid=l+r>>1;
if(s[rt].sumv+1ll*mid*curc<=b)l=mid+1;
else p=mid,r=mid-1;
}
if(cur+p>len){
int cnt=len-cur+1;
res+=1ll*s[rt].sumv*cnt+1ll*cnt*(cnt-1)/2*curc;
inc(rt,cnt);break;
}else{
res+=1ll*s[rt].sumv*p+1ll*p*(p-1)/2*curc;
inc(rt,p);cur+=p;
if(s[rt].flg[1]==(findmn()!=0)&&s[rt].sumv-curc<=b){
int P=s[rt].sum-s[rt].sum/2+1,lft=len-cur+1;
ll sum0=1ll*s[rt].sumv*(P-1)-1ll*P*(P-1)/2*curc;
int rem=lft%P;res+=sum0*(lft/P);
if(rem)res+=1ll*s[rt].sumv*(rem-1)-1ll*(P-1+P-rem+1)*(rem-1)/2*curc;
inc(rt,-(P-rem)%P);
break;
}
work(rt,0);cur++;
}
}
}printf("%lld\n",res);
return 0;
}