头像

zmy




离线:8小时前



zmy
17天前

简单的理解,并整理了一下,来此分享一波
屏幕截图 2020-11-18 004928.png




zmy
20天前

总结一下有关二叉树的部分操作以备不时之需,嘿嘿
老师布置的一道实验题,题目内容直接搬过来用用
屏幕截图 2020-11-12 215622.png

想要完成上述操作,基本上可根据以下步骤来写

1、造轮子:写出栈结构(用于非递归遍历),队列(用于层次遍历),二叉树的节点结构

1.1 栈结构
首先要知道的是,栈的特点是后进先出,LIFO(Last In First Out)
栈的基本操作:(方便起见,在此借用STL的stack来展示这些操作,$stack<$Typename$> st$)
(1)返回栈顶元素 $st.top()$;
(2)入栈 $st.push(x)$;
(3)出栈 $st.pop()$;
(4)判断栈是否为空栈$st.empty()$;(栈空返回真,否则返回假)

/*栈结构*/
struct Stack {
    bitree* base;
    int top;//栈顶
    int bot;//栈底
    int max_size;
};

1.2 队列结构
队列的特点是先进先出,FIFO(First In First Out)
队列的基本操作:($queue<$Typename$> q$)
(1)返回队头元素 $q.front()$;
(2)入队$q.push(x)$;
(3)出队$q.pop()$;
(4)判断队列是否为空$q.empty()$;

/*队列结构*/
struct Queue {
    bitree* base;
    int front;
    int tail;
    int max_size;
};

1.3 二叉树的结点结构
(1)数据域
(2)左孩子指针
(3)右孩子指针

/*二叉树结点结构*/
typedef struct Node {
    char Data;
    struct Node* Left_child;
    struct Node* Right_child;
}*bitree, binode;

2、建树(按照二叉树的先序遍历创建二叉树)

根据先序遍历的规则(根左右),依次创建即可,递归创建比较简单,就写递归版的吧

/*递归创建*/
void CreatBiTree(bitree& bt)//按先序遍历创建二叉链表
{
    //根据输入的字符串建立二叉树bt的二叉链表,‘#’表示虚节点
    char ch;
    ch = getchar();
    if (ch == '\n') return;
    if (ch == '#') bt = NULL;
    else {
        bt = new binode;
        bt->Data = ch;
        CreatBiTree(bt->Left_child);
        CreatBiTree(bt->Right_child);
    }
}

3、先序(根、左、右),中序(左、根、右),后序(左、右、根)遍历

3.1 先序遍历
(1)访问根结点;
(2)先序遍历左子树;
(3)先序遍历右子树。

/*递归先序遍历*/
void Pre_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        printf("%c", bt->Data);
        Pre_Order_Verse(bt->Left_child);
        Pre_Order_Verse(bt->Right_child);
    }
}

3.2 中序遍历
(1)中序遍历左子树;
(2)访问根结点;
(3)中序遍历右子树。

/*递归中序遍历*/
void Mid_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        Mid_Order_Verse(bt->Left_child);
        printf("%c", bt->Data);
        Mid_Order_Verse(bt->Right_child);
    }
}

3.3 后序遍历
(1)后序遍历左子树;
(2)后序遍历右子树;
(3)访问根结点。

/*递归后续遍历*/
void Last_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        Last_Order_Verse(bt->Left_child);
        Last_Order_Verse(bt->Right_child);
        printf("%c", bt->Data);
    }
}

5、非递归版遍历

注意:在这里维护的栈是允许空结点入栈的
5.1 非递归先序遍历
屏幕截图 2020-11-15 101623.png
屏幕截图 2020-11-15 100224.png

/*非递归先序遍历*/
void Pre_Inorder_Verse(bitree bt)
{
    Stack st;
    bitree p;
    if (bt)
    {
        Init_Stack(st);
        Push_Stack(st, bt);
        while (!Empty_Stack(st))
        {
            while (Get_Stack_top(st, p) && p != NULL)
            {
                Push_Stack(st, p->Left_child);
            }
            Pop_Stack(st, p);
            if (!Empty_Stack(st))
            {
                Pop_Stack(st, p);
                Push_Stack(st, p->Right_child);
            }
        }
    }
}

