头像

线段树天下第一


访客:970

在线 



#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int w[N];
int f[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)    scanf("%d", w + i);

    int res = -1e9;
    for(int i = 1; i <= n; i++){
        f[i] = w[i];
        for(int j = 1; j < i; j++){
            if(w[j] < w[i]) f[i] = max(f[i], f[j] + w[i]);
        }
        res = max(res, f[i]);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

/*
北岸有且仅有一个友好城市
南岸, 北岸
这个题目不要求有且只有一个友好城市也可写, 方法一下,就是结构体排序, second 进行L I S
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 101010;
typedef pair<int, int> PII;
PII q[N];
int w[N];
int f[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &q[i].first, &q[i].second);
    }

    sort(q + 1, q + n + 1);
    for(int i = 1; i <= n; i++) w[i] = q[i].second;
    ///w[i] 的 最长上升子序列, f[i] changdu wei i
    int len = 0;    int l, r, mid;
    f[0] = -1e9;    
    for(int i = 1; i <= n; i++){
        ///zebanchazhao
        l = 0, r = len;
        while(l < r){
            mid = l + r + 1 >> 1;
            if(f[mid] < w[i])   l = mid;
            else    r = mid - 1;
        }
        len = max(len, l + 1);
        f[l + 1] = w[i];
    }

    cout<<len<<endl;

    return 0;
}



活动打卡代码 AcWing 482. 合唱队形

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int w[N];
int f[N], g[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) scanf("%d", w + i);

    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
        }
    }

    for(int i = n; i; i--){
        g[i] = 1;
        for(int j = n; j > i; j--){
            if(w[j] < w[i]) g[i] = max(g[i], g[j] + 1);
        }
    }

    int res = 1;
    for(int i = 1; i <= n; i++) res = max(res, f[i] + g[i] -1);

    cout<<n - res<<endl;

    return 0;
}


活动打卡代码 AcWing 1014. 登山

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N], g[N];
int w[N], n;

int main(){
    cin>>n;

    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);

    for(int i = 1; i <= n; i++){
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
        }
    }

    for(int i = n; i; i--){
        g[i] = 1;
        for(int j = n; j > i; j--){
            if(w[j] < w[i]) g[i] = max(g[i], g[j] + 1);
        }
    }

    int res = 1;
    for(int i = 1; i <= n; i++){
        res = max(res, f[i] + g[i] - 1);
    }

    cout<<res<<endl;
    return 0;
}



#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int w[N];
int f[N];

int main(){
    int T;  cin>>T;
    int n;
    int res = 0;
    while(T--){
        cin>>n;
        for(int i = 1; i <= n; i++)     scanf("%d", &w[i]);
        res = 0;
        for(int i = 1; i <= n; i++){
            f[i] = 1;
            for(int j = 1; j < i; j++){
                if(w[j] < w[i])     f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
        }
        for(int i = n; i; i--){
            f[i] = 1;
            for(int j = n; j > i; j--){
                if(w[j] < w[i]) f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
        }

        cout<<res<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1027. 方格取数

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int f[N+N][N][N];
int w[N][N];

int main()
{
    int n;  cin>>n;
    memset(f, 0, sizeof f);
    memset(w, 0, sizeof w);

    int a, b, c;
    while(cin>>a>>b>>c, a || b || c)    w[a][b] = c;

    int x;
    for(int k = 1; k <= n * 2; k++){
        for(int i1 = 1; i1 <= n; i1++){
            for(int i2 = 1; i2 <= n; i2++){
                int j1 = k - i1, j2 = k - i2;
                if(j1 <= 0 || j2 <= 0 || j1 > n || j2 > n)  continue;
                ///一旦没有这个特判, 妥妥的完蛋
                x = w[i1][j1] + w[i2][j2];
                if(i1 == i2)    x /= 2;
                int &y = f[k][i1][i2];
                y = max(y, f[k-1][i1][i2] + x);
                y = max(y, f[k-1][i1][i2-1] + x);
                y = max(y, f[k-1][i1-1][i2] + x);
                y = max(y, f[k-1][i1-1][i2-1] + x);
            }
        }
    }

    cout<<f[2*n][n][n]<<endl;

    return 0;
}



活动打卡代码 AcWing 1018. 最低通行费

#include <bits/stdc++.h>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int f[N][N];
int w[N][N];

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++)
            scanf("%d", &w[i][j]);

    memset(f, 0x3f, sizeof f);      
    f[0][1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            f[i][j] = min(f[i-1][j], f[i][j-1]) + w[i][j];
        }
    }
    cout<<f[n][n]<<endl;
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int f[N][N];
int w[N][N];
int r, c;

int main()
{
    int T;  cin>>T;
    while(T--){
        cin>>r>>c;
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                scanf("%d", &w[i][j]);
            }
        }
        memset(f, 0, sizeof f);
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
            }
        }
        cout<<f[r][c]<<endl;
    }
    return 0;
}



线段树果真是强,区间修改,区间查询
注意线段树刚刚开始的build的初始化
sum:区间的和,但是忽略祖宗节点的add懒标记
add:懒标记, 表示的是子节点的懒标记,自身的标记已经是加上了(这个是属于个人习惯hh)
除了build, 其他搜索的子区间都是直接l, r, 没必要吧mid 更新进去, 因为他不一定是到mid啊, right 可能比mid小
有些地方的sum千万别忘了 += (r - l)*d; modify ,pushdown;

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 101010;
struct Node{
    int l, r;
    LL sum, add;    ///qu jian he ,yi ji lan biao ji
}tr[4*N];
int n, m;
int w[N];

void pushup(int u){
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown(int u){
    Node &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];  ///yin yong
    if(root.add == 0)   return;
    left.add += root.add;   left.sum += (left.r - left.l + 1) * root.add;
    right.add += root.add;  right.sum += (right.r - right.l + 1) * root.add;
    root.add = 0;
}

void build(int u, int l, int r){
    if(l == r){
        tr[u] = {l, r, w[l], 0};            ///千万看准了,不是w[u],是w[r]或者w[l]
    }else{
        int mid = l + r >> 1;
        tr[u] = {l, r, 0, 0};
        build(u << 1, l, mid);  build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].add += d; tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
    }else{
        pushdown(u);            ///lazy
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)    modify(u << 1, l, r, d);
        if(r > mid)     modify(u << 1 | 1, l, r, d);
        pushup(u);              ///adjust
    }
}

LL query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u].sum;   ///没必要在进行pushdown 操作了
    pushdown(u);
    LL sum = 0;
    int mid  = tr[u].l + tr[u].r >> 1;

    if(l <= mid)
        sum += query(u << 1, l, r);
    if(r > mid) 
        sum += query(u << 1 | 1, l, r);
    /*
    if(l <= mid)
        sum += query(u << 1, l, mid);   因为他不一定是到mid啊, right 可能比mid小
    if(r > mid) 
        sum += query(u << 1 | 1, mid + 1, r);
    */
    return sum;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);

    build(1, 1, n);

    char op[5];
    int l, r, d;
    while(m--){
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'C'){
            scanf("%d", &d);
            modify(1, l, r, d);
        }else{
            printf("%lld\n", query(1, l, r));
        }
    }
    return 0;
}



