头像

迟早青

广州大学




离线:34分钟前


最近来访(100)
用户头像
次饭
用户头像
大羊驼
用户头像
Mellina
用户头像
GlaDos
用户头像
michaelzzz
用户头像
丁真大佬
用户头像
艾特不出来我
用户头像
yxc的小迷妹
用户头像
Heart_0
用户头像
Matsuko_2
用户头像
摆烂波比
用户头像
用户头像
Klei真香
用户头像
Geo-star
用户头像
垫底抽风-小号
用户头像
摘樱桃
用户头像
0iq
用户头像
husheng
用户头像
鄭Y
用户头像
kblues


迟早青
3小时前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 500010;

int n , m ;
int w[N];
struct node
{
  int l , r;
  int sum , lmax , rmax , tmax;
}tr[N * 4];
void pushup(node &u, node &l, node &r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(int u)
{
    pushup(tr[u] , tr[u << 1] , tr[u << 1 | 1]);
}

void build(int u ,int l , int r)
{
    if(l == r) tr[u] = {l , r , w[r] , w[r] , w[r], w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u<<1 , l , mid) , build(u<<1 | 1 , mid + 1 , r);
        pushup(u);
    }
}

void modify(int u , int x , int d)
{
    if(tr[u].l == x && tr[u].r == x)
    tr[u] = {x , x , d , d , d,d};

    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1 , x , d);
        else modify(u << 1 | 1 , x , d);
        pushup(u);
    }
}

node query(int u , int l ,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1 , l , r);
        else if(l > mid) return  query(u << 1 | 1 , l , r);
        else 
        {
            auto left = query(u << 1 , l , r);
            auto right = query(u << 1 | 1 , l , r);
            node res;
            pushup(res , left , right);
            return res;
        }
    }

}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++ )
        cin >> w[i];

    build (1, 1, n);
    int k , x , y;
    while(m--)
    {
        cin >> k >> x >> y;
        if(k == 1)
        {
            if(x > y) swap(x,y);
            cout << query(1 , x , y).tmax << endl;
        }
        else 
            modify(1,x,y);
    }
    return 0;
}



首先,知道线段树的基本操作和基本作用:

基本操作:
1. build(构建)
2. pushup(用子节点求父节点)
3. pushdown(懒标记)
4. query(查询)
5. change(修改) — 单点修改和区域修改

基本作用
1. 在某个位置修改一个数
2. 求某一个区间的信息值

然后思考怎么构建线段树:

  1. 结构体的设定
    (1) 左右区间
    (2) 信息值:该值要确保能从子节点得到
  2. 递归建立线段树:
void build(int u , int l , int r)
{
    tr[u] = {l,r} // 记录区间
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1 , l , mid) , build(u << 1 | 1 , mid + 1 , r);
}
  1. 结构体数组一般要开四倍



树状数组:区间修改 + 区间查询

利用差分数组实现简单区间修改,单单用差分不能很好的算区间值

利用前缀和思路 , 区间查询可以实现到O(1)

用差分后我们可以发现,tr数组存的是差分数组的前缀和,即为a[i] ,

而要再加一层前缀和即要:tr[1] + tr[2] + tr[3] +…+tr[r] - (tr[1] + tr[2] + … + tr[l - 1]) , 用此求出区间值

通过数学变换可得,区间值可以用: b[i] = (i + 1) * (a[1] + a[2] + … + a[i]) - (1 * a[1] + 2 * a[2] + … + i * a[i])

11.png

故拿tr1 存储差分树状数组,tr2 存储i * b[i] 的树状数组

#include<iostream>
#include<algorithm>
#include<cstring>

typedef long long LL;
using namespace std;

const int N = 100010;

int n , m ;
int a[N];
LL tr1[N] , tr2[N];

int lowbit(int x)
{
    return x&-x;
}

void add(LL tr[] , int x , LL c)
{
    for(int i = x ; i <= n ; i += lowbit(i))  tr[i] += c;
}

LL sum(LL tr[] , int x)
{
    LL res = 0;
    for(int i = x ; i ; i -= lowbit(i) ) res += tr[i];
    return res;
}

LL p_sum(int x) // 1 ~ x
{
    return sum(tr1 , x) * (x+1) - sum(tr2 , x); 
}

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];

    for(int i = 1 ; i <= n ; i ++ )
    {
        int b = a[i] - a[i-1];
        add(tr1 , i , b);
        add(tr2 , i , (LL)b * i);
    }

    while(m--)
    {
        char x;
        cin >> x;
        int l , r;
        cin >> l >> r;
        if(x == 'Q')
            cout << p_sum(r) - p_sum(l - 1) << endl;
        else 
        {
            int d;
            cin >> d;
             // a[l] += d
            add(tr1, l, d), add(tr2, l, l * d);
            // a[r + 1] -= d
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }
    return 0;

}



树状数组:区间修改 + 单点查询(差分实现)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int n , m;
int a[N] , tr[N];

int lowbit(int x)
{
    return x & -x;
}

int add(int x , int c)
{
    for(int i = x ;i <= n;i += lowbit(i))   tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x ; i ; i -= lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];

    for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]); //差分

    while(m--)
    {
        char x;
        cin >> x;
        if(x == 'C')
        {
        //改值(l,r)l处加 , r+1处减
            int l , r , d;
            cin >> l >> r >> d;
            add(l , d);
            add(r + 1 , -d);//
        }
        else 
        {
            int d;
            cin >> d;
            cout << sum(d) << endl;
        }
    }
    return 0;

}


