线段树 get！

A4paper · 2018-05-24 20:38:52 · 个人记录

模板：

不多说，上模板。

传送门

#define _R k*2+1
#define _L k*2

long long x,y,num;
long long n,m,p,flag;

struct node
{
    int L,R;
    long long W;
    long long tag_add,tag_mul;
}tree[500005];

void buildtree(int l, int r, int k)
{
    tree[k].L = l;
    tree[k].R = r;
    tree[k].tag_add = 0;
    tree[k].tag_mul = 1;
    if(tree[k].L == tree[k].R)
    {
        cin >> tree[k].W;
        return;
    }
int mid = (tree[k].L + tree[k].R) / 2;
    buildtree(l,mid,_L);
    buildtree(mid+1,r,_R);
    tree[k].W = tree[_L].W + tree[_R].W;
}

void down(int k)
{
    if(tree[k].tag_add!=0 || tree[k].tag_mul!=1)
    {
        tree[_L].W     = (tree[ k].tag_add*(tree[_L].R - tree[_L].L+1) % p + tree[_L].W*tree[k].tag_mul % p) % p;
        tree[_R].W    = (tree[ k].tag_add*(tree[_R].R - tree[_R].L+1) % p + tree[_R].W*tree[k].tag_mul % p) % p;
        tree[_L].tag_add = (tree[_L].tag_add* tree[k].tag_mul + tree[k].tag_add) % p;
        tree[_R].tag_add = (tree[_R].tag_add* tree[k].tag_mul + tree[k].tag_add) % p;
        tree[_L].tag_mul =  tree[_L].tag_mul* tree[k].tag_mul % p;
        tree[_R].tag_mul =  tree[_R].tag_mul* tree[k].tag_mul % p;
        tree[ k].tag_add =  0;
        tree[ k].tag_mul =  1;
    }
}

void add_line(int k)
{
    if(tree[k].L>=x && tree[k].R<=y)
    {
        tree[k].W = (tree[k].W+num*(tree[k].R - tree[k].L+1)) % p;
        tree[k].tag_add = (tree[k].tag_add + num) % p;
        return;
    }
    down(k);
int mid = (tree[k].L + tree[k].R)/2;
    if(x <= mid)    add_line(_L);
    if(y >  mid)    add_line(_R);
    tree[k].W = tree[_L].W + tree[_R].W;
}

void mul_line(int k)
{
    if(tree[k].L>=x && tree[k].R<=y)
    {
        tree[k].W       = tree[k].W      *num % p;
        tree[k].tag_add = tree[k].tag_add*num % p;
        tree[k].tag_mul = tree[k].tag_mul*num % p;
        return;
    }
    down(k);
int mid = (tree[k].L + tree[k].R)/2;
    if(x <= mid)    mul_line(_L);
    if(y >  mid)    mul_line(_R);
    tree[k].W = tree[_L].W + tree[_R].W; 
}

long long ask_line(int k)
{
    if(tree[k].L>=x && tree[k].R<=y)
    {
        return tree[k].W % p;
    }
    down(k);
long long mid = (tree[k].L + tree[k].R)/2;
long long ans = 0;
    if(x <= mid)    ans += ask_line(_L) % p;
    if(y >  mid)    ans += ask_line(_R) % p;
    return ans % p;
}

int main()
{
    cin >> n >> m >> p;
    buildtree(1,n,1);
    for(int i=1;i<=m;i++)
    {
        cin >> flag;
        if(flag == 1)   {
            cin >> x >> y >> num;
            mul_line(1);
        }
        if(flag == 2)   {
            cin >> x >> y >> num;
            add_line(1);
        }
        if(flag == 3)   {
            cin >> x >> y;
            cout << ask_line(1) % p << endl;
        }
    }
    return 0;
}

线段树求区间最大子段和：

//SP1716

区间最大子段和 + 单点修改

#define Ls k*2
#define Rs k*2+1

int m,n;
int a;

struct node{
    int L,R;
    int sum,maxL,maxR,maxS;
}tree[4*MAXN];

