刷題記錄 -- 筆記文檔

Leetcode

序号	题目	状态	备注
1	Two Sum	完成	暴力破解， 哈希表
2	Add Two Numbers	完成	链表， 处理细节
3	Length Of Longest Substring	完成	滑动窗口，哈希表
4	Median of Two Sorted Arrays	完成	二分搜索，双指针
5	Longest palindromic Substring	完成	動態規劃、中心擴散、馬拉度
6	ZigZagContersion	完成

Question 1: Two Sum 参考题解 Optional C++

#include 
#include 

class Solution {
private:
    using VInt = std::vector;
    using UMIntInt = std::unordered_map;
    using UMIntIntIter = std::unordered_map>::iterator;
    struct WithHashTable {};
    struct WithEnumForce {};
public:
    Solution() = default;
    ~Solution() = default;

    static VInt twoSum(VInt& nums, int target) {
        return twoSumImpl(WithEnumForce(), nums, target);
    }
    static VInt twoSumImpl(WithEnumForce, VInt& nums, int target) {
        if (nums.size() < 2) return {};
        // FIXME: !!!static_cast(nums.size()) will loss some data!!!
        int n = static_cast(nums.size()), i = 0, j = 0;
        for (i = 0; i < n; ++i) 
            for (j = i + 1; j < n; ++j)
                if (target == nums[i] + nums[j]) 
                    return {i, j};
        return {};
    }
    static VInt twoSumImpl(WithHashTable, VInt& nums, int target) {
        UMIntInt hashtable;
        // FIXME: !!!static_cast(nums.size()) will loss some data!!!
        int n = static_cast(nums.size()), i = 0;
        for (i = 0; i < n; ++i) {
            UMIntIntIter it = hashtable.find(target - nums[i]);
            // auto it = hashtable.find(target - nums[i]);
            if (hashtable.end() != it) return {it->second, i};
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

Optional Rust

// Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
// 
// You may assume that each input would have exactly one solution, and you may not use the same element twice.
// 
// You can return the answer in any order.
// Example 1:
// 
//     Input: nums = [2,7,11,15], target = 9
//     Output: [0,1]
//     Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
//     Example 2:
// 
//     Input: nums = [3,2,4], target = 6
//     Output: [1,2]
//     Example 3:
// 
//     Input: nums = [3,3], target = 6
//     Output: [0,1]
trait SolutionMethod {
    fn two_sum(nums: Vec, target: i32) -> Vec;
}

struct WithEnumForce {}

impl SolutionMethod for WithEnumForce {
    fn two_sum(nums: Vec, target: i32) -> Vec {
        if nums.len() < 2 {
            return vec![];
        }
        let nums_size = nums.len();
        for i in 0..nums_size {
            for j in i + 1 .. nums_size {
                if target == nums[i] + nums[j] {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}

struct WithHastTable {}

impl SolutionMethod for WithHastTable {
    fn two_sum(nums: Vec, target: i32) -> Vec {
        if nums.len() < 2 {
            return vec![];
        }
        use std::collections::HashMap;
        let mut position = HashMap::new();
        for (i, num) in nums.iter().enumerate() {
            if position.contains_key(num)  {
                return vec![position[num] as i32, i as i32]
            } else {
                position.insert(target - num, i);
            }
        };
        vec![]
    }
}

pub struct Solution {}

impl Solution {
    pub fn two_sum(nums: Vec, target: i32) -> Vec {
        // ::two_sum(nums, target)
        ::two_sum(nums, target)
    }
}

#[cfg(test)]
mod question_1_leetcode_test {
    use super::Solution;
    #[test]
    fn test1() {
        assert_eq!(vec![0, 1], Solution::two_sum(vec![2, 7, 11, 15], 9i32));
    }
    #[test]
    fn test2() {
        assert_eq!(vec![1, 2], Solution::two_sum(vec![3, 2, 4], 6i32));
    }
    #[test]
    fn test3() {
        assert_eq!(vec![0, 1], Solution::two_sum(vec![3, 3], 6i32));
    }

}

Question 2: addTwoNumbers 参考代码 Optional C++

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
    struct Simulation {};
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addTwoNumberImpl(Simulation(), l1, l2);
    }

    ListNode* addTwoNumberImpl(Simulation, ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry > 0) tail->next = new ListNode(carry);
        return head;
    }
};

Optional Rust

// You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
//
// You may assume the two numbers do not contain any leading zero, except the number 0 itself.
// Example 1
//     Input: l1 = [2,4,3], l2 = [5,6,4]
//     Output: [7,0,8]
//     Explanation: 342 + 465 = 807.
// 
// Example 2:
//     Input: l1 = [0], l2 = [0]
//     Output: [0]
//     Example 3:
// 
// Example 3:
//     Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
//     Output: [8,9,9,9,0,0,0,1]
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
  #[inline]
  fn _new(val: i32, next: Option>) -> Self {
    ListNode {
      next,
      val
    }
  }
}
trait SolutionMethod {
    fn add_two_numbers_impl(l1: Option>, l2: Option>) -> Option>;
}

struct Simulation {}

impl SolutionMethod for Simulation {
    fn add_two_numbers_impl(l1: Option>, l2: Option>) -> Option> {
        let mut _l1 = l1;
        let mut _l2 = l2;
        let mut _head = Some(Box::new(ListNode::new(0)));
        let mut _tail = &mut _head;
        let mut _carry = 0;

        while _l1.is_some() || _l2.is_some() {
            match _tail {
                Some(_list_node) => {
                    let mut _1 = _l1.take().unwrap_or(Box::new(ListNode::new(0)));
                    let mut _2 = _l2.take().unwrap_or(Box::new(ListNode::new(0)));
                    let mut sum = _1.val + _2.val + _carry;
                    _carry = sum / 10; sum  = sum % 10;
                    _list_node.next.get_or_insert(Box::new(ListNode::new(sum)));
                    _tail = &mut _list_node.next;
                    // if _l1.is_some() { _l1 = _1.next; }
                    // if _l2.is_some() { _l2 = _2.next; }
                    _l1 = _1.next; _l2 = _2.next;
                },
                None => break,
            }
        }

        if _carry == 1 {
            if let Some(_carry_node) = _tail {
                _carry_node.next.get_or_insert(Box::new(ListNode::new(1)));
            }
        }
        _head.unwrap().next
    }
}

pub struct Solution {}

impl Solution {
    pub fn add_two_numbers(l1: Option>, l2: Option>) -> Option> {
        ::add_two_numbers_impl(l1, l2)
    }
}


#[cfg(test)]
mod question_2_leetcode_test {
    use super::*;
    #[test]
    fn test_question() {
        let mut _header1: Option> = None;
        let mut _header2: Option> = None;
        let mut _header3: Option> = None;
        let mut _item1 = &mut _header1;
        let mut _item2 = &mut _header2;
        let mut _item3 = &mut _header3;
        // [2 4 3] [5 6 4]
        _item1.insert(Box::new(ListNode::new(2)));
        _item1.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(4)));
        _item1.as_mut().unwrap().next.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(3)));

