黄老师的博客

模板：

const int N=1e5+5;int a[N],belong[N]/*属于哪个块*/,blo/*块的大小*/,block[1000];void update(int l,int r){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++){            //你的操作         }        return ;    }    for(int i=l;i<=belong[l]*blo;i++){        //你的操作     }     for(int i=belong[l]+1;i<=belong[r]-1;i++){        //你的操作     }     for(int i=(belong[r]-1)*blo+1;i<=r;i++){        //你的操作     } } int query(int l,int r){    int ans=0;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++){            //你的操作         }        return ans;    }    for(int i=l;i<=belong[l]*blo;i++){        //你的操作     }     for(int i=belong[l]+1;i<=belong[r]-1;i++){        //你的操作     }     for(int i=(belong[r]-1)*blo+1;i<=r;i++){        //你的操作     }     return ans;}

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=5e4+5;int belong[N],a[N],block[1000],b;void add(int l,int r,int c){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)        a[i]+=c;        return ;    }    for(int i=l;i<=belong[l]*b;i++)a[i]+=c;    for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;    for(int i=(belong[r]-1)*b+1;i<=r;i++)a[i]+=c;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,o,l,r,c;    cin>>n;    b=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++)belong[i]=(i-1)/b+1;    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)add(l,r,c);        else cout<
       
        <
       
      

新技能：边缘块的重置

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=5e4+5;int a[N],belong[N],block[1000],blo;vector
       
        vc[1000];void reset(int x){    vc[x].clear();    for(int i=(x-1)*blo+1;i<=x*blo;i++)vc[x].pb(a[i]);    sort(vc[x].begin(),vc[x].end());}void add(int l,int r,int c){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)a[i]+=c;        reset(belong[l]);        return ;    }    for(int i=l;i<=belong[l]*blo;i++)a[i]+=c;    reset(belong[l]);    for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;    for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c;    reset(belong[r]);}int query(int l,int r,int c){    int ans=0;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)if(a[i]+block[belong[i]]
        
         >n;    blo=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++){        belong[i]=(i-1)/blo+1;        vc[belong[i]].pb(a[i]);    }    for(int i=1;i<=belong[n];i++)sort(vc[i].begin(),vc[i].end());    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)add(l,r,c);        else cout<
         
          <
         
        
       
      

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int a[N],belong[N],block[1000],blo;vector
       
        vc[1000];void reset(int x){    vc[x].clear();    for(int i=(x-1)*blo+1;i<=x*blo;i++)vc[x].pb(a[i]);    sort(vc[x].begin(),vc[x].end());}void add(int l,int r,int c){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)a[i]+=c;        reset(belong[l]);        return ;    }    for(int i=l;i<=belong[l]*blo;i++)a[i]+=c;    reset(belong[l]);    for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;    for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c;    reset(belong[r]);}int query(int l,int r,int c){    int ans=-1;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)if(a[i]+block[belong[i]]
        
         >n;    blo=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++){        belong[i]=(i-1)/blo+1;        vc[belong[i]].pb(a[i]);    }    for(int i=1;i<=belong[n];i++)sort(vc[i].begin(),vc[i].end());    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)add(l,r,c);        else cout<
         
          <
         
        
       
      

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int a[N],belong[N],blo;ll sum[1000],block[1000];void add(int l,int r,int c){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)a[i]+=c,sum[belong[i]]+=c;        return ;    }    for(int i=l;i<=belong[l]*blo;i++)a[i]+=c,sum[belong[i]]+=c;    for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;    for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c,sum[belong[i]]+=c;}ll query(int l,int r,int c){    ll ans=0;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)ans=(ans+a[i]+block[belong[i]]);        return ans;    }    for(int i=l;i<=belong[l]*blo;i++)ans=(ans+a[i]+block[belong[i]]);    for(int i=belong[l]+1;i<=belong[r]-1;i++)ans=(ans+sum[i]+blo*block[i]);    for(int i=(belong[r]-1)*blo+1;i<=r;i++)ans=(ans+a[i]+block[belong[i]]);    return ans;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,o,l,r,c;    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++){        belong[i]=(i-1)/blo+1;        sum[belong[i]]+=a[i];    }    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)add(l,r,c);        else cout<
       
        <
       
      

套路套路

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int a[N],belong[N],blo,flag[1000];ll sum[1000];void solve_sqrt(int x){    if(flag[x])return ;    flag[x]=1;    sum[x]=0;    for(int i=(x-1)*blo+1;i<=x*blo;i++){        a[i]=sqrt(a[i]);        sum[x]+=a[i];        if(a[i]>1)flag[x]=0;    }}void update(int l,int r){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++){            sum[belong[i]]-=a[i];            a[i]=sqrt(a[i]);            sum[belong[i]]+=a[i];        }        return ;    }    for(int i=l;i<=belong[l]*blo;i++){        sum[belong[i]]-=a[i];        a[i]=sqrt(a[i]);        sum[belong[i]]+=a[i];    }    for(int i=belong[l]+1;i<=belong[r]-1;i++)solve_sqrt(i);    for(int i=(belong[r]-1)*blo+1;i<=r;i++){        sum[belong[i]]-=a[i];        a[i]=sqrt(a[i]);        sum[belong[i]]+=a[i];    }}ll query(int l,int r){    ll ans=0;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)ans+=a[i];        return ans;    }    for(int i=l;i<=belong[l]*blo;i++)ans+=a[i];    for(int i=belong[l]+1;i<=belong[r]-1;i++)ans+=sum[i];    for(int i=(belong[r]-1)*blo+1;i<=r;i++)ans+=a[i];    return ans;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,o,l,r,c;    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++){        belong[i]=(i-1)/blo+1;        sum[belong[i]]+=a[i];    }    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)update(l,r);        else cout<
       
        <
       
      

