Increasing Subsequence II (CSES) | Segment Tree + Coordinate Compression (Hard DP)

Welcome back to the 𝐒𝐞𝐠𝐦𝐞𝐧𝐭 𝐓𝐫𝐞𝐞 𝐒𝐞𝐫𝐢𝐞𝐬 🎉⁣⁣ ⁣⁣ In this video, we solve the CSES Problem – 𝐈𝐧𝐜𝐫𝐞𝐚𝐬𝐢𝐧𝐠 𝐒𝐮𝐛𝐬𝐞𝐪𝐮𝐞𝐧𝐜𝐞 𝐈𝐈 𝐮𝐬𝐢𝐧𝐠 𝐒𝐞𝐠𝐦𝐞𝐧𝐭 𝐓𝐫𝐞𝐞 + 𝐂𝐨𝐨𝐫𝐝𝐢𝐧𝐚𝐭𝐞 𝐂𝐨𝐦𝐩𝐫𝐞𝐬𝐬𝐢𝐨𝐧.⁣⁣ ⁣⁣ This is an 𝐚𝐝𝐯𝐚𝐧𝐜𝐞𝐝 𝐃𝐲𝐧𝐚𝐦𝐢𝐜 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 𝐰𝐢𝐭𝐡 𝐃𝐚𝐭𝐚 𝐒𝐭𝐫𝐮𝐜𝐭𝐮𝐫𝐞𝐬 𝐩𝐫𝐨𝐛𝐥𝐞𝐦, where we count the number of increasing subsequences in an array, modulo 1e9+7.⁣⁣ ⁣⁣ 𝐖𝐞 𝐜𝐨𝐯𝐞𝐫 𝐞𝐯𝐞𝐫𝐲𝐭𝐡𝐢𝐧𝐠 𝐬𝐭𝐞𝐩 𝐛𝐲 𝐬𝐭𝐞𝐩:⁣⁣ - Understanding the problem statement 📖⁣⁣ - Brute force approach and why it fails ❌⁣⁣ - Using 𝐃𝐏 + 𝐒𝐞𝐠𝐦𝐞𝐧𝐭 𝐓𝐫𝐞𝐞 to efficiently calculate subsequences ⚡⁣⁣ - 𝐂𝐨𝐨𝐫𝐝𝐢𝐧𝐚𝐭𝐞 𝐜𝐨𝐦𝐩𝐫𝐞𝐬𝐬𝐢𝐨𝐧 to handle large values (up to 1e9)⁣⁣ ⁣⁣ Full C++ implementation with detailed explanation⁣⁣ ⁣⁣ 💡 𝐁𝐲 𝐭𝐡𝐞 𝐞𝐧𝐝 𝐨𝐟 𝐭𝐡𝐢𝐬 𝐯𝐢𝐝𝐞𝐨, 𝐲𝐨𝐮 𝐰𝐢𝐥𝐥:⁣⁣ - Master how to use 𝐒𝐞𝐠𝐦𝐞𝐧𝐭 𝐓𝐫𝐞𝐞𝐬 𝐟𝐨𝐫 𝐜𝐨𝐮𝐧𝐭𝐢𝐧𝐠 𝐩𝐫𝐨𝐛𝐥𝐞𝐦𝐬⁣⁣ - Understand 𝐜𝐨𝐨𝐫𝐝𝐢𝐧𝐚𝐭𝐞 𝐜𝐨𝐦𝐩𝐫𝐞𝐬𝐬𝐢𝐨𝐧 clearly⁣⁣ - Be ready to solve other 𝐚𝐝𝐯𝐚𝐧𝐜𝐞𝐝 𝐃𝐏 + 𝐒𝐞𝐠𝐦𝐞𝐧𝐭 𝐓𝐫𝐞𝐞 problems in contests⁣⁣ ⁣⁣ 🔗 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐋𝐢𝐧𝐤: ⁣⁣⁣ https://cses.fi/problemset/task/1748/⁣⁣ ⁣⁣⁣ 🎥 𝐏𝐥𝐚𝐲𝐥𝐢𝐬𝐭 𝐋𝐢𝐧𝐤: https://youtube.com/playlist?list=PLtfqa971vD5GTQjH9U0H6kiq9cQlFFa5k&si=tpC7IxUtmfO49W--⁣⁣⁣⁣ ⁣⁣⁣⁣ 👉 𝐒𝐭𝐚𝐲 𝐭𝐮𝐧𝐞𝐝, 𝐬𝐮𝐛𝐬𝐜𝐫𝐢𝐛𝐞, 𝐚𝐧𝐝 𝐟𝐨𝐥𝐥𝐨𝐰 𝐭𝐡𝐞 𝐩𝐥𝐚𝐲𝐥𝐢𝐬𝐭 to not miss the advanced problems!⁣⁣⁣⁣ ⁣⁣⁣ 🔔 Don’t forget to 𝐥𝐢𝐤𝐞, 𝐬𝐡𝐚𝐫𝐞, 𝐚𝐧𝐝 𝐬𝐮𝐛𝐬𝐜𝐫𝐢𝐛𝐞 if you find this helpful!⁣⁣⁣ ⁣⁣ #SegmentTree #CSES #CompetitiveProgramming #DynamicProgramming #DataStructures #CodingInterview #Codeforces #Programming