HDu 4391 Paint The Wall(ルートNセグメントハッシュ)

区間全体をsqrt(n)セグメントセル間に分割し、各セグメント長をsqrt(n)とし、各セグメントの統計量を維持することで、sqrt(n)時間内に区間クエリーまたは更新を完了することができる.バランスクエリーと更新の矛盾はデータ構造設計時の重要な考慮要素であり、この方法は古典的なバランスの方法であり、とっくに理解していたが、以前は「セグメント」でしか解決できない問題に遭遇したことがないので、いつもやむを得ない「頼り」だと感じていた.結局悲劇は毎回O(n)を調べるように書かれた.エラーをまとめます.
1.区間全体の更新については、各要素の値を実際に処理する必要はなく、1つの変数でマークするだけでよい.セグメント全体の要素の更新量が一致しない場合に各要素を更新することで、クエリ時のsqrt(n)の複雑さを保証することができる.そうしないとO(n)になる.
2.ハッシュ・テーブルの代わりにmapを使用する場合、クエリーが存在しない要素が自動的に挿入されるため、要素がmapに存在しない場合は直接クエリーしないでください.空間の複雑さはn*nになります.
3.最後のセグメントについては、前のセグメントと長さが異なる場合がありますので、最後のセグメントの長さを特別に処理する必要があります.
Javaの中でHashMapの効率が客観的であることを考慮して、自分でハッシュ表を書くのがおっくうで、mapを使うと複雑度が増加して、ojの支持はよくなくてしかも下のcaozを支持しないが、結局javaでセグメントハッシュをすることを選んだ.
その他のテーマ:
Spoj 3261 Race Against Timeある値を修正し、クエリはk以下の要素の個数を求める
解法:セグメント+ソート/Treap
spoj 861 SWAPS動的メンテナンス逆シーケンス対
解法:セグメント/Treap+ツリー配列(http://blog.csdn.net/kksleric/article/details/7929903)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;

public class Hash {
	int maxn = 100010, maxm = 335;
	class Zone {
		HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
		int color[] = new int[maxm], len, all;
		void init(int ln) {
			mp.clear();
			all = -1;
			len = ln;
		}
		int get(int c) {
			if (mp.containsKey(c))
				return mp.get(c);
			else
				return 0;
		}
		void set(int c) {
			all = c;
		}
		void update(int left, int right, int c) {
			if (all == c)
				return;
			if (all != -1) {
				for (int i = 1; i < left; i++)
					color[i] = all;
				for (int i = right + 1; i <= len; i++)
					color[i] = all;
			}
			for (int i = left; i <= right; i++)
				color[i] = c;
			all = -1;
			mp.clear();
			for (int i = 1; i <= len; i++)
				mp.put(color[i], get(color[i])+1);
		}

		int query(int left, int right, int c) {
			if (all == -1) {
				int sum = 0;
				for (int i = left; i <= right; i++)
					if (color[i] == c)
						sum++;
				return sum;
			} else {
				if (all == c)
					return right - left + 1;
				else
					return 0;
			}
		}
	}
	Zone zz[] = new Zone[maxm];
	int belong[] = new int[maxn], id[] = new int[maxn];
	int a[] = new int[maxn], M;
	void build(int n) {
		for (int i = 1; i * i <= n; i++)
			M = i;
		int cnt = 0, len = M;
		for (int i = 1; i <= n; i++) {
			if (len == M) {
				zz[++cnt].init(M);
				len = 0;
			}
			belong[i] = cnt;
			id[i] = ++len;
			zz[cnt].color[len] = a[i];
			zz[cnt].mp.put(a[i], zz[cnt].get(a[i]) + 1);
		}
		zz[cnt].len = len;
	}

	void update(int left, int right, int c) {
		int l = belong[left], r = belong[right];
		if (l == r) {
			zz[r].update(id[left], id[right], c);
		} else {
			zz[l].update(id[left], zz[l].len, c);
			for (int i = l + 1; i < r; i++)
				zz[i].set(c);
			zz[r].update(1, id[right], c);
		}
	}

	int query(int left, int right, int c) {
		int sum = 0;
		int l = belong[left], r = belong[right];
		if (l == r) {
			sum += zz[l].query(id[left], id[right], c);
		} else {
			sum += zz[l].query(id[left], zz[l].len, c);
			for (int i = l + 1; i < r; i++) {		
				if (zz[i].all == c)
					sum += zz[i].len;
				if(zz[i].all==-1)
					sum += zz[i].get(c);
			}
			sum += zz[r].query(1, id[right], c);
		}
		return sum;
	}
	void run() throws IOException {
		for (int i = 1; i < maxm; i++)
			zz[i] = new Zone();
		while (in.nextToken() != in.TT_EOF) {
			int n = (int) in.nval;
			int m = nextInt();
			for (int i = 1; i <= n; i++)
				a[i] = nextInt();
			build(n);
			int t, a, b, c;
			while (m-- > 0) {
				t = nextInt();
				a = nextInt() + 1;
				b = nextInt() + 1;
				c = nextInt();
				if (t == 1)
					update(a, b, c);
				else
					System.out.println(query(a, b, c));
			}
		}
	}
	StreamTokenizer in = new StreamTokenizer(new BufferedReader(
			new InputStreamReader(System.in)));

	int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}
	public static void main(String[] args) throws IOException {
		new Hash().run();
	}
}