5.2 非递归中序遍历
遍历方法和先序遍历类似,不过是按照左根右来遍历即可,代码实现也只是将访问结点的那句代码移动一下位置即可,在这里就不再细述了。

/*非递归中序遍历*/
/*非递归后序遍历*/
void Last_Inorder_Verse(bitree bt)
{
    Stack st;
    bitree p1, p2;
    if (bt)
    {
        Init_Stack(st);
        Push_Stack(st, bt);
        while (!Empty_Stack(st))
        {
            while (Get_Stack_top(st, p1) && p1 != NULL)
            {
                Push_Stack(st, p1->Left_child);
            }
            Pop_Stack(st, p1);//pop掉最左端的空结点
            if (!Empty_Stack(st))
            {
                Get_Stack_top(st, p1);
                Push_Stack(st, p1->Right_child);//将结点的右放入栈中
                if (Get_Stack_top(st, p1) && p1 == NULL)//若结点的右是空,pop掉右,打印结点,若非空,后续遍历右子树
                {
                    Pop_Stack(st, p1);
                    Pop_Stack(st, p1);
                    printf("%c", p1->Data);
                    /*上一次出栈结点是当前栈顶结点的右孩子的处理*/
                    while (!Empty_Stack(st) && Get_Stack_top(st, p2) && p2->Right_child == p1)
                    {
                        Pop_Stack(st, p1);
                        printf("%c", p1->Data);
                    }

                    if (!Empty_Stack(st))
                    {
                        Get_Stack_top(st, p1);
                        Push_Stack(st, p1->Right_child);
                    }
                }
            }
        }
    }
}

6、层次遍历(BFS的方法依次遍历即可)

这个最好写了,直接就是BFS的常规操作啊。直接不多言

/*层次遍历*/
void Level_Traversal(bitree bt)
{
    Queue q;
    Init_Queue(q);
    Push_Queue(q, bt);
    bitree p;
    while (!Empty_Queue(q))
    {
        Pop_Queue(q, p);
        if (p != NULL)
        {
            printf("%c", p->Data);
        }
        if (p->Left_child != NULL) Push_Queue(q, p->Left_child);
        if (p->Right_child != NULL) Push_Queue(q, p->Right_child);
    }
}

7、计算叶子结点的个数(左右都为空的结点)

当左右孩子都是空,该结点就是叶子,记录数量

/*遍历计算叶子结点个数*/
void LeavesCount(bitree bt,int &count)
{
    if (bt != NULL)
    {
        LeavesCount(bt->Left_child, count);
        if (bt->Left_child == NULL && bt->Right_child == NULL) count++;
        LeavesCount(bt->Right_child, count);
    }
}

放上实现作业中要求的所有代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define STACK_SIZE 50
#define QUEUE_SIZE 50
using namespace std;

/*二叉树结点结构*/
typedef struct Node {
    char Data;
    struct Node* Left_child;
    struct Node* Right_child;
}*bitree, binode;

/*栈结构*/
struct Stack {
    bitree* base;
    int top;//栈顶
    int bot;//栈底
    int max_size;
};

/*队列结构*/
struct Queue {
    bitree* base;
    int front;
    int tail;
    int max_size;
};

/*初始化队列*/
void Init_Queue(Queue& q)
{
    q.base = new bitree[QUEUE_SIZE];
    q.front = q.tail = 0;
    q.max_size = QUEUE_SIZE;
}

/*初始化栈*/
void Init_Stack(Stack& st)
{
    st.base = new bitree[STACK_SIZE];
    st.top = 0;
    st.bot = 0;
    st.max_size = STACK_SIZE;
}

/*判栈空*/
bool Empty_Stack(Stack st)
{
    if (st.top == 0) return true;
    else return false;
}

/*判队列空*/
bool Empty_Queue(Queue q)
{
    if (q.front == q.tail) return true;
    else return false;
}

/*入队操作*/
void Push_Queue(Queue& q, bitree e)
{
    if (q.tail > q.max_size)
    {
        bitree* tmp = new bitree[q.max_size + QUEUE_SIZE];
        for (int i = q.front;i < q.tail;i++)//原数据拷贝到新地址
        {
            tmp[i - q.front] = q.base[i];
        }
        int len = q.tail - q.front;
        q.base = tmp;//指针指向新地址
        q.front = 0;q.tail = len;//更改现有队头队尾指针
    }
    q.base[q.tail++] = e;
}