void build(int L, int R, int k)
{
    tree[k].L = L;
    tree[k].R = R;
    if(L == R)
    {
        cin >> a;
        tree[k].sum  = tree[k].maxS = tree[k].maxL = tree[k].maxR = a;
        return;
    }
    int mid = (L+R)/2;
    build(L,mid,Ls);
    build(mid+1,R,Rs);
    tree[k].sum  = tree[Ls].sum+tree[Rs].sum;
    tree[k].maxL = max(tree[Ls].maxL,tree[Ls].sum+tree[Rs].maxL);
    tree[k].maxR = max(tree[Rs].maxR,tree[Rs].sum+tree[Ls].maxR);
    tree[k].maxS = max(max(tree[Ls].maxS,tree[Rs].maxS),tree[Ls].maxR+tree[Rs].maxL);
}
void add(int x, int y, int k)
{
    int l = tree[k].L;
    int r = tree[k].R;
    if(l == r)
    {
        tree[k].sum  = tree[k].maxS = tree[k].maxL = tree[k].maxR = y;
        return;
    }
    int mid  = (l+r)/2;
    if(x <= mid)    add(x,y,Ls);
    if(x >  mid)    add(x,y,Rs);
    tree[k].sum  = tree[Ls].sum+tree[Rs].sum;
    tree[k].maxL = max(tree[Ls].maxL,tree[Ls].sum+tree[Rs].maxL);
    tree[k].maxR = max(tree[Rs].maxR,tree[Rs].sum+tree[Ls].maxR);
    tree[k].maxS = max(max(tree[Ls].maxS,tree[Rs].maxS),tree[Ls].maxR+tree[Rs].maxL);
}
node query(int L, int R, int k)
{
    node _L,_R,ans;
    int l = tree[k].L;
    int r = tree[k].R;
    if(l >= L && r <= R)    return tree[k];
    int mid = (l+r)/2;
    if(R <= mid)        return query(L,R,Ls);
    else if(L >  mid)   return query(L,R,Rs);
    else{
        _L = query(L,R,Ls); _R = query(L,R,Rs);
        ans.sum  = _L.sum+_R.sum;
        ans.maxL = max(_L.maxL,_L.sum+_R.maxL);
        ans.maxR = max(_R.maxR,_R.sum+_L.maxR);
        ans.maxS = max(max(_L.maxS,_R.maxS),_L.maxR+_R.maxL);
        return ans;
    }
}

线段树求平均数+方差：

传送门

在线段树内存的并不是平均数和方差，而是先存区间和与区间平方和，查询时再间接求出。

struct node{
    long long L,R;
    long long x2,sum;
    long long tag;
    node(){
        L = R = tag = x2 = sum = 0;
    }
}tree[4*MAXN];
void down(long long k)
{
    long long w = tree[k].tag;
    tree[_L].tag += w;
    tree[_R].tag += w;
    tree[_L].x2  += w*w*(tree[_L].R-tree[_L].L+1)+2*w*tree[_L].sum;
    tree[_R].x2  += w*w*(tree[_R].R-tree[_R].L+1)+2*w*tree[_R].sum;
    tree[_L].sum += w*  (tree[_L].R-tree[_L].L+1);
    tree[_R].sum += w*  (tree[_R].R-tree[_R].L+1);
    tree[k].tag = 0;
}
void build(long long L, long long R, long long k)
{
    tree[k].L = L;
    tree[k].R = R;
    if(L == R)
    {
        cin >> tree[k].sum;
        tree[k].x2 = tree[k].sum*tree[k].sum;
        return;
    }
    long long mid = (L+R)>>1;
    build(L,mid,_L);
    build(mid+1,R,_R);
    tree[k].sum = tree[_L].sum+tree[_R].sum;
    tree[k].x2  = tree[_L].x2 +tree[_R].x2;
}
void update(long long l, long long r, long long k, long long w)
{
    long long L = tree[k].L;
    long long R = tree[k].R;
    if(L>=l && R<=r)
    {
        tree[k].x2  += w*w*(R-L+1)+2*w*tree[k].sum;
        tree[k].sum += w*(R-L+1);
        tree[k].tag += w;
        return;
    }
    down(k);
    long long mid = (L+R)>>1;
    if(l <= mid) update(l,r,_L,w);
    if(r >  mid) update(l,r,_R,w);
    tree[k].sum = tree[_L].sum+tree[_R].sum;
    tree[k].x2  = tree[_L].x2 +tree[_R].x2;
}
node query(long long l, long long r, long long k)
{
    node x,y,ans;
    long long L = tree[k].L;
    long long R = tree[k].R;
    if(L>=l && R<=r) return tree[k];
    down(k);
    long long mid = (L+R)>>1;
    if(l <= mid) x = query(l,r,_L);
    if(r >  mid) y = query(l,r,_R);
    ans.sum = x.sum+y.sum;
    ans.x2  = x.x2 +y.x2;
    return ans;
}
long long gcd(long long a, long long b)
{
    if(b == 0) return a;
    return gcd(b,a%b);
}
int main()
{
    cin >> n >> m;
    build(1,n,1);
    for(long long i=1;i<=m;i++)
    {
        node p;
        long long k,l,r,d,N,g,as,bs;
        cin >> k >> l >> r;
        switch(k)
        {
            case 1:
                cin >> d;
                update(l,r,1,d);
            break;
            case 2:
                p = query(l,r,1);
                N = (r-l+1);
                g = gcd(p.sum,N);
                p.sum /= g;
                N /= g;
                cout << p.sum << '/' << N << endl;
            break;
            case 3:
                p = query(l,r,1);
                N = (r-l+1);
                as = p.x2*N-p.sum*p.sum;
                bs = N*N;
                if(as == 0) bs = 1;
                else
                {
                    g = gcd(as,bs);
                    as /= g;    bs /= g;
                } 
                cout << as << '/' << bs << endl;
            break;
        }
    }
    return 0;
}

