1
public class Code01_SetAllHashMap {
2

3
  public static HashMap<Integer, int[]> map = new HashMap<>();
4
  public static int setAllValue;
5
  public static int setAllTime;
6
  public static int cnt;
7

8
  public static void put(int k, int v) {
9
    if (map.containsKey(k)) {
10
      int[] value = map.get(k);
11
      value[0] = v;
12
      value[1] = cnt++;
13
    } else {
14
      map.put(k, new int[] { v, cnt++ });
15
    }
16
  }
17

18
  public static void setAll(int v) {
19
    setAllValue = v;
20
    setAllTime = cnt++;
21
  }
22

23
  public static int get(int k) {
24
    if (!map.containsKey(k)) {
25
      return -1;
26
    }
27
    int[] value = map.get(k);
28
    if (value[1] > setAllTime) {
29
      return value[0];
30
    } else {
31
      return setAllValue;
32
    }
33
  }
34

35
  public static int n, op, a, b;
36

37
  public static void main(String[] args) throws IOException {
38
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
39
    StreamTokenizer in = new StreamTokenizer(br);
40
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
41
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
42
      map.clear();
43
      setAllValue = 0;
44
      setAllTime = -1;
45
      cnt = 0;
46
      n = (int) in.nval;
47
      for (int i = 0; i < n; i++) {
48
        in.nextToken();
49
        op = (int) in.nval;
50
        if (op == 1) {
51
          in.nextToken();
52
          a = (int) in.nval;
53
          in.nextToken();
54
          b = (int) in.nval;
55
          put(a, b);
56
        } else if (op == 2) {
57
          in.nextToken();
58
          a = (int) in.nval;
59
          out.println(get(a));
60
        } else {
61
          in.nextToken();
62
          a = (int) in.nval;
63
          setAll(a);
64
        }
65
      }
66
    }
67
    out.flush();
68
    out.close();
69
    br.close();
70
  }
71

72
}

1
class LRUCache {
2

3
    class DoubleListNode {
4
        int value;
5
        int key;
6
        DoubleListNode pre;
7
        DoubleListNode next;
8

9
        DoubleListNode (int k ,int v) {
10
            this.key = k;
11
            this.value = v;
12
            pre = null;
13
            next = null;
14
        }
15
    }
16

17
    class DoubleList {
18
        DoubleListNode head;
19
        DoubleListNode tail;
20

21
        DoubleList () {
22
            head = null;
23
            tail = null;
24
        }
25

26
        void addNode (DoubleListNode newNode) {
27
            if (newNode == null) return;
28
            if (head == null) {
29
                head = newNode;
30
                tail = newNode;
31
                newNode.pre = null;
32
                newNode.next = null;
33
            } else {
34
                tail.next = newNode;
35
                newNode.pre = tail;
36
                newNode.next = null;
37
                tail = newNode;
38
            }
39
        }
40

41
        void moveNodeTail (DoubleListNode node) {
42
            if (tail == node){
43
                return;
44
            }
45
            if (head == node) {
46
                head = head.next;
47
                head.pre = null;
48
                node.next = null;
49
                tail.next = node;
50
                node.pre = tail;
51
                tail = node;
52
            } else {
53
                node.pre.next = node.next;
54
                node.next.pre = node.pre;
55
                tail.next = node;
56
                node.pre = tail;
57
                node.next= null;
58
                tail = node;
59
            }
60
        }
61

62
        DoubleListNode removeHead () {
63
            if (head == null) return null;
64
            DoubleListNode ans = null;
65
            if (head == tail) {
66
                ans = head;
67
                head = null;
68
                tail = null;
69
            } else {
70
                ans = head;
71
                head = head.next;
72
                head.pre.next = null;
73
                head.pre = null;
74
            }
75
            return ans;
76
        }
77
    }
78

79
    private HashMap<Integer, DoubleListNode> keyNodeMap;
80

81
    private DoubleList nodeList;
82

83
    private final int capacity;
84

85
    public LRUCache(int capacity) {
86
        this.capacity = capacity;
87
        keyNodeMap = new HashMap<>();
88
        nodeList = new DoubleList();
89
    }
90

91
    public int get(int key) {
92
        if (keyNodeMap.containsKey(key)) {
93
            DoubleListNode doubleListNode = keyNodeMap.get(key);
94
            nodeList.moveNodeTail(doubleListNode);
95
            return doubleListNode.value;
96
        } else {
97
            return -1;
98
        }
99
    }
100

101
    public void put(int key, int value) {
102
        if (capacity == 0) return;
103
        if (keyNodeMap.containsKey(key)) {
104
            DoubleListNode doubleListNode = keyNodeMap.get(key);
105
            doubleListNode.value = value;
106
            nodeList.moveNodeTail(doubleListNode);
107
        } else {
108
            DoubleListNode newNode = new DoubleListNode(key ,value);
109
            if (keyNodeMap.size() == capacity) {
110
                DoubleListNode doubleListNode = nodeList.removeHead();
111
                keyNodeMap.remove(doubleListNode.key);
112
                nodeList.addNode(newNode);
113
            } else {
114
                nodeList.addNode(newNode);
115
            }
116
            keyNodeMap.put(newNode.key ,newNode);
117
        }
118
    }
119
}

