树状数组、线段树专题（待完善

下面是OI Wiki对树状数组和线段树原理的详解：
树状数组
 线段树
 动态 DP
upd: 图片说明

线段树非递归的单点写法：（需要维护每个元素所在的叶结点的位置）

int mp[N];//a[i]放在哪个叶结点

void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    if(l==r){
        tree[u].v=a[l];
        mp[l]=u;/*plus*/
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void add(int u,ll v){
    u=mp[u];
    tree[u].v+=v;
    while(u>>=1) pushup(u);
}

A [NOIP2012]借教室

做法：二分+差分
由于随着订单数量的增加，每天可用教室的数量一定单调下降。
因此我们可以二分出第一天出现负值的订单编号。

剩下的问题是如何快速求出经过若干订单后，每天所剩的教室数量。
每个订单的操作是 [L,R]全部减去d。

因此我们可以用差分来加速处理过程。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48606005

int n,m,s[N],t[N];
ll r[N],d[N],diff[N];

bool check(int x){
    mst(diff,0);
    for(int i=1;i<=x;i++){
        diff[s[i]]+=d[i];
        diff[t[i]+1]-=d[i];
    }
    ll need=0;
    rep(i,1,n){
        need+=+diff[i];
        if(need>r[i]) return 0;
    }
    return 1;
}

void solve(){
    cin>>n>>m;
    rep(i,1,n) cin>>r[i];
    rep(i,1,m) cin>>d[i]>>s[i]>>t[i];

    int l=1,r=m,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1,ans=mid;
    }
    if(ans) cout<<"-1\n"<<ans<<"\n";
    else cout<<"0\n";
}

B [SDOI2009]HH的项链

题意求区间内这一段中有多少不同的数字
这是一道很经典的离线莫队的模板题
莫队算法

莫队

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48657705

ll a[N],id[N];
ll res[W],ans[M];
ll cnt;

struct query {
    int l,r,id;
}q[M];

