U366685 code

### 团队:[【GSOI】出题组](https://www.luogu.com.cn/team/70241#main) **综合**：[【题单大全】](https://www.luogu.com.cn/training/93910) **收藏** [【收藏题单】](https://www.luogu.com.cn/training/419957) **NOI辞典**： [【NOI辞典1】](https://www.luogu.com.cn/training/414220#problems) **USACO**： [【2022-2023铜银】](https://www.luogu.com.cn/training/434467) **动态规划**：[【CF绿蓝DP】](https://www.luogu.com.cn/training/434694)[【提高组DP】](https://www.luogu.com.cn/training/12927#information)[【普及-省选DP】](https://www.luogu.com.cn/training/414277)[【各种综合DP】](https://www.luogu.com.cn/paste/o1v83qvj)[【动态规划基础】](https://www.luogu.com.cn/training/435271)[【CFdp2000分左右】](https://www.luogu.com.cn/training/3963)[【CF1600~2000分DP】](https://www.luogu.com.cn/training/436091) **图论**： [【强连通分量】](https://www.luogu.com.cn/training/1645#problems)[【树形结构】](https://www.luogu.com.cn/training/1185#problems) **贪心**： [【黄绿以上贪心】](https://www.luogu.com.cn/training/414279) **数学数论**： [【数论1】](https://www.luogu.com.cn/training/75320#problems)[【数论2】](https://www.luogu.com.cn/training/435255)[【数论3】](https://www.luogu.com.cn/training/435262)[【紫黑博弈论】](https://www.luogu.com.cn/training/4203#problems)[【绿蓝博弈论】](https://www.luogu.com.cn/training/435278) **数据结构**： [【线段树】](https://www.luogu.com.cn/training/1124#problems) **技巧题目** [【CF小技巧】](https://www.luogu.com.cn/paste/py95ug9a)

#### 常用设备 ```cpp // Author: gsczl71 // Copyright (c) 2024 gsczl71 All rights reserved. #include #define ll long long #define i128 __int128 #define ull unsigned long long #define pii pair #define pll pair #define fs first #define sc second #define endl '\n' #define debug puts("AK IOI") #define re register #define pb push_back #define mem(a,x) memset((a),(x),sizeof(a)) #define vi vector #define pq priority_queue using namespace std; namespace gsczl71_fastIO { template inline T read() { T s=0,w=1;char c=getchar(); while(!isdigit(c)){if(c=='-')w=-1;c=getchar();} while(isdigit(c))s=(s

#### 卡常设备 ```cpp /* Author: gsczl71 Copyright (c) 2023 gsczl71 All rights reserved. problem： */ //#pragma omp parallel for num_threads(64) //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") //#pragma GCC optimize(2,3,"Ofast","inline","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-falign-functions","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks") //#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") //#pragma comment(linker,"/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //--------------------------------------------------------火车头 #include #include //有历史意义，我不想成为下一个hzlqwq //#include //--------------------------------------------------------头文件 #define ll long long //#define int unsigned long long #define i128 __int128 #define ull unsigned long long #define pii pair #define fir first #define se second #define endl '\n' #define debug puts("AK IOI RP INF") #define debug1 puts("AK IOI -- part 1") #define debug2 puts("AK IOI -- part 2") #define debug3 puts("AK IOI -- part 3") #define debug4 puts("AK IOI -- part 4") #define re register #define Yes puts("Yes") #define No puts("No") #define YES puts("YES") #define NO puts("NO") #define yes puts("yes") #define no puts("no") #define error puts("error") #define IMPOSSIBLE puts("IMPOSSIBLE") #define Impossible puts("Impossible") #define fy puts("-1") #define pll pair #define AC exit(0) #define pb push_back //-------------------------------------------------------define好习惯 using namespace std; namespace gsczl71_function{ inline int Min(int a, int b) { return a < b ? a : b;}//取min inline int Max(int a, int b) { return a > b ? a : b;}//取max inline void Swap(int& a,int& b) {a^=b,b^=a,a^=b;}//交换 inline void tomin(int& a,int b) {if(a>b)a=b;}//a=min(a,b) inline void tomax(int& a,int b) {if(a>31))-(x >> 31);}//绝对值 inline ll gcd(ll a,ll b){/*最大公因数*/int i=__builtin_ctz(a),j=__builtin_ctz(b),x=i>j?j:i,y;b>>=j;while(a){a>>=i;y=b-a;i=__builtin_ctz(y);b=a