活动打卡代码 AcWing 1275. 最大数

注意事项

1.build 注意递归终点

2.modify注意pushup

3.modify递归终点跳出,直接return,免得被pushup

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 202020;
struct Node{
    int l, r;
    int v;  ///max
}node[N*4];

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

void build(int u, int l, int r){
    node[u] = {l, r, int(-2e9)};
    if(l == r)  return;     ///the end!!!
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, int v){
    int mid = node[u].l + node[u].r >> 1;
    if(node[u].l == node[u].r){
        node[u].v = v;
        return;     ///加上一个return 免得被pushup
    }
    else if(x <= mid)   modify(u << 1, x, v);
    else    modify(u << 1 | 1, x, v);
    pushup(u);
}

int query(int u, int l, int r){
    if(node[u].l >= l && node[u].r <= r)    return node[u].v;
    int mid = node[u].l + node[u].r >> 1;
    int res = -2e9;
    if(l <= mid)    res = query(u << 1, l, r);
    if(r > mid)     res = max(res, query(u << 1 | 1, l, r));
    return res;
}

int main(){
    LL m, p, a, t, n;
    char op[5];
    cin>>m>>p;
    n = a = 0;

    build(1, 1, N - 20);
    for(int i = 0; i < m; i++){
        scanf("%s%d", op, &t);
        if(*op == 'Q'){
            a = query(1, n - t + 1, n);
            //printf("%lld %lld %lld\n", n - t + 1, n, a);
            printf("%lld\n", a);
        }else{///add
            //cout<<((a + t) % p + p) % p<<endl;
            modify(1, ++n, ((a + t) % p + p) % p);
        }
    }
    /*cout<<endl<<n<<endl;
    a = query(1, 1, 1);
    printf("%lld\n", a);
    a = query(1, 2, 2);
    printf("%lld\n", a);
    a = query(1, 3, 3);
    printf("%lld\n", a);
    a = query(1, 4, 4);
    printf("%lld\n", a);*/
    return 0;
}