Codeforces线段树题单

【CF 1200-1600 - 线段树】(基础应用, RMQ, 简单区间修改)

• CF339D Xenia and Bit Operations (线段树模板，操作为OR/XOR交替)
• CF474B Worms (前缀和 + 二分，但可用权值线段树理解)
• CF276C Little Girl and Maximum Sum (差分数组 + 排序，线段树可做区间加)
• CF380C Sereja and Brackets (线段树维护括号序列匹配信息)
• CF459D Pashmak and Parmida's problem (离线 + 树状数组/线段树)
• CF617A Elephant (贪心，但如果步长不固定可用线段树优化DP)
• CF520B Two Buttons (BFS，但如果操作更复杂可用线段树模拟)
• CF1374C Move Brackets (栈，但如果查询子区间括号匹配...)
• CF1353C Board Moves (规律，但如果棋盘任意可用线段树维护)
• CF580A Kefa and First Steps (LIS，但如果在线修改...)
• CF431C k-Tree (DP，如果查询路径上的和...)
• CF466A Cheap Travel (DP，如果价格动态修改...)
• CF489C Given Length and Sum of Digits... (构造，如果查询区间数字和...)
• CF977C Less or Equal (排序，如果动态插入删除...)
• CF1462A Favorite Sequence (双指针，如果查询子序列...)
• CF1335C Two Teams Composing (map计数，如果查询区间不同元素...)
• CF492B Vanya and Lanterns (排序，如果灯笼动态增删...)
• CF189A Cut Ribbon (DP，如果长度限制动态...)
• CF414B Mashmokh and ACM (DP，如果查询路径方案数...)
• CF711C Coloring Trees (DP，如果查询子树染色方案...)
• CF1097B Petr and a Combination Lock (DFS，如果查询区间和...)
• CF118D String Task (Incorrect name, actually about sequences) (DP，如果查询子串方案...)
• CF467C George and Job (DP，如果查询区间k段和...)
• CF1105C Ayoub and Lost Array (DP，如果查询区间模m余数分布...)
• CF2B The least round way (DP，如果查询路径最少因子...)
• CF1350B Orac and Models (DP，如果查询路径最优值...)
• CF1399D Binary String To Subsequences (贪心，如果查询区间子序列...)
• CF1426F Number of Subsequences (DP，如果查询区间abc...)
• CF327A Flipping Game (最大子段和，线段树可维护)
• CF546D Soldier and Number Game (预处理质因子+DP，如果查询区间...)

【CF 1600-2100 - 线段树】(线段树维护复杂信息, 扫描线, 简单可持久化)

• CF86D Powerful array (莫队算法，可以用线段树辅助小区间暴力)
• CF220B Little Elephant and Array (莫队算法，同上)
• CF438D The Child and Sequence (线段树，区间取模、区间和，吉司机思想入门)
• CF915E Physical Education Lessons (动态开点线段树/珂朵莉树，区间染色覆盖)
• CF242E XOR on Segment (线段树，每个二进制位分别维护1的个数，支持区间异或)
• CF484B Maximum Value (枚举/数据结构优化枚举，线段树找前驱后继)
• CF620E New Year Tree (树链剖分/DFS序+线段树维护颜色集合(状压))
• CF558E A Simple Task (线段树维护字符出现次数，区间排序)
• CF149D Coloring Brackets (区间DP，但如果查询子区间染色方案...)
• CF1303E Erase Subsequences (DP，如果查询子串能否构成...)
• CF813E Army Creation (主席树，限制每个数出现次数的区间查询)
• CF474D Flowers (DP + 前缀和，线段树可维护区间DP值)
• CF1000F One Occurrence (莫队/主席树/可持久化分块，查询区间只出现一次的数)
• CF786B Legacy (线段树优化建图 + 最短路)
• CF375D Tree and Queries (DSU on Tree，线段树合并也可做)
• CF570D Tree Requests (DFS序 + 离线查询/树上启发式合并，线段树合并也可)
• CF446A DZY Loves Sequences (DP，如果在线修改查询...)
• CF702E Analysis of Pathes in Functional Graph (倍增，如果路径上有点权修改...)
• CF455C Civilization (并查集维护直径，如果动态修改边权...)
• CF295B Greg and Graph (Floyd倒序加点，如果在线加点用线段树维护连通性...)
• CF1100E Andrew and Taxi (拓扑排序+二分，如果边权动态...)
• CF920E Connected Components? (BFS/DFS+set，如果动态加删边...)
• CF1471 方差 (洛谷P1471) (线段树维护区间和、平方和) - 重复洛谷题，但经典
• CF835D Palindromic characteristics (区间DP，线段树可辅助查询回文性质)
• CF1061C Multiplicity (DP，如果查询区间约数倍数对...)
• CF1036C Classy Numbers (数位DP，如果查询区间满足条件的数...)
• CF1114D Flood Fill (区间DP，如果在线修改颜色...)
• CF1285D Dr. Evil Underscores (01Trie+分治/DP，Trie是线段树思想)
• CF1076E Vasya and a Tree (DFS序 + 树状数组/线段树维护子树加和路径查询)
• CF358D Dima and Hares (DP，如果在线修改权值...)