1
class RandomizedCollection {
2

3
    public HashMap<Integer, HashSet<Integer>> map;
4

5
    public ArrayList<Integer> arr;
6

7
    public RandomizedCollection() {
8
      map = new HashMap<>();
9
      arr = new ArrayList<>();
10
    }
11

12
    public boolean insert(int val) {
13
      arr.add(val);
14
      HashSet<Integer> set = map.getOrDefault(val, new HashSet<Integer>());
15
      set.add(arr.size() - 1);
16
      map.put(val, set);
17
      return set.size() == 1;
18
    }
19

20
    public boolean remove(int val) {
21
      if (!map.containsKey(val)) {
22
        return false;
23
      }
24
      HashSet<Integer> valSet = map.get(val);
25
      int valAnyIndex = valSet.iterator().next();
26
      int endValue = arr.get(arr.size() - 1);
27
      if (val == endValue) {
28
        valSet.remove(arr.size() - 1);
29
      } else {
30
        HashSet<Integer> endValueSet = map.get(endValue);
31
        endValueSet.add(valAnyIndex);
32
        arr.set(valAnyIndex, endValue);
33
        endValueSet.remove(arr.size() - 1);
34
        valSet.remove(valAnyIndex);
35
      }
36
      arr.remove(arr.size() - 1);
37
      if (valSet.isEmpty()) {
38
        map.remove(val);
39
      }
40
      return true;
41
    }
42

43
    public int getRandom() {
44
      return arr.get((int) (Math.random() * arr.size()));
45
    }
46
  }

1
class MedianFinder {
2

3
    private PriorityQueue<Integer> maxHeap;
4

5
    private PriorityQueue<Integer> minHeap;
6

7
    public MedianFinder() {
8
      maxHeap = new PriorityQueue<>((a, b) -> b - a);
9
      minHeap = new PriorityQueue<>((a, b) -> a - b);
10
    }
11

12
    public void addNum(int num) {
13
      if (maxHeap.isEmpty() || maxHeap.peek() >= num) {
14
        maxHeap.add(num);
15
      } else {
16
        minHeap.add(num);
17
      }
18
      balance();
19
    }
20

21
    public double findMedian() {
22
      if (maxHeap.size() == minHeap.size()) {
23
        return (double) (maxHeap.peek() + minHeap.peek()) / 2;
24
      } else {
25
        return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
26
      }
27
    }
28

29
    private void balance() {
30
      if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {
31
        if (maxHeap.size() > minHeap.size()) {
32
          minHeap.add(maxHeap.poll());
33
        } else {
34
          maxHeap.add(minHeap.poll());
35
        }
36
      }
37
    }
38

39
  }

