头像

acw_weian


访客:9284

离线:12小时前


活动打卡代码 AcWing 143. 最大异或对

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010, idx;
    static int[][] tr = new int[31 * N][2];
    static int[] a = new int[N];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        String[] ss = read.readLine().split(" ");
        for(int i = 0; i < n; i++)    a[i] = Integer.valueOf(ss[i]);
        int res = 0;
        for(int i = 0; i < n; i++){
            insert(a[i]);
            res = Math.max(res, query(a[i]) ^ a[i]);
        }
        System.out.println(res);
    }

    public static void insert(int a){
        int p = 0;
        for(int i = 30; i >= 0; i--){
            int u = a >> i & 1;
            if(tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
    }


    public static int query(int a){
        int p = 0, res = 0;
        for(int i = 30; i >= 0; i--){
            int u = a >> i & 1;
            if(tr[p][u ^ 1] != 0){
                p = tr[p][u ^ 1];
                res = (res << 1) + (u ^ 1);
            }else{
                p = tr[p][u];
                res = (res << 1) + u;

            }
        }
        return res;
    }


}


活动打卡代码 AcWing 247. 亚特兰蒂斯

acw_weian
13天前

import java.io.*;
import java.util.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N = 100010, n;
    static Segment[] seg;
    static Node[] tr = new Node[N * 8];
    static List<Double> ys = new ArrayList<>();


    public static void main(String[] args) throws Exception{
        int T = 1;
        while (true){
            n = Integer.valueOf(read.readLine());
            seg = new Segment[n * 2];
            if(n == 0)  break;
            ys.clear();
            for(int i = 0, j = 0; i < n; i++){
                String[] ss = read.readLine().split(" ");
                double x1 = Double.valueOf(ss[0]), y1 = Double.valueOf(ss[1]);
                double x2 = Double.valueOf(ss[2]), y2 = Double.valueOf(ss[3]);
                seg[j++] = new Segment(x1, y1, y2, 1);
                seg[j++] = new Segment(x2, y1, y2, -1);
                ys.add(y1); ys.add(y2);
            }
            Collections.sort(ys);
            ys = unique(ys);

            build(1, 0, ys.size() - 2);
            Arrays.sort(seg, (o1, o2) -> o1.x > o2.x ? 1 : -1);
            double res = 0;
            for(int i = 0; i < n * 2; i++){
                if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
                modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
            }

            log.write("Test case #" + T++ + "\n");
            log.write("Total explored area: " + String.format("%.2f", res) + "\n");
            log.write("\n");
        }

        log.flush();


    }

    public static void pushUp(int u){
        if(tr[u].cnt != 0){
            tr[u].len = ys.get(tr[u].r + 1) - ys.get(tr[u].l);
        }else if(tr[u].l != tr[u].r){
            tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
        }else tr[u].len = 0;
    }

    public static void build(int u, int l, int r){
        tr[u] = new Node(l, r, 0, 0);
        if(l != r){
            int mid = l + r >> 1;
            build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        }
    }

    public static void modify(int u, int l, int r, int k){
        if(tr[u].l >= l && tr[u].r <= r){
            tr[u].cnt += k;
            pushUp(u);
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(l <= mid) modify(u << 1, l, r, k);
            if(r > mid) modify(u << 1 | 1, l, r, k);
            pushUp(u);
        }
    }


    public static int find(double target){
        int l = 0, r = ys.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(ys.get(mid) >= target)  r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static List<Double> unique(List<Double> list){
        List<Double> res = new ArrayList(list.size());
        for(int i = 0; i < list.size(); i++){
            if(res.isEmpty() || res.get(res.size() - 1) != list.get(i)) res.add(list.get(i));
        }
        return res;
    }

    static class Segment{
        double x, y1, y2;
        int k;
        Segment(double x, double y1, double y2, int k){
            this.x = x; this.y1 = y1; this.y2 = y2; this.k = k;
        }
    }

    static class Node{
        int l, r;
        int cnt;
        double len;
        Node(int l, int r, int cnt, double len){
            this.l = l; this.r = r; this.cnt = cnt; this.len = len;
        }
    }

}



acw_weian
13天前

线段树:
1. 永远只考虑根节点的信息 -> 说明query时不需要pushdown
2. 所有操作都是成对出现, 且先加后减(要么区间加1, 要么区间减1, 且区间是一致的) -> modify时不需要pushdown
3. 离散化, y1 表示的是一个区间, y1表示y1~y2, y2表示y2~y3 … , 如果要求L~R区间, 就是求yL ~ yR - 1

第3点解释: 我们需要的是求区间长度, 如果维护的是一个点的话, 是没有长度意义的, 总共有2n个点, 所以维护的是2n-1个区间


import java.io.*;
import java.util.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N = 100010, n;
    static Segment[] seg;
    static Node[] tr = new Node[N * 8];          //映射到y坐标的线段树
    static List<Double> ys = new ArrayList<>();  //加入ys, 实现y坐标的离散化


    public static void main(String[] args) throws Exception{
        int T = 1;
        while (true){
            n = Integer.valueOf(read.readLine());
            seg = new Segment[n * 2];
            if(n == 0)  break;
            for(int i = 0, j = 0; i < n; i++){
                String[] ss = read.readLine().split(" ");
                double x1 = Double.valueOf(ss[0]), y1 = Double.valueOf(ss[1]);
                double x2 = Double.valueOf(ss[2]), y2 = Double.valueOf(ss[3]);
                seg[j++] = new Segment(x1, y1, y2, 1);
                seg[j++] = new Segment(x2, y1, y2, -1);
                ys.add(y1); ys.add(y2);
            }
            //排序, 去重 实现离散化
            Collections.sort(ys);
            ys = unique(ys);

            //构建线段树
            build(1, 0, ys.size() - 2);
            Arrays.sort(seg, (o1, o2) -> o1.x > o2.x ? 1 : -1);
            double res = 0;
            for(int i = 0; i < n * 2; i++){
                if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
                modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
            }

            log.write("Test case #" + T++ + "\n");
            log.write("Total explored area: " + String.format("%.2f", res) + "\n");
            log.write("\n");
        }

        log.flush();


    }

    public static void pushUp(int u){
        //如果cnt > 0, 则整个区间长度就是len
        if(tr[u].cnt > 0){
            //tr[u].r,是区间从r到r + 1的左端点, 所以tr[u].r + 1 -> 右端点, 因为存的是区间
            tr[u].len = ys.get(tr[u].r + 1) - ys.get(tr[u].l);
        }else {
            if(tr[u].l != tr[u].r){
                tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
            }else {
                //如果tr[u].l == tr[u].r 叶节点的话, 区间长度为0
                tr[u].len = 0;
            }
        }
    }

    public static void build(int u, int l, int r){
        tr[u] = new Node(l, r, 0, 0);
        if(l != r){
            int mid = l + r >> 1;
            build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        }
        //这里不需要pushup是因为cnt和len都是0, pushup后结果一样
    }

    public static void modify(int u, int l, int r, int k){
        if(tr[u].l >= l && tr[u].r <= r){
            tr[u].cnt += k;
            pushUp(u);
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(l <= mid) modify(u << 1, l, r, k);
            if(r > mid) modify(u << 1 | 1, l, r, k);
            pushUp(u);
        }
    }


    public static int find(double target){
        int l = 0, r = ys.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(ys.get(mid) >= target)  r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static List<Double> unique(List<Double> list){
        List<Double> res = new ArrayList(list.size());
        for(int i = 0; i < list.size(); i++){
            if(res.isEmpty() || res.get(res.size() - 1) != list.get(i)) res.add(list.get(i));
        }
        return res;
    }

    static class Segment{
        double x, y1, y2;
        int k;
        Segment(double x, double y1, double y2, int k){
            this.x = x; this.y1 = y1; this.y2 = y2; this.k = k;
        }
    }

    static class Node{
        int l, r;
        int cnt;  //当前区间整个被覆盖的次数
        double len;   //不考虑祖先节点cnt的前提下, cnt > 0的区间总长
        Node(int l, int r, int cnt, double len){
            this.l = l; this.r = r; this.cnt = cnt; this.len = len;
        }
    }

}



acw_weian
14天前

懒标记

懒标记, 是线段树解决区间更新问题的利器。
听完y总的视频, 实在被该算法设计震撼到了, 真的是一个很懒的算法哈哈。

拙见

下面讲下个人对懒标记的拙见。
顾名思义, 懒标记, 就是以偷懒闻名的。

特性

线段树的查询, 从根节点出发, 如果走到某个节点, 该节点的左右区间满足查询要求, 直接可以返回结果。
懒标记就是利用这一特性, 如果更新区间值, 需要从上往下更新(push down)。只要更新到达某个节点的左右区间满足更新需求, 就停止更新,剩下的区间用一个标记add来表示,等以后需要用到再更新
实在是够懒的哈哈。


import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static long[] a;
    static Node[] tr;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]), m = Integer.valueOf(ss[1]);
        a = new long[n + 1];
        tr = new Node[n * 4];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Long.valueOf(ss[i - 1]);
        }

        while(m -- > 0){
            ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[1]), b = Integer.valueOf(ss[2]);
            switch("ss[0]"){
                case "Q":
                    log.write(query(1, a, b) + "\n");
                    break;
                case "C":
                    modify(1, a, b, Integer.valueOf(ss[3]);
                    break;
            }
        }
        log.flush();

    }

    public static void modify(int u, int l, int r, int add){
        if(tr[u].l >= l && tr[u].r <= r){
            tr[u].sum += (long)(tr[u].r - tr[u].l + 1) * add;
            tr[u].add += add;
        }else{
            pushDown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            modify(u << 1, l, r, add);
            modify(u << 1 | 1, l, r, add);
            pushUp(u);
        }
    }

    public static long query(int u, int l, int r){
        if(tr[u].l >= l &&tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        pushDown(u);
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        long res = 0;
        if(l <= mid) res = query(u << 1, l, r);
        if(r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }

    public static void build(int u, int l, int r){
        if(l == r){
            tr[u] = new (l, r, a[l]);
        }else{
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(tr[u << 1], l, mid); build(tr[u << 1 | 1], mid + 1, r);
            pushUp(u);
        }
    }

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

    public static void pushDown(int u){
        if(tr[u].add != 0){
            Node l = tr[u << 1], r = tr[u << 1 | 1];
            l.add = tr[u].add; l.sum = (long)tr[u].add * (l.r - l.l + 1);
            r.add = tr[u].add; r.sum = (long)tr[u].add * (r.r - r.l + 1);
            tr[u].add = 0;
        }
    }



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




acw_weian
14天前

懒标记

懒标记, 是线段树解决区间更新问题的利器。
听完y总的视频, 实在被该算法设计震撼到了, 真的是一个很懒的算法哈哈。

拙见

下面讲下个人对懒标记的拙见。
顾名思义, 懒标记, 就是以偷懒闻名的。

特性

线段树的查询, 从根节点出发, 如果走到某个节点, 该节点的左右区间满足查询要求, 直接可以返回结果。
懒标记就是利用这一特性, 如果更新区间值, 需要从上往下更新(push down)。只要更新到达某个节点的左右区间满足更新需求, 就停止更新,剩下的区间用一个标记add来表示,等以后需要用到再更新
实在是够懒的哈哈。


import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static long[] a;
    static Node[] tr;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]), m = Integer.valueOf(ss[1]);
        a = new long[n + 1];
        tr = new Node[n * 4];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Long.valueOf(ss[i - 1]);
        }

        while(m -- > 0){
            ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[1]), b = Integer.valueOf(ss[2]);
            switch("ss[0]"){
                case "Q":
                    log.write(query(1, a, b) + "\n");
                    break;
                case "C":
                    modify(1, a, b, Integer.valueOf(ss[3]);
                    break;
            }
        }
        log.flush();

    }

    public static void modify(int u, int l, int r, int add){
        if(tr[u].l >= l && tr[u].r <= r){
            tr[u].sum += (long)(tr[u].r - tr[u].l + 1) * add;
            tr[u].add += add;
        }else{
            pushDown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            modify(u << 1, l, r, add);
            modify(u << 1 | 1, l, r, add);
            pushUp(u);
        }
    }

    public static long query(int u, int l, int r){
        if(tr[u].l >= l &&tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        pushDown(u);
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);
        long res = 0;
        if(l <= mid) res = query(u << 1, l, r);
        if(r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }

    public static void build(int u, int l, int r){
        if(l == r){
            tr[u] = new (l, r, a[l]);
        }else{
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(tr[u << 1], l, mid); build(tr[u << 1 | 1], mid + 1, r);
            pushUp(u);
        }
    }

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

    public static void pushDown(int u){
        if(tr[u].add != 0){
            Node l = tr[u << 1], r = tr[u << 1 | 1];
            l.add = tr[u].add; l.sum = (long)tr[u].add * (l.r - l.l + 1);
            r.add = tr[u].add; r.sum = (long)tr[u].add * (r.r - r.l + 1);
            tr[u].add = 0;
        }
    }



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




acw_weian
16天前

区间最大公约数.png

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    static long[] w;
    static int n, m;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        n = Integer.valueOf(ss[0]); m = Integer.valueOf(ss[1]);
        w = new long[n + 1]; tr = new Node[n * 4];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            w[i] = Long.valueOf(ss[i - 1]);
        }
        build(1, 1, n);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[1]), b = Integer.valueOf(ss[2]);

            switch(ss[0]){
                case "Q":
                    long left = query(1, 1, a).sum, right = query(1, a + 1, b).gcd;
                    log.write(Math.abs(gcd(left, right)) + "\n");
                    break;
                case "C":
                    long c = Long.valueOf(ss[3]);
                    modify(1, a, c); if(b + 1 <= n) modify(1, b + 1, -c);
                    break;
            }
        }
        log.flush();
    }

    public static void build(int u, int l, int r){
        if(l == r){
            tr[u] = new Node(l, r, w[l] - w[l - 1], w[l] - w[l - 1]);
        }else{
            tr[u] = new Node(l, r);
            int mid = tr[u].l + tr[u].r >> 1;
            build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
            pushUp(u);
        }
    }


    public static Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        else{
            long 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{
                Node left = query(u << 1, l, r);
                Node right = query(u << 1 | 1, l, r);
                Node res = new Node(l, r);
                pushUp(res, left, right);
                return res;
            }
        }
    }

    public static void modify(int u, int x, long c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].sum += c;
            tr[u].gcd += c;
        }else{
            long mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void pushUp(int u){
        pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }
    public static void pushUp(Node u, Node l, Node r){
        u.sum = l.sum + r.sum;
        u.gcd = gcd(l.gcd, r.gcd);
    }

    public static long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a % b);
    }


    static class Node{
        int l, r;
        long sum;
        long gcd;
        Node(int l, int r){
            this.l = l; this.r = r;
        }
        Node(int l, int r, long sum, long gcd){
            this.l = l; this.r = r; this.sum = sum; this.gcd = gcd;
        }
    }

}