线段树求单调上升子序列：

传送门

结构体中的 max 表示区间最大值，不过在本题中还有一个意义，就是单调上升子序列中的右端点（建议诸君不要学我用关键字当变量。。。） num 表示子序列长度。

建树和单点修改都不难，重点在于更新 num 。

如何将两个区间的子序列合并并统计长度呢？

首先，我们发现，左区间的子序列是不会变的，而右区间低于左区间 max 的部分要被减去，所以可以二分的查找左区间 max 在右区间的位置。

如果小于 mid ，那说明左区间还有大于它的数没记，要询问左区间并加上右区间的长度。

反之亦然。

struct Segment_T{
    int L,R;
    double max;
    int num;
}tree[4*MAXN];

void build(int L, int R, int k)
{
    tree[k].L = L;
    tree[k].R = R;
    if(L == R) return;
    int mid = (L+R)>>1;
    build(L    ,mid,_L);
    build(mid+1,R  ,_R);
}

int update_tree(int k, double w)
{
    int L = tree[k].L;
    int R = tree[k].R;
    if(L >= R) return tree[k].max > w;
    if(w >= tree[_L].max) return update_tree(_R,w);
    else return tree[k].num-tree[_L].num+update_tree(_L,w);
}

void update(int x, double w, int k)
{
    int L = tree[k].L;
    int R = tree[k].R;
    if(L == R)
    {
        tree[k].max = w;
        tree[k].num = 1;
        return;
    }
    int mid = (L+R)>>1;
    if(x <= mid) update(x,w,_L);
    if(x >  mid) update(x,w,_R);
    tree[k].max = max(tree[_L].max,tree[_R].max);
    tree[k].num = tree[_L].num+update_tree(_R,tree[_L].max);
}

int main(void)
{
    cin >> n >> m;
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int num,Yi;
        cin >> num >> Yi;
        double w = (double)Yi/num;
        update(num,w,1);
        cout << tree[1].num << endl;
    }
    return 0;
}

线段树求第k个值：

传送门

又学到了新姿势，在这之前我一直以为这只能动态开点求的，，，

其实十分简单，一看就会，

利用权值线段树的思想，当这个点有值时 tree[k].cnt 为 1 ，统计它的和，查询第 k 个值时若 k <= tree[\_L].cnt ，说明第 k 个数在左边，否则在右边。

注意，查询右子树时要将 k 减去 tree[\_L].cnt 。

#define _L k<<1
#define _R k<<1|1
#define L(x) tree[(x)].L
#define R(x) tree[(x)].R
#define W(x) tree[(x)].w
#define int long long

int n,m;
int a[MAXN];

struct node{
    int L,R;
    int w,cnt;
}tree[4*MAXN];