        _item2.insert(Box::new(ListNode::new(5)));
        _item2.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(6)));
        _item2.as_mut().unwrap().next.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(4)));


        _item3.insert(Box::new(ListNode::new(7)));
        _item3.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(0)));
        _item3.as_mut().unwrap().next.as_mut().unwrap().next.get_or_insert(Box::new(ListNode::new(8)));
        println!("List: 1       {:?}", _header1);
        println!("List: 2       {:?}", _header2);
        let l1 =  _header1; let l2 =  _header2;

        let ans = Solution::add_two_numbers(l1, l2);

        println!("List: expect  {:?}", _header3);
        println!("List: ans     {:?}", ans);
        assert_eq!(_header3, ans);
    }
}

Question 3: lengthOfLongestSubstring 参考代码 Optional C++

#include 
#include 

class Solution {
    struct WindowWithHashTable {};
    struct WindowWithArray {};
public:
    int lengthOfLongestSubstring(std::string s) {
        return lengthOfLongestSubstringImpl(WindowWithArray(), s);
    }
    int lengthOfLongestSubstringImpl(WindowWithHashTable, std::string &s) {
        int start(0), end(0), length(0), result(0);
        int s_size = s.size();
        std::unordered_map hashTable;
        while (end < s_size) {
            char tmp_char = s[end];
            if (hashTable.find(tmp_char) != hashTable.end() && hashTable[tmp_char] >= start) {
                start = hashTable[tmp_char] + 1;
                length = end - start;
            }
            hashTable[tmp_char] = end;
            end++;length++;
            result = std::max(result, length);
        }
        return result;

    }
    int lengthOfLongestSubstringImpl(WindowWithArray, std::string &s) {
        int start(0), end(0), length(0), result(0);
        int s_size = s.size();
        std::vector vec(128, -1);
        // FIXME: There is wrong in code [" ", 1, 0] in std::array
        // std::array arr = {0};
        while (end < s_size) {
            char tmp_char = s[end];
            if (! (vec[tmp_char] < start)) {
                start =  vec[tmp_char] + 1;
                length = end - start;
            }
            vec[tmp_char] = end;
            end++; length++;
            result = std::max(result, length);
        }
        return result;
    }
};

Optional Rust

// Given a string s, find the length of the longest substring without repeating characters.
// 
// Example 1:
// 
//     Input: s = "abcabcbb"
//     Output: 3
//     Explanation: The answer is "abc", with the length of 3.
// Example 2:
// 
//     Input: s = "bbbbb"
//     Output: 1
//     Explanation: The answer is "b", with the length of 1.
// Example 3:
// 
//     Input: s = "pwwkew"
//     Output: 3
//     Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

use std::collections::HashMap;

trait SolutionMethod {
    fn length_of_longest_substring_impl(s: String) -> i32;
}

struct WindowWithHashTable {}

impl SolutionMethod for WindowWithHashTable {
    fn length_of_longest_substring_impl(s: String) -> i32 {
        let mut _window = HashMap::new();
        let (mut start, mut res) = (0, 0);
        for (end, ch) in s.chars().enumerate() {
            if let Some(pos) = _window.get(&ch) {
                start = start.max(*pos);
            }
            res = res.max(end + 1 - start);
            _window.insert(ch, end+1);
        }
        res as i32
    }
}

struct WindowWithVec {}

impl SolutionMethod for WindowWithVec {
    fn length_of_longest_substring_impl(s: String) -> i32 {
        let (mut ret, mut l, mut cache) = (0, 0, vec![0; 128]); // There is a problem with cache.len()
        s.chars().enumerate().for_each(|(i, ch)| {
            l = l.max(cache[ch as usize]);
            ret = ret.max(i as i32 - l + 1);
            cache[ch as usize] = i as i32 + 1;
        });
        ret
    }
}


struct Solution {}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        ::length_of_longest_substring_impl(s)
    }
}

#[cfg(test)]
mod question_3_leetcode_test {
    use super::*;

    #[test]
    fn test_question() {
        assert_eq!(3i32, Solution::length_of_longest_substring("abcabcbb".into()));
        assert_eq!(1i32, Solution::length_of_longest_substring("bbbbb".into()));
        assert_eq!(3i32, Solution::length_of_longest_substring("pwwkew".into()));
    }

}

Question 4: medianOfTwoSortedArrays 参考代码 Optional C++

