#1083936 (C++17) No.1020 Reverse

• 問題: No.1020 Reverse
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:10:02
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 144 ms / 2,000 ms
• コード長: 7,054 bytes
• コンパイル時間: 955 ms
• コンパイル使用メモリ: 107,616 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2025-05-14 13:11:18
• 合計ジャッジ時間: 3,080 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 15

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <random> // Required for std::mt19937 and std::random_device
#include <chrono> // For a better seed based on time

// Use Mersenne Twister for generating priorities. Provides better randomness than rand().
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

// Define the Node structure for the Treap
struct Node {
    char key; // The character stored in this node
    unsigned int priority; // Random priority for maintaining heap property
    int size; // Size of the subtree rooted at this node (number of nodes)
    bool reversed; // Lazy propagation flag for reversal operation
    Node *l, *r; // Pointers to left and right children

    // Constructor for creating a new node
    Node(char k) : key(k), priority(rng()), size(1), reversed(false), l(nullptr), r(nullptr) {}
    
    // Destructor (optional, generally omitted in competitive programming for speed)
    // ~Node() { delete l; delete r; } 
};

// Helper function to get the size of a subtree (handles nullptr case)
int get_size(Node* t) {
    return t ? t->size : 0;
}

// Updates the size of node 't' based on the sizes of its children
void update_size(Node* t) {
    if (t) {
        t->size = get_size(t->l) + get_size(t->r) + 1;
    }
}

// Pushes the lazy 'reversed' tag down to children
// This function must be called before accessing children of a node potentially marked as reversed
void push(Node* t) {
    if (t && t->reversed) {
        t->reversed = false; // Clear the flag on the current node
        std::swap(t->l, t->r); // Swap children pointers physically reverses the order
        // Propagate the reversed state to children by toggling their flags
        if (t->l) t->l->reversed ^= true; 
        if (t->r) t->r->reversed ^= true;
    }
}

// Splits the Treap 't' into two Treaps 'l' and 'r'.
// 'l' will contain the first 'k' elements of the sequence represented by 't'.
// 'r' will contain the remaining elements.
// 'k' is the count of elements for the left part.
void split(Node* t, Node*& l, Node*& r, int k) {
    // Base case: If the treap is empty, both resulting treaps are empty.
    if (!t) {
        l = r = nullptr;
        return;
    }
    
    push(t); // Process lazy tags before operating on the node or its children.
    
    int left_size = get_size(t->l); // Get the size of the left subtree

    // Determine if the split point is in the left or right subtree
    if (k <= left_size) { 
        // Split point is within the left subtree.
        // The current node 't' and its right subtree belong to the right part 'r'.
        split(t->l, l, t->l, k); // Recursively split the left child. The resulting left part is 'l', right part updates t->l.
        r = t; 
    } else {
        // Split point is within the right subtree.
        // The current node 't' and its left subtree belong to the left part 'l'.
        // Adjust 'k' for the recursive call on the right subtree: need k - left_size - 1 elements from it.
        split(t->r, t->r, r, k - left_size - 1); 
        l = t; 
    }
    update_size(t); // Update the size of 't' after potential structural changes.
}

// Merges two Treaps 'l' and 'r' into a single Treap 't'.
// Assumes that all keys (implicitly, indices) in 'l' are less than all keys in 'r'.
void merge(Node*& t, Node* l, Node* r) {
    push(l); // Process lazy tags before merging.
    push(r);
    
    // Base case: If one treap is empty, the result is the other treap.
    if (!l || !r) {
        t = l ? l : r;
    } else if (l->priority > r->priority) { 
        // If 'l' has higher priority, it becomes the root.
        // Recursively merge 'r' into the right subtree of 'l'.
        merge(l->r, l->r, r);
        t = l;
    } else {
        // If 'r' has higher priority (or equal), it becomes the root.
        // Recursively merge 'l' into the left subtree of 'r'.
        merge(r->l, l, r->l);
        t = r;
    }
    update_size(t); // Update the size of the resulting root 't'.
}

// Performs an inorder traversal of the Treap 't' and appends characters to 'res' string.
// This reconstructs the string represented by the Treap.
void inorder_traversal(Node* t, std::string& res) {
    if (!t) return;
    push(t); // Ensure lazy tags are processed before visiting children.
    inorder_traversal(t->l, res); // Visit left child
    res += t->key; // Append current node's character
    inorder_traversal(t->r, res); // Visit right child
}

// Optional: function to delete the treap nodes to free memory (usually skipped in CP)
void delete_treap(Node* t) {
    if (!t) return;
    delete_treap(t->l);
    delete_treap(t->r);
    delete t;
}

int main() {
    // Optimize C++ standard streams for faster I/O.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N, K; // Read N (string length) and K (substring length for reversal)
    std::cin >> N >> K;
    std::string S; // Read the input string
    std::cin >> S;

    Node* root = nullptr; // Initialize root of the Treap as null

    // Build the initial Treap from the input string S.
    // Each character becomes a node, merged sequentially. O(N log N) build time.
    for (char c : S) {
        merge(root, root, new Node(c));
    }

    // Perform the sequence of reversal operations.
    // Loop runs N-K+1 times, from i=1 to N-K+1.
    for (int i = 1; i <= N - K + 1; ++i) {
        Node *T1, *T2, *T3; // Temporary pointers for split parts
        
        // The problem uses 1-based indexing [i, i+K-1].
        // In 0-based indexing, this corresponds to [i-1, i+K-2].
        // We need to extract the substring of length K starting at index i-1.
        
        // Split the treap `root` into `T1` and `T2_T3`.
        // `T1` contains the first `i-1` elements (indices 0 to i-2).
        // `T2_T3` contains the rest (indices i-1 to N-1).
        split(root, T1, T2, i - 1); 
        
        // Split `T2_T3` into `T2` and `T3`.
        // `T2` contains the first `K` elements (indices i-1 to i+K-2). This is the target substring.
        // `T3` contains the remaining elements (indices i+K-1 to N-1).
        split(T2, T2, T3, K);

        // Apply the reverse operation lazily to the extracted substring `T2`.
        if (T2) {
            T2->reversed ^= true; // Toggle the reversed flag. Actual reversal happens on push.
        }

        // Merge the three parts back together in the correct order.
        merge(root, T1, T2); // Merge T1 and the (potentially reversed) T2.
        merge(root, root, T3); // Merge the result with T3.
    }

    // Retrieve the final string by performing an inorder traversal of the modified Treap.
    std::string final_S = "";
    final_S.reserve(N); // Reserve capacity for efficiency.
    inorder_traversal(root, final_S);
    
    // Print the resulting string.
    std::cout << final_S << std::endl;

    // Optional cleanup (can be important for very large N or strict memory limits)
    // delete_treap(root); 
    
    return 0;
}