/*入栈操作*/
void Push_Stack(Stack& st,bitree e)
{
    if (st.top - st.bot >= st.max_size)
    {
        bitree* tmp = new bitree[st.max_size + STACK_SIZE];
        for (int i = 0;i < st.max_size;i++) tmp[i] = st.base[i];//原数据拷贝
        st.base = tmp;//指向更大的内存块
    }
    st.base[st.top++] = e;
}

/*出队操作*/
void Pop_Queue(Queue& q, bitree& e)
{
    if (q.tail == q.front)
    {
        cout << "Error Error Error!!!" << endl;
        exit(0);
    }
    else {
        e = q.base[q.front++];
    }
}

/*出栈操作*/
void Pop_Stack(Stack& st, bitree& e)
{
    if (st.top > 0) e = st.base[--st.top];
    else
    {
        cout << "Error Error !!!" << endl;
        exit(0);
    }
}

/*返回队头元素*/
bool Get_Queue_top(Queue q,bitree& e)
{
    if (Empty_Queue(q)) return false;
    else {
        e = q.base[q.front];
        return true;
    }
}

/*返回栈顶元素*/
bool Get_Stack_top(Stack st,bitree& e)
{
    if (Empty_Stack(st)) return false;
    else {
        e = st.base[st.top - 1];
        return true;
    }
}


/*递归创建*/
void CreatBiTree(bitree& bt)//按先序遍历创建二叉链表
{
    //根据输入的字符串建立二叉树bt的二叉链表,‘#’表示虚节点
    char ch;
    ch = getchar();
    if (ch == '\n') return;
    if (ch == '#') bt = NULL;
    else {
        bt = new binode;
        bt->Data = ch;
        CreatBiTree(bt->Left_child);
        CreatBiTree(bt->Right_child);
    }
}

/*递归先序遍历*/
void Pre_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        printf("%c", bt->Data);
        Pre_Order_Verse(bt->Left_child);
        Pre_Order_Verse(bt->Right_child);
    }
}

/*递归中序遍历*/
void Mid_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        Mid_Order_Verse(bt->Left_child);
        printf("%c", bt->Data);
        Mid_Order_Verse(bt->Right_child);
    }
}

/*递归后续遍历*/
void Last_Order_Verse(bitree bt)
{
    if (bt != NULL)
    {
        Last_Order_Verse(bt->Left_child);
        Last_Order_Verse(bt->Right_child);
        printf("%c", bt->Data);
    }
}

/*非递归先序遍历*/
void Pre_Inorder_Verse(bitree bt)
{
    Stack st;
    bitree p;
    if (bt)
    {
        Init_Stack(st);
        Push_Stack(st, bt);
        while (!Empty_Stack(st))
        {
            while (Get_Stack_top(st, p) && p != NULL)
            {
                printf("%c", p->Data);
                Push_Stack(st, p->Left_child);
            }
            Pop_Stack(st, p);
            if (!Empty_Stack(st))
            {
                Pop_Stack(st, p);
                Push_Stack(st, p->Right_child);
            }
        }
    }
}

/*非递归中序遍历*/
void Mid_Inorder_Verse(bitree bt)
{
    Stack st;
    bitree p;
    if (bt)
    {
        Init_Stack(st);
        Push_Stack(st, bt);
        while (!Empty_Stack(st))
        {
            while (Get_Stack_top(st, p) && p != NULL)
            {
                Push_Stack(st, p->Left_child);
            }
            Pop_Stack(st, p);
            if (!Empty_Stack(st))
            {
                Pop_Stack(st, p);
                printf("%c", p->Data);
                Push_Stack(st, p->Right_child);
            }
        }
    }
}

