求调
  • 板块学术版
  • 楼主DreamSpaceDream
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/4 19:30
  • 上次更新2023/12/4 21:46:26
查看原帖
求调
229474
DreamSpaceDream楼主2023/12/4 19:30

P9130

#include<bits/stdc++.h>
#define lb lower_bound
using namespace std;
typedef long long ll;
const ll N=1e5,INF=1e15,mod=1e9+7,mod2=500000004;
ll q;
ll a[N+1],b[N+1];
ll X[N+2],n;
struct S{
    ll h,t;
    ll ans;
    ll l,o;
}T[N*4+1];
inline ll S(ll p,ll k){
	
    ll l=X[T[p].h],r=X[T[p].t+1]-k;
    return (((r-l)%mod)*((l+r-1)%mod)%mod)*mod2%mod; 
}
inline ll F(ll p,ll k){
    if(T[p].h==T[p].t)return S(p,T[p].l-k);  
    if(T[p<<1].l>=k)return (F(p<<1,k)+T[p<<1|1].ans        )%mod;
    else            return (S(p<<1,0)+F(p<<1|1,k-T[p<<1].l))%mod;
}
inline void PU(ll p){
    if(T[p<<1].o>T[p<<1|1].l){
        T[p].ans=T[p<<1].ans+S(p<<1|1,0),T[p].ans%=mod;
        T[p].l  =T[p<<1].l;
        T[p].o  =T[p<<1|1].o+(T[p<<1].o-T[p<<1|1].l);
    }else{
        T[p].o  =T[p<<1|1].o;
        T[p].l  =T[p<<1].l+(T[p<<1|1].l-T[p<<1].o);
        T[p].ans=T[p<<1].ans+F(p<<1|1,T[p<<1].o),T[p].ans%=mod; 
	}
}
inline void B(ll p,ll l,ll r){
    T[p].h=l,T[p].t=r;T[p].l=X[r+1]-X[l];
    if(l==r)return ;
    ll mid=l+r>>1;
    B(p<<1  ,l    ,mid);
    B(p<<1|1,mid+1,r  );
    return ;
}
inline void UD(ll p,ll id,ll k){
    if(T[p].h==T[p].t){
        ll len=X[T[p].t+1]-X[T[p].h];
        if(k<=len)T[p].l=len-k,T[p].o=0    ;
        else      T[p].l=0    ,T[p].o=k-len;
        T[p].ans=S(p,T[p].l);
        return ;
    }
    ll mid=T[p].h+T[p].t>>1;
    if(id<=mid)UD(p<<1  ,id,k);
    else       UD(p<<1|1,id,k);
    PU(p);
    return ;
}
inline ll R(){
    char c=getchar();
    ll s=1;
    for(;!('0'<=c&&c<='9'||c=='-');c=getchar());
    if(c=='-'){
        s=-1;
        c=getchar();
    }
    ll num=0; 
    while('0'<=c&&c<='9'){
        num=num*10+(c-'0');
        c=getchar();      
    }
    num=num*s;
    return num;
}
int main(){
    ll i,j;
    
    q=R();
    for(i=1;i<=q;i++){
        a[i]=R(),b[i]=R();
        X[++n]=a[i];
    }
    sort(X+1,X+n+1);n=unique(X+1,X+n+1)-X-1;
    X[n+1]=INF;
    B(1,1,n);
    for(i=1;i<=q;i++)a[i]=lb(X+1,X+n+1,a[i])-X;
    for(i=1;i<=q;i++){
        UD(1,a[i],b[i]);
        printf("%lld\n",T[1].ans);
    }
    return 0;
}
2023/12/4 19:30
加载中...