class Solution {
    struct BinarySearch {};
    struct DoublePointer {};
    static int get_k_th_element(const std::vector& nums1, const std::vector& nums2, int k) {
        

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return std::min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = std::min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = std::min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }
public:
    double findMedianSortedArrays(std::vector& nums1, std::vector& nums2) {
        return findMedianSortedArraysImpl(BinarySearch(), nums1, nums2);
    }
    double findMedianSortedArraysImpl(BinarySearch, std::vector& nums1, std::vector& nums2) {
                int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return get_k_th_element(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (get_k_th_element(nums1, nums2, totalLength / 2) + get_k_th_element(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
    double findMedianSortedArraysImpl(DoublePointer, std::vector& nums1, std::vector& nums2) {
        int m = nums1.size(), n = nums2.size(), i = 0, j = 0, p = 0, q = 0, _ = 0;
        int len = n + m;
    Loop:
        if (! (((_) << 1) < len + 1) ) goto End; p = q;
        if (i < m && (j >= n || nums1[i] < nums2[j])) {
            q = nums1[i]; ++i;
        } else {
            q = nums2[j]; ++j;
        }
        ++_; goto Loop;
    End:
        return(len & 1) ? q : (p + q) / 2.0;
    }
};

Optional Rust

// Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
// 
// The overall run time complexity should be O(log (m+n)).
// 
// Example 1:
// 
//     Input: nums1 = [1,3], nums2 = [2]
//     Output: 2.00000
//     Explanation: merged array = [1,2,3] and median is 2.
// Example 2:
// 
//     Input: nums1 = [1,2], nums2 = [3,4]
//     Output: 2.50000
//     Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
use std::cmp::min;

trait SolutionMethod {
    fn find_median_sorted_arrays_impl(nums1: Vec, nums2: Vec) -> f64;
}

struct Abandon {}

impl SolutionMethod for Abandon {
    fn find_median_sorted_arrays_impl(nums1: Vec, nums2: Vec) -> f64 {
        let mut nums1 = nums1;
        let mut nums2 = nums2;
        nums1.append(&mut nums2);
        nums1.sort();
        let len = nums1.len();
        if len <= 1 {
            return nums1[0] as f64 ;
        }
        match len % 2 {
            1 => nums1[len/2] as f64,
            0 => (nums1[len/2]+nums1[len/2-1]) as f64/2.0,
            _ => 0.0f64,
        }
    }
}


struct BinarySearch {}

impl BinarySearch {
    fn find_k(v1: &Vec, i: usize, v2: &Vec, j: usize, k: usize) -> i32 {
    // 当nums1 删除完，则直接返回j+k-1位置的数字，nums2删完同理
        if i >= v1.len() {
            return v2[j + k - 1]
        }
        if j >= v2.len() {
            return v1[i + k - 1]
        }
        // k==1时表示找最小的数字
        if k == 1 {
            return min(v1[i], v2[j]);
        }
        let max1 = if (i + k/2 - 1) < v1.len() { v1[i + k/2 - 1] } else { i32::MAX };
        let max2 = if (j + k/2 - 1) < v2.len() { v2[j + k/2 - 1] } else { i32::MAX };
        if max1 > max2 {
            Self::find_k(v1, i, v2, j + k / 2, k - k / 2)
        } else {
            Self::find_k(v1, i + k / 2, v2, j, k - k / 2)
        }
    }
}

impl SolutionMethod for BinarySearch {
    fn find_median_sorted_arrays_impl(nums1: Vec, nums2: Vec) -> f64 {
        let min_left = (nums1.len() + nums2.len() + 1) / 2;
        let min_right = (nums1.len() + nums2.len() + 2) / 2;
        (Self::find_k(&nums1, 0, &nums2, 0, min_left) + Self::find_k(&nums1, 0, &nums2, 0, min_right)) as f64 / 2.0
    }
}

struct DoublePointer {}

impl SolutionMethod for DoublePointer {
    fn find_median_sorted_arrays_impl(nums1: Vec, nums2: Vec) -> f64 {
        let m = nums1.len();
        let n = nums2.len();
        let len = m + n;

        let mut i: usize = 0; let mut j: usize = 0;
        let mut p = 0i32; let mut q = 0i32;

        for _ in 0..len / 2 + 1 {
            p = q;
            if i < m && (j >= n || nums1[i] < nums2[j]) {
                q = nums1[i]; i += 1;
            } else {
                q = nums2[j]; j += 1;
            }
        }

        if len & 1 == 0 { (p + q) as f64 / 2.0 } else { q as f64 }
    }
}

pub struct Solution {}

impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec, nums2: Vec) -> f64 {
        ::find_median_sorted_arrays_impl(nums1, nums2)
    }
}

#[cfg(test)]
mod question_4_leetcode_test {
    use super::*;
    #[test]
    fn test_question() {
        let ans = Solution::find_median_sorted_arrays(vec![1, 2], vec![3, 4]);
        assert_eq!(ans, 2.50000);
    }
}

Question 5: longestPalindrome 參考代碼 Optional C++

class Solution {
    struct DynamicProgramming {};
    struct CenterDiffusion {};
    std::pair expandAroundCenter(const std::string& s, int left, int right) {
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                --left;
                ++right;
            }
            return {left + 1, right - 1};
        }
    struct Manacher {};
    int expand(const std::string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }
public:
    std::string longestPalindromeImpl(DynamicProgramming, std::string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        std::vector> dp(n, std::vector(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
    std::string longestPalindromeImpl(CenterDiffusion, std::string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
    std::string longestPalindromeImpl(Manacher, std::string s) {
        int start = 0, end = -1;
        std::string t = "#";
        for (char c: s) {
            t += c;
            t += '#';
        }
        t += '#';
        s = t;

        std::vector arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = std::min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        std::string ans;
        for (int i = start; i <= end; ++i) {
            if (s[i] != '#') {
                ans += s[i];
            }
        }
        return ans;
    }
    std::string longestPalindrome(std::string s) {
        return longestPalindromeImpl(DynamicProgramming(), s);
    }
};

Optional Rust

// Given a string s, return the longest palindromic substring in s.
// 
// Example 1:
// 
//     Input: s = "babad"
//     Output: "bab"
//     Explanation: "aba" is also a valid answer.
// Example 2:
// 
//     Input: s = "cbbd"
//     Output: "bb"
trait SolutionMethod {
    fn longest_palindrome_impl(s: String) -> String;
}

struct DynamicProgramming {}

impl SolutionMethod for DynamicProgramming {
    fn longest_palindrome_impl(s: String) -> String {
        let arr: Vec = s.chars().collect();
        let mut start_idx = 0usize;
        let mut max = 1usize;
        let count = s.chars().count();
        // 初始化dp的是时候，就插入表示 每个位置的单个字符就是回文
        let mut dp: Vec> = (0..count).map(|_| { vec![false; count] }).collect();
        for size in 2..=count {
            for i in 0..count {
                let j = size + i - 1;
                if j >= count {
                    break;
                }
                if arr[i] == arr[j] {
                    if size >= 4 {
                        dp[i][j] = dp[i + 1][j - 1];
                    } else {
                        dp[i][j] = true;
                    }
                } else {
                    dp[i][j] = false;
                }
                if dp[i][j] && size > max {
                    max = size;
                    start_idx = i;
                }
            }
        }
        arr.iter().enumerate()
            .filter(|&(i, _)| i >= start_idx && i < start_idx + max)
            .map(|(_, v)| v)
            .collect()
    }
}


struct Manacher {}

impl Manacher {
    fn check(s: &Vec, mut lt: usize, mut rt: usize) -> usize {
        while rt < s.len() && s[lt] == s[rt] {
            if lt == 0 {
                return rt - lt + 1;
            }
            lt -= 1;
            rt += 1;
        }
        rt - lt - 1 // (rt - 1) - (lt + 1) + 1 = rt - lt - 1
    }
}

impl SolutionMethod for Manacher {
    fn longest_palindrome_impl(s: String) -> String {
        let mut start_idx = 0;
        let mut max_len = 1;
        let mut arr_chars = vec!['#'];
        for c in s.chars() {
            arr_chars.push(c);
            arr_chars.push('#');
        }
        let len =  arr_chars.len();
        let mut center = 0;
        let mut r = 0;
        let mut r_arr = vec![0; len];
        for i in 0..len {
            let tmp_len = if i < center + r {
                let tmp_dis = (center + r - i).min(r_arr[2 * center - i]);
                Self::check(&arr_chars, i - tmp_dis - 1, i + tmp_dis + 1)
            } else {
                Self::check(&arr_chars, i, i)
            };
            let tmp_r = (tmp_len - 1) / 2; // get radis
            r_arr[i] = tmp_r;

            if tmp_len > max_len {
                max_len = tmp_len;
                start_idx = i - (tmp_len - 1) / 2;
            }
            // set center and r 
            if i + tmp_r + 1 > center + r {
                center = i;
                r = tmp_r;
            }
        }
        arr_chars.iter().enumerate()
            .filter(|&(i, _)| i >= start_idx && i < start_idx + max_len && i & 1 != 0)
            .map(|(_, v)| v)
            .collect()
    }
}

struct CenterDiffusion {}

impl CenterDiffusion {}

impl CenterDiffusion {
    fn check(s: &Vec, mut lt: usize, mut rt: usize) -> (usize, usize) {
        while rt < s.len() && s[lt] == s[rt] {
            if lt == 0 {
                return (0, rt + 1)
            }
            lt -= 1;
            rt += 1;
        }
        (lt + 1, rt - lt - 1)
    }
}

impl SolutionMethod for CenterDiffusion {
    fn longest_palindrome_impl(s: String) -> String {
        let arr: Vec = s.chars().collect();
    let (mut start_idx, mut max) = (0, 1);
    for i in 0..arr.len() {
        let (start1, len1) = Self::check(&arr, i, i);
        let (start2, len2) = Self::check(&arr, i, i + 1);
        if len2 > len1 {
            if len2 > max {
                start_idx = start2;
                max = len2;
            } 
        } else {
            if len1 > max {
                start_idx = start1;
                max = len1;
            }
        }
    }
    arr.iter().enumerate()
        .filter(|&(i, _)| i >= start_idx && i < start_idx + max)
        .map(|(_, v)| v)
        .collect()
    }
}

pub struct Solution {}

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        ::longest_palindrome_impl(s)
    }
}

#[cfg(test)]
mod question_5_leetcode_test {
    use super::*;
    #[test]
    fn test_question() {
        assert_eq!("bab".to_string(), Solution::longest_palindrome("babad".to_string()));
        assert_eq!("bb".to_string(), Solution::longest_palindrome("cbbd".to_string()));
    }
}

Question 6: ZigZagConversion 參考代碼 Optional C++

class Solution {
    struct MatrixSimulation {};
    struct MatrixCompression {};
    struct Construction {};
public:
    std::string convertImpl(MatrixSimulation, std::string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        int t = r * 2 - 2;
        int c = (n + t - 1) / t * (r - 1);
        std::vector mat(r, std::string(c, 0));
        for (int i = 0, x = 0, y = 0; i < n; ++i) {
            mat[x][y] = s[i];
            if (i % t < r - 1) {
                ++x; // 向下移动
            } else {
                --x;
                ++y; // 向右上移动
            }
        }
        std::string ans;
        for (auto &row : mat) {
            for (char ch : row) {
                if (ch) {
                    ans += ch;
                }
            }
        }
        return ans;
    }
    std::string convertImpl(MatrixCompression, std::string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        std::vector mat(r);
        for (int i = 0, x = 0, t = r * 2 - 2; i < n; ++i) {
            mat[x] += s[i];
            i % t < r - 1 ? ++x : --x;
        }
        std::string ans;
        for (auto &row : mat) {
            ans += row;
        }
        return ans;
    }
    std::string convertImpl(Construction, std::string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        std::string ans;
        int t = r * 2 - 2;
        for (int i = 0; i < r; ++i) { // 枚举矩阵的行
            for (int j = 0; j + i < n; j += t) { // 枚举每个周期的起始下标
                ans += s[j + i]; // 当前周期的第一个字符
                if (0 < i && i < r - 1 && j + t - i < n) {
                    ans += s[j + t - i]; // 当前周期的第二个字符
                }
            }
        }
        return ans;
    }
    std::string convert(std::string s, int numRows) {
        return convertImpl(MatrixSimulation(), s, numRows);
    }
};

Optional Rust

// The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
// 
// P   A   H   N
// A P L S I I G
// Y   I   R
// And then read line by line: "PAHNAPLSIIGYIR"
// 
// Write the code that will take a string and make this conversion given a number of rows:
// 
// string convert(string s, int numRows);
//  
// 
// Example 1:
// 
//     Input: s = "PAYPALISHIRING", numRows = 3
//     Output: "PAHNAPLSIIGYIR"
// Example 2:
// 
//     Input: s = "PAYPALISHIRING", numRows = 4
//     Output: "PINALSIGYAHRPI"
//     Explanation:
//     P     I    N
//     A   L S  I G
//     Y A   H R
//     P     I
// Example 3:
// 
//     Input: s = "A", numRows = 1
//     Output: "A"
trait SolutionMethod {
    fn convert_impl(s: String, num_rows: i32) -> String;
}

struct MatrixSimulation {}

impl SolutionMethod for MatrixSimulation {
    fn convert_impl(s: String, num_rows: i32) -> String {
        // 为什么输入类型总是i32
        let num_rows = num_rows as usize;
        // 每行一个String
        let mut rows = vec![String::new(); num_rows];
        // z字形往复的迭代器，01232101232......
        let iter = (0..num_rows).chain((1..num_rows-1).rev()).cycle();
        // 按迭代器给出的下标访问对应行，推入字符
        iter.zip(s.chars()).for_each(|(i, c)| rows[i].push(c));
        // collect连接每行
        rows.into_iter().collect()
    }
}
struct MatrixCompression {}

impl SolutionMethod for MatrixCompression {
    fn convert_impl(s: String, num_rows: i32) -> String {
        let (n, r) = (s.len(), num_rows as usize);
        if r == 1 || r >= n {
            return s;
        }

        s.chars()
            .collect::>()
            .iter()
            .enumerate()
            .fold((vec![String::new(); r], 0), |(mut mat, mut x), (i, ch)| {
                mat.get_mut(x).unwrap_or(&mut String::new()).push(*ch);
                if i % (r * 2 - 2) < r - 1 {
                    x += 1;
                } else {
                    x -= 1;
                }
                (mat, x)
            })
            .0
            .join("")
    }
}

struct Construction {}

impl SolutionMethod for Construction {
    fn convert_impl(s: String, num_rows: i32) -> String {
        let (n, r) = (s.len(), num_rows as usize);
        if r == 1 || r >= n {
            return s;
        }

        let s = s.chars().collect::>();
        let mut ans = String::new();
        for i in 0..r {
            for j in (0..n - i).step_by(r * 2 - 2) {
                ans.push(s[j + i]);
                if 0 < i && i < r - 1 && j + (r * 2 - 2) - i < n {
                    ans.push(s[j + (r * 2 - 2) - i]);
                }
            }
        }
        ans
    }
}


struct Solution {}


impl Solution {
    pub fn convert(s: String, num_rows: i32) -> String {
        ::convert_impl(s, num_rows)
    }
}

CCF CSP

• 开始之前的一些说明
  • 只是刷题记录
  • 所有题目的提交链接，都需要登入到CCF CSP，因为都是模拟考试，需要账号登录的

辅助代码的参考

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#define DO_PRAGMA(x) _Pragma (#x)
#define TODO(x) DO_PRAGMA(message ("TODO - " #x))

#include 
#include 
#include 
#include 

int main(int argc, char const *argv[]) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    char *str = (char*)malloc(2 * sizeof(char)); memset(str, 0, sizeof(char)); 
    // char str[32]; memset(str, 0, sizeof(char));
    printf("the size of str: %ldn", sizeof(str));
    scanf("%2[^abcd]", str); scanf("%*c");
    printf("str = %sn", str);
    free(str);
    return 0;
}

2021年12月 赛题 第一题 202112-1 序列查询

题目提交链接 这题是真的简单 

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#include 

#define BUFFSIZE (int)10e7

int item[BUFFSIZE], partial_sum[BUFFSIZE];

int main(int argc, const char **argv) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
	int a = 0, n = 0, N = 0, i = 0, _sum= 0;
	scanf("%d%d", &n, &N);scanf("%*c");
	for (i = 0; i < n; ++i) {
		scanf("%d", &a);scanf("%*c");
		item[a]++;
	}
	for (i = 0; i < N - 1; ++i) {
		partial_sum[i + 1] = partial_sum[i] + item[i + 1];
		_sum += partial_sum[i + 1];
	}
	printf("%d", _sum);
	return 0;
}

第二题 序列查询新解 第三题 登机牌条码 第四题 磁盘文件操作 极差路径 2021年09月 赛题 第一题 202109-1 数组推导

题目提交链接 这题是真的简单 

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#include 
#include 

int main(int argc, const char **argv) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
	int n = 0,  max = 0, min = 0, i = 0, b[100]; 
	memset(b, 0, sizeof(int));
  	scanf("%d", &n);scanf("%*c");
	for(i=0; i scanf("%d", &b[i]);scanf("%*c"); }
	max = min = b[0];
	for(i=1; i
		max += b[i]; if(b[i]>b[i-1]) min += b[i];
	}
	printf("%dn%d", max, min);
	return 0;
}