新技能：单块过大，重建块

#include
      
       using namespace std;#define ll long long #define pb push_back#define mp make_pair#define pii pair
       
        #define mem(a,b) memset(a,b,sizeof(a))const int N=2e5+5;int a[N],belong[N],blo,m;vector
        
         vc[1000];pii query(int a){    int top=1;    while(a>vc[top].size())a-=vc[top++].size();    return mp(top,a-1);}void rebuild(){    int top=0;    for(int i=1;i<=m;i++){        for(int j=0;j
         
          15*blo)rebuild();}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,o,l,r,c;    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++){        cin>>a[i];        belong[i]=(i-1)/blo+1;        vc[belong[i]].pb(a[i]);        }    m=belong[n];    for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0)insert(l,r);        else{            pii t=query(r);            cout<
          
           <
          
         
        
       
      

新技能：乘法和加法的标记

#include
      
       using namespace std;#define ll long long #define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;const int MOD=1e4+7;ll a[N],belong[N],tim[1000],plu[1000];int n,blo;void reset(int x){    for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++)a[i]=(a[i]*tim[belong[i]]+plu[belong[i]])%MOD;    tim[x]=1;plu[x]=0;}void add(int l,int r,int c){    if(belong[l]==belong[r]){        reset(belong[l]);        for(int i=l;i<=r;i++){            a[i]+=c;            a[i]%=MOD;        }        return ;    }    reset(belong[l]);    for(int i=l;i<=belong[l]*blo;i++){        a[i]+=c;        a[i]%=MOD;    }    for(int i=belong[l]+1;i<=belong[r]-1;i++){        plu[i]+=c;        plu[i]%=MOD;    }    reset(belong[r]);    for(int i=(belong[r]-1)*blo+1;i<=r;i++){        a[i]+=c;        a[i]%=MOD;    }}void mul(int l,int r,int c){    if(belong[l]==belong[r]){        reset(belong[l]);        for(int i=l;i<=r;i++){            a[i]*=c;            a[i]%=MOD;        }        return ;    }    reset(belong[l]);    for(int i=l;i<=belong[l]*blo;i++){        a[i]*=c;        a[i]%=MOD;    }    for(int i=belong[l]+1;i<=belong[r]-1;i++){        plu[i]*=c;        plu[i]%=MOD;        tim[i]*=c;        tim[i]%=MOD;     }    reset(belong[r]);    for(int i=(belong[r]-1)*blo+1;i<=r;i++){        a[i]*=c;        a[i]%=MOD;    }}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int o,l,r,c;    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++){        cin>>a[i];        belong[i]=(i-1)/blo+1;    }     for(int i=1;i<=belong[n];i++)tim[i]=1;     for(int i=1;i<=n;i++){        cin>>o>>l>>r>>c;        if(o==0){            add(l,r,c);        }        else if(o==1){            mul(l,r,c);        }        else{            cout<<(a[r]*tim[belong[r]]+plu[belong[r]])%MOD<
      

#include
      
       using namespace std;#define ll long long #define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;int a[N],belong[N],blo,block[1000];void reset(int x){    for(int i=(x-1)*blo+1;i<=x*blo;i++){        a[i]=block[belong[i]];    }     block[x]=-1;}int query(int l,int r,int c){    int ans=0;    if(belong[l]==belong[r]){        if(block[belong[l]]!=-1)reset(belong[l]);        for(int i=l;i<=r;i++){            if(a[i]!=c)a[i]=c;            else ans++;        }        return ans;    }    if(block[belong[l]]!=-1)reset(belong[l]);    for(int i=l;i<=belong[l]*blo;i++){        if(a[i]!=c)a[i]=c;        else ans++;     }    for(int i=belong[l]+1;i<=belong[r]-1;i++){        if(block[i]!=-1){                if(block[i]!=c)block[i]=c;                else ans+=blo;         }         else{            for(int j=(i-1)*blo+1;j<=i*blo;j++){                if(a[j]!=c)a[j]=c;                else ans++;            }            block[i]=c;        }    }    if(block[belong[r]]!=-1)reset(belong[r]);    for(int i=(belong[r]-1)*blo+1;i<=r;i++){        if(a[i]!=c)a[i]=c;        else ans++;    }    return ans;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    mem(block,-1);    int n,o,l,r,c;    cin>>n;    blo=sqrt(n);    for(int i=1;i<=n;i++){        cin>>a[i];        belong[i]=(i-1)/blo+1;    }     for(int i=1;i<=n;i++){        cin>>l>>r>>c;        cout<
       
        <
       
      

区间众数

#include
      
       using namespace std;#define ll long long #define pb push_back#define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+5;int a[N],belong[N],blo,cnt[N],val[N];vector
       
        pos[N];vector
        
         v;int f[1000][1000];int n,l,r;void init(int x){    mem(cnt,0);    int mx=0,c=0;    for(int i=(x-1)*blo+1;i<=n;i++){        cnt[a[i]]++;        if(cnt[a[i]]>c){            c=cnt[a[i]];            mx=a[i];        }        else if(cnt[a[i]]==c&&a[i]
         
          c){                c=t;                ans=a[i];            }             else if(t==c&&a[i]
          
           c){            c=t;            ans=a[i];        }         else if(t==c&&a[i]
           
            c){ c=t; ans=a[i]; } else if(t==c&&a[i]
            
             >n; blo=sqrt(n); for(int i=1;i<=n;i++){ cin>>a[i]; v.pb(a[i]); belong[i]=(i-1)/blo+1; } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++){ int t=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; val[t]=a[i]; a[i]=t; pos[a[i]].pb(i); } for(int i=1;i<=belong[n];i++){ init(i); } for(int i=1;i<=n;i++){ cin>>l>>r; cout<
             
              <