[均攤 線段樹] UOJ #228. 基礎資料結構練習題

靠信仰做題

其實很好感性的了解複雜度

想象數列是一排山峰高低不平 可以用O(K*n)次開根把他們削平

區間加操作不過是把其中一段整體擡高 

隻要在這段兩邊多做常數次 loglogn 次就能把他削平

Evan可是用偏導證明的 %%%

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=100005;
struct node{
  ll min,max,sum,add;
  void upd(int l,int r,ll x){
    add+=x,min+=x,max+=x;
    sum+=x*(r-l+1);
  }
}T[N<<2];

inline void Pushup(int x,int l,int r) {
  T[x].min=min(T[x<<1].min,T[x<<1|1].min)+T[x].add;
  T[x].max=max(T[x<<1].max,T[x<<1|1].max)+T[x].add;
  T[x].sum=T[x<<1].sum+T[x<<1|1].sum+T[x].add*(r-l+1);
}

inline void Sqrt(int x,int l,int r,int ql,int qr,ll tag) {
  if(ql<=l && r<=qr) {
    if (T[x].min==T[x].max  || T[x].max-T[x].min==(ll)sqrt(T[x].max+tag)-(ll)sqrt(T[x].min+tag)) {
      ll ad=(ll)sqrt(T[x].min+tag)-T[x].min-tag;
      T[x].upd(l,r,ad);
      return;
    }
    Sqrt(x<<1,l,mid,ql,qr,tag+T[x].add),Sqrt(x<<1|1,mid+1,r,ql,qr,tag+T[x].add);
    Pushup(x,l,r);
    return;
  }
  if(ql<=mid) Sqrt(x<<1,l,mid,ql,qr,tag+T[x].add);
  if(qr>mid) Sqrt(x<<1|1,mid+1,r,ql,qr,tag+T[x].add);
  Pushup(x,l,r);
}

inline void Add(int x,int l,int r,int ql,int qr,ll tag) {
  if(ql<=l&&r<=qr){
    T[x].upd(l,r,tag);
    return;
  }
  if(ql<=mid)
    Add(x<<1,l,mid,ql,qr,tag);
  if(qr>mid)
    Add(x<<1|1,mid+1,r,ql,qr,tag);
  Pushup(x,l,r);
}

inline ll Query(int x,int l,int r,int ql,int qr,ll add) {
  ll ret=0;
  if(ql<=l&&r<=qr)
    return T[x].sum+add*(r-l+1);
  if(ql<=mid)
    ret+=Query(x<<1,l,mid,ql,qr,add+T[x].add);
  if(qr>mid)
    ret+=Query(x<<1|1,mid+1,r,ql,qr,add+T[x].add);
  return ret;
}

int n;
int Val[N];

inline void Build(int x,int l,int r) {
  if(l==r){ T[x].min=T[x].max=T[x].sum=Val[l]; return; }
  Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
  Pushup(x,l,r);
}

int main(){
  int Q; int order,l,r,t;
  freopen("extra.in","r",stdin);
  freopen("extra.out","w",stdout);
  read(n); read(Q);
  for (int i=1;i<=n;i++) read(Val[i]);
  Build(1,1,n);
  while (Q--){
    read(order); read(l); read(r);
    if (order==1){
      read(t);
      Add(1,1,n,l,r,t);
    }else if (order==2){
      Sqrt(1,1,n,l,r,0);
    }else{
      printf("%lld\n",Query(1,1,n,l,r,0));
    }
  }
  return 0;
}
           

UPD: 吉麗的證明

就是勢能函數 是 相鄰兩數 的差  最初勢能是 O(nV)

每次區間加 會讓勢能增加 V 分别在兩端

對一個滿足條件的區間 開根 log log n 次勢能下降 V  每次時間複雜度 logn

總勢能 (n+m)V 時間複雜度是 n+m logn loglogn

除了替罪羊樹以外第一次接觸勢能分析 好神奇