/*非递归后序遍历*/
void Last_Inorder_Verse(bitree bt)
{
    Stack st;
    bitree p1, p2;
    if (bt)
    {
        Init_Stack(st);
        Push_Stack(st, bt);
        while (!Empty_Stack(st))
        {
            while (Get_Stack_top(st, p1) && p1 != NULL)
            {
                Push_Stack(st, p1->Left_child);
            }
            Pop_Stack(st, p1);//pop掉最左端的空结点
            if (!Empty_Stack(st))
            {
                Get_Stack_top(st, p1);
                Push_Stack(st, p1->Right_child);//将结点的右放入栈中
                if (Get_Stack_top(st, p1) && p1 == NULL)//若结点的右是空,pop掉右,打印结点,若非空,后续遍历右子树
                {
                    Pop_Stack(st, p1);
                    Pop_Stack(st, p1);
                    printf("%c", p1->Data);
                    /*上一次出栈结点是当前栈顶结点的右孩子的处理*/
                    while (!Empty_Stack(st) && Get_Stack_top(st, p2) && p2->Right_child == p1)
                    {
                        Pop_Stack(st, p1);
                        printf("%c", p1->Data);
                    }

                    if (!Empty_Stack(st))
                    {
                        Get_Stack_top(st, p1);
                        Push_Stack(st, p1->Right_child);
                    }
                }
            }
        }
    }
}


/*遍历计算叶子结点个数*/
void LeavesCount(bitree bt,int &count)
{
    if (bt != NULL)
    {
        LeavesCount(bt->Left_child, count);
        if (bt->Left_child == NULL && bt->Right_child == NULL) count++;
        LeavesCount(bt->Right_child, count);
    }
}

/*层次遍历*/
void Level_Traversal(bitree bt)
{
    Queue q;
    Init_Queue(q);
    Push_Queue(q, bt);
    bitree p;
    while (!Empty_Queue(q))
    {
        Pop_Queue(q, p);
        if (p != NULL)
        {
            printf("%c", p->Data);
        }
        if (p->Left_child != NULL) Push_Queue(q, p->Left_child);
        if (p->Right_child != NULL) Push_Queue(q, p->Right_child);
    }
}

/*主函数*/
int main()
{
    bitree root;
    cout << "请输入一个字符串,用#为虚结点" << endl;
    //根据输入的字符串建立二叉树的二叉链表,#表示虚结点
    CreatBiTree(root);
    int ans = 0;
    LeavesCount(root, ans);
    cout << "该二叉树的叶子节点个数为:" << ans << endl;
    /*先序遍历*/
    cout << "先序递归遍历序列为:";
    Pre_Order_Verse(root);puts("");
    cout << "先序非递归遍历序列为:";
    Pre_Inorder_Verse(root);puts("");
    /*中序遍历*/
    cout << "中递归遍历序列为:";
    Mid_Order_Verse(root);puts("");
    cout << "中序非递归遍历序列为:";
    Mid_Inorder_Verse(root);puts("");
    /*后序遍历*/
    cout << "后序递归遍历序列为:";
    Last_Order_Verse(root);puts("");
    cout << "后序非递归遍历序列为:";
    Last_Inorder_Verse(root);puts("");
    /*层次遍历*/
    cout << "层次遍历序列为:";
    Level_Traversal(root);puts("");
    return 0;
}



zmy
24天前

区间最大公约数(线段树维护差分序列来求最大公约数)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;
struct Tree{
    int l,r;
    ll sum,d;
}tree[4 * N];
ll arr[N];
ll gcd(ll a,ll b)
{
    if(b == 0) return a;
    else return gcd(b,a % b);
}
void pushup(Tree &u,Tree &l,Tree &r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d,r.d);
}
void pushup(int u)
{
    pushup(tree[u],tree[u << 1],tree[u << 1 | 1]);
}
void build(int u,int l,int r)
{
    if(l == r)
    {
        ll c = arr[l] - arr[l - 1];
        tree[u] = {l,r,c,c};
    }
    else{
        tree[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void update(int u,int idx,ll val)
{
    if(tree[u].l == idx && tree[u].r == idx)
    {
        ll c = tree[u].sum + val;
        tree[u] = {idx,idx,c,c};
    }
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(idx <= mid) update(u << 1,idx,val);
        else update(u << 1 | 1,idx,val);
        pushup(u);
    }
}
Tree query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r) return  tree[u];
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(r <= mid) return query(u << 1,l,r);
        else if(l > mid) return query(u << 1 | 1,l,r);
        else{
            Tree ans,left,right;
            left = query(u << 1,l,r);
            right = query(u << 1 | 1,l,r);
            pushup(ans,left,right);
            return ans;
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&arr[i]);
    }
    build(1,1,n);
    char op[2];
    int l,r;
    ll val;
    while(m--)
    {
        scanf("%s",op);
        if(*op=='Q')
        {
            scanf("%d%d",&l,&r);
            Tree left,ans;
            left = query(1,1,l);
            if(l + 1 <= r) ans = query(1,l + 1,r);
            printf("%lld\n",abs(gcd(left.sum,ans.d)));
        }
        else{
            scanf("%d%d%lld",&l,&r,&val);
            update(1,l,val);
            if(r + 1 <= n) update(1,r + 1,-val);
        }
    }
    return 0;
}