bool cmp(query a, query b) {
    return (id[a.l] ^ id[b.l]) ? id[a.l] < id[b.l] : ((id[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

void solve(){
    int n;cin>>n;
       int len=sqrt(n),siz=(n+len-1)/len;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++) {
        cin>>q[i].l>>q[i].r;
        q[i].id=i; 
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++) {
        int ql=q[i].l,qr=q[i].r;
        while(l < ql) cnt -= !--res[a[l++]];
        while(l > ql) cnt += !res[a[--l]]++;
        while(r < qr) cnt += !res[a[++r]]++;
        while(r > qr) cnt -= !--res[a[r--]];
        ans[q[i].id]=cnt; 
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}

树状数组

先将求区间元素种类数问题转化成求区间和问题
那么怎么转化呢？
我们可以先将所有的询问离线下来，对于每一个r来统计区间[1,r]的元素种类数，利用前缀和的思想来求区间[l,r]的元素种类数（即[1,r]的元素种类数减去[1,l-1]的元素种类数）

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48669053

int n,m;
int a[N],c[N];
int ans[M];
int pre[W];//上一次w出现的位置

struct node{
    int l,id;
};//固定r

//在x位置加上v
void add(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}

//求前缀和
int getsum(int x){
    int res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

vector<node> q[N];

void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    cin>>m;

    rep(i,1,m){
        int l,r;cin>>l>>r;
        q[r].pb({l,i});
    }

    rep(r,1,n){
        if(pre[a[r]]) add(pre[a[r]],-1);
        add(r,1);
        pre[a[r]]=r;
        for(auto [l,id]:q[r]){
            ans[id]=getsum(r)-getsum(l-1);
        }
    }
    rep(i,1,m) cout<<ans[i]<<"\n";
}

C [HEOI2012]采花

这题和上题类似，只要记录上两次次w出现的位置并进行单点修改即可

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48669075

int n,m,w;
int a[N],c[N];
int ans[N];
int pre[N][2];//pre[w][0]:上一次w出现的位置 pre[w][1]:上两次w出现的位置

struct node{
    int l,id;
};//固定r

void add(int x,int v){    //在x位置加上v
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}

//求前缀和
int getsum(int x){
    int res=0;
    while(x>0){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

vector<node> q[N];

void solve(){
    cin>>n>>w>>m;
    rep(i,1,n) cin>>a[i];

    rep(i,1,m){
        int l,r;cin>>l>>r;
        q[r].pb({l,i});
    }

    rep(r,1,n){
        if(pre[a[r]][1]) add(pre[a[r]][1],-1),add(pre[a[r]][0],1);
        else if(pre[a[r]][0]) add(pre[a[r]][0],1);
        pre[a[r]][1]=pre[a[r]][0];
        pre[a[r]][0]=r;
        for(auto [l,id]:q[r]){
            ans[id]=getsum(r)-getsum(l-1);
        }
    }
    rep(i,1,m) cout<<ans[i]<<"\n";
}

D 数据结构

模板题需要维护两个值以及两个懒标记

区间和： $\sum_{x=l}^r (ax+b)=a\sum_{x=l}^r x+\sum_{x=l}^r b$
区间平方和： $\sum_{x=l}^r (ax+b)^2=a^2\sum_{x=l}^r x^2+2ab\sum_{x=l}^r x+\sum_{x=l}^r b^2$

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48657607

int n,m;
ll a[N];
struct node{
    int l,r;
    ll add,mul;
    ll v1,v2;
}tree[N<<2];

void pushup(int u){
    tree[u].v1=tree[u<<1].v1+tree[u<<1|1].v1;
    tree[u].v2=tree[u<<1].v2+tree[u<<1|1].v2;
}

void pushdown(int u){
    if(tree[u].add||tree[u].mul!=1){
        //cal_lazy
        tree[u<<1].v2 = tree[u].mul*tree[u].mul*tree[u<<1].v2 + 2*tree[u].mul*tree[u].add*tree[u<<1].v1 + tree[u].add*tree[u].add*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].v2 = tree[u].mul*tree[u].mul*tree[u<<1|1].v2 + 2*tree[u].mul*tree[u].add*tree[u<<1|1].v1 + tree[u].add*tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1);
        tree[u<<1].v1 = tree[u].mul*tree[u<<1].v1 + tree[u].add*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].v1 = tree[u].mul*tree[u<<1|1].v1 + tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1);

        //union_lazy
        tree[u<<1].mul = tree[u<<1].mul*tree[u].mul;
        tree[u<<1|1].mul = tree[u<<1|1].mul*tree[u].mul;
        tree[u<<1].add = tree[u<<1].add*tree[u].mul + tree[u].add;
        tree[u<<1|1].add = tree[u<<1|1].add*tree[u].mul + tree[u].add;

        //init_lazy
        tree[u].mul=1;tree[u].add=0;
    }
}

void build(int u,int l,int r){
    tree[u].l=l;tree[u].r=r;
    tree[u].mul=1;tree[u].add=0; //init_lazy
    if(l==r){
        tree[u].v2=a[l]*a[l];
        tree[u].v1=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify_add(int u,int l,int r,ll v){
    if(l<=tree[u].l&&tree[u].r<=r){
        tree[u].v2 = tree[u].v2 + 2*v*tree[u].v1 + v*v*(tree[u].r-tree[u].l+1);
        tree[u].v1 = tree[u].v1 + v*(tree[u].r-tree[u].l+1);

        tree[u].add=tree[u].add+v;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify_add(u<<1,l,r,v);
    else if(l>mid) modify_add(u<<1|1,l,r,v);
    else modify_add(u<<1,l,r,v),modify_add(u<<1|1,l,r,v);
    pushup(u);
}

void modify_mul(int u,int l,int r,ll v){
    if(l<=tree[u].l&&tree[u].r<=r){
        tree[u].v2 = tree[u].v2*v*v;
        tree[u].v1 = tree[u].v1*v;

        tree[u].mul=tree[u].mul*v;
        tree[u].add=tree[u].add*v;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify_mul(u<<1,l,r,v);
    else if(l>mid) modify_mul(u<<1|1,l,r,v);
    else modify_mul(u<<1,l,r,v),modify_mul(u<<1|1,l,r,v);
    pushup(u);
}

ll query_sum1(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v1;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query_sum1(u<<1,l,r);
    else if(l>mid) return query_sum1(u<<1|1,l,r);
    else return query_sum1(u<<1,l,r)+query_sum1(u<<1|1,l,r);
}

ll query_sum2(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v2;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query_sum2(u<<1,l,r);
    else if(l>mid) return query_sum2(u<<1|1,l,r);
    else return query_sum2(u<<1,l,r)+query_sum2(u<<1|1,l,r);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            cout<<query_sum1(1,l,r)<<"\n";
        }
        else if(op==2){
            int l,r;cin>>l>>r;
            cout<<query_sum2(1,l,r)<<"\n";
        }
        else if(op==3){
            int l,r;ll x;cin>>l>>r>>x;
            modify_mul(1,l,r,x);
        }
        else{
            int l,r;ll x;cin>>l>>r>>x;
            modify_add(1,l,r,x);
        }
    }
}

$\sum_{i=l}^{r}\sum_{j=i+1}^{r}a_{i}a_{j}\Longrightarrow \sum_{i=l}^{r}a_{i}\sum_{j=i+1}^{r}a_{j}\Longrightarrow \frac{\sum_{i=l}^{r}a_{i}\sum_{j=l}^{r}a_{j}-\sum_{i=l}^{r}a_{i}^{2}}{2}$
然后可以根据上一题求出的区间和和区间平方和套上去即可
代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48662189

ll mod;
int n,m;
ll a[N];

ll fpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

struct node{
    int l,r;
    ll add,mul;
    ll v1,v2;
}tree[N<<2];

void pushup(int u){
    tree[u].v1=(tree[u<<1].v1+tree[u<<1|1].v1)%mod;
    tree[u].v2=(tree[u<<1].v2+tree[u<<1|1].v2)%mod;
}

void pushdown(int u){
    if(tree[u].add||tree[u].mul!=1){
        //cal_lazy
        tree[u<<1].v2 = (tree[u].mul*tree[u].mul%mod*tree[u<<1].v2%mod
        + 2*tree[u].mul%mod*tree[u].add%mod*tree[u<<1].v1%mod
        + tree[u].add*tree[u].add%mod*(tree[u<<1].r-tree[u<<1].l+1)%mod)%mod;
        tree[u<<1|1].v2 = (tree[u].mul*tree[u].mul%mod*tree[u<<1|1].v2%mod
        + 2*tree[u].mul%mod*tree[u].add%mod*tree[u<<1|1].v1%mod 
        + tree[u].add*tree[u].add%mod*(tree[u<<1|1].r-tree[u<<1|1].l+1)%mod)%mod;
        tree[u<<1].v1 = (tree[u].mul*tree[u<<1].v1%mod + tree[u].add*(tree[u<<1].r-tree[u<<1].l+1)%mod)%mod;
        tree[u<<1|1].v1 = (tree[u].mul*tree[u<<1|1].v1%mod + tree[u].add*(tree[u<<1|1].r-tree[u<<1|1].l+1)%mod)%mod;

        //union_lazy
        tree[u<<1].mul = tree[u<<1].mul*tree[u].mul%mod;
        tree[u<<1|1].mul = tree[u<<1|1].mul*tree[u].mul%mod;
        tree[u<<1].add = (tree[u<<1].add*tree[u].mul%mod + tree[u].add)%mod;
        tree[u<<1|1].add = (tree[u<<1|1].add*tree[u].mul%mod + tree[u].add)%mod;

        //init_lazy
        tree[u].mul=1;tree[u].add=0;
    }
}

void build(int u,int l,int r){
    tree[u].l=l;tree[u].r=r;
    tree[u].mul=1;tree[u].add=0; //init_lazy
    if(l==r){
        tree[u].v2=a[l]*a[l]%mod;
        tree[u].v1=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify_add(int u,int l,int r,ll v){
    if(l<=tree[u].l&&tree[u].r<=r){
        tree[u].v2 = (tree[u].v2 + 2*v%mod*tree[u].v1%mod + v*v%mod*(tree[u].r-tree[u].l+1)%mod)%mod;
        tree[u].v1 = (tree[u].v1 + v*(tree[u].r-tree[u].l+1)%mod)%mod;

        tree[u].add=(tree[u].add+v)%mod;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify_add(u<<1,l,r,v);
    else if(l>mid) modify_add(u<<1|1,l,r,v);
    else modify_add(u<<1,l,r,v),modify_add(u<<1|1,l,r,v);
    pushup(u);
}

void modify_mul(int u,int l,int r,ll v){
    if(l<=tree[u].l&&tree[u].r<=r){
        tree[u].v2 = tree[u].v2*v%mod*v%mod;
        tree[u].v1 = tree[u].v1*v%mod;

        tree[u].mul=tree[u].mul*v%mod;
        tree[u].add=tree[u].add*v%mod;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify_mul(u<<1,l,r,v);
    else if(l>mid) modify_mul(u<<1|1,l,r,v);
    else modify_mul(u<<1,l,r,v),modify_mul(u<<1|1,l,r,v);
    pushup(u);
}

ll query_sum1(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v1;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query_sum1(u<<1,l,r);
    else if(l>mid) return query_sum1(u<<1|1,l,r);
    else return (query_sum1(u<<1,l,r)+query_sum1(u<<1|1,l,r))%mod;
}

ll query_sum2(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v2;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) return query_sum2(u<<1,l,r);
    else if(l>mid) return query_sum2(u<<1|1,l,r);
    else return (query_sum2(u<<1,l,r)+query_sum2(u<<1|1,l,r))%mod;
}

void solve(){
    cin>>n>>m>>mod;
    ll inv2=fpow(2,mod-2);
    for(int i=1;i<=n;i++) cin>>a[i],a[i]%=mod;
    build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r;ll x;cin>>l>>r>>x;
            modify_add(1,l,r,x);
        }
        else if(op==2){
            int l,r;ll x;cin>>l>>r>>x;
            modify_mul(1,l,r,x);    
        }

        else{
            int l,r;cin>>l>>r;
            ll ans1=query_sum1(1,l,r);
            ll ans2=query_sum2(1,l,r);
            cout<<(ans1*ans1%mod-ans2+mod)*inv2%mod<<"\n";
        }
    }
}

F little w and Discretization

代码链接：

G 智乃酱的平方数列

代码链接：

H 仓鼠的鸡蛋

线段树树上二分
维护区间最大值，并用二分的思想存放在哪个结点中
优先放左子树，不行放右子树
每次存放修改结点的最大容量

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48704051

int n,m,k;
ll a[N],cnt[N];
struct node{
    int l,r;
    ll v;
}tree[N<<2];

void pushup(int u){
    tree[u].v=max(tree[u<<1].v,tree[u<<1|1].v);
}

void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    if(l==r){
        tree[u].v=m;
        cnt[l]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

ll modify(int u,ll v){
    while(tree[u].l<tree[u].r){
        if(tree[u<<1].v>=v) u<<=1;
        else (u<<=1)|=1;
    }
    tree[u].v-=v;
    int ans=tree[u].l;
    if(++cnt[tree[u].l]==k) tree[u].v=0;
    while(u>>=1) pushup(u);
    return ans;
}

void solve(){
    cin>>n>>m>>k;
    build(1,1,n);
    rep(i,1,n){
        ll x;cin>>x;
        if(x>m) cout<<"-1\n";
        else cout<<modify(1,x)<<"\n";
    }
}