分享 树状数组



活动打卡代码 AcWing 241. 楼兰图腾

树状数组

该题需想清的几件事:

  1. 在使用add函数加入数字1时,是将对应高度的出现次数+1,在后面的数往前查找或者前面的数往后查找时,对应tr值会改变

  2. 此题中,是以一个高度y为顶点,greater存其前面比起高的点的数量,反之lower,第二次循环中直接拿来相乘

  3. sum(n) : 1 ~ n中的总数 , add为其加数,只有 add 后 sum 才能求到数

    故求greater 是y+1 ~ n : sum(n) - sum(y) , lower 是 1 ~ y-1 : sum(y - 1)

思考为什么能用树状数组解题?

整体思路中包含了:单点修改,区间求值 ———————— 故可以使用树状数组

数组数组的解析: https://www.cnblogs.com/xenny/p/9739600.html

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N] , tr[N];
int Greater[N] , lower[N];

int lowbit(int x)
{
    return x&-x;
}

int add(int x , int c)
{
    for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x ; i ; i -= lowbit(i))  res+=tr[i];
    return res;
}

int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];

    for(int i = 1 ; i <= n ; i ++ )
    {
        int y = a[i];

        Greater[i] = sum(n) - sum(y);//高度为y ,找
        lower[i] = sum(y - 1);

        add(y , 1);
    }

    memset(tr , 0 , sizeof tr);
    LL res1 = 0 , res2 = 0;

    for(int i = n ; i >= 1 ; i -- )
    {
        int y = a[i];
        res1 += Greater[i] *(LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)(sum(y - 1));
        add(y , 1);
    }
    cout << res1 << " " << res2 << endl;
    return 0;
}


新鲜事 原文

提高课还有180


活动打卡代码 AcWing 237. 程序自动分析

并查集 + 离散化

思路:

  1. 实际用到的数据量远小于给的数据量用离散化 : 其中离散化分有序和无序,此处用哈希表实现无序

  2. 先进行相等再进行不相等: 因为矛盾出现必然是在判断两者在一个集合中却出现不相等的条件,故先合并在判断是最合适的

  3. 初始化 f 数组要从1开始,因为哈希表离散化也是从1开始

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

const int N = 200010;
int f[N];
int t , n , m;

unordered_map<int , int> s;

struct Query
{
    int a , b , c;
}query[N];

int get(int x)
{
    if(s.count(x) == 0) s[x] = ++n;
    return s[x];
}

int find(int x)
{
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}


int main()
{
    cin >> t;
    while(t--)
    {
        n = 0;
        cin >> m;
        s.clear();
        for(int i = 0 ; i < m ; i ++ )
        {
            int d , e , f;
            cin >> d >> e >> f;
            query[i] = {get(d) , get(e) , f};
        }

        for(int i = 1 ; i <= n ; i ++ ) f[i] = i;

        // 相等
        for(int i = 0 ; i < m ; i ++ )
            if(query[i].c == 1)
            {
                int pa = find(query[i].a) , pb = find(query[i].b);
                f[pa] = pb;
            }

        // 不相等
        bool mark = true;
        for(int i = 0 ; i < m && mark; i ++ )
        {
            if(query[i].c == 0)
            {
                int pa = find(query[i].a) , pb = find(query[i].b);
                if(pa == pb)
                {
                    mark = false;
                    break;
                }
            }
        }

        if(mark) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;

}



动态规划(记忆化搜索) + 剪枝

题解: https://leetcode.cn/problems/soup-servings/solution/by-lcbin-44pu/

class Solution {
public:
    double f[200][200] = {0.0};
    double dfs(int i , int j)
    {
        if(i <= 0 && j <= 0) return 0.5;
        if(i <= 0) return 1;
        if(j <= 0) return 0;
        if(f[i][j] > 0)return f[i][j];//计算过(被记忆过)
        double ans = 0.25 * (dfs(i - 4 , j) + dfs(i - 3 , j - 1) + dfs(i - 2 , j - 2) + dfs(i - 1 , j - 3));
        f[i][j] = ans;
        return ans;
    }
    double soupServings(int n) {
        if(n > 4800) return 1;
        else return dfs((n + 24)/25 , (n + 24)/25);
    }
};



活动打卡代码 AcWing 1252. 搭配购买

并查集 + 01背包

  1. 由于云朵是1~n故不能使用0~n-1

  2. v[pa] += v[pb]; w[pa] += w[pb]; f[pb] = pa;其中pa和pb可以调换但是要注意定一个始终为父亲
    出现v[pa] += v[pb]; w[pa] += w[pb]; f[pa] = pb;等情况都会使结果出错

  3. 01背包中需要判断是否为祖宗才开始计算(判断条件:f[x] = x)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10010;

int n , m , k;

int f[N] , v[N] , w[N] , g[N];

int find(int x)
{
    if(f[x] != x) f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++ )  f[i] = i;
    for(int i = 1 ; i <= n ; i ++ )  cin >> v[i] >> w[i];

    while(m--)
    {
        int a , b;
        cin >> a >> b;
        int pa = find(a) , pb = find(b);
        if(pa!=pb)
        {
            v[pa] += v[pb];
            w[pa] += w[pb];
            f[pb] = pa;
        }
    }
    //01背包
    for(int i = 1 ; i <= n ; i ++ )
        if(f[i] == i)
            for(int j = k ; j >= v[i] ; j -- )
                g[j] = max(g[j] , g[j - v[i]] + w[i]);

    cout << g[k] << endl;
    return 0;
}