1. 首页
2. 线段树
3. 本页

线段树单点更新(二)

poj2828 Buy Tickets

逆序维护区间和

import java.util.*;
import java.math.*;

public class Main {
	static int MAXN = 220010;
	static int[] sum = new int[MAXN << 2];

	static int[] a = new int[200010];
	static int[] b = new int[200010];
	static int[] vis = new int[200010];
	static int mk;

	public static void pushup(int rt) {
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}

	public static void bulid(int l, int r, int rt) {
		sum[rt] = r - l + 1;
		if (r == l) {
			return;
		}
		int m = (l + r) >> 1;
		bulid(l, m, rt << 1);
		bulid(m + 1, r, rt << 1 | 1);
		// pushup(rt);
	}

	public static void update(int pos, int add, int l, int r, int rt) {
		sum[rt]--;
		if (l == r) {
			mk = l;
			return;
		}
		int m = (l + r) >> 1;
		if (pos <= sum[rt << 1]) {
			update(pos, add, l, m, rt << 1);
		} else {
			update(pos - sum[rt << 1], add, m + 1, r, rt << 1 | 1);
		}
		pushup(rt);
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n;
		while (cin.hasNext()) {
			n = cin.nextInt();
			bulid(1, n, 1);
			int sum = 0;
			for (int i = 0; i < n; ++i) {
				a[i] = cin.nextInt();
				b[i] = cin.nextInt();
			}
			for (int i = n - 1; i >= 0; i--) {
				update(a[i] + 1, b[i], 0, n - 1, 1);
				vis[mk] = b[i];
			}
			System.out.print(vis[0]);
			for (int i = 1; i < n; ++i) {
				System.out.print(" " + vis[i]);
			}
			System.out.print("\n");
		}
		cin.close();
	}

}

poj2886 Who Gets the Most Candies?

import java.util.*;
import java.math.*;

public class Main {
	static int MAXN = 500010;
	static int[] tree = new int[MAXN << 2];
	static int[] ans = new int[MAXN];
	static String[] str = new String[MAXN];
	static int[] val = new int[MAXN];

	public static void pushup(int rt) {
		tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
	}

	public static void bulid(int l, int r, int rt) {
		if (r == l) {
			tree[rt] = 1;
			return;
		}
		int m = (l + r) >> 1;
		bulid(l, m, rt << 1);
		bulid(m + 1, r, rt << 1 | 1);
		pushup(rt);
	}

	public static int update(int add, int l, int r, int rt) {
		if (l == r) {
			tree[rt]--;
			return l;
		}
		int m = (l + r) >> 1;
		int pos;
		if (tree[rt << 1] >= add) {
			pos = update(add, l, m, rt << 1);
		} else {
			pos = update(add - tree[rt << 1], m + 1, r, rt << 1 | 1);
		}
		pushup(rt);
		return pos;
	}

	static int id;

	public static void init(int n) {
		Arrays.fill(ans, 0);
		for (int i = 1; i <= n; i++) {
			ans[i]++;
			for (int j = 2 * i; j <= n; j += i)
				ans[j]++;
		}
		int max = ans[1];
		id = 1;
		for (int i = 2; i <= n; i++)
			if (ans[i] > max) {
				max = ans[i];
				id = i;
			}
	}

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n, k;
		while (cin.hasNext()) {
			n = cin.nextInt();
			k = cin.nextInt();
			init(n);
			bulid(1, n, 1);
			for (int i = 1; i <= n; ++i) {
				str[i] = cin.next();
				val[i] = cin.nextInt();
			}
			int cnt = id;
			int mod = n;
			val[0] = 0;
			int pos = 0;
			while (cnt > 0) {
				cnt--;
				if (val[pos] > 0)
					k = ((k - 1 + val[pos] - 1) % mod + mod) % mod + 1;
				else
					k = ((k - 1 + val[pos]) % mod + mod) % mod + 1;
				pos = update(k, 1, n, 1);
				// System.out.println(pos);
				mod = tree[1];
			}

			System.out.println(str[pos] + " " + ans[id]);
		}
		cin.close();

	}

}