全蛙求条

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,s,a[N],c[N],e[N];
struct node{
	int l,t;
}p[N];
bool cmp(node x,node y){
	return x.t<y.t;
}
int lowbit(int x){
	return x&(-x);
}
void add_c(int x,int v){
	for(int i=x;i<=1e5;i+=lowbit(i)){
		c[i]+=v;
	}
}
int find_c(int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i)){
		ans+=c[i];
	}
	return ans;
}
void add_e(int x,int v){
	for(int i=x;i<=1e5;i+=lowbit(i)){
		e[i]+=v;
	}
}
int find_e(int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i)){
		ans+=e[i];
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p[i].l,&p[i].t);
	}
	sort(p+1,p+1+n,cmp);
	int ans=0,sum=0;
	for(int i=1;i<=n;i++){
		sum+=p[i].t;
		ans+=p[i].l-sum;
		add_c(p[i].t,1);
		add_e(p[i].t,p[i].t);
	}
	printf("%d\n",ans);
	while(s--){
		int d,l,t;
		scanf("%d%d%d",&d,&l,&t);
		int cnt=find_c(t)-find_c(p[d].t);
		ans+=cnt*p[d].t;
		int cou=find_c(1e5)-find_c(t);
		ans-=cou*(t-p[d].t);
		ans-=p[d].l-find_e(p[d].t);
		add_c(p[d].t,-1);
		add_e(p[d].t,-p[d].t);
		add_c(t,1);
		add_e(t,t);
		p[d].l=l;
		p[d].t=t;
		ans+=p[d].l-find_e(p[d].t);
		printf("%d\n",ans);
	}
	return 0;
}