meme.java

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

import static java.lang.Integer.min;


public class Main {


    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter pw = new PrintWriter(System.out);
        FastScanner sc = new FastScanner(System.in);
//        Scanner sc = new Scanner(new File("input.txt"));

        long now = System.currentTimeMillis();

        new Solution().run(sc, pw);

        pw.close();
        sc.close();

        System.err.println("\n\n#Done in " + (System.currentTimeMillis()-now) / 1000.0 + " sec.");
    }

    static public class Solution {

        public static Random rand = new Random();

        public class Fenwick {

            public long[] tr;
            public int sz;

            public Fenwick(int sz) {
                this.sz = sz;
                tr = new long[sz];
                Arrays.fill(tr, 0);
            }

            public Fenwick(int[] a) {
                this.sz = a.length;
                tr = new long[sz];
                Arrays.fill(tr, 0);
                for(int i = 0; i < sz; i++)
                    inc(i, a[i]);
            }

            public long get(int r) {
                long res = 0;
                for(; r >= 0; r = (r&(r+1)) - 1)
                    res += tr[r];
                return res;
            }

            public long get(int l, int r) {
                return get(r) - get(l-1);
            }

            public void inc(int p, long val) {
                for(; p < sz; p |= (p+1))
                    tr[p] += val;
            }
        }

        public class MinSegmentTree {

            public int tr[];
            public int sz;

            MinSegmentTree() {}

            MinSegmentTree(int[] ar) {
                this.sz = ar.length;
                this.tr = new int[this.sz<<1];

                for(int i = 0; i < sz; i++)
                    tr[i+sz] = ar[i];
                for(int i = sz-1; i > 0; i--)
                    tr[i] = min(tr[i<<1], tr[i<<1|1]);
            }

            public int query(int l, int r) {
                int res = Integer.MAX_VALUE;
                for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
                    if((l&1) > 0)
                        res = min(res, tr[l++]);
                    if((r&1) > 0)
                        res = min(res, tr[--r]);
                }
                return res;
            }

        }

        public class SegmentTree {

            public class pair {
                int x;
                int y;

                public pair() {}
                public pair(int x, int y) {
                    this.x = x;
                    this.y = y;
                }
            }

            public long sum(int r) {
                long res = r;
                res *= (r+1);
                res >>= 1;
                return res;

            }

            long sum(int l, int r) {
                return sum(r) - sum(l-1);
            }

            long[] tr;
            pair[] upd;
            int sz;

            public SegmentTree() {}

            public SegmentTree(int[] a) {
                int z = 1;
                while(z < a.length)
                    z <<= 1;
                sz = z;

                tr = new long[sz<<1];
                upd = new pair[sz<<1];


                for(int i = 0; i < (sz<<1); i++) {
                    upd[i] = new pair(-1, -1);
                    tr[i] = 0;
                }

                for(int i = 0; i < a.length; i++)
                    tr[i+sz] = a[i];

                for(int i = sz-1; i > 0; i--)
                    tr[i] = tr[i<<1] + tr[i<<1|1];
            }


            private void upd(int v) {
                if(upd[v].x == -1)
                    return;

                tr[v] = sum(upd[v].x, upd[v].y);
                if(v < sz) {
                    int mid = (upd[v].x + upd[v].y) >> 1;
                    upd[v<<1].x = upd[v].x;
                    upd[v<<1].y = mid;
                    upd[v<<1|1].x = mid+1;
                    upd[v<<1|1].y = upd[v].y;
                }

                upd[v].x = upd[v].y = -1;
            }


            public long query(int l, int r) {
                return query(l + sz, r + sz, sz, (sz<<1) - 1, 1);
            }

            public long query(int l, int r, int lv, int rv, int v) {
                upd(v);
//                System.err.print( "(" + l + "; " +  r + ") ");
//                System.err.println("(" + lv + "; " + rv + ") " + v);

                if(rv < l || lv > r)
                    return 0;

                if(lv >= l && rv <= r)
                    return tr[v];

                int mid = (lv+rv)>>1;

                long res = query(l, r, lv, mid, v<<1)
                        + query(l, r, mid+1, rv, v<<1|1);

                tr[v] = tr[v<<1] + tr[v<<1|1];
                return res;

            }

            public void modify(int l, int r) {
                modify(l+sz, r+sz, sz, (sz<<1)-1, 1);
            }

            public void modify(int l, int r, int lv, int rv, int v) {
                upd(v);

//                System.err.print( "(" + l + "; " +  r + ") ");
//                System.err.println("(" + lv + "; " + rv + ") " + v);

                if(rv < l || lv > r)
                    return;

                if(lv >= l && rv <= r) {
                    upd[v].x = lv-l+1;
                    upd[v].y = rv-l+1;
                    upd(v);
                    return;
                }

                int mid = (lv+rv)>>1;
                modify(l, r, lv, mid, v<<1);
                modify(l, r, mid+1, rv, v<<1|1);

                tr[v] = tr[v<<1] + tr[v<<1|1];
            }

        }

        public void run(FastScanner sc, PrintWriter pw) {
            int n = sc.nextInt();
            int[] a = sc.readIntArray(n);

            SegmentTree tr = new SegmentTree(a);

            int m = sc.nextInt();

            for(; m > 0; m--) {
                int t = sc.nextInt();
                if(t == 1) {
                    pw.println(tr.query(sc.nextInt()-1, sc.nextInt()-1));
                } else {
                    tr.modify(sc.nextInt()-1, sc.nextInt()-1);
                }
            }
        }

        public Solution() {}
    }

    public static class FastScanner {

        final static int BUFFER_SIZE = 65536;

        BufferedReader br;
        char[] buf = new char[BUFFER_SIZE];
        int len = 0;
        int it = 0;
        boolean end = false;

        boolean delim(char c) {
            return c == ' ' || c == '\n' || c == '\r';
        }

        void fillBuffer() {
            try {
                len = br.read(buf);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        void ensureBuffer() {
            if (it == len) {
                it = 0;
                fillBuffer();
                if (len == -1) end = true;
            }
        }

        void moveNext() {
            while (!end) {
                ensureBuffer();
                if (!delim(buf[it])) return;
                while (it < len && delim(buf[it])) it++;
            }
        }

        public char nextChar() {
            moveNext();
            if (end) throw new NullPointerException("End was reached");
            return buf[it++];
        }

        public String next() {
            moveNext();
            StringBuilder sb = new StringBuilder();
            while (!end) {
                int l = it;
                while (++it < len && !delim(buf[it]));
                sb.append(buf, l, it - l);
                ensureBuffer();
                if (delim(buf[it])) break;
            }
            return sb.toString();
        }

        public int nextInt() {
            moveNext();
            if (buf[it] == '-') {
                it++;
                return -nextInt();
            }
            if (buf[it] == '+') {
                it++;
                return nextInt();
            }
            int result = 0;
            while (!end) {
                int l = it;
                while (it < len && !delim(buf[it])) {
                    result = (result * 10) + buf[it] - '0';
                    it++;
                }
                ensureBuffer();
                if (end || delim(buf[it])) break;
            }
            return result;
        }

        public long nextLong() {
            moveNext();
            if (buf[it] == '-') {
                it++;
                return -nextLong();
            }
            if (buf[it] == '+') {
                it++;
                return nextLong();
            }
            long result = 0;
            while (!end) {
                int l = it;
                while (it < len && !delim(buf[it])) {
                    result = (result * 10) + buf[it] - '0';
                    it++;
                }
                ensureBuffer();
                if (delim(buf[it])) break;
            }
            return result;
        }

        public FastScanner(String file) {
            try {
                br = new BufferedReader(new FileReader(file), BUFFER_SIZE);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is), BUFFER_SIZE);
        }

        public void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            ensureBuffer();
            if (end) return null;
            StringBuilder sb = new StringBuilder();
            while (!end) {
                int l = it;
                while (++it < len && buf[it] != '\n');
                sb.append(buf, l, it - l);
                ensureBuffer();
                if (buf[it] == '\n') break;
            }
            it++;
            return sb.toString();
        }

        public int[] readIntArray(int count) {
            int[] arr = new int[count];
            for (int i = 0; i < count; i++) arr[i] = nextInt();
            return arr;
        }
    }

}