2020-11-11 重写线段树




zmy
24天前

你能回答这些问题吗(线段树求最大连续子段和)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500010;
typedef long long ll;
struct Tree{
    int l,r;
    ll sum,tmax,lmax,rmax;//区间和,区间最大和,区间最大前缀和,区间最大后缀和
}tree[4 * N];
ll arr[N];
void pushup(Tree &t,Tree &l,Tree &r)
{
    t.sum = l.sum + r.sum;
    t.lmax = max(l.lmax,l.sum + r.lmax);
    t.rmax = max(r.rmax,r.sum + l.rmax);
    t.tmax = max(l.rmax + r.lmax,max(l.tmax,r.tmax));
}
void pushup(int u)
{
    pushup(tree[u],tree[u << 1],tree[u << 1 | 1]);
}
void build(int u,int l,int r)
{
    if(l == r)
    {
        tree[u]={l,r,arr[l],arr[l],arr[l],arr[l]};
    }
    else{
        tree[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void update(int u,int idx,ll val)
{
    if(tree[u].l == idx && tree[u].r == idx)
    {
        tree[u] = {idx,idx,val,val,val,val};
    }
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(idx <= mid) update(u << 1,idx,val);
        else update(u << 1 | 1,idx,val);
        pushup(u);
    }
}
Tree query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r)
    {
        return tree[u];
    }
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(r <= mid) return query(u << 1,l,r);
        else if(l > mid) return query(u << 1 | 1,l,r);
        else{
            Tree ans,left,right;
            left = query(u << 1,l,r);
            right = query(u << 1 | 1,l,r);
            pushup(ans,left,right);
            return ans;
        }
    }

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%lld",&arr[i]);
    build(1,1,n);
    int type,l,r,idx;
    ll val;
    while(m--)
    {
        scanf("%d",&type);
        if(type==1)
        {
            scanf("%d%d",&l,&r);
            if(l > r) swap(l,r);
            Tree ans = query(1,l,r);
            printf("%lld\n",ans.tmax);
        }
        else{
            scanf("%d%lld",&idx,&val);
            update(1,idx,val);
        }
    }
    return 0;
}

2020-11-10 重写线段树



活动打卡代码 AcWing 1277. 维护序列

zmy
28天前

维护序列(维护区间乘和区间加)