第二题 202109-2 非零段划分

题目提交链接 这题挺复杂的，要那分的话 

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")
#include 

#define N (int)5e5+5
#define M (int)1e4+1
#define _max(a,b) ((a) > (b) ? (a): (b))

int main(int argc, const char **argv) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    int n = 0, sum = 0, phrase = 0, i = 0, a[N], cnt[N]; // 整数个数，段数
    scanf("%d", &n); scanf("%*c");
    for(i = 1; i <= n; i++) {
        scanf("%d", &a[i]); scanf("%*c");
        if(a[i] > a[i-1]) { //差分，p取a[i-1]+1~a[i]的非零段数量加一
            cnt[a[i-1]+1]++; cnt[a[i]+1]--;
        }
    }
 
    for(i = 1; i < M; i++) {
        sum += cnt[i]; phrase = _max(phrase, sum);
    }
 
    printf("%dn", phrase);
    return 0;
}

第三题 202109-3 脉冲神经网络

题目提交链接 五味杂陈 

注意: 提交测试的时候，如果太多的变量定义在局部栈中，可能会出现栈内存申请不足的情况，最好定义在全局的变量中，虽然让人十分难受，但是现在可能能力不足，无法改善这个问题。

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#include 
#include 

#define N  2010
#define INF 1e8
#define _max(a, b) ({(a) > (b) ? (a): (b);})
#define _min(a, b) ({(a) > (b) ? (b): (a);})
#define _rand() ({ _next = _next * 1103515245 + 12345; (unsigned)(_next/65536) % 32768;})
#define add(a,b,c,d) do {e[idx] = (b), W[idx] = (c), D[idx] = (d), ne[idx] = h[(a)], h[(a)] = idx++ ;} while(0)

