牛客算法周周练15

1. 数列下标

解题思路

这道题是一道单调栈的经典问题，一般涉及到单调栈的问题都是在问(数列左/右边比当前数字大/小的最近的一个数字的下标)， 使用单调栈解决这类问题的时间复杂度为, 用这道题中的样例来举例:

3 2 6 1 1 2

由于题目中要求的是某个数字右边最近的一个比它大的，故这里需要从右向左遍历，如果当前的值大于等于栈顶元素，则栈顶元素对于前面的值就已经没有任何意义了，进行弹栈操作，否则栈顶就是要找的值，然后将当前元素入栈，这样每一个元素只会入队一次，出队一次，故时间复杂度是线性的。

参考代码：

import java.io.*;

public class Main{
    static int N = 10010;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static int[] sk = new int[N];
    static int tt = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        String[] arr = in.readLine().split(" ");
        for(int i=1; i<=n; i++) a[i] = Integer.parseInt(arr[i-1]);

        for(int i=n; i>=1; i--){
            while(tt > 0 && a[i] >= a[sk[tt]]) tt --;
            b[i] = sk[tt];
            sk[++ tt] = i;
        }

        for(int i=1; i<=n; i++) System.out.print(b[i] + " ");
    }
}

2.可持久化动态图上树状数组维护01背包

解题思路
这道题刚开始真的被题目吓到了，且这道题会卡输入输出，使用java会TLE，思路就是贪心的来想，对于所有的负数，我们从后往前删，就可以保证每一个负数都乘以它最初的i，而剩下的所有非负数，当然是从头一个一个的删，这样就保证它们乘的下标都为1

参考代码

#include <iostream>
#include <cstdio> 

typedef long long LL;

using namespace std;

int n;

int main()
{
    scanf("%d", &n);

    LL ans = 0;
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d", &x);

        if(x < 0)
        {
            ans += (LL)x * i;    
        }else{
            ans += x;
        }
    }

    printf("%lld\n", ans);


    return 0;
} 

3. 璀璨光滑

这道题先不补了。。。。。

4. 树上求和

解题思路
这道题看到对应的操作之后，首先想到的肯定是使用线段树来解，但是如何维护序列呢，序列又是什么呢? 这里就有一个比较巧妙的思路就是对于题目给定的树，求一遍前序遍历的顺序(因为题目中要修改和查询的都是一个节点及它的子节点)， 在求前序遍历顺序的过程中，记录每一个节点所对应的l和r，然后在求出dfs序的序列上使用线段树来维护就可以了，这里涉及到了区间修改以及区间查询，所以要使用懒标记，之后我们考虑线段树中的节点需要维护哪些信息呢? (sum(区间内所有数字的和), squ(区间内所有数字的平方和), l(区间左边界), r(区间右边界), add(懒标记)), 当当前区间的所有数字需要加上一个x时，sum很好维护，add直接加上x就行，而对于squ，可以用如下公式解决:

这样线段树的所有信息都可以维护了，问题也就解决了。

我在做这道题的时候遇到一个坑点，我刚开始只建立了一条单向边，但是题目中的边不一定都是父亲指向儿子的，所以会出现问题，因此需要建立双向边。

参考代码

import java.io.*;
import java.util.*;

class Node{

    int l, r;
    long sum, squ; // sum存储该区间所有数字的和，squ存储该区间所有数字的平方和
    long add; // 懒标记

    public Node() {

    }

    public Node(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public Node(int l, int r, long sum, long squ, long add) {
        this.l = l;
        this.r = r;
        this.sum = sum;
        this.squ = squ;
        this.add = add;
    }
}

public class Main{
    static int N = 100050, M = N * 2;
    static int[] w = new int[N]; // 存储所有节点的权值
    static int[] a = new int[N];
    static int[] L = new int[N]; // 存储某个根节点的左边界
    static int[] R = new int[N]; // 存储某个根节点的右边界
    static Node[] tr = new Node[N * 4];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx, tot;
    static int MOD = 23333;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    static void dfs(int u, int fa) {
        a[++ tot] = u;
        L[u] = tot;

        for(int i=h[u]; i!=-1; i=ne[i]) {
            int j = e[i];
            if(j == fa) continue;
            dfs(j, u);
        }

        R[u] = tot;
    }

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

    static void eval(Node t, long y) {
        t.add = (t.add + y) % MOD;
        t.squ = ((t.squ + 2 * t.sum * y) % MOD + (t.r -  t.l + 1) * y % MOD * y % MOD) % MOD;
        t.sum = (t.sum + (t.r - t.l + 1) * y) % MOD;
    }