void update(int k)
{
    W(k) = W(_L)+W(_R);
    tree[k].cnt = tree[_L].cnt+tree[_R].cnt;
}

void build(int L, int R, int k)
{
    L(k) = L;
    R(k) = R;
    if(L == R)
    {
        W(k) = a[L];
        if(a[L]) tree[k].cnt = 1;
        return;
    }
    int mid = (L+R)>>1;
    build(L,mid,_L);
    build(mid+1,R,_R);
    update(k);
}

void update_point(int k, int x, int w)
{
    if(L(k) == R(k))
    {
        W(k) -= w;
        return;
    }
    int mid = (L(k)+R(k))>>1;
    if(x <= mid) update_point(_L,x,w);
    else         update_point(_R,x,w);
    update(k);
}

void add_point(int k, int x, int w)
{
    if(L(k) == R(k))
    {
        W(k) = w;
        tree[k].cnt = 1;
        return;
    }
    int mid = (L(k)+R(k))>>1;
    if(x <= mid) add_point(_L,x,w);
    else         add_point(_R,x,w);
    update(k);
}

void Delete(int k, int x)
{
    if(L(k)==R(k) && x==tree[k].cnt)
    {
        W(k) = 0;
        tree[k].cnt--;
        return;
    }
    if(x <= tree[_L].cnt)   Delete(_L,x);
    else                    Delete(_R,x-tree[_L].cnt);
    update(k);
}

signed main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,MAXN,1);
    for(int i=1;i<=m;i++)
    {
        char c;
        int x,y;
        cin >> c;
        switch(c)
        {
            case 'C':
                cin >> x >> y;
                update_point(1,x,y);
                break;
            case 'I':
                cin >> x >> y;
                add_point(1,x,y);
                break;
            case 'D':
                cin >> x;
                Delete(1,x);
                break;
            case 'Q':
                cout << W(1) << "\n";
                break;
        }
    }
    return 0;
}

题目：

高难：

传送门

不过是真的累。。。我们以每个水面高度的答案为叶节点建树，向上建树时维护区间和（其实随便维护什么都行，因为用不到。。。），然后这道题就变成了区间修改+单点查询那么，怎么统计并维护信息呢？首先，开结构体存下所有数据并离散化（因为高度可达 $10^9$）然后，再一个个处理这些结构体，对于每个点的初始高度，其实可以和操作 1 的方法一样进行处理，不过就是特判旁边石头高度为 0 的情况，所以就直接讲一下操作 1 怎么维护：把一个石头改成另一个高度，可以看成先变成 0 ，再加上某一高度。这两个过程是反着的，所以我就只讲一下怎么增加高度（即从 0 变成某高度）：我们设该石头的位置为 $k$，高度为 $a[k] = 0$，要变成 $h$ ，有三种情况：（前排提示：请结合画图食用） 1. $a[k-1] < h \ \&\&\ a[k+1] < h

**中间的石头最高。**