int n = 0, s = 0, p = 0, T = 0, i = 0, j = 0, k = 0, idx = 0, mod = 0, minc = (int)INF, maxc = (int)-INF, h[N], e[N], D[N], ne[N], r[N], cnt[N];
double dt = 0.0, minv = INF, maxv = -INF, W[N], v[N], u[N], a[N], b[N], c[N], d[N], I[1<<10][N>>1];
static unsigned long _next = 1;

int main(int argc, const char **argv) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    memset(h, -1, sizeof(h));
    scanf("%d%d%d%d%lf", &n, &s, &p, &T,&dt); scanf("%*c");
    for (i = 0; i < n;) {
        int rn; scanf("%d", &rn); scanf("%*c");
        double vv, uu, aa, bb, cc, dd;
        scanf("%lf%lf%lf%lf%lf%lf", &vv, &uu, &aa, &bb, &cc, &dd); scanf("%*c");
        for (j = 0; j < rn; j++, i++ ) {
            v[i] = vv, u[i] = uu, a[i] = aa, b[i] = bb, c[i] = cc, d[i] = dd;
        }
    }

    for (i = n; i < n + p; i++ ) {scanf("%d", &r[i]); scanf("%*c");}

    while (s--) {
        int a = 0, b = 0, d = 0;
        double c;
        scanf("%d%d%lf%d", &a, &b, &c, &d); scanf("%*c");
        add(a, b, c, d);
        mod = _max(mod, d + 1);
    }

    for (i = 0; i < T; i++ ) {
        int t = i % mod;
        for (j = n; j < n + p; j++ )
            if (r[j] > _rand()) {
                for (k = h[j]; ~k; k = ne[k]) {
                    int x = e[k];
                    I[(t + D[k]) % mod][x] += W[k];
                }
            }

        for (j = 0; j < n; j++ ) {
            double vv = v[j], uu = u[j];
            v[j] = vv + dt * (0.04 * vv * vv + 5 * vv + 140 - uu) + I[t][j];
            u[j] = uu + dt * a[j] * (b[j] * vv - uu);

            if (v[j] >= 30) {
                for (k = h[j]; ~k; k = ne[k]) {
                    int x = e[k];
                    I[(t + D[k]) % mod][x] += W[k];
                }
                cnt[j]++ ;
                v[j] = c[j], u[j] += d[j];
            }
        }
        memset(I[t], 0, sizeof(I[t]));
    }

    for (i = 0; i < n; i++ ) {
        minv = _min(minv, v[i]);
        maxv = _max(maxv, v[i]);
        minc = _min(minc, cnt[i]);
        maxc = _max(maxc, cnt[i]);
    }

    printf("%.3lf %.3lfn", minv, maxv); printf("%d %dn", minc, maxc);
    return 0;
}

