$O(q \log n)$ 但是被常数砸死了。

极限数据下大概跑到了时限的两倍。

求正确做法或卡常。

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define rd read()
static char buf[100000], * pa(buf), * pb(buf);
using namespace std;
inline int read()
{
	unsigned register int x=0,s=gc;
	while(s<'0'||s>'9')s=gc;
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
int n,m;
int mx[N<<2];
int len[N<<2],sumv[N<<2],s0[N<<2];
int rs[N<<2],tag1[N<<2],tag2[N<<2];
int ad(int u,int l,int r,int x)
{
   	if(l==r)return max(x,mx[u]);
   	int mid=l+r>>1;
   	if(x>mx[u<<1])return x*(mid-l+1)+ad(u<<1|1,mid+1,r,x);
   	else return ad(u<<1,l,mid,x)+rs[u];
}
inline void pushup1(int u,int l,int r)
{
   	int mid=l+r>>1;
   	mx[u]=max(mx[u<<1],mx[u<<1|1]),rs[u]=ad(u<<1|1,mid+1,r,mx[u<<1]),s0[u]=s0[u<<1]+rs[u];
}
inline void addv(int v,int id,int x){tag1[id]+=x,sumv[id]+=v*x;}
inline void addm(int id,int x){tag2[id]+=x,sumv[id]+=rs[id>>1]*x;}
inline void pushup2(int v,int id){sumv[id]=sumv[id<<1]+sumv[id<<1|1]+tag1[id]*v+tag2[id]*rs[id>>1];}
void add(int id,int l,int r,int x,int w)
{
   	if(l==r)
   	{   	
	   addv(r-l+1,id,w*max(x,mx[id]));
	   return;
	}
   	int mid=l+r>>1;
   	if(x>mx[id<<1])
   	{
      	addv(mid-l+1,id<<1,x*w);
      	add(id<<1|1,mid+1,r,x,w);
   	}
   	else
   	{
      	add(id<<1,l,mid,x,w);
      	addm(id<<1|1,w);
   	}
   	pushup2(r-l+1,id);
}
inline void pushdown(int id,int l,int r)
{
   int x=tag1[id],y=tag2[id];
   tag1[id]=tag2[id]=0;
   int mid=l+r>>1;
   addv(mid-l+1,id<<1,x),addv(r-mid,id<<1|1,x);
   if(id&1)add(id,l,r,mx[id-1],y);
}
void change(int id,int l,int r,int p,int x)
{
   	if(l==r)
   	{
	   mx[id]=x;
	   return;
   	}
   	int mid=l+r>>1;
   	pushdown(id,l,r);
   	if(p<=mid)
   	{
      	if(mid+1<r)pushdown(id<<1|1,mid+1,r);
     	change(id<<1,l,mid,p,x);
   	}
   	else change(id<<1|1,mid+1,r,p,x);
   	pushup1(id,l,r);
}
int qry(int id,int l,int r,int L,int R)
{
	if(r<L||l>R)return 0;
   	if(L<=l&&r<=R)return sumv[id];
	pushdown(id,l,r);
   	int mid=l+r>>1;
   	return qry(id<<1,l,mid,L,R)+qry(id<<1|1,mid+1,r,L,R);
}
signed main()
{
	n=rd,m=rd;
	cout.tie(0);
	while(m--)
   	{
   		int x=rd,y=rd;
      	change(1,1,n,x,y);
		add(1,1,n,0,1);
      	cout<<qry(1,1,n,1,x)<<'\n';
   	}
   return 0;
}