http://acm.hdu.edu.cn/showproblem.php?pid=6521
待填
代码
#include<bits/stdc++.h>
#define ls o<<1
#define rs o<<1|1
#define ll long long
using namespace std;
const int MAXN = 5e5+5;
int Mx[MAXN<<2],Mx2[MAXN<<2],Mn[MAXN<<2],ly[MAXN<<2];
ll V[MAXN<<2];
int n,m,l,r;
void push_up(int o){
Mx[o]=max(Mx[ls],Mx[rs]);
Mx2[o]=0;
if(Mx[ls]==Mx[rs]){
Mn[o]=Mn[ls]+Mn[rs];
Mx2[o]=max(Mx2[ls],Mx2[rs]);
}else{
if(Mx[ls]>Mx[rs]){
Mx[o]=Mx[ls];Mn[o]=Mn[ls];V[o]=V[ls];Mx2[o]=Mx2[ls];ly[o]=ly[ls];
}else{
Mx[o]=Mx[rs];Mn[o]=Mn[rs];V[o]=V[rs];Mx2[o]=Mx2[rs];ly[o]=ly[rs];
}
Mx2[o]=max(Mx2[ls],Mx2[rs]);
if(Mx[o]==Mx[ls])Mx2[o]=max(Mx2[o],Mx[rs]);
else Mx2[o]=max(Mx2[o],Mx[ls]);
}
V[o]=V[ls]+V[rs];
}
void ch(int o,int x){
V[o]-=(1ll*Mx[o]-x)*Mn[o];
Mx[o]=ly[o]=x;
}
void push_down(int o){
if(Mx[ls]>ly[o]){ch(ls,ly[o]);ly[ls]=ly[o];}
if(Mx[rs]>ly[o]){ch(rs,ly[o]);ly[rs]=ly[o];}
ly[o]=-1;
}
void build(int o,int l,int r){
ly[o]=-1;Mx2[o]=0;
if(l==r){V[o]=Mx[o]=l;Mn[o]=1;return;}
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(o);
}
void ud(int o,int l,int r,int L,int R,int x){
if(~ly[o])push_down(o);
int mid=(l+r)/2;
if(L<=l&&r<=R){
if(x>=Mx[o])return;
else if(x>Mx2[o]){ch(o,x);return;}
else{
ud(ls,l,mid,L,R,x);ud(rs,mid+1,r,L,R,x);
//return; //没有return;
}
}
if(L<=mid)ud(ls,l,mid,L,R,x);
if(R>mid)ud(rs,mid+1,r,L,R,x);
push_up(o);
}
ll qSum(int o,int l,int r,int L,int R){
if(~ly[o])push_down(o);
if(L<=l&&r<=R)return V[o];
int mid=(l+r)/2;
ll ans=0;
if(L<=mid)ans+=qSum(ls,l,mid,L,R);
if(R>mid)ans+=qSum(rs,mid+1,r,L,R);
push_up(o);
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
build(1,1,n);
while(m--){
scanf("%d%d",&l,&r);
ll tp=qSum(1,1,n,l,r);
ud(1,1,n,l,r,l);
printf("%lld\n",tp-qSum(1,1,n,l,r));
}
}
}