acw_weian
16天前

区间最大公约数.png

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    static long[] w;
    static int n, m;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        n = Integer.valueOf(ss[0]); m = Integer.valueOf(ss[1]);
        w = new long[n + 1]; tr = new Node[n * 4];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            w[i] = Long.valueOf(ss[i - 1]);
        }
        build(1, 1, n);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            int a = Integer.valueOf(ss[1]), b = Integer.valueOf(ss[2]);

            switch(ss[0]){
                case "Q":
                    long left = query(1, 1, a).sum, right = query(1, a + 1, b).gcd;
                    log.write(Math.abs(gcd(left, right)) + "\n");
                    break;
                case "C":
                    long c = Long.valueOf(ss[3]);
                    modify(1, a, c); if(b + 1 <= n) modify(1, b + 1, -c);
                    break;
            }
        }
        log.flush();
    }

    public static void build(int u, int l, int r){
        if(l == r){
            tr[u] = new Node(l, r, w[l] - w[l - 1], w[l] - w[l - 1]);
        }else{
            tr[u] = new Node(l, r);
            int mid = tr[u].l + tr[u].r >> 1;
            build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
            pushUp(u);
        }
    }


    public static Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        else{
            long 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{
                Node left = query(u << 1, l, r);
                Node right = query(u << 1 | 1, l, r);
                Node res = new Node(l, r);
                pushUp(res, left, right);
                return res;
            }
        }
    }

    public static void modify(int u, int x, long c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].sum += c;
            tr[u].gcd += c;
        }else{
            long mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void pushUp(int u){
        pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }
    public static void pushUp(Node u, Node l, Node r){
        u.sum = l.sum + r.sum;
        u.gcd = gcd(l.gcd, r.gcd);
    }

    public static long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a % b);
    }


    static class Node{
        int l, r;
        long sum;
        long gcd;
        Node(int l, int r){
            this.l = l; this.r = r;
        }
        Node(int l, int r, long sum, long gcd){
            this.l = l; this.r = r; this.sum = sum; this.gcd = gcd;
        }
    }

}