第四题 202109-4 收集卡牌

题目提交链接 

#pragma GCC POSITION goto

#pragma GCC optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#include 

#define N 16

double dp[1<
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    int n = 0, k = 0, i = 0, j = 0, l = 0; scanf("%d%d", &n, &k); scanf("%*c");
    for(i=0; i scanf("%lf", &p[i]); scanf("%*c"); }
    dp[(1< -1; i--){
    	for(j = k*n; j > -1; j--) {
	    	for(l = 0; l < n; l++) {
	    		if((i >> l) & 1) dp[i][j] += dp[i][j+1] * p[l];
	    		else dp[i][j] += dp[i | (1 << l)][j] * p[l];
			}
			dp[i][j] += 1;
			int cnt = n;
			for(l = 0; l < n; l++) if((i >> l) & 1) cnt--;
			if(j >= (cnt * k)) dp[i][j] = 0;
		}
	}
    printf("%.10lfn",dp[0][0]);
	return 0;
}

第五题 202109-5 箱根山岳险天下

题目提交链接  难，真的太难了 

为什么这题 宏函数 会出现 Segmention fault

#pragma G++ POSITION goto

#pragma G++ optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#define DO_PRAGMA(x) _Pragma (#x)
#define TODO(x) DO_PRAGMA(message ("TODO - " #x))

#include 
#include 
#include 
#include 

#define maxn (int)3e5+10
#define ls ch[x][0]
#define rs ch[x][1]

#define getch(x) ({ch[fa[x]][1] == x;})
#define isRoot(x) ({ch[fa[x]][0] != x && ch[fa[x]][1] != x;})
#define _swap(a,b) do {
    void* _tmp = malloc(sizeof((a)));
    memcpy(_tmp, &a, sizeof(a)); (a) = (b); memcpy(&b, _tmp, sizeof(a));
    free(_tmp);
} while(0)
#define pushdownRev(x) do { _swap(ls, rs); lazy_rev[(x)] ^= 1; } while(0)
#define pushdownMul(x,v) do {
    val[(x)] = ( val[(x)] * (v) ) % mod;
    sum[(x)] = (sum[(x)] * (v)) % mod;
    lazy_mul[(x)] = (lazy_mul[(x)] * (v)) % mod;
} while(0)
#define pushdown(x) do {
    if (lazy_rev[(x)]) {
        if (ls) pushdownRev(ls);
        if (rs) pushdownRev(rs);
        lazy_rev[(x)] ^= 1;
    }
    if (lazy_mul[(x)] != 1) {
        if (ls) pushdownMul(ls, lazy_mul[(x)]);
        if (rs) pushdownMul(rs, lazy_mul[(x)]);
        lazy_mul[x] = 1;
    }
} while(0)

