代码模板
csxx601cjy · · 个人记录
stylus插件
几何画板
实用工具
目录[^1]
- 基础代码模板
- 调试信息输出模板
- 快速输入输出模板
- 高精度整数
- 二分答案
- 链式前向星
- 笛卡尔树
- 组合数
- 扩展欧几里得
- 欧拉筛
- 最近公共祖先
- 线段树
- 矩阵计算
以下是正文：
代码模板[^2]
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}CF 代码模板（多测）
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,a[N];
void solve();
int main(){
cin>>T;
while(T--);
return 0;
}
void solve(){
}:::info[]
#include<bits/stdc++.h>
using namespace std;
string a,b,c,d,A,B,C,D,am,bm,cm,dm,base="C:\\Users\\Jifang1\\desktop\\陈敬筠\\";
string cpp[3]={
"#include<bits/stdc++.h>\nusing namespace std;\n\nint main(){\n\t//freopen(\"",
".in\",\"r\",stdin);\n\t//freopen(\"",
".out\",\"w\",stdout);\n\n\treturn 0;\n}"
};
int main(){
cout<<"请输入4道试题的名字：";
cin>>a>>b>>c>>d;
system("mkdir C:\\Users\\Jifang1\\desktop\\陈敬筠");
am="mkdir C:\\Users\\Jifang1\\desktop\\陈敬筠\\"+a;
system(am.c_str());
A=base+a+"\\"+a+".cpp";
freopen(A.c_str(),"w",stdout);
cout<<cpp[0]<<a<<cpp[1]<<a<<cpp[2];
fclose(stdout);
bm="mkdir C:\\Users\\Jifang1\\desktop\\陈敬筠\\"+b;
system(bm.c_str());
B=base+b+"\\"+b+".cpp";
freopen(B.c_str(),"w",stdout);
cout<<cpp[0]<<b<<cpp[1]<<b<<cpp[2];
fclose(stdout);
cm="mkdir C:\\Users\\Jifang1\\desktop\\陈敬筠\\"+c;
system(cm.c_str());
C=base+c+"\\"+c+".cpp";
freopen(C.c_str(),"w",stdout);
cout<<cpp[0]<<c<<cpp[1]<<c<<cpp[2];
fclose(stdout);
dm="mkdir C:\\Users\\Jifang1\\desktop\\陈敬筠\\"+d;
system(dm.c_str());
D=base+d+"\\"+d+".cpp";
freopen(D.c_str(),"w",stdout);
cout<<cpp[0]<<d<<cpp[1]<<d<<cpp[2];
fclose(stdout);
return 0;
}:::
调试信息输出模板[^3]
（使用方法：把 cout 换成 dbg 或 debug，用法同 cout）
#ifndef ONLINE_JUDGE
struct Debug{template<typename T>Debug&operator<<(const T& val){std::cerr<<"\033[32m"<<val<<"\033[0m";return *this;}Debug&operator<<(std::ostream&(*manip)(std::ostream&)){std::cerr<<manip;return *this;}}dbg,debug;
#else
struct Debug{template<typename T>Debug&operator<<(const T&){return *this;}Debug&operator<<(std::ostream&(*)(std::ostream&)){return *this;}}dbg,debug;
#endif
template<typename T>void print(T head){dbg<<head<<'\n';}template<typename T,typename...Args>void print(T head,Args...rest){dbg<<head<<",";print(rest...);}第二种调试信息输出模板
#ifndef ONLINE_JUDGE
#define dbg(x) std::cerr<<"\033[32m"<<#x<<'='<<(x)<<';'<<"\033[0m";
#else
#define dbg(x) ;
#endif使用方法：dbg(x)，x是你想输出的变量。
\large\color{green}{\texttt{祖传快读}} [^4]
#include <sys/mman.h>
unsigned char *cur = (unsigned char *)mmap(0, 1 << 30, 1, 2, 0, 0);
#define gc() (*(cur++))压行版
namespace FastIO{
#include<iostream>
#include<stdio.h>
#define endl '\n'
char obuf[65536],*ooh=obuf;inline void pc(char c){if(ooh==obuf+65536)fwrite(obuf,1,65536,stdout),ooh=obuf;*ooh++=c;}inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
#ifdef __linux__
#include<sys/mman.h>
unsigned char *cur=(unsigned char *)mmap(0,1<<30,1,2,0,0);unsigned char *out=(unsigned char *)mmap(0,1<<30,2,1,1,0);
#define gc() (*(cur++))
#else
char ch;int len;short f,s;inline char gc(){static char buf[65536],*l=buf,*r=buf;if(l==r)r=(l=buf)+fread(buf,1,65536,stdin);return (l==r)?EOF:*l++;}
#endif
char c;short top;struct Reader{template<typename T>Reader&operator>>(T &x){T m0=1;x=0,c=gc();while(!isdigit(c)){if(c=='-')m0=-1;c=gc();}while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();x=x*m0;return *this;}Reader&operator>>(char &x){c=gc();while(c==' ')c=gc();x=c;return *this;}Reader(){}}cin;struct Writer{template<typename T>Writer&operator<<(T x){if(x==0){pc('0');return *this;}static short sta[30];top=0;if(x<0)pc('-'),x=-x;while(x>0)sta[++top]=x%10,x/=10;while(top>0)pc(sta[top]+'0'),top--;return *this;}Writer&operator<<(const char *str){int cur=0;while(str[cur])pc(str[cur++]);return *this;}inline Writer&operator<<(char c){pc(c);return *this;}Writer(){}~Writer(){flush();}}cout;struct Debug1{template<typename T>Debug1&operator<<(const T&){return *this;}Debug1&operator<<(std::ostream&(*)(std::ostream&)){return *this;}}debug1;struct Debug2{template<typename T>Debug2&operator<<(const T& val){std::cerr<<"\033[32m"<<val<<"\033[0m";return *this;}Debug2&operator<<(std::ostream&(*manip)(std::ostream&)){std::cerr<<manip;return *this;}}debug2;}
#define dbg FastIO::debug2
#ifdef ONLINE_JUDGE
#define cin FastIO::cin
#define cout FastIO::cout
#undef dbg
#define dbg FastIO::debug1
#endif
template<typename T>void print(T head){dbg<<head<<'\n';}template<typename T,typename...Args>void print(T head,Args...rest){dbg<<head<<",";print(rest...);}不压行版
namespace FastIO{
#define IN_LEN 65536
#define OUT_LEN 65536
#define endl '\n'
char ch,c;
int len;
short f,top,s;
inline char Getchar(){
static char buf[IN_LEN],*l=buf,*r=buf;
if(l==r)r=(l=buf)+fread(buf,1,IN_LEN,stdin);
return (l==r)?EOF:*l++;
}
char obuf[OUT_LEN],*ooh=obuf;
inline void Putchar(char c){
if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;
*ooh++=c;
}
inline void flush(){
fwrite(obuf,1,ooh-obuf,stdout);
}
#undef IN_LEN
#undef OUT_LEN
struct Reader{
template<typename T>Reader&operator>>(T &x){
T m0=1;
x=0,c=Getchar();
while(!isdigit(c)){
if(c=='-')m0=-1;
c=Getchar();
}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=Getchar();
x=x*m0;
return *this;
}
Reader&operator>>(char &x){
c=Getchar();
while(c==' ')c=Getchar();
x=c;
return *this;
}
Reader(){}
}cin;
struct Writer{
template<typename T>Writer&operator<<(T x){
if(x==0){
Putchar('0');
return *this;
}
static short sta[30];
top=0;
if(x<0)Putchar('-'),x=-x;
while(x>0)sta[++top]=x%10,x/=10;
while(top>0)Putchar(sta[top]+'0'),top--;
return *this;
}
Writer&operator<<(const char *str){
int cur=0;
while(str[cur])Putchar(str[cur++]);
return *this;
}
inline Writer&operator<<(char c){
Putchar(c);
return *this;
}
Writer(){}
~Writer(){flush();}
}cout;
struct Debug1{
template<typename T>Debug1&operator<<(const T&){
return *this;
}
Debug1&operator<<(std::ostream&(*)(std::ostream&)){
return *this;
}
}debug1;
struct Debug2{
template<typename T>Debug2&operator<<(const T& val){
std::cerr<<"\033[32m"<<val<<"\033[0m";
return *this;
}
Debug2&operator<<(std::ostream&(*manip)(std::ostream&)){
std::cerr<<manip;
return *this;
}
}debug2;
#define dbg FastIO::debug2
}
#ifdef ONLINE_JUDGE
#define cin FastIO::cin
#define cout FastIO::cout
#define dbg FastIO::debug1
#endif高精度[^5]
class BigNum {
private:
static const long long BASE = 1000000000;
static const int BASE_DIGITS = 9;
vector<long long> digits;
bool is_negative;
friend std::istream& operator>>(std::istream& is, BigNum& num) { std::string s; is >> s; num = BigNum(s); return is; }
friend std::ostream& operator<<(std::ostream& os, const BigNum& num) { if (num.digits.empty()) { os << '0'; return os; } if (num.is_negative) os << '-'; os << num.digits.back(); char original_fill = os.fill('0'); for (int i = static_cast<int>(num.digits.size()) - 2; i >= 0; i--) { os << std::setw(BASE_DIGITS) << num.digits[i]; } os.fill(original_fill); return os; }
void trim() { while (digits.size() > 1 && digits.back() == 0) { digits.pop_back(); } if (digits.size() == 1 && digits[0] == 0) { is_negative = false; } }
static pair<BigNum, BigNum> divmod(const BigNum& a, const BigNum& b) { if (b == 0) throw runtime_error("Division by zero"); BigNum abs_a = a.absolute(); BigNum abs_b = b.absolute(); if (abs_a < abs_b) { return {0, a}; } vector<long long> quotient_digits; BigNum current; for (int i = static_cast<int>(a.digits.size()) - 1; i >= 0; i--) { current.digits.insert(current.digits.begin(), a.digits[i]); current.trim(); if (current < abs_b) { quotient_digits.push_back(0); continue; } long long l = 0, r = BASE; while (l < r - 1) { long long mid = (l + r) / 2; BigNum mid_big = abs_b * mid; if (mid_big <= current) { l = mid; } else { r = mid; } } quotient_digits.push_back(l); current = current - abs_b * l; } reverse(quotient_digits.begin(), quotient_digits.end()); BigNum q(quotient_digits, false); q.trim(); current.trim(); q.is_negative = (a.is_negative != b.is_negative); current.is_negative = a.is_negative; if (current == 0) current.is_negative = false; return {q, current}; }
public:
BigNum() : digits(1, 0), is_negative(false) {}
BigNum(long long n) { if (n == LLONG_MIN) { is_negative = true; n = -(n + 1); while (n) { digits.push_back(n % BASE); n /= BASE; } if (digits.empty()) digits = {0}; long long carry = 1; for (size_t i = 0; i < digits.size(); i++) { digits[i] += carry; carry = digits[i] / BASE; digits[i] %= BASE; if (carry == 0) break; } if (carry) digits.push_back(carry); return; } if (n == 0) { digits = {0}; is_negative = false; return; } is_negative = n < 0; unsigned long long abs_n = abs(static_cast<long long>(n)); while (abs_n) { digits.push_back(abs_n % BASE); abs_n /= BASE; } }
BigNum(const string& s) { if (s.empty()) { digits = {0}; is_negative = false; return; } size_t start = 0; if (s[0] == '-') { is_negative = true; start = 1; } else { is_negative = false; if (s[0] == '+') start = 1; } while (start < s.size() && s[start] == '0') start++; if (start == s.size()) { digits = {0}; is_negative = false; return; } digits.clear(); size_t end = s.size(); while (end - start > 0) { size_t chunk_start = (end >= BASE_DIGITS) ? end - BASE_DIGITS : start; if (chunk_start < start) chunk_start = start; string chunk = s.substr(chunk_start, end - chunk_start); long long digit = stoll(chunk); digits.push_back(digit); end = chunk_start; } trim(); if (digits.empty()) { digits = {0}; is_negative = false; } }
BigNum(const string& s, bool sin) : BigNum(s) { if (digits.size() == 1 && digits[0] == 0) { is_negative = false; } else { is_negative = sin; } }
BigNum(const vector<long long>& d, bool neg) : digits(d), is_negative(neg) { trim(); }
void setNumber(const string& s) { *this = BigNum(s); }
string getNumber() const { return (is_negative ? "-" : "") + to_string(); }
void setSign(bool s) { is_negative = s; if (digits.size() == 1 && digits[0] == 0) is_negative = false; }
bool getSign() const { return is_negative; }
BigNum absolute() const { return BigNum(digits, false); }
string to_string() const { if (digits.empty()) return "0"; string s; for (int i = static_cast<int>(digits.size()) - 1; i >= 0; i--) { string digit_str = std::to_string(digits[i]); if (i < static_cast<int>(digits.size()) - 1) { digit_str = string(BASE_DIGITS - digit_str.size(), '0') + digit_str; } s += digit_str; } return s; }
BigNum& operator=(const BigNum& b) { if (this == &b) return *this; digits = b.digits; is_negative = b.is_negative; return *this; }
bool operator==(const BigNum& b) const { return digits == b.digits && is_negative == b.is_negative; }
bool operator!=(const BigNum& b) const { return !(*this == b); }
bool operator>(const BigNum& b) const { if (is_negative != b.is_negative) { return !is_negative; } if (digits.size() != b.digits.size()) { return is_negative ? (digits.size() < b.digits.size()) : (digits.size() > b.digits.size()); } for (int i = static_cast<int>(digits.size()) - 1; i >= 0; i--) { if (digits[i] != b.digits[i]) { return is_negative ? (digits[i] < b.digits[i]) : (digits[i] > b.digits[i]); } } return false; }
bool operator<(const BigNum& b) const { return b > *this; }
bool operator>=(const BigNum& b) const { return !(*this < b); }
bool operator<=(const BigNum& b) const { return !(*this > b); }
BigNum& operator++() { *this += 1; return *this; }
BigNum operator++(int) { BigNum temp = *this; ++*this; return temp; }
BigNum& operator--() { *this -= 1; return *this; }
BigNum operator--(int) { BigNum temp = *this; --*this; return temp; }
BigNum operator+(const BigNum& b) const { if (is_negative == b.is_negative) { vector<long long> result; long long carry = 0; size_t max_size = max(digits.size(), b.digits.size()); for (size_t i = 0; i < max_size || carry; i++) { long long sum = carry; if (i < digits.size()) sum += digits[i]; if (i < b.digits.size()) sum += b.digits[i]; carry = sum >= BASE; if (carry) sum -= BASE; result.push_back(sum); } return BigNum(result, is_negative); } else { if (absolute() == b.absolute()) { return 0; } BigNum abs_this = absolute(); BigNum abs_b = b.absolute(); bool result_sign = (abs_this > abs_b) ? is_negative : b.is_negative; if (abs_this < abs_b) { swap(abs_this, abs_b); } vector<long long> result; long long borrow = 0; for (size_t i = 0; i < abs_this.digits.size(); i++) { long long diff = abs_this.digits[i] - borrow; if (i < abs_b.digits.size()) { diff -= abs_b.digits[i]; } borrow = diff < 0; if (borrow) diff += BASE; result.push_back(diff); } BigNum res(result, result_sign); res.trim(); return res; } }
BigNum operator-(const BigNum& b) const { return *this + (-b); }
BigNum operator*(const BigNum& b) const { if (*this == 0 || b == 0) return 0; vector<long long> result(digits.size() + b.digits.size(), 0); for (size_t i = 0; i < digits.size(); i++) { long long carry = 0; for (size_t j = 0; j < b.digits.size() || carry; j++) { long long product = result[i + j] + carry; if (j < b.digits.size()) { product += digits[i] * b.digits[j]; } carry = product / BASE; result[i + j] = product % BASE; } } bool result_sign = is_negative != b.is_negative; BigNum res(result, result_sign); res.trim(); return res; }
BigNum operator/(const BigNum& b) const { return divmod(*this, b).first; }
BigNum operator%(const BigNum& b) const { return divmod(*this, b).second; }
BigNum& operator+=(const BigNum& b) { *this = *this + b; return *this; }
BigNum& operator-=(const BigNum& b) { *this = *this - b; return *this; }
BigNum& operator*=(const BigNum& b) { *this = *this * b; return *this; }
BigNum& operator/=(const BigNum& b) { *this = *this / b; return *this; }
BigNum& operator%=(const BigNum& b) { *this = *this % b; return *this; }
BigNum operator-() const { if (*this == 0) return *this; return BigNum(digits, !is_negative); }
operator string() const { return to_string(); }
};:::info[精简版]
class BigNum{
private:
static const long long BASE=1000000000;
static const int BASED=9;
vector<long long>d;
bool neg;
friend std::istream&operator>>(std::istream&is,BigNum&num){std::string s;is>>s;num=BigNum(s);return is;}
friend std::ostream&operator<<(std::ostream&os,const BigNum&num){if(num.d.empty()){os<<'0';return os;}if(num.neg)os<<'-';os<<num.d.back();char original_fill=os.fill('0');for(int i=static_cast<int>(num.d.size())-2;i>=0;i--){os<<std::setw(BASED)<<num.d[i];}os.fill(original_fill);return os;}
void trim(){while(d.size()>1&&d.back()==0){d.pop_back();}if(d.size()==1&&d[0]==0){neg=false;} }
static pair<BigNum,BigNum>divmod(const BigNum&a,const BigNum&b){if(b==0)throw runtime_error("Division by zero");BigNum abs_a=a.absolute();BigNum abs_b=b.absolute();if(abs_a<abs_b){return{0,a};}vector<long long>quo;BigNum cur;for(int i=static_cast<int>(a.d.size())-1;i>=0;i--){cur.d.insert(cur.d.begin(),a.d[i]);cur.trim();if(cur<abs_b){quo.push_back(0);continue;}long long l=0,r=BASE;while(l<r-1){long long mid=(l+r)/2;BigNum mid_big=abs_b*mid;if(mid_big<=cur){l=mid;}else{r=mid;} }quo.push_back(l);cur=cur-abs_b*l;}reverse(quo.begin(),quo.end());BigNum q(quo,false);q.trim();cur.trim();q.neg=(a.neg!=b.neg);cur.neg=a.neg;if(cur==0)cur.neg=false;return{q,cur};}
public:
BigNum():d(1,0),neg(false){}
BigNum(long long n){if(n==LLONG_MIN){neg=true;n=-(n+1);while(n){d.push_back(n%BASE);n/=BASE;}if(d.empty())d={0};long long carry=1;for(size_t i=0;i<d.size();i++){d[i]+=carry;carry=d[i]/BASE;d[i]%=BASE;if(carry==0)break;}if(carry)d.push_back(carry);return;}if(n==0){d={0};neg=false;return;}neg=n<0;unsigned long long abs_n=abs(static_cast<long long>(n));while(abs_n){d.push_back(abs_n%BASE);abs_n/=BASE;} }
BigNum(const string&s){if(s.empty()){d={0};neg=false;return;}size_t start=0;if(s[0]=='-'){neg=true;start=1;}else{neg=false;if(s[0]=='+')start=1;}while(start<s.size()&&s[start]=='0')start++;if(start==s.size()){d={0};neg=false;return;}d.clear();size_t end=s.size();while(end-start>0){size_t cnk=(end>=BASED)?end-BASED:start;if(cnk<start)cnk=start;string chunk=s.substr(cnk,end-cnk);long long digit=stoll(chunk);d.push_back(digit);end=cnk;}trim();if(d.empty()){d={0};neg=false;} }
BigNum(const string&s,bool sin):BigNum(s){if(d.size()==1&&d[0]==0){neg=false;}else{neg=sin;} }
BigNum(const vector<long long>&d,bool neg):d(d),neg(neg){trim();}
void setNumber(const string&s){*this=BigNum(s);}
string getNumber()const{return(neg?"-":"")+to_string();}
void setSign(bool s){neg=s;if(d.size()==1&&d[0]==0)neg=false;}
bool getSign()const{return neg;}
BigNum absolute()const{return BigNum(d,false);}
string to_string()const{if(d.empty())return "0";string s;for(int i=static_cast<int>(d.size())-1;i>=0;i--){string digit_str=std::to_string(d[i]);if(i<static_cast<int>(d.size())-1){digit_str=string(BASED-digit_str.size(),'0')+digit_str;}s+=digit_str;}return s;}
BigNum&operator=(const BigNum&b){if(this==&b)return*this;d=b.d;neg=b.neg;return*this;}
bool operator==(const BigNum&b)const{return d==b.d&&neg==b.neg;}
bool operator!=(const BigNum&b)const{return!(*this==b);}
bool operator>(const BigNum&b)const{if(neg!=b.neg){return!neg;}if(d.size()!=b.d.size()){return neg?(d.size()<b.d.size()): (d.size()>b.d.size());}for(int i=static_cast<int>(d.size())-1;i>=0;i--){if(d[i]!=b.d[i]){return neg?(d[i]<b.d[i]): (d[i]>b.d[i]);} }return false;}
bool operator<(const BigNum&b)const{return b>*this;}
bool operator>=(const BigNum&b)const{return!(*this<b);}
bool operator<=(const BigNum&b)const{return!(*this>b);}
BigNum&operator++(){*this+=1;return*this;}
BigNum operator++(int){BigNum temp=*this;++*this;return temp;}
BigNum&operator--(){*this-=1;return*this;}
BigNum operator--(int){BigNum temp=*this;--*this;return temp;}
BigNum operator+(const BigNum&b)const{if(neg==b.neg){vector<long long>result;long long carry=0;size_t max_size=max(d.size(),b.d.size());for(size_t i=0;i<max_size||carry;i++){long long sum=carry;if(i<d.size())sum+=d[i];if(i<b.d.size())sum+=b.d[i];carry=sum>=BASE;if(carry)sum-=BASE;result.push_back(sum);}return BigNum(result,neg);}else{if(absolute()==b.absolute()){return 0;}BigNum abs_this=absolute();BigNum abs_b=b.absolute();bool result_sign=(abs_this>abs_b)?neg:b.neg;if(abs_this<abs_b){swap(abs_this,abs_b);}vector<long long>result;long long borrow=0;for(size_t i=0;i<abs_this.d.size();i++){long long diff=abs_this.d[i]-borrow;if(i<abs_b.d.size()){diff-=abs_b.d[i];}borrow=diff<0;if(borrow)diff+=BASE;result.push_back(diff);}BigNum res(result,result_sign);res.trim();return res;} }
BigNum operator-(const BigNum&b)const{return*this+(-b);}
BigNum operator*(const BigNum&b)const{if(*this==0||b==0)return 0;vector<long long>result(d.size()+b.d.size(),0);for(size_t i=0;i<d.size();i++){long long carry=0;for(size_t j=0;j<b.d.size()||carry;j++){long long product=result[i+j]+carry;if(j<b.d.size()){product+=d[i]*b.d[j];}carry=product/BASE;result[i+j]=product%BASE;} }bool result_sign=neg!=b.neg;BigNum res(result,result_sign);res.trim();return res;}
BigNum operator/(const BigNum&b)const{return divmod(*this,b).first;}
BigNum operator%(const BigNum&b)const{return divmod(*this,b).second;}
BigNum&operator+=(const BigNum&b){*this=*this+b;return*this;}
BigNum&operator-=(const BigNum&b){*this=*this-b;return*this;}
BigNum&operator*=(const BigNum&b){*this=*this*b;return*this;}
BigNum&operator/=(const BigNum&b){*this=*this/b;return*this;}
BigNum&operator%=(const BigNum&b){*this=*this%b;return*this;}
BigNum operator-()const{if(*this==0)return*this;return BigNum(d,!neg);}
operator string()const{return to_string();}
};:::
二分答案[^6]
二分答案（闭区间
int ans,l,r,mid;
while(l<=r){
mid=l+r>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
return ans;链式前向星[^7]
#define MAXN 10005
#define MAXE 20005
struct Edge{
int to,w,next;
}edge[MAXE];
int cnt,head[MAXN];
void add(int u,int v,int w){
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}#define MAXN 10005 // 最大节点数
#define MAXE 20005 // 最大边数
struct Edge{ // 存边结构体
int to; // 这条边的终点
int w; // 边权（无权图可省略）
int next; // 指向下一条边的数组下标（链表指针）
}edge[MAXE]; // 存储所有边的数组
int cnt,head[MAXN]; // 每个节点的“第一条边”的下标
void add(int u,int v,int w){ // 添加一条从u到v边权为w的有向边
edge[++cnt].to=v; // 这条边的终点是v
edge[cnt].w=w; // 边权赋值
edge[cnt].next=head[u]; // 新边的next指向u原来的第一条边（头插法）
head[u]=cnt; // u的第一条边更新为当前边（下标cnt）
}
#define For(i,u) for(int i=head[u];i;i=edge[i].next) // 遍历u的所有邻接边笛卡尔树[^8]
for(int i=1;i<=n;i++){
int k=tp;
while(k>0&&w[stk[k]]>w[i])k--;
if(k)rs[stk[k]]=i;
if(k<tp)ls[i]=stk[k+1];
stk[++k]=i;
tp=k;
}// stk 维护笛卡尔树中节点对应到序列中的下标
for (int i = 1; i <= n; i++) {
int k = top; // top 表示操作前的栈顶，k 表示当前栈顶
while (k > 0 && w[stk[k]] > w[i]) k--; // 维护右链上的节点
if (k) rs[stk[k]] = i; // 栈顶元素.右儿子 := 当前元素
if (k < top) ls[i] = stk[k + 1]; // 当前元素.左儿子 := 上一个被弹出的元素
stk[++k] = i; // 当前元素入栈
top = k;
}