此时 $1$ 到 $\min(a[k-1],a[[k+1])$ 高度的答案 $-1$ 

$\max(a[k-1],a[k+1])$ 到 $a[k]$ 高度的答案 $+1$

a[k-1] > h \ \&\&\ a[k+1] > h
中间的石头最低。

此时 1 到 h 高度的答案 -1
(a[k-1] <= h <= a[k+1]) \ ||\ (a[k-1] >= h >= a[k+1])
中间石头的高度处于中等位置。

此时 \min(a[k+1],a[k-1]) 到 h 高度的答案 -1

然后就是注意 a[k-1] 和 a[k+1] 为 0 的时候。

剩下的，就是拼码力了。

#define _L k<<1
#define _R k<<1|1
#define L(a) tree[a].L
#define R(a) tree[a].R
#define W(a) tree[a].w
#define T(a) tree[a].tag

int n,m,cnt,ans;
int tmp[MAXN];
int a[MAXN];

struct node{
    int F,h,x;
}flag[2*MAXN];

struct Node{
    int L,R;
    int w,tag;
}tree[4*MAXN];

void down(int k)
{
    int T = T(k);   T(k) = 0;
    T(_L) += T;
    T(_R) += T;
    W(_L) += T*(R(_L)-L(_L)+1);
    W(_R) += T*(R(_R)-L(_R)+1);
}

void build(int L, int R, int k)
{
    L(k) = L;   R(k) = R;
    if(L == R)
    {
        if(!L) W(k) = 1;
        else W(k) = 0;
        return;
    }
    int mid = (L+R)>>1;
    build(L,mid,_L);
    build(mid+1,R,_R);
    W(k) = W(_L)+W(_R);
}

void update_section(int k, int l, int r, int w)
{
    if(L(k)>=l && R(k)<=r)
    {
        W(k) += w*(R(k)-L(k)+1);
        T(k) += w;  return;
    }
    down(k);
    int mid = (L(k)+R(k))>>1;
    if(l <= mid) update_section(_L,l,r,w);
    if(r >  mid) update_section(_R,l,r,w);
    W(k) = W(_L)+W(_R);
}

void query(int k, int x)
{
    if(L(k) == R(k)){ans = W(k); return;}
    down(k);
    int mid = (L(k)+R(k))>>1;
    if(x <= mid) query(_L,x);
    else         query(_R,x);
}

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin >> a;
        flag[i] = (node){0,a,0};
        tmp[++cnt] = a;
    }
    for(int i=1;i<=m;i++)
    {
        int x,a,b;
        cin >> x >> a;
        if(x == 1)
        {
            flag[i+n] = (node){1,a,0};
            tmp[++cnt] = a;
        }
        if(x == 2)
        {
            cin >> b;
            flag[i+n] = (node){2,b,a};
            tmp[++cnt] = b;
        }
    }
    sort(tmp+1,tmp+n+m+1);
    int len = unique(tmp+1,tmp+1+n+m)-tmp-1;
    for(int i=1;i<=n+m;i++)
    {
        flag[i].h = lower_bound(tmp+1,tmp+1+len,flag[i].h)-tmp;
    }
    build(0,len,1);
    for(int i=1;i<=n+m;i++)
    {
        int F = flag[i].F;
        int h = flag[i].h;
        int k = flag[i].x;
        if(F == 0)
        {
            if(!a[i+1]&&!a[i-1])update_section(1,1,h,1);
            else if(a[i+1]==h&&h==a[i-1]) update_section(1,1,h,-1);
            else if(a[i+1]<h&&a[i-1]<h)
            {
                if(!a[i+1]&&!a[i-1]) update_section(1,1,min(a[i+1],a[i-1]),-1);
                update_section(1,max(a[i+1],a[i-1])+1,h,1);
            }
            else if(a[i+1]>h&&a[i-1]>h) update_section(1,1,h,-1);
            else if((a[i+1]>=h&&a[i-1]<=h&&a[i-1])||(a[i+1]<=h&&a[i-1]>=h&&a[i+1])) update_section(1,1,min(a[i+1],a[i-1]),-1);
            a[i] = h;
        }
        if(F == 1)
        {
            query(1,h);
            cout << ans << "\n";
        }
        if(F == 2)
        {
            if(!a[k+1]&&!a[k-1]) update_section(1,1,a[k],-1);
            else if(a[k+1]==a[k]&&a[k]==a[k-1]) update_section(1,1,a[k],1);
            else if(a[k+1]<a[k]&&a[k-1]<a[k])
            {
                if(a[k+1]&&a[k-1]) update_section(1,1,min(a[k+1],a[k-1]),1);
                update_section(1,max(a[k+1],a[k-1])+1,a[k],-1);
            }
            else if(a[k+1]>a[k]&&a[k-1]>a[k]) update_section(1,1,a[k],1);
            else if((a[k+1]>=a[k]&&a[k-1]<=a[k]&&a[k-1])||(a[k+1]<=a[k]&&a[k-1]>=a[k]&&a[k+1])) update_section(1,1,min(a[k+1],a[k-1]),1);
            if(!a[k+1]&&!a[k-1])update_section(1,1,h,1);
            else if(a[k+1]==h&&h==a[k-1]) update_section(1,1,h,-1);
            else if(a[k+1]<h&&a[k-1]<h)
            {
                if(a[k+1]&&a[k-1]) update_section(1,1,min(a[k+1],a[k-1]),-1);
                update_section(1,max(a[k+1],a[k-1])+1,h,1);
            }
            else if(a[k+1]>h&&a[k-1]>h) update_section(1,1,h,-1);
            else if((a[k+1]>=h&&a[k-1]<=h&&a[k-1])||(a[k+1]<=h&&a[k-1]>=h&&a[k+1])) update_section(1,1,min(a[k+1],a[k-1]),-1);
            a[k] = h;
        }
    }
    return 0;
}