#define pushup(x) do { sum[(x)] = (sum[ls] + sum[rs] + val[(x)]) % mod; } while(0)

#define rotate(x) do {
    int _y = fa[(x)], _z = fa[_y], _chk = getch((x)), _w = ch[(x)][_chk ^ 1];
    if (!isRoot(_y)) ch[_z][getch(_y)] = (x);
    ch[(x)][_chk ^ 1] = _y;
    ch[_y][_chk] = _w;
    if (_w) fa[_w] = _y;
    fa[_y] = (x), fa[(x)] = _z;
    pushup(_y);
} while(0)

#define splay(x) do {
    int _top = 0, _y = (x);
    st[++_top] = _y;
    while (!isRoot(_y)) {
        _y = fa[_y];
        st[++_top] = _y;
    }
    while (_top) pushdown(st[_top--]);
    while (!isRoot((x))) {
        _y = fa[(x)];
        if (!isRoot(_y)) rotate(getch((x)) == getch(_y) ? _y : (x));
        rotate(x);
    }
    pushup((x));
} while(0)

#define access(x) do {
    int _y = 0;
    for (_y = 0; (x); (x) = fa[_y = (x)]) {
        splay(x);
        rs = _y;
        pushup((x));
    }
} while(0)

#define makeRoot(x) do {
    access((x));
    splay((x));
    pushdownRev((x));
} while(0)

#define split(x,y) do {
    makeRoot((x));
    access((y));
    splay((y));
} while(0)

#define link(x,y) do {
    makeRoot((x));
    fa[(x)] = (y);
} while(0);

#define insertPlayer(day,v) do {
    ++tot;
    player[tot] = {(day), (cur)};
    ranklist[cur_rank].push_back(tot);
    val[tot] = sum[tot] = (v);
    lazy_mul[tot] = 1;
    lazy_rev[tot] = 0;
    if (cur) link(tot, cur);
    cur = tot;
} while(0)

#define findPlayer(_day,rk) ({
    int _l = 0, _r = ranklist[(rk)].size() - 1, _mid = 0, _ans = 0;
    while (_l <= _r) {
        _mid = (_l + _r) >> 1;
        if (player[ranklist[(rk)][(_mid)]].day <= (_day)) {
            _ans = _mid;
            _l = _mid + 1;
        } else {
            _r = _mid - 1;
        }
    }
    ranklist[(rk)][_ans];
})


struct {int day, fa;} player[maxn];


int m = 0, T = 0, cur = 0, cur_rank = 0, tot = 0, opt = 0, s = 0, l = 0, r = 0, x = 0, y = 0, A = 0, st[maxn], ch[maxn][2], fa[maxn], lazy_rev[maxn];
long long mod = 0, val[maxn], sum[maxn], lazy_mul[maxn];
std::vector ranklist[maxn];

int main(int argc, const char **argv) {
    TODO(這題是錯的，代碼不能通過，會出現Segmentation fault)
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    scanf("%d%lld%d", &m, &mod, &T); scanf("%*c");
    for (int day = 1; day <= m; ++day) {
        scanf("%d", &opt); scanf("%*c");
        if (opt == 1) {
            scanf("%d", &x); scanf("%*c");
            if (T == 1)
                x ^= A;
            if (x == 0) {
                cur = player[cur].fa;
                --cur_rank;
            } else {
                insertPlayer(day, x);
            }
        } else if (opt == 2) {
            scanf("%d%d%d%d", &s, &l, &r, &y); scanf("%*c");
            if (T == 1)
                y ^= A;
            l = findPlayer(s, l);
            r = findPlayer(s, r);
            split(l, r);
            pushdownMul(r, y);
        } else {
            scanf("%d%d%d", &s, &l, &r); scanf("%*c");
            l = findPlayer(s, l);
            r = findPlayer(s, r);
            split(l, r);
            A = sum[r];
            printf("%dn", A);
        }
    }
}