[2024寒假学习计划](https://www.luogu.com.cn/discuss/763497) [cf插](https://codeforces.com/blog/entry/103660)

#### My CnBlog ###### [【link】](https://www.cnblogs.com/gsczl71/p/17990420) ### 个人草稿区 #### 网站 [【链接汇总】](https://www.luogu.com.cn/blog/ltzlInstallBl/sajdkljsaldjsalkjdlksa) [洛谷](https://www.luogu.com.cn/)|[SWOJ](https://www.swoj.cn/)|[学军OJ](https://xjoi.net/)|[AtCoder](https://atcoder.jp/) |[LOJ](https://loj.ac/)|[Codeforces](https://codeforces.com/)|[UVA](https://uva.onlinejudge.org/)|[USACO](http://train.usaco.org/usacogate)|[SPOJ](http://www.spoj.com/ )|[VJ](https://vjudge.csgrandeur.cn/)|[OIWiki](https://oiwiki.com/)|[数据结构与算法演示](https://visualgo.net/zh) |[作图器](https://csacademy.com/app/graph_editor/)|[CSDN](https://www.csdn.net/) |[AC源](http://101.43.142.51/home)|[Alex_Wei 图论笔记](https://www.cnblogs.com/alex-wei/p/basic_graph_theory.html)|[wjyyy博客](http://www.wjyyy.top/)|[LaTeX公式大全](https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan)| #### 文件&安装包 [文件题单](https://www.luogu.com.cn/training/389842#problems)|[devc++6.7.5安装包](https://cowtransfer.com/s/8885bd8a226644)|[微软壁纸](https://cowtransfer.com/s/8fd1a3993e0d44) #### CCF官方文件 [GD_2023_CSP-J_code](https://cowtransfer.com/s/5641881b48d74e)|[GD_2023_CSP-S code](https://cowtransfer.com/s/eec773285b2f41)|[GD NOIP 2023 code](https://cowtransfer.com/s/c9ffddc571f14c)|[2023CSP测试数据](https://cowtransfer.com/s/3437ef5817474c)|[NOIP2023测试数据](https://cowtransfer.com/s/c838f815c56f48) #### 插件 [at 插件](https://greasyfork.org/zh-CN/scripts/465777-codeforces-better)|[cf插件](https://greasyfork.org/zh-CN/scripts/471106-atcoder-better)|[exlg](https://www.luogu.com.cn/blog/654958/luo-gu-cha-jian-exlg-an-zhuang-zhi-na)|[OIso++](https://oiso.luogu.link/index.min.user.js)|[CF-Predictor](https://cowtransfer.com/s/814368e79a364f) #### 有意思的东西 [洛谷试炼场（公开）](https://www.luogu.com.cn/paste/vxj5nmlk)|[烧机神器](https://www.luogu.com.cn/paste/pne1kx3b) [copy别人的主页---干货](https://www.luogu.com.cn/paste/x1kpveh3) #### U盘解限： 1. HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\USBSTOR\Start 设为 3； 2. 用户配置→管理模板→Windows组件→Windows资源管理器→防止从“我的电脑”访问驱动器 设为“不限制驱动器”； 3. 计算机配置→管理模板→系统→可移动存储访问→所有可移动存储类：拒绝所有权限； 4. 运行cmd命令 sc stop TDFileFilter 和 sc delete TDFileFilter； #### 模板题 [$\color{F39C11}普及-$](https://www.luogu.com.cn/training/369132) [$\color{FFC116}普及/提高-$](https://www.luogu.com.cn/training/369134) [$\color{52C41A}普及+/提高$](https://www.luogu.com.cn/training/369135) [$\color{3498DB}提高+/省选-$](https://www.luogu.com.cn/training/369136) [$\color{9D3DCF}省选/NOI-1$](https://www.luogu.com.cn/training/369137) [$\color{9D3DCF}省选/NOI- 2$](https://www.luogu.com.cn/training/369138) [$\color{0E1D69}NOI/NOI+/CTSC$](https://www.luogu.com.cn/training/369139) $$ \boxed{\color{Gold}\LARGE\text{洛谷相关颜色参考表}} $$ $$ \def\arraystretch{1.2} \begin{array}{|c|l|l||c|l|l|} \hline 颜色 & 十六进制 & RGB值 & 颜色 & 十六进制 & RGB值 \\ \hline \color{#52C41A}\text{AC绿} & \text{52C41A} & \text{(82,196,26)} & \color{#FE4C61}\text{入门红} & \text{FE4C61} & \text{(254,76,97)} \\ \hline \color{#E74C3C}\text{WA红} & \text{E74C3C} & \text{(231,76,60)} & \color{#F39C11}\text{普及-橙} & \text{F39C11} & \text{(243,156,17)} \\ \hline \color{#9D3DCF}\text{RE紫} & \text{9D3DCF} & \text{(157,61,207)} & \color{#FFC116}\text{普及黄} & \text{FFC116} & \text{(255,193,22)}\\ \hline \color{#FADB14}\text{CE黄} & \text{FADB14} & \text{(250,219,20)} & \color{#52C41A}\text{普及+提高 绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#052242}\text{TLE黑} & \text{052242} & \text{(5,34,66)} & \color{#3498DB}\text{提高+省选-蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \color{#052242}\text{MLE黑} & \text{052242} & \text{(5,34,66)} & \color{#9D3DCF}\text{省选紫} & \text{9D3DCF} & \text{(157,61,207)} \\ \hline \color{#052242}\text{OLE黑} & \text{052242} & \text{(5,34,66)} & \color{#0E1D69}\text{NOI黑} & \text{0E1D69} & \text{(14,39,105)} \\ \hline \color{#0E1D69}\text{UKE蓝} & \text{0E1D69} & \text{(14,29,105)} & \color{#BFBFBF}\text{未评定灰} & \text{BFBFBF} & \text{(191,191,191)} \\ \hline \hline \color{#8E44AD}\text{紫名} & \text{8E44AD} & \text{(142,68,173)} & \color{#52C41A}\text{排行绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#E74C3C}\text{红名} & \text{E74C3C} & \text{(231,76,60)} & \color{#F39C11}\text{排行橙} & \text{F39C11} & \text{(243,156,17)} \\ \hline \color{#E67E22}\text{橙名} & \text{E67E22} & \text{(230,126,34)} & \color{#FADB14}\text{排行黄} & \text{FADB14} & \text{(250,219,20)} \\ \hline \color{#5EB95E}\text{绿名} & \text{5EB95E} & \text{(94,185,94)} & \color{#E74C3C}\text{排行红} & \text{E74C3C} & \text{(231,76,60)}\\ \hline \color{#0E90D2}\text{蓝名} & \text{0E90D2} & \text{(14,144,210)} & \color{#52C41A}\text{通过钩绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#BFBFBF}\text{灰名} & \text{BFBFBF} & \text{(191,191,191)} & \color{#E74C3C}\text{不通过叉红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \hline \color{#E74C3C}\text{吉利红} & \text{E74C3C} & \text{(231,76,60)} & \color{#E74C3C}\text{官方比赛红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \color{#5EB95E}\text{中平绿} & \text{5EB95E} & \text{(94,185,94)} & \color{#054310}\text{团队比赛绿} & \text{054310} & \text{(5,67,16)} \\ \hline \color{#000000}\text{凶兆黑} & \text{000000} & \text{(0,0,0)} & \color{#3498DB}\text{个人比赛蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \hline \color{#8E44AD}\text{ACM制紫} & \text{8E44AD} & \text{(142,68,173)} & \color{#5EB95E}\text{Rated绿} & \text{5EB95E} & \text{(94,185,94)} \\ \hline \color{#F1C40F}\text{IOI制黄} & \text{F1C40F} & \text{(241,196,15)} & \color{#5EB95E}\text{未开始绿} & \text{5EB95E} & \text{(94,185,94)} \\ \hline \color{#F1C40F}\text{乐多制黄} & \text{F1C40F} & \text{(241,196,15)} & \color{#E74C3C}\text{已结束红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \color{#F39C11}\text{OI制橙} & \text{F39C11} & \text{(243,156,17)} & \color{#4290D8}\text{进行中*} & \text{4290D8} & \text{(66,144,216)} \\ \hline \hline \color{#EFEFEF}\text{背景灰} & \text{EFEFEF} & \text{(239, 239, 239)} & \color{#7F7F7F}\text{小字灰} & \text{7F7F7F} & \text{(127,127,127)} \\ \hline \hline \color{#0E90D2}\text{按钮蓝} & \text{0E90D2} & \text{(14,144,210)} & \color{#3498DB}\text{链接蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \color{#DD514C}\text{按钮红} & \text{DD514C} & \text{(221,81,76)} & \color{#3498DB}\text{通过率蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \hline \color{#FFE169}\text{金钩黄} & \text{FFE169} & \text{(255,225,105)} & \color{#F5CECD}\text{背景粉} & \text{F5CECD} & \text{(245,206,205)} \\ \hline \color{#5EB95E}\text{绿钩绿} & \text{5EB95E} & \text{(94,185,94)} & \color{#C9E7C9}\text{背景绿} & \text{C9E7C9} & \text{(201,231,201)} \\ \hline \color{#3498DB}\text{蓝钩蓝} & \text{3498DB} & \text{(52,152,219)} & \color{#CAEBFB}\text{背景蓝} & \text{CAEBFB} & \text{(202,235,251)} \\ \hline \hline \color{#3498DB}\text{题目来源蓝} & \text{3498DB} & \text{(52,152,219)} &\color{#7F7F7F}\text{灰色} & \text{7F7F7F} & \text{(127,127,127)} \\ \hline \color{#E74C3C}\text{题目算法红} & \text{E74C3C} & \text{(231,76,60)}& \color{#FFFFFF}\text{白色} & \text{FFFFFF} & \text{(255,255,255)} \\ \hline \color{#52C41A}\text{题目地点绿} & \text{52C41A} & \text{(82,196,26)}& \color{#000000}\text{黑色} & \text{000000} & \text{(0,0,0)} \\ \hline \end{array} $$ Tools (about Competitive Programming) : --------------------------------------- **[Csacademy Graph Editor（画“图”）](https://csacademy.com/app/graph_editor/)** **[Data Structure Visualization（算法/数据结构可视化）](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)** **[BZOJ 离线题库](https://bzoj.netlify.com/)** **[模板题 OJ](https://judge.yosupo.jp/)** **[OIerDB（OIer数据库）](http://bytew.net/OIer/)** **[各大 OJ 做题量统计](https://ojhunt.com/statistics)** **[OI Archive](https://oi-archive.memset0.cn/#/)** **[AI generate CP ideas](https://fjzzq2002.github.io/cpideas/)** **[OnlineIDE](https://tio.run/#)** **About Codeforces:** **[CodeForces Rating Predictor](http://codeforces.com/blog/entry/50411)** **[Codeforces Comments&Blogs Statistics](https://codeforces.igorjan94.ru/index/blogs)** **[CF tracker（比赛列表、显示做题情况）](https://cftracker.netlify.app/contests)** **[Codeforces 练习情况统计与比较](https://recommender.codedrills.io/tools/comparator)** **Atcoder:** **[AtCoder Rating Perdictor](https://greasyfork.org/zh-CN/scripts/369954-ac-predictor)** **[AtCoder Problems（题目列表、显示题目难度、显示做题情况）](https://kenkoooo.com/atcoder/)** Tools (not about Competitive Programming) : ------------------------------------------- **[Geogebra 图形计算器](https://www.geogebra.org/graphing)** **[Desmos 图形计算器](https://www.desmos.com/calculator)** **[图床 sm.ms](https://sm.ms/)** **[图床 imgtu.com](https://imgchr.com/)** **[图片压缩](https://tinypng.com/)** **[GIF maker](https://imgflip.com/gif-maker)** **[Ubuntu Pastebin 剪贴板](https://paste.ubuntu.com/)** **[乱码修复](http://www.mytju.com/classcode/tools/messycoderecover.asp)** **[Stackedit（在线 Markdown 编辑器）](https://stackedit.io/)** **[Compiler Explorer（查看汇编码）](https://gcc.godbolt.org/)** **[OEIS（数列查询）](http://oeis.org/)** **[手写符号识别](https://detexify.kirelabs.org/symbols.html)** Blogs/Articles (about Competitive Programming) : ------------------------------------------------ **[OI Wiki](https://oi-wiki.org/)** **[Algorithms for Competitive Programming](https://cp-algorithms.com/navigation.html)** **[洛谷日报](https://www.craft.do/s/N0l80k2gv46Psq)** **[OI-Public-Library（包含 IOI 中国国家候选队论文）](https://github.com/enkerewpo/OI-Public-Library/tree/master)** **[list of useful blogs on codeforces](https://codeforces.com/blog/entry/91363)** **[The Ultimate Topic List (with Resources, Problems and Templates)](https://codeforces.com/blog/entry/95106)** **[A List of Useful Equations in Competitive Programming](https://blog.shahjalalshohag.com/equation-list)** **[综合题单](https://studyingfather.com/archives/841)** **[USACO guide](https://usaco.guide/)** **[Comoetitive Programming Hall Of Fame](https://cphof.org/standings/icpc/2021)** **[UOJ 精神之源流（这个不算是实用性的，偏题了，只是我觉得大家都应该看一看）](https://vfleaking.blog.uoj.ac/blog/909)** Blogs/Articles (not about Competitive Programming) : ---------------------------------------------------- **[C++ Reference](https://en.cppreference.com/w/)** **[Another C++ Reference](http://www.cplusplus.com/reference/)** **[LaTeX 数学公式大全](https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan)** **[TheFreeDictionary（内含 wikipedia 镜像）](https://www.thefreedictionary.com/)** Discussions ----------- 这里我没有怎么收集过，如果有发现很有意义的讨论可以在下方评论或者直接私信我，我会考虑添加。 内容最好和算法竞赛相关，但其他的也可以接受。任何地方的讨论都行（不一定要是洛谷的）。 **[（洛谷讨论）小蒟蒻求 dp 好题](https://www.luogu.org/discuss/show/73921)** **[（洛谷讨论）关于广义 SAM 的讨论](https://www.luogu.com.cn/discuss/322224)** Games ----- **[Simon Tatham's Portable Puzzle Collection](https://www.chiark.greenend.org.uk/~sgtatham/puzzles/)** **[好吃棋](http://43.143.206.254:3000/)** - 数学是火，点亮物理的灯； - 物理是灯，照亮化学的路； - 化学是路，通向生物的坑； - 生物是坑，埋葬理科的生。 - 语文是火，点亮历史的灯； - 历史是灯，照亮政治的路； - 政治是路，通向哲学的坑； - 哲学是坑，埋葬文科的生。 - OI 是神，埋葬了文科理科生，永远的神！ [$\small\texttt{\color{gray}(\color{#768530}{\#768530}\color{gray})\color{#E74C3C}gsczl71}$](https://www.luogu.com.cn/user/768530) [$\color{3BA4A4}\text{\&}$](https://vdse.bdstatic.com//192d9a98d782d9c74c96f09db9378d93.mp4) [$\small\texttt{\color{#E74C3C}Saint\_ying\_xtf\color{gray}(\color{#999666}{\#1073995}\color{gray})}$](https://www.luogu.com.cn/user/1073995)   [](https://www.luogu.com.cn/paste/7e9c2sxy) # 警钟长鸣 ###### [I am Joker.](https://www.luogu.com.cn/problem/U366685) - **你开 long long 了吗？** - ~~#define int long long~~ 赶紧改掉吧！ - **多测清空了吗？** - 多测清空会不会爆炸？ - 你的数组开够了吗？ - **n，m有没有反** - 优先队列的结构体重载函数写对了吗？ - **位运算加括号了吗？** - **复制 long long 变量的算式有没有把1改成1ll？** - 取模有没有 `(x + mod) % mod`？ - `scanf` 加 `&` 了吗？ - 你用万能头有没有重名？类似：$y1$。 - 没加万能头的你，写对应头文件了吗？ - 你确定用龟速的输入输出流吗？ - 关闭同步流还用格式化输入输出吗？ - **你的字符串是否用的是 `a+=x` 而不是 `a=a+x`? 【NOIP 2023 挂 10分】** - 你的函数调用了吗？ - **下标从 $0$ 开始是否还会取到 $i-1$** - 换行和空格搞反了吗？ - 有没有直接遍历到 `const int N` 的 $N$ 的下标？ [](https://atcoder.jp/users/gsczl71) [](https://codeforces.com/profile/gsczl71) [AtCoder做题情况](https://kenkoooo.com/atcoder/#/table/gsczl71)。PS：最近督促自己把1Kyu以下难度的近期题目补起来！ [CF难度](https://cftracker.netlify.app/contests) ### [目前学习内容](https://www.luogu.com.cn/team/70241) | About Me | My target | other | | :----------: | :----------: | :----------: | | **[【My OIerDb】](https://www.xn--vuqs4zq3d.com/oier/149780)** | **[【2023目标】](https://www.luogu.com.cn/paste/lbkxnrn7)** | **[【大事祭】](https://www.luogu.com.cn/paste/dlqefdfc)**| | **[【My Account】](https://www.luogu.com.cn/paste/0mssngn5)** | **[【2024目标】](https://www.luogu.com.cn/paste/0asawh8z)** | **[【名言】](https://www.luogu.com.cn/paste/rcxxky0d)** | | **[【My cnblog】](https://www.cnblogs.com/gsczl71/)** | | **[【链接】](https://www.cnblogs.com/gsczl71/p/17857576.html)** | | **[【My Luogu Blog】](https://www.luogu.com.cn/paste/u9cr71ob)** | | **[【备忘录】](https://www.luogu.com.cn/paste/wiorte5e)** | | **[【My bilibili】](https://space.bilibili.com/513386027)** **** [](https://vdse.bdstatic.com//192d9a98d782d9c74c96f09db9378d93.mp4) [](https://badges.toozhao.com/stats/01HBGBSY9MGKYQP9TDVRS191M3 "Get your own page views count badge on badges.toozhao.com")