acw_weian
17天前

解析:
线段树.png

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    static int[] w;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        tr = new Node[n * 4];
        w = new int[n + 1];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++) w[i] = Integer.valueOf(ss[i - 1]);

        buildTree(1, 1, n);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            switch(ss[0]){
                case "1":
                    int l = Integer.valueOf(ss[1]), r = Integer.valueOf(ss[2]);
                    if(l > r)    {int tmp = l; l = r; r = tmp;}
                    log.write(query(1, l, r).tmax + "\n");
                    break;
                case "2":
                    int x = Integer.valueOf(ss[1]), c = Integer.valueOf(ss[2]);
                    modify(1, x, c);
                    break;
            }
        }
        log.flush();
    }


    public static Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        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);
        {
            Node n1 = query(u << 1, l, r);
            Node n2 = query(u << 1 | 1, l, r);
            Node res = new Node(l, r);
            pushUp(res, n1, n2);
            return res;
        }
    }

    public static void modify(int u, int x, int c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].tmax = c; tr[u].lmax = c; tr[u].rmax = c; tr[u].sum = c;
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void buildTree(int u, int l, int r){
        if(l == r){
            tr[u] = new Node(l, r, w[l], w[l], w[l], w[l]);
        }else{
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            buildTree(u << 1, l, mid); buildTree(u << 1 | 1, mid + 1, r);
            pushUp(u);
        }

    }

    public static void pushUp(int u){
        pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }

    public static void pushUp(Node u, Node l, Node r){
        u.sum = l.sum + r.sum;
        u.lmax = Math.max(l.lmax, l.sum + r.lmax);
        u.rmax = Math.max(r.rmax, l.rmax + r.sum);
        u.tmax = Math.max(Math.max(l.tmax, r.tmax), l.rmax + r.lmax);
    }

    static class Node{
        int l, r;
        int tmax, lmax, rmax, sum;
        Node(int l, int r, int tmax, int lmax, int rmax, int sum){
            this.l = l; this.r = r; this.tmax = tmax; this.lmax = lmax;
            this.rmax = rmax; this.sum = sum;
        }
        Node(int l, int r){
            this.l = l; this.r = r;
        }
    }
}



