目录
牛牛的凑数游戏：
题目大意：
思路解析：
代码实现：
牛牛的凑数游戏：
题目大意：
思路解析：
我们可以很容易一个区间是否会存在1，那么我们想如果存在1，且有3个1，那我们一定可以组成 1，2，3，那么为出现的数为4，如果这个区间还有一个四，我们可以发现我们一定可以组成5，6，7，那我们如果这个区间还有 a个3，b个2，那我们发现我们一定可以组成 [1,3+4+3*a+2*b]，这是因为任意一个数都可以表示为 n = 4 * k + m, 0<=m<=3,那我们假设组成的3+4+3*a+2*b == 17，那么下一次的数一定可以表示为 n = 17 * k + m ( 0<=m<=16)..... 这个问题就转化为了 计算[1,1]的和 记作 a， 计算[1,a+1]的和 记住b，计算[1,b+1]的和。。。一直迭代下去最后一定会因为某些数字的未出现而结束。
那么问题变为了查询 [l,r]这个区间 里面数字属于 [L,R]这个范围的和为多少。这个可以使用主席树实现。
代码实现：
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int MAXN = (int) 1e5 + 5;static int tot = 0;static int[] a = new int[MAXN];static int[] root = new int[MAXN];static Node[] t = new Node[MAXN * 32];static int ans = 0;static int INF = (int) 1e9 +100;public static void main(String[] args) {int n = f.nextInt(); int m = f.nextInt();t[0] = new Node();for (int i = 1; i <= n; i++) {a[i] = f.nextInt();root[i] = ins(root[i], root[i - 1], 1, INF, a[i]);}while (m > 0){int l = f.nextInt();int r = f.nextInt();long cur = 0, res = 0;do {cur = res + 1;res = qry(root[l - 1], root[r], 1, INF, 1, Math.min(cur, INF));}while (cur <= res);System.out.println(cur);m--;}}public static long qry(int s, int e, int l, int r, int L, long R){if (L <= l && R >= r) return t[e].sum - t[s].sum;long res = 0;int mid = (l + r) >> 1;if (L <= mid) res += qry(t[s].l, t[e].l, l, mid, L, R);if (R > mid) res += qry(t[s].r, t[e].r, mid+1, r, L, R);return res;}public static int ins(int p, int q, int l, int r, int x){p = ++tot;t[p] = new Node(t[q]);t[p].sum += x;if (l == r) return p;int mid = (l + r) >> 1;if (x <= mid) t[p].l = ins(t[p].l, t[q].l, l, mid, x);else t[p].r = ins(t[p].r, t[q].r, mid+1, r, x);return p;}static class Node{int l, r;long sum;public Node(Node node) {this.l = node.l;this.r = node.r;this.sum = node.sum;}public Node(){}}static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));static Input f = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}