【CF 2100-2500+ - 线段树】(李超树, 吉司机树, 整体二分, 线段树分治, 复杂树套树)

• CF464E The Classic Problem (Dijkstra + 可持久化线段树优化大数比较/哈希)
• CF671D Roads in Yusland (树形DP + 李超线段树合并 / 全局平衡二叉树)
• CF1083E The Fair Share (斜率优化DP + 李超线段树/凸包)
• CF840D Destiny (主席树/莫队+分块/整体二分，查询区间众数)
• CF1290E Cartesian Tree (笛卡尔树 + 线段树/平衡树维护区间信息)
• CF526F Pudding Monsters (分治 + 单调栈 + 线段树/树状数组，统计满足条件的子区间)
• CF750E New Year and Old Subsequence (线段树维护DP状态/矩阵，处理"2017"子序列)
• CF1093E Intersection of Permutations (二维数点，CDQ/树套树/BIT，内层线段树)
• CF896E Welcome home, Chtholly (珂朵莉树/ODT/分块暴力，线段树是基础)
• CF280D k-Maximum Subsequence Sum (线段树维护费用流模型/复杂DP状态，支持区间翻转选k个不交子段)
• CF911G Mass Change Queries (分块/线段树维护每个值的映射，区间值替换)
• CF1198E Rectangles (扫描线 + 网络流最大权闭合子图，线段树维护扫描线)
• CF1479D Odd Mineral Resource (树上启发式合并/主席树维护异或和出现次数，类似权值线段树)
• CF765F Souvenirs (主席树/KD-Tree/分块+离线处理最近值对，线段树维护)
• CF1045G AI Robots (CDQ分治/KD-Tree，内层数据结构可用线段树)
• CF1175E Minimal Segment Cover (倍增优化区间覆盖，可用线段树辅助)
• CF739C Alyona and towers (线段树维护复杂DP信息，区间合并判断山峰山谷)
• CF115E Linear Kingdom Races (线段树优化DP，区间加+查询区间最大值)
• CF833B The Bakery (DP + 线段树优化转移，维护区间不同元素个数的贡献)
• CF449D Jzzhu and Numbers (高维前缀和/FWHT，但如果区间查询...)
• CF1209G2 Into Blocks (hard version) (贪心 + 单调栈/线段树维护区间信息，计算分割代价)
• CF1304F2 Animal Observation (hard version) (DP + 单调队列/滑动窗口优化，线段树可维护窗口最值)
• CF1208F Extend LIS (DP + 线段树/Trie优化转移，找满足特定异或条件的数)
• CF1151E Number of Components (扫描线/差分思想，线段树维护连通块变化)
• CF1073E Segment Sum (数位DP，如果查询区间数位和...)
• CF467E Berland Local Positioning System (DP + 单调栈/笛卡尔树思想，线段树可辅助查询)
• CF888G Xor-MST (Boruvka算法 + 01Trie，Trie是线段树思想)
• CF626F Group Projects (DP计数，如果用线段树维护状态...)
• CF1082E Increasing Frequency (线性DP，转化问题为最大子段和，线段树维护)
• CF1285E Edit Fee (扫描线 + 线段树维护连通块信息，合并区间)