acw_weian
17天前

解析:
线段树.png

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    static int[] w;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        tr = new Node[n * 4];
        w = new int[n + 1];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++) w[i] = Integer.valueOf(ss[i - 1]);

        buildTree(1, 1, n);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            switch(ss[0]){
                case "1":
                    int l = Integer.valueOf(ss[1]), r = Integer.valueOf(ss[2]);
                    if(l > r)    {int tmp = l; l = r; r = tmp;}
                    log.write(query(1, l, r).tmax + "\n");
                    break;
                case "2":
                    int x = Integer.valueOf(ss[1]), c = Integer.valueOf(ss[2]);
                    modify(1, x, c);
                    break;
            }
        }
        log.flush();
    }


    public static Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        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);
        {
            Node n1 = query(u << 1, l, r);
            Node n2 = query(u << 1 | 1, l, r);
            Node res = new Node(l, r);
            pushUp(res, n1, n2);
            return res;
        }
    }

    public static void modify(int u, int x, int c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].tmax = c; tr[u].lmax = c; tr[u].rmax = c; tr[u].sum = c;
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void buildTree(int u, int l, int r){
        if(l == r){
            tr[u] = new Node(l, r, w[l], w[l], w[l], w[l]);
        }else{
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            buildTree(u << 1, l, mid); buildTree(u << 1 | 1, mid + 1, r);
            pushUp(u);
        }

    }

    public static void pushUp(int u){
        pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }

    public static void pushUp(Node u, Node l, Node r){
        u.sum = l.sum + r.sum;
        u.lmax = Math.max(l.lmax, l.sum + r.lmax);
        u.rmax = Math.max(r.rmax, l.rmax + r.sum);
        u.tmax = Math.max(Math.max(l.tmax, r.tmax), l.rmax + r.lmax);
    }

    static class Node{
        int l, r;
        int tmax, lmax, rmax, sum;
        Node(int l, int r, int tmax, int lmax, int rmax, int sum){
            this.l = l; this.r = r; this.tmax = tmax; this.lmax = lmax;
            this.rmax = rmax; this.sum = sum;
        }
        Node(int l, int r){
            this.l = l; this.r = r;
        }
    }
}


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