参考的代码

#pragma G++ POSITION goto

#pragma G++ optimize(2)

// #pragma GCC optimize(3,"Ofast","inline")

#define DO_PRAGMA(x) _Pragma (#x)
#define TODO(x) DO_PRAGMA(message ("TODO - " #x))

#include 
#include 
#include 
#include 

#define maxn (int)3e5+10

struct { int day, fa; } player[maxn];
int m = 0, T = 0, cur = 0, cur_rank = 0, tot = 0, opt = 0, s = 0, l = 0, r = 0, x = 0, y = 0, A = 0,
    st[maxn], ch[maxn][2], fa[maxn], lazy_rev[maxn];
long long mod = 0, val[maxn], sum[maxn], lazy_mul[maxn];
std::vector ranklist[maxn];

#define getch(x) ({ch[fa[(x)]][1] == (x);})
#define isRoot(x) ({ch[fa[(x)]][0] != (x) && ch[fa[(x)]][1] != (x);})
#define swap(a,b) do {(a) ^= (b) ^= (a) ^= (b); } while(0)

void pushdownRev(int x) {
    // 执行翻转操作
    swap(ch[x][0], ch[x][1]);
    lazy_rev[x] ^= 1;
}
void pushdownMul(int x, long long v) {
    // 执行区间乘操作
    val[x] = (val[x] * v) % mod;
    sum[x] = (sum[x] * v) % mod;
    lazy_mul[x] = (lazy_mul[x] * v) % mod;
}
void pushdown(int x) {
    // 下传懒惰标记
    if (lazy_rev[x]) {
        if (ch[x][0]) pushdownRev(ch[x][0]);
        if (ch[x][1]) pushdownRev(ch[x][1]);
        lazy_rev[x] ^= 1;
    }
    if (lazy_mul[x] != 1) {
        if (ch[x][0]) pushdownMul(ch[x][0], lazy_mul[x]);
        if (ch[x][1]) pushdownMul(ch[x][1], lazy_mul[x]);
        lazy_mul[x] = 1;
    }
}
void pushup(int x) {
    // 更新状态 (maintain)
    sum[x] = (sum[ch[x][0]] + sum[ch[x][1]] + val[x]) % mod;
}
void rotate(int x) {
    // splay 旋转操作
    int y = fa[x], z = fa[y], chk = getch(x), w = ch[x][chk ^ 1];
    if (!isRoot(y)) ch[z][getch(y)] = x;
    ch[x][chk ^ 1] = y; ch[y][chk] = w;
    if (w) fa[w] = y;
    fa[y] = x, fa[x] = z;
    pushup(y);
}
void splay(int x) {
    // 将目前结点旋转到所在 splay 的根
    int top = 0, y = x;
    st[++top] = y;
    while (!isRoot(y)) {
        y = fa[y]; st[++top] = y;
    }
    while (top) pushdown(st[top--]);
    while (!isRoot(x)) {
        y = fa[x];
        if (!isRoot(y)) rotate(getch(x) == getch(y) ? y : x);
        rotate(x);
    }
    pushup(x);
}
void access(int x) {
    // 开辟一条只含有原树的根到 x 的路径结点的实链
    for (int y = 0; x; x = fa[y = x]) {
        splay(x);
        ch[x][1] = y;
        pushup(x);
    }
}
void makeRoot(int x) {
    // 让 x 称为原树的根
    access(x);  splay(x); pushdownRev(x);
}
void split(int x, int y) {
    // 开辟一条只含有 x 到 y 路径结点的实链，y 为 splay 的根
    makeRoot(x); access(y); splay(y);
}
void link(int x, int y) {
    // 连接两个部分
    makeRoot(x); fa[x] = y;
}
void insertPlayer(int day, long long v) {
    // 加入新队员
    ++tot;
    // 对原树进行操作
    player[tot] = { day, cur };
    ++cur_rank;
    ranklist[cur_rank].push_back(tot);
    // 对辅助树进行操作
    val[tot] = sum[tot] = v;
    lazy_mul[tot] = 1;
    lazy_rev[tot] = 0;
    // 如果目前队伍有人，则加入队伍
    if (cur) link(tot, cur);
    cur = tot;
}
int findPlayer(int day, int rk) {
    // 查找在第 day 天排名 rk 的队员编号
    int l = 0, r = ranklist[rk].size() - 1, mid, ans = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (player[ranklist[rk][mid]].day <= day) {
            ans = mid; l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ranklist[rk][ans];
}


int main(int argc, const char **argv) {
#ifndef ONLINE_DEBUG
    freopen("input.data", "r", stdin);
    freopen("output.data", "w", stdout);
#endif
    scanf("%d%lld%d", &m, &mod, &T); scanf("%*c");
    for (int day = 1; day <= m; ++day) {
        scanf("%d", &opt); scanf("%*c");
        if (opt == 1) {
            scanf("%d", &x); scanf("%*c");
            if (T == 1) x ^= A;
            if (x == 0) {
                cur = player[cur].fa; --cur_rank;
            } else insertPlayer(day, x);
        } else if (opt == 2) {
            scanf("%d%d%d%d", &s, &l, &r, &y); scanf("%*c");
            if (T == 1) y ^= A;
            l = findPlayer(s, l);
            r = findPlayer(s, r);
            split(l, r);
            pushdownMul(r, y);
        } else {
            scanf("%d%d%d", &s, &l, &r); scanf("%*c");
            l = findPlayer(s, l); r = findPlayer(s, r);
            split(l, r); A = sum[r]; printf("%dn", A);
        }
    }
    return 0;
}