#include<cstdio>
#include<deque>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;
struct Tree{
    int l,r;
    int sum;
    int mul,add;
}tree[4 * N];
int arr[N],n,q,mod;
void pushup(int u)
{
    tree[u].sum = (tree[u << 1].sum + tree[u << 1 | 1].sum) % mod;
}
void eval(Tree &t,int mul,int add)
{
    t.sum = ((ll)t.sum * mul + ((ll)(t.r - t.l + 1) * add)) % mod;
    t.mul = (ll)t.mul * mul % mod;
    t.add = ((ll)t.add * mul + add) % mod;
}
void pushdown(int u)
{
    eval(tree[u << 1],tree[u].mul,tree[u].add);
    eval(tree[u << 1 | 1],tree[u].mul,tree[u].add);
    tree[u].mul = 1;
    tree[u].add = 0;
}
void build(int u,int l,int r)
{
    if(l == r)
    {
        tree[u] = {l,l,arr[l],1,0};
    }
    else{
        tree[u] = {l,r,0,1,0};
        int mid = l + r >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
} 
void update(int u,int l,int r,int mul,int add)
{
    if(l <= tree[u].l && tree[u].r <= r)
    {
        eval(tree[u],mul,add);
    }
    else{
        pushdown(u);
        int mid = tree[u].l + tree[u].r >> 1;
        if(l <= mid) update(u << 1,l,r,mul,add);
        if(r > mid) update(u << 1 | 1,l,r,mul,add);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r)
    {
        return tree[u].sum;
    }
    else{
        pushdown(u);
        int sum = 0;
        int mid = tree[u].l + tree[u].r >> 1;
        if(l <= mid) sum = query(u << 1,l,r) % mod;
        if(r > mid) sum = (sum + query(u << 1 | 1,l,r)) % mod;
        return sum % mod;
    }
}

int main()
{
    scanf("%d%d",&n,&mod);
    for(int i = 1;i <= n;i++) scanf("%d",&arr[i]);
    build(1,1,n);
    scanf("%d",&q);
    while(q--)
    {
        int op,l,r,z;
        scanf("%d%d%d",&op,&l,&r);
        if(op == 1)
        {
            scanf("%d",&z);
            update(1,l,r,z,0);
        }
        else if(op == 2)
        {
            scanf("%d",&z);
            update(1,l,r,1,z);
        }
        else{
            printf("%d\n",query(1,l,r)%mod);
        }
    }
    return 0;
}

因变量多次定义而出现的浮点错误的这个bug真让我好找啊,。。。




zmy
1个月前

一个简单的整数问题2

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
struct Tree{
    int l,r;
    ll sum;
    ll lazy;
}tree[4 * N];
ll arr[N];
void pushup(int u)
{
    tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
}
void pushdown(int u)
{
    if(tree[u].lazy != 0)
    {
        tree[u << 1].lazy += tree[u].lazy;
        tree[u << 1 | 1].lazy += tree[u].lazy;
        tree[u << 1].sum += tree[u].lazy * (tree[u << 1].r - tree[u << 1].l + 1);
        tree[u << 1 | 1].sum += tree[u].lazy * (tree[u << 1 | 1].r - tree[u << 1 | 1].l + 1);
        tree[u].lazy = 0;
    }
}
void build(int u,int l,int r)
{
    if(l == r){
        tree[u] = {l,l,arr[l],0};
    }
    else{
        tree[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void update(int u,int l,int r,ll v)
{
    if(l <= tree[u].l && tree[u].r <= r)
    {
        tree[u].sum += (tree[u].r - tree[u].l + 1) * v;
        tree[u].lazy += v;
    }
    else{
        pushdown(u);
        int mid = tree[u].l + tree[u].r >> 1;
        if(l <= mid) update(u << 1,l,r,v);
        if(r > mid) update(u << 1 | 1,l,r,v);
        pushup(u);
    }
}
ll query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r)
    {
        return tree[u].sum;
    }
    else{
        pushdown(u);
        int mid = tree[u].l + tree[u].r >> 1;
        ll ans = 0;
        if(l <= mid){
            ans += query(u << 1,l,r);
        } 
        if(r > mid)
        {
           ans += query(u << 1 | 1,l,r);
        }
        return ans;
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&arr[i]);
    }
    build(1,1,n);
    char op[2];
    int l,r;
    while(m--)
    {
        scanf("%s%d%d",op,&l,&r);
        if(*op=='Q')
        {
            printf("%lld\n",query(1,l,r));
        }
        else{
            ll x;
            scanf("%lld",&x);
            update(1,l,r,x);
        }
    }
    return 0;
}



zmy
1个月前

线段树求区间最大公约数

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500010;
typedef long long ll;
struct Tree{
  int l,r;
  ll sum,d;//差分的区间和,区间的最大公约数
}tree[4 * N];
ll arr[N];
ll gcd(ll x,ll y)
{
    return y ? gcd(y,x % y) : x;
}
void pushup(Tree& u,Tree& l,Tree& r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d,r.d);
}
void pushup(int u)
{
    pushup(tree[u],tree[u << 1],tree[u << 1 | 1]);
}
void build(int u,int l,int r)
{
    if(l == r) tree[u] = {l,r,arr[l] - arr[l - 1],arr[l] - arr[l - 1]};
    else{
        tree[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void update(int u,int idx,ll v)
{
    if(tree[u].l == idx && tree[u].r == idx)
    {
        ll c = tree[u].sum + v;
        tree[u] = {idx,idx,c,c};
    }
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(idx <= mid) update(u << 1,idx,v);
        else update(u << 1 | 1,idx,v);
        pushup(u);
    }
}
Tree query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r) return tree[u];
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(r <= mid) return query(u << 1,l,r);
        else if(l > mid) return query(u << 1 | 1,l,r);
        else{
            Tree Left = query(u << 1,l,r);
            Tree Right = query(u << 1 | 1,l,r);
            Tree ans;
            pushup(ans,Left,Right);
            return ans;
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%lld",&arr[i]);
    build(1,1,n);
    char op[2];
    int l,r;
    ll x;
    while(m--)
    {
        scanf("%s%d%d",op,&l,&r);
        if(*op=='Q')
        {
            Tree Left = query(1,1,l),Right = {0,0,0,0};
            if(l + 1 <= r) Right = query(1,l + 1,r);
            printf("%lld\n",abs(gcd(Left.sum,Right.d)));
        }
        else{
            scanf("%lld",&x);
            update(1,l,x);
            if(r + 1 <= n) update(1,r + 1,-x);
        }
    }
    return 0;
}



zmy
1个月前

线段树解决区间连续最大和问题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500010;
int arr[N];
struct Tree{
  int l,r;
  int sum,tmax,lmax,rmax;//区间和,区间最大连续子段和,区间最大前缀和,区间最大后缀和
}tree[4 * N];
void pushup(Tree& u,Tree& lson,Tree& rson)
{
    u.sum = lson.sum + rson.sum;
    u.lmax = max(lson.lmax,lson.sum + rson.lmax);
    u.rmax = max(rson.rmax,rson.sum + lson.rmax);
    u.tmax = max(max(lson.tmax,rson.tmax),lson.rmax + rson.lmax);
}
void pushup(int u)
{
    pushup(tree[u],tree[u << 1],tree[u << 1 | 1]);
}
void build(int u,int l,int r)
{
    tree[u] = {l,r};
    if(l == r)
    {
        tree[u].sum = tree[u].lmax = tree[u].rmax = tree[u].tmax = arr[l];
    }
    else{
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void update(int u,int idx,int val)
{
    if(tree[u].l == idx && tree[u].r == idx) tree[u] = {idx,idx,val,val,val,val};
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(idx <= mid) update(u << 1,idx,val);
        else update(u << 1 | 1,idx,val);
        pushup(u);
    }
}
Tree query(int u,int l,int r)
{
    if(l <= tree[u].l && tree[u].r <= r) return tree[u];
    else{
        int mid = tree[u].l + tree[u].r >> 1;
        if(r <= mid) return query(u << 1,l,r);
        else if(l > mid) return query(u << 1 | 1,l,r);
        else{
            Tree Left = query(u << 1,l,r);
            Tree Right = query(u << 1 | 1,l,r);
            Tree res;
            pushup(res,Left,Right);
            return res;
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
    }
    build(1,1,n);
    int k,x,y;
    while(m--)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(k==1)
        {
            if(x>y) swap(x,y);
            Tree ans=query(1,x,y);
            printf("%d\n",ans.tmax);
        }
        else{
            update(1,x,y);
        }
    }
    return 0;
}



活动打卡代码 LeetCode 14. 最长公共前缀

zmy
1个月前

最长公共前缀(二分做法)

class Solution {
public:
bool check(vector<string>& strs,int mid)
{
    for(int i=0;i<strs.size();i++)
    {
        if(strs[i].substr(0,mid)!=strs[0].substr(0,mid)) return false;
    }
    return true;
}
    string longestCommonPrefix(vector<string>& strs) {
        if(!strs.size()) return "";
        for(int i=0;i<strs.size();i++)
        {
            if(strs[i].size()==0) return "";
        }
        int l=0,r=100000;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(check(strs,mid)) l=mid;
            else r=mid-1;
        }
        return strs[0].substr(0,l);
    }
};



zmy
1个月前

盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& h) {
        int ans = 0;
        int n = h.size();
        int l = 0,r = n - 1;
        while(l < r)
        {
            ans = max(ans,min(h[l],h[r]) * (r - l));
            if(h[l] < h[r]) l++;
            else r--;
        }
        return ans;
    }
};