1
class FreqStack {
2

3
    // 出现的最大次数
4
    private int topTimes;
5
    // 每层节点
6
    private HashMap<Integer, ArrayList<Integer>> cntValues = new HashMap<>();
7
    // 每一个数出现了几次
8
    private HashMap<Integer, Integer> valueTimes = new HashMap<>();
9

10
    public void push(int val) {
11
      valueTimes.put(val, valueTimes.getOrDefault(val, 0) + 1);
12
      int curTopTimes = valueTimes.get(val);
13
      if (!cntValues.containsKey(curTopTimes)) {
14
        cntValues.put(curTopTimes, new ArrayList<>());
15
      }
16
      ArrayList<Integer> curTimeValues = cntValues.get(curTopTimes);
17
      curTimeValues.add(val);
18
      topTimes = Math.max(topTimes, curTopTimes);
19
    }
20

21
    public int pop() {
22
      ArrayList<Integer> topTimeValues = cntValues.get(topTimes);
23
      int ans = topTimeValues.remove(topTimeValues.size() - 1);
24
      if (topTimeValues.size() == 0) {
25
        cntValues.remove(topTimes--);
26
      }
27
      int times = valueTimes.get(ans);
28
      if (times == 1) {
29
        valueTimes.remove(ans);
30
      } else {
31
        valueTimes.put(ans, times - 1);
32
      }
33
      return ans;
34
    }
35
  }

1
class AllOne {
2

3
    class Bucket {
4
      public HashSet<String> set;
5
      public int cnt;
6
      public Bucket last;
7
      public Bucket next;
8

9
      public Bucket(String s, int c) {
10
        set = new HashSet<>();
11
        set.add(s);
12
        cnt = c;
13
      }
14
    }
15

16
    private void insert(Bucket cur, Bucket pos) {
17
      cur.next.last = pos;
18
      pos.next = cur.next;
19
      cur.next = pos;
20
      pos.last = cur;
21
    }
22

23
    private void remove(Bucket cur) {
24
      cur.last.next = cur.next;
25
      cur.next.last = cur.last;
26
    }
27

28
    Bucket head;
29

30
    Bucket tail;
31

32
    HashMap<String, Bucket> map;
33

34
    public AllOne() {
35
      head = new Bucket("", 0);
36
      tail = new Bucket("", Integer.MAX_VALUE);
37
      head.next = tail;
38
      tail.last = head;
39
      map = new HashMap<>();
40
    }
41

42
    public void inc(String key) {
43
      if (!map.containsKey(key)) {
44
        if (head.next.cnt == 1) {
45
          map.put(key, head.next);
46
          head.next.set.add(key);
47
        } else {
48
          Bucket newBucket = new Bucket(key, 1);
49
          map.put(key, newBucket);
50
          insert(head, newBucket);
51
        }
52
      } else {
53
        Bucket bucket = map.get(key);
54
        if (bucket.next.cnt == bucket.cnt + 1) {
55
          map.put(key, bucket.next);
56
          bucket.next.set.add(key);
57
        } else {
58
          Bucket newBucket = new Bucket(key, bucket.cnt + 1);
59
          map.put(key, newBucket);
60
          insert(bucket, newBucket);
61
        }
62
        bucket.set.remove(key);
63
        if (bucket.set.isEmpty()) {
64
          remove(bucket);
65
        }
66
      }
67
    }
68

69
    public void dec(String key) {
70
      Bucket bucket = map.get(key);
71
      if (bucket.cnt == 1) {
72
        map.remove(key);
73
      } else {
74
        if (bucket.last.cnt == bucket.cnt - 1) {
75
          map.put(key, bucket.last);
76
          bucket.last.set.add(key);
77
        } else {
78
          Bucket newBucket = new Bucket(key, bucket.cnt - 1);
79
          map.put(key, newBucket);
80
          insert(bucket.last, newBucket);
81
        }
82
      }
83
      bucket.set.remove(key);
84
      if (bucket.set.isEmpty()) {
85
        remove(bucket);
86
      }
87
    }
88

89
    public String getMaxKey() {
90
      return tail.last.set.iterator().next();
91
    }
92

93
    public String getMinKey() {
94
      return head.next.set.iterator().next();
95
    }
96

97
  }