巨难：

传送门

虽然很难，但我还是一遍切掉了。。。（一遍切紫 nice!）

思维难度还是灰常大的。

首先讲讲我认为的难点：二分（这个东西我看了题解才恍然大悟）

对于此题，我们直接排序肯定是不现实的，所以考虑离线做法，我们二分这个答案，把数列中大于答案的赋为 1 ，小于或等于答案的赋为 0 。然后按操作排序，如果最后查询的位置上是 1 ，说明答案可以尝试性的变小一点，否则变大一点。

二分的大体思路就是这样，现在讲讲为什么要这样二分，因为数列中的数花花绿绿，可以认为，每个数都是不同的，那么，排序的复杂度会很高，线段树也失去了用武之地（如果思考一下的话会发现时间主要浪费在这里，所以要对这里进行优化），而如果可以减少数的种类，那么就可以用线段树提速了。此时，利用二分，将数列变成 01 串，那么数字就只有两种了，此时用线段树会有奇效。

最后，查看第 $q$ 个数是否为 1 就好了。整个过程就是 **二分 + 区间查询 + 区间修改 + 单点查询** ```cpp #define _L k<<1 #define _R k<<1|1 #define L(k) tree[k].L #define R(k) tree[k].R #define W(k) tree[k].one #define T(k) tree[k].tag int n,m,Rank,L=1,R,ans,mid; int a[MAXN]; struct shit{ int pos,L,R; }sht[MAXN]; struct node{ int L,R; int one,tag; }tree[4*MAXN]; void down(int k) { if(T(k) == 0) return; if(T(k) == 1) { W(_L) = R(_L)-L(_L)+1; T(_L) = 1; W(_R) = R(_R)-L(_R)+1; T(_R) = 1; } if(T(k) ==-1) W(_L) = W(_R) = 0,T(_L) = T(_R) = -1; T(k) = 0; } void build(int L, int R, int k) { L(k) = L; R(k) = R; if(L == R) { if(a[L] <= mid) W(k) = 0; else W(k) = 1; T(k) = 0; return; } int mid = (L+R)>>1; build(L,mid,_L); build(mid+1,R,_R); W(k) = W(_L)+W(_R); T(k) = 0; } void query(int k, int l, int r) { if(L(k)>=l && R(k)<=r) {ans += W(k); return;} down(k); int mid = (L(k)+R(k))>>1; if(l <= mid) query(_L,l,r); if(r > mid) query(_R,l,r); W(k) = W(_L)+W(_R); } void update(int k, int l, int r, int F) { if(L(k)>=l && R(k)<=r) { if(F) {W(k) = R(k)-L(k)+1; T(k) = 1;} else {W(k) = 0; T(k) = -1;} return; } down(k); int mid = (L(k)+R(k))>>1; if(l <= mid) update(_L,l,r,F); if(r > mid) update(_R,l,r,F); W(k) = W(_L)+W(_R); } void query_point(int k, int x) { if(L(k) == R(k)) {ans = W(k); return;} down(k); int mid = (L(k)+R(k))>>1; if(x <= mid) query_point(_L,x); else query_point(_R,x); } bool check() { build(1,n,1); for(int i=1;i<=m;i++) { int ps = sht[i].pos; int nL = sht[i].L; int nR = sht[i].R; ans = 0; query(1,nL,nR); if(ps == 1) update(1,nL,nL+ans-1,1),update(1,nL+ans,nR,0); else update(1,nR-ans+1,nR,1),update(1,nL,nR-ans,0); } query_point(1,Rank); return !ans; } int main(void) { cin >> n >> m; for(int i=1;i<=n;i++) { cin >> a[i]; R = max(R,a[i]); } for(int i=1;i<=m;i++) cin >> sht[i].pos >> sht[i].L >> sht[i].R; cin >> Rank; while(L <= R) { mid = (L+R)>>1; if(check()) R = mid-1; else L = mid+1; } cout << L; } ```