acw_weian
17天前
import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int m = Integer.valueOf(ss[0]), p = Integer.valueOf(ss[1]);
        tr = new Node[m * 4];
        int last = 0, n = 1, x;
        buildTree(1, 1, m);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            x = Integer.valueOf(ss[1]);
            if("Q".equals(ss[0])){
                last = query(1, n - x + 1, n);
                log.write(last + "\n");
            }else{
                modify(1, n + 1, (last + x) % p);  //注意,这里根节点是1, 修改的数是从n + 1开始。
                n++;
            }
        }
        log.flush();

    }

    public static int query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
        int mid = tr[u].l + tr[u].r >> 1;
        int v = 0;
        if(l <= mid) v = query(u << 1, l, r);
        if(r > mid) v = Math.max(v, query(u << 1 | 1, l, r));
        return v;
    }

    public static void pushUp(int u){
        tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
    }

    public static void modify(int u, int x, int c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].v = c;
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void buildTree(int u, int l, int r){
        tr[u] = new Node(l, r);
        if(l == r) return;
        int mid = l + r >> 1;
        buildTree(u << 1, l , mid);
        buildTree(u << 1 | 1, mid + 1, r);
    }

    static class Node{
        int l, r, v;
        Node(int l, int r){
            this.l = l;
            this.r = r;
        }
    }
}