    static void pushdown(int u) {
        Node t = tr[u];
        Node l = tr[u<<1];
        Node r = tr[u<<1|1];

        eval(l, t.add);
        eval(r, t.add);
        t.add = 0;
    }

    static void build(int u, int l, int r) {
        if(l == r) tr[u] = new Node(l, r, w[a[l]], (long)w[a[l]]*w[a[l]] % MOD, 0);
        else {
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid+1, r);
            pushup(u);
        }
    }

    static void modify(int u, int l, int r, int y) {
        if(tr[u].l >= l && tr[u].r <= r) {
            eval(tr[u], y);
        }else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if(l <= mid) modify(u<<1, l, r, y);
            if(r > mid) modify(u<<1|1, l, r, y);
            pushup(u);
        }
    }

    static long query(int u, int l, int r) {
        if(tr[u].l >= l && tr[u].r <= r) return tr[u].squ;

        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        long res = 0;
        if(l <= mid) res = query(u<<1, l, r);
        if(r > mid) res = (res + query(u<<1|1, l, r)) % MOD;
        return res;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader  in = new BufferedReader(new InputStreamReader(System.in));

        Arrays.fill(h, -1);

        String[] arr = in.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int q = Integer.parseInt(arr[1]);

        String[] cur = in.readLine().split(" ");
        for(int i=1; i<=n; i++) w[i] = Integer.parseInt(cur[i-1]);

        for(int i=0; i<n-1; i++) {
            String[] tmp = in.readLine().split(" ");
            int u = Integer.parseInt(tmp[0]);
            int v = Integer.parseInt(tmp[1]);

            add(u, v);
            add(v, u);
        }

        dfs(1, 0);

        build(1, 1, n);

        while(q -- > 0) {
            String[] tmp = in.readLine().split(" ");
            int op = Integer.parseInt(tmp[0]);
            if(op == 1) {
                int x = Integer.parseInt(tmp[1]);
                int y = Integer.parseInt(tmp[2]);
                modify(1, L[x], R[x], y);
            }else {
                int x = Integer.parseInt(tmp[1]);
                System.out.println(query(1, L[x], R[x]));
            }
        }
    }
}

5. 算式子

解题思路
这道题首先发现，我们可以将左半边和右半边分开计算
对于左边的式子，假设 的值为，则的值就会在这个区间内，这里使用cnt1[i]数组记录i这个值出现的次数，求出cnt1的前缀和之后，cnt1[i]表示的就是小于等于i这个值所有数字的个数，之后枚举x的所有的值，枚举所有的类似上面的区间，对于每一个区间，它对左边式子和的贡献为, 求和之后就可以求出左边式子的和
对于右边的式子，假设 的值为, 则的值就会在这个区间内，这里使用cnt2[i]来记录当的值为时，右边式子的和，这里求cnt2的时候可以使用差分的思想，方法是枚举所有的值，枚举所有类似于上面的区间，在这个区间的左端点加上对于这个区间的贡献，也就是出现的次数乘以, 在这个区间的右端点加1处减去对于这个区间的贡献，最后求这个数组的前缀和之后，cnt2[i]就表示了当为时，右边式子的和

参考代码

import java.io.*;
import java.util.*;

public class Main{
    static int N = 2000010;
    static int[] a = new int[N];
    static long[] cnt1 = new long[N];
    static long[] cnt2 = new long[N];

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = in.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        String[] cur = in.readLine().split(" ");
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(cur[i]);
            cnt1[a[i]] ++;
        }

        // 枚举所有x / ai的情况
        for(int i=1; i<=m; i++) {
            if(cnt1[i] == 0) continue;
            for(int k=1; k*i<=m; k++) {
                int l = k * i; int r = Math.min(m, (k + 1) * i - 1);
                cnt2[l] += cnt1[i] * k;
                cnt2[r + 1] -= cnt1[i] * k;
            }
        }

        for(int i=1; i<=m; i++) cnt1[i] += cnt1[i-1];
        for(int i=1; i<=m; i++) cnt2[i] += cnt2[i-1];

        long res = 0;
        for(int i=1; i<=m; i++) {
            long tmp = 0;
            for(int j=i; j<=m; j+=i) {
                int t = Math.min(m, j+i-1);

                tmp += (cnt1[t] - cnt1[j-1]) * (j / i);
            }

            res ^= (tmp + cnt2[i]);
        }

        System.out.println(res);
    }
}