代码模板

UnionRE · 2025-07-15 14:42:39 · 科技·工程

Codes

代码模板

//#pragma GCC optimize("Ofast,no-stack-protector")
//#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")

//include:

#include <bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>//用tree
// #include<ext/pb_ds/hash_policy.hpp>//用hash
// #include<ext/pb_ds/trie_policy.hpp>//用trie
// #include<ext/pb_ds/priority_queue.hpp>//用priority_queue

// using namespace __gnu_pbds;
// __gnu_pbds::priority_queue<T, Compare, Tag, Allocator>
// __gnu_pbds::tree<Key, Mapped, Cmp_Fn = std::less<Key>, Tag = rb_tree_tag,
//                  Node_Update = null_tree_node_update,
//                  Allocator = std::allocator<char>>

#define mp make_pair
#define cchash cc_hash_table<int,bool> 
#define gphash gp_hash_table<int,bool> 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> bbtr;//平衡树
//tree不可重！！！

//存储的类型:long long
//映射类型:null_type,无映射(低版本g++为null_mapped_type)
//顺序:less<long long>,从小到大排序
//rb_tree_tag,红黑树
//更新方式 :tree_order_statistics_node_update,更新节点的顺序统计信息
#define pqueue __gnu_pbds::priority_queue
#define grt greater//greater<int>小根堆
#define pair_h pairing_heap_tag
#define thin_h thin_heap_tag
#define bino_h binomial_heap_tag 
#define rcbino_h rc_binomial_heap_tag
#define binary_h binary_heap_tag
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
/*
pairing_heap_tag
thin_heap_tag
binomial_heap_tag
rc_binomial_heap_tag 
binary_heap_tag
*/

//#define endl '\n'
#define pow fastpow
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
//unlocked WINDOWS会报错

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
    return x*f;
}//快读
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}//快输
//常数较小的快输：
inline void fastwrite(int x) {
    static int sta[35];
    int top =0;
    do{sta[top++]=x%10,x/=10;}while (x);
    while(top) putchar(sta[--top]+48);
}
struct cnt_trie{
    vector<vector<int>>ch;
    vector<int>cnt;
    int ct=0;
    int gn_map[128];
    //如果用全局数组，不用vector，常数约为1/2
    void clear(){
        ch.clear();
        cnt.clear();
        ch.push_back(vector<int>(65, 0)); // 初始化根节点
        cnt.push_back(0);
        ct=0;
    }
    cnt_trie(){cnt_trie::init_gn();clear();}
    void init_gn() {
        for(int i=0;i<128;i++) gn_map[i]=-1;
        for(char c='A';c<='Z';c++) gn_map[c]=c-'A';
        for(char c='a';c<='z';c++) gn_map[c]=c-'a'+26;
        for(char c='0';c<='9';c++) gn_map[c]=c-'0'+52;
    }
    inline int gn(char x){return gn_map[(int)x];}
    void insert(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]){
                ch.push_back(vector<int>(65, 0));//全局数组就不用这两个push_back，直接用
                cnt.push_back(0);
                ch[p][c]=++ct;
            }
            p=ch[p][c];
            cnt[p]++;
        }
    }
    int find_cnt(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]) return 0;
            p=ch[p][c];
        }
        return cnt[p];
    }
    pair<int,int> find_range(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]) return {0,0};
            p=ch[p][c];
        }
        return {p,ct};
    }
};
namespace fast_io{
    const int fread_cnt=(1<<20);
    const int fwrite_cnt=(1<<20);
    class fast_read{
    private:
        char buf_in[fread_cnt],*p1,*p2;
        inline char gc(){return (p1==p2&&(p2=(p1=buf_in)+fread(buf_in,1,fread_cnt,stdin),p1==p2)?EOF:*p1++);}
        inline bool read_bool(){char ch=gc();while(ch<'0'||ch>'1'){ch=gc();}return (ch=='1');}
        inline char read_ch(){char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}return ch;}
        inline string read_string(){
            string s;char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}
            while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!='\t'){s+=ch;ch=gc();}return s;
        }
        template <typename T>
        inline T read_int(){
            T x=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
            while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
            return x*f;
        }
        template <typename T>
        inline T read_unsigned(){
            T x=0;char ch=gc();while(ch<'0'||ch>'9'){ch=gc();}
            while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
            return x;
        }
        template <typename T>
        inline T read_float(){
            T x=0,f=1,c=1;char ch=gc();
            while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
            while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=gc();}
            if(ch=='.'){ch=gc();while(ch>='0'&&ch<='9'){c/=10;x+=c*(ch^48);ch=gc();}}
            return x*f;
        }
    public:
        fast_read& operator >> (bool &valx){valx=read_bool();return *this;}
        fast_read& operator >> (char &valx){valx=read_ch();return *this;}
        fast_read& operator >> (string &valx){valx=read_string();return *this;}
        fast_read& operator >> (float &valx){valx=read_float<float>();return *this;}
        fast_read& operator >> (double &valx){valx=read_float<double>();return *this;}
        fast_read& operator >> (long double &valx){valx=read_float<long double>();return *this;}
        fast_read& operator >> (short &valx){valx=read_int<short>();return *this;}
        fast_read& operator >> (int &valx){valx=read_int<int>();return *this;}
        fast_read& operator >> (long &valx){valx=read_int<long>();return *this;}
        fast_read& operator >> (long long &valx){valx=read_int<long long>();return *this;}
        fast_read& operator >> (unsigned short &valx){valx=read_unsigned<unsigned short>();return *this;}
        fast_read& operator >> (unsigned int &valx){valx=read_unsigned<unsigned int>();return *this;}
        fast_read& operator >> (unsigned long &valx){valx=read_unsigned<unsigned long>();return *this;}
        fast_read& operator >> (unsigned long long &valx){valx=read_unsigned<unsigned long long>();return *this;}
    }fin;
    class fast_write{
    private:
        char buf_out[fwrite_cnt],*p=buf_out;
        inline void write_bool(bool x){char ch=(x==1)?'1':'0';pc(ch);}
        inline void write_ch(char x){char ch=x;pc(ch);}
        inline void write_string(string s){for(string::iterator it=s.begin();it!=s.end();it=next(it)){pc(*it);}}
        template <typename T>
        inline void write_int(T x){
            if(x<(T)0){pc('-');x=-x;}
            if(x>=10){write_int(x/10);}pc((x%10)^48);
        }
        template <typename T>
        inline void write_unsigned(T x){
            if(x>=10){write_unsigned(x/10);}pc((x%10)^48);
        }
        template <typename T>
        inline void write_float(T x){
            if(x<(T)0)pc('-'),x=-x;
            write_int((int)x);pc('.');x-=(int)x;
            while(x!=0){x*=10;pc((int)x^48);x-=(int)x;}
        }
    public:
        inline void pc(char ch){if(p-buf_out==fwrite_cnt){fwrite(buf_out,1,fwrite_cnt,stdout),p=buf_out;}*p=ch;++p;}
        inline void flush(){fwrite(buf_out,1,p-buf_out,stdout);p=buf_out;}
        inline fast_write& operator << (bool valx){write_bool(valx);return *this;}
        inline fast_write& operator << (char valx){write_ch(valx);return *this;}
        inline fast_write& operator << (string valx){write_string(valx);return *this;}
        inline fast_write& operator << (float valx){write_float<float>(valx);return *this;}
        inline fast_write& operator << (double valx){write_float<double>(valx);return *this;}
        inline fast_write& operator << (long double valx){write_float<long double>(valx);return *this;}
        inline fast_write& operator << (short valx){write_int<short>(valx);return *this;}
        inline fast_write& operator << (int valx){write_int<int>(valx);return *this;}
        inline fast_write& operator << (long valx){write_int<long>(valx);return *this;}
        inline fast_write& operator << (long long valx){write_int<long long>(valx);return *this;}
        inline fast_write& operator << (unsigned short valx){write_unsigned<unsigned short>(valx);return *this;}
        inline fast_write& operator << (unsigned int valx){write_unsigned<unsigned int>(valx);return *this;}
        inline fast_write& operator << (unsigned long valx){write_unsigned<unsigned long>(valx);return *this;}
        inline fast_write& operator << (unsigned long long valx){write_unsigned<unsigned long long>(valx);return *this;}
        inline fast_write& operator << (fast_write& (*func)(fast_write&)){return func(*this);}
    }fout;inline fast_write& endl(fast_write& fastout){fastout.pc('\n');fastout.flush();return fastout;}
}using namespace fast_io;
#define int long long
int Reverse_order_pairs=0;//逆序对，个数
const int MAXN=1000001;
int a[MAXN],c[MAXN];
class Graph {//DAG有向无环图
private:
    int n;
    vector<unordered_map<int, int>> adj; // 邻接表，adj[u][v] = 初始边权w0
    vector<int> add_in;   // 每个节点的入边附加权值
    vector<int> add_out;  // 每个节点的出边附加权值
    vector<int> topo;     // 拓扑序
    vector<int> topo_index; // 节点在拓扑序中的索引
    vector<int> in_degree;  // 节点的入度
public:
    Graph(int num_nodes) : n(num_nodes), adj(num_nodes), add_in(num_nodes, 0), 
    add_out(num_nodes, 0), topo_index(num_nodes, -1), 
    in_degree(num_nodes, 0) {}

    // 添加有向边 u->v，初始权值为w
    void addedge(int u, int v, int w) {
        if (u < 0 || u >= n || v < 0 || v >= n) return;
        if (adj[u].find(v) == adj[u].end()) {
            adj[u][v] = w;
            in_degree[v]++;
        } else {
            adj[u][v] = w; // 如果边已存在，覆盖权值
        }
    }
    // 构建拓扑序
    void build_topo() {
        topo.clear();
        vector<int> in_deg = in_degree; // 复制入度数组
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (in_deg[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            topo.push_back(u);
            for (auto& edge : adj[u]) {
                int v = edge.first;
                if (--in_deg[v] == 0) {
                    q.push(v);
                }
            }
        }
        // 设置拓扑序索引
        for (int i = 0; i < topo.size(); i++) {
            topo_index[topo[i]] = i;
        }
    }
    // 修改单边(u->v)的初始权值，加上delta
    void change_edge(int u, int v, int delta) {
        if (u < 0 || u >= n || v < 0 || v >= n) return;
        if (adj[u].find(v) != adj[u].end()) {
            adj[u][v] += delta;
        }
    }
    // 修改节点v的所有入边，每条边加上delta
    void change_in_edges(int v, int delta) {
        if (v >= 0 && v < n) {
            add_in[v] += delta;
        }
    }
    // 修改节点u的所有出边，每条边加上delta
    void change_out_edges(int u, int delta) {
        if (u >= 0 && u < n) {
            add_out[u] += delta;
        }
    }
    // 查询s到t的最短路径长度
    int shortest_path(int s, int t) {
        if (s < 0 || s >= n || t < 0 || t >= n) return INT_MIN;
        if (topo.empty() || topo_index[s] == -1) return INT_MIN;
        vector<long long> dist(n, LLONG_MAX / 2); // 防止溢出
        dist[s] = 0;
        int start_idx = topo_index[s];
        for (int i = start_idx; i < topo.size(); i++) {
            int u = topo[i];
            if (dist[u] == LLONG_MAX / 2) continue; // 不可达节点
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int w0 = edge.second;
                long long actual_weight = (long long)w0 + add_out[u] + add_in[v];
                if (dist[u] + actual_weight < dist[v]) {
                    dist[v] = dist[u] + actual_weight;
                }
            }
        }
        return (dist[t] >= LLONG_MAX / 2) ? INT_MIN : (int)dist[t];
    }
    // 查询s到t的最长路径长度
    int longest_path(int s, int t) {
        if (s < 0 || s >= n || t < 0 || t >= n) return INT_MIN;
        if (topo.empty() || topo_index[s] == -1) return INT_MIN;
        vector<long long> dist(n, LLONG_MIN);
        dist[s] = 0;
        int start_idx = topo_index[s];
        for (int i = start_idx; i < topo.size(); i++) {
            int u = topo[i];
            if (dist[u] == LLONG_MIN) continue; // 不可达节点
            for (auto& edge : adj[u]) {
                int v = edge.first;
                int w0 = edge.second;
                long long actual_weight = (long long)w0 + add_out[u] + add_in[v];
                if (dist[u] + actual_weight > dist[v]) {
                    dist[v] = dist[u] + actual_weight;
                }
            }
        }
        return (dist[t] == LLONG_MIN) ? INT_MIN : (int)dist[t];
    }
};
const long long maxPrime=6000010,maxNumber=10000100;
bitset<maxNumber> isPrime;
int Prime[maxPrime];//质数
int cntPrime=0;
void GetPrime(int n){
    isPrime.set();
    isPrime[1]=0;
    for(int i=2;i<=n;i++){
        if(isPrime[i])Prime[++cntPrime]=i; 
        for(int j=1;j<=cntPrime&&i*Prime[j]<=n;j++) {
            isPrime[i*Prime[j]]=0;
            if(i%Prime[j]==0)break; 
        }
    }
}
//支持对a数组排序
void MergeSort(int beg,int end)//begin&end
{
    if(beg==end)  
        return;
    int mid=(beg+end)/2,i=beg,j=mid+1,k=beg;
    MergeSort(beg,mid),MergeSort(mid+1,end);
    while(i<=mid&&j<=end)
        if(a[i]<=a[j])

            c[k++]=a[i++];
    else{
        c[k++]=a[j++];
        Reverse_order_pairs+=mid-i+1;//左边即个数
    }//inplace_merge();

    while(i<=mid)c[k++]=a[i++];
    while(j<=end)c[k++]=a[j++];
    for(int x=beg;x<=end;x++)a[x]=c[x];
} //归并排序

namespace largetype{
    class largeint{
    private:
        string num;
        bool isNegative;
    public:
        largeint():num("0"),isNegative(false){}
        largeint(const string& s){
            if(s.empty()){
                num="0";
                isNegative=false;
                return;
            }
            isNegative=(s[0]=='-');
            num=isNegative?s.substr(1):s;
        }
        largeint(int n){
            if(n==0){
                num="0";
                isNegative=false;
                return;
            }
            isNegative=(n<0);
            num=to_string(abs(n));
        }
        string getNum()const{return num;}
        bool getIsNegative()const{return isNegative;}
        bool operator<(const largeint& other)const{
            if(isNegative!=other.isNegative)return isNegative;
            if(num.length()!=other.num.length())
                return isNegative?(num.length()>other.num.length()):(num.length()<other.num.length());
            return isNegative?(num>other.num):(num<other.num);
        }
        bool operator==(const largeint& other)const{return num==other.num&&isNegative==other.isNegative;}
        bool operator<=(const largeint& other)const{return *this<other||*this==other;}
        bool operator>(const largeint& other)const{return !(*this<=other);}
        bool operator>=(const largeint& other)const{return !(*this<other);}
        largeint operator+(const largeint& other)const{
            if(isNegative==other.isNegative){
                string a=num,b=other.num;
                int i=a.length()-1,j=b.length()-1,carry=0;
                string res;
                while(i>=0||j>=0||carry){
                    int x=(i>=0)?(a[i--]-'0'):0;
                    int y=(j>=0)?(b[j--]-'0'):0;
                    int sum=x+y+carry;
                    res.push_back(sum%10+'0');
                    carry=sum/10;
                }
                reverse(res.begin(),res.end());
                largeint result(res);
                result.isNegative=isNegative;
                return result;
            }else{
                if(isNegative){
                    largeint temp=*this;
                    temp.isNegative=false;
                    return other-temp;
                }else{
                    largeint temp=other;
                    temp.isNegative=false;
                    return *this-temp;
                }
            }
        }
        largeint operator-(const largeint& other)const{
            if(isNegative!=other.isNegative){
                largeint temp=other;
                temp.isNegative=isNegative;
                return *this+temp;
            }
            string a=num,b=other.num;
            bool resNegative=false;
            if((isNegative&&*this>other)||(!isNegative&&*this<other)){
                swap(a,b);
                resNegative=true;
            }
            int i=a.length()-1,j=b.length()-1,borrow=0;
            string res;
            while(i>=0||j>=0){
                int x=(i>=0)?(a[i--]-'0'):0;
                int y=(j>=0)?(b[j--]-'0'):0;
                int diff=x-y-borrow;
                if(diff<0){
                    diff+=10;
                    borrow=1;
                }else{
                    borrow=0;
                }
                res.push_back(diff+'0');
            }
            while(res.length()>1&&res.back()=='0')res.pop_back();
            reverse(res.begin(),res.end());
            largeint result(res);
            result.isNegative=resNegative;
            return result;
        }
        largeint operator*(const largeint& other)const{
            string a=num,b=other.num;
            int m=a.length(),n=b.length();
            vector<int> res(m+n,0);
            for(int i=m-1;i>=0;i--){
                for(int j=n-1;j>=0;j--){
                    int mul=(a[i]-'0')*(b[j]-'0');
                    int sum=mul+res[i+j+1];
                    res[i+j+1]=sum%10;
                    res[i+j]+=sum/10;
                }
            }
            string resultStr;
            for(int num:res){
                if(!(resultStr.empty()&&num==0)){
                    resultStr.push_back(num+'0');
                }
            }
            if(resultStr.empty())resultStr="0";
            largeint result(resultStr);
            result.isNegative=isNegative^other.isNegative;
            return result;
        }
        void write()const{
            if(isNegative)cout<<"-";
            cout<<num;
        }
    };
}

using namespace largetype;

struct fantastic     {//这个也可以
    int len,s[9999];
    fantastic(){
        memset(s,0,sizeof(s));
        len=1;
    }
    fantastic operator=(const char*num){
        len=strlen(num);
        for(int i=0;i<len;++i)
            s[i]=num[len-i-1]-'0';
        return *this;
    }
    fantastic operator=(const int num){
        char a[9999];
        sprintf(a,"%lld",num);
        *this=a;
        return *this;
    }
    fantastic (const int num){*this=num;}
    fantastic (const char * num){*this=num;}
    fantastic operator+(const fantastic &a)   {
        fantastic c;
        c.len=max(len,a.len)+1;                
        for(int i=0,x=0;i<c.len;++i)
        {
            c.s[i]=s[i]+a.s[i]+x;
            x=c.s[i]/10;
            c.s[i]=c.s[i]%10;
        }
        if(c.s[c.len-1]==0)
            --c.len;
        return c;
    }
    fantastic operator * (const fantastic &x)           {
        fantastic c;
        c.len=len+x.len;                 
        for(int i=0;i<len;++i)
            for(int j=0;j<x.len;++j)
            {
                c.s[i+j]+=s[i]*x.s[j];
                c.s[i+j+1]+=c.s[i+j]/10;
                c.s[i+j]%=10;
            }
        if(c.s[c.len-1]==0)
            --c.len;
        return c;
    }
};

//另一种快读
/*
#include <bits/stdc++.h>
using lint = long long;

// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}

~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc() {
#if DEBUG  // 调试，可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}

bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}

template <class T>
T read(T &x) {
double tmp = 1;
bool sign = 0;
x = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc())
tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
return x;
}

void read(char *s) {
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}

void read(char &c) { for (c = gc(); blank(c); c = gc()); }

void push(const char &c) {
#if DEBUG  // 调试，可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}

template <class T>
void write(T x) {
if (x < 0) x = -x, push('-');  // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}

template <class T>
void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;

int main() {
int n = io.read(n);
lint sum = 0;
for (int t; n; --n) sum += io.read(t);
io.write(sum, '\n');
return 0;
}
*/
int Mod;//支持输入模值
int fastpow(int a,int b) {
    if(b==0)return 1;
    int sum=1;
    while(b) {
        if(b&1) sum=sum*a%Mod;
        a=a*a%Mod,b>>=1;
    }
    return sum;
}
//GetPrime(MAXP);MAXP为查询范围（查询到质数的最大值<=MAXP）
void FindPrime(){//查询质数
    int k;
    k=read();
    write(Prime[k]);
    puts("");
    return;
}
signed main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    //TODO
    int n;//个数
    int node_cnt,edge_cnt;//节点个数
    cin>>node_cnt>>edge_cnt;
    Graph dag(node_cnt);
    while(edge_cnt--){
        int u,v,w;
        cin>>u>>v>>w;
        dag.addedge(u,v,w);
    }
    dag.build_topo();

//  cin>>n;
//  for(int i=1;i<=n;i++)cin>>a[i];
//  MergeSort(1,n);
    int order_pairs=n*(n-1)/2-Reverse_order_pairs;
    //顺序对（请先MergeSort）
//  cout<<order_pairs;
    return 0;

}

高精度python卡法

from decimal import *
import sys
setcontext(Context(prec=2000000, Emax=2000000, Emin=0))
print((Decimal(sys.stdin.readline())-Decimal(sys.stdin.readline())))

分块模板

#include<bits/stdc++.h>
#define int long long
#define sint int
using namespace std;
const int MAXN=1000010;
int L[MAXN],R[MAXN],s[MAXN],a[MAXN],pos[MAXN],add[MAXN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}//快读
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}//快输
inline void update(int x,int y,int k){//在x,y范围每个内增加k
    int p=pos[x],q=pos[y];
    if(p==q){
        for(int i=x;i<=y;i++)a[i]+=k;
        s[p]=s[p]+(y-x+1)*k;
        return;
    }
    for(int i=p+1;i<=q-1;i++){
        add[i]+=k;
        s[i]=s[i]+(R[i]-L[i]+1)*k;
    }
    for(int i=x;i<=R[p];i++)a[i]+=k;
    s[p]=s[p]+(R[p]-x+1)*k;
    for(int i=L[q];i<=y;i++){
        a[i]+=k;
        s[q]+=k;
    }
}
int select(int x,int y){
    int p=pos[x],q=pos[y];
    int ans=0;
    if(p==q){
        for(int i=x;i<=y;i++)ans+=a[i]+add[p];
        return ans;
    }
    else {
        for(int i=x;i<=R[p];i++)ans+=a[i]+add[p];//左不完整块
        for(int i=p+1;i<=q-1;i++)ans+=s[i];//中间完整块
        for(int i=L[q];i<=y;i++)ans+=a[i]+add[q];//右不完整块
        return ans;
    }

}
int n,m,opt;

signed main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=t*(i-1)+1;
        R[i]=t*i;
        for(int j=L[i];j<=R[i];j++)pos[j]=i;
    }
    if(R[t]<n){
        t++;
        L[t]=R[t-1]+1;
        R[t]=n;
        for(int i=L[t];i<=R[t];i++)pos[i]=t;
    }
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++){
            s[i]+=a[j];
            pos[j]=i;
        }
    }
    while(m--){
        opt=read();
        if(opt==1){
            int x,y,k;
            x=read(),y=read(),k=read();
            update(x,y,k);
        }
        else {
            int x;
            x=read();
            write(a[x]+add[pos[x]]);
            puts("");
        }
    }

    return 0;
}

欧拉筛

#include <bits/stdc++.h>
using namespace std;
bitset<100000010> isPrime;
int Prime[6000010];
int cnt = 0;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
void GetPrime(int n)
{
    isPrime.set();

    isPrime[1] = 0;

    for(int i = 2; i <= n; i++)
    {
        if(isPrime[i])
            Prime[++cnt] = i; 

        for(int j = 1; j <= cnt && i*Prime[j] <= n; j++) 
        {
            isPrime[i*Prime[j]] = 0;

            if(i % Prime[j] == 0)
                break; 
        }
    }
}
void solve(){
    int k;
    k=read();
    write(Prime[k]);
    puts("");
    return;
}
signed main()
{
    long long n;int q;
    n=read();q=read();
    GetPrime(n);
    while (q--)
    {
        solve();
    }
    return 0;
}

线段树模板

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls id<<1
#define rs id<<1|1
using namespace std;

inline int read(){//fastread
    int res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){ res=res*10+ch-48; ch=getchar();}
    return res*f;
}
const int maxn=100000+10;
struct Node{
    int L,R;
    int sum,lazy,ma;
} t[maxn*4];
int n,a[maxn];
void up(int id){
    t[id].sum=t[ls].sum+t[rs].sum;
    t[id].ma=max(t[ls].ma,t[rs].ma);
}
void down(int id){//下传
    t[ls].lazy+=t[id].lazy; t[rs].lazy+=t[id].lazy;
    t[ls].sum+=(t[ls].R-t[ls].L+1)*t[id].lazy;
    t[ls].ma+=t[id].lazy;
    t[rs].sum+=(t[rs].R-t[rs].L+1)*t[id].lazy;
    t[rs].ma+=t[id].lazy;
    t[id].lazy=0;
}
void build(int id,int l,int r){//建立
    t[id].L=l; t[id].R=r;
    if(l==r){
        t[id].sum=a[l]; t[id].ma=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid); //左子树
    build(rs,mid+1,r);//右子树
    up(id);
}
void update(int id,int l,int r,int val){//将l，r区间同时加上一个val
    if(t[id].L>r || t[id].R<l) return;
    if(t[id].L>=l && t[id].R<=r){//节点自己处理
        t[id].lazy+=val;
        t[id].sum+=(t[id].R-t[id].L+1)*val;
        t[id].ma+=val;
        return;
    }
    if(t[id].lazy!=0) down(id);
    update(ls,l,r,val); update(rs,l,r,val);
    up(id);
}//修改操作
int ask_sum(int id,int l,int r){//查询元素的和
    if(t[id].L>r || t[id].R<l) return 0;
    if(t[id].L>=l && t[id].R<=r) return t[id].sum;
    if(t[id].lazy !=0) down(id);
    return ask_sum(ls,l,r)+ask_sum(rs,l,r);
}
int ask_max(int id,int l,int r){//查询区间最大值
    if(t[id].L>r || t[id].R<l) return -0x7f7f7f7f;
    if(t[id].L>=l && t[id].R<=r) return t[id].ma;
    if(t[id].lazy !=0) down(id);
    return max(ask_max(ls,l,r),ask_max(rs,l,r));
}
signed main(){
    int m,opt,l,r,val;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>val; update(1,l,r,val);
        } 
        else if(opt==2){
            cin>>l>>r;
            cout<<ask_sum(1,l,r)<<endl;
        } 
    }
    return 0;
}

扶苏线段树模板

#include<bits/stdc++.h>
//#define int long long
//#define endl '\n' 
#define ls id<<1
#define rs id<<1|1
#define getchar getchar_unlocked
#define putchar putchar_unlocked

typedef long long ll;
typedef short st;

using namespace std;
const ll maxn=1e6+10;
struct SegmentTree{
    int L,R;
    ll add,max,cov;
    bool used;//used?
} t[maxn<<2];
int n,m;
ll a[maxn];
void up(int id){
    t[id].max=max(t[ls].max,t[rs].max);
}
void down(int id){//下传
    if((t[id].used)){
        t[ls].cov=t[id].cov;
        t[rs].cov=t[id].cov;

        t[ls].add=t[id].add;
        t[rs].add=t[id].add;

        t[ls].max=t[id].add+t[id].cov;
        t[rs].max=t[id].add+t[id].cov;

        t[ls].used=1;t[rs].used=1;

    }
    else{//unused
        t[ls].add+=t[id].add;
        t[rs].add+=t[id].add;

        t[ls].max+=t[id].add;
        t[rs].max+=t[id].add;

    }
    t[id].add=t[id].cov=t[id].used=0;

}
void build(int id,int l,int r){//建立
    t[id].L=l; t[id].R=r;
    t[id].max=-1e18;
//  t[id].add=0;
//  t[id].cov=LLONG_MIN;
    if(l==r){
        t[id].max=a[l];
//      t[id].used=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid); //左子树
    build(rs,mid+1,r);//右子树
    up(id);
}

void change(int id,int l,int r,ll val){//updcov
//  if(l>t[id].R || t[id].L<r) return;
    if(l<=t[id].L&&t[id].R<=r){
        t[id].cov=val;
        t[id].add=0;
        t[id].max=val;
        t[id].used=1;
        return;
    }
    /*  if(t[id].add !=0)*/ down(id);
    int mid=(t[id].L+t[id].R)>>1;
    if(l<=mid)change(ls,l,r,val);
    if(mid+1<=r)change(rs,l,r,val);
    up(id);

}//覆盖操作

void update(int id,int l,int r,ll val){//updadd
//  if(t[id].L>r || t[id].R<l) return;
    if(t[id].L>=l && t[id].R<=r){//节点自己处理
        t[id].add+=val;
        t[id].max+=val;
        return;
    }
    down(id);
    int mid=(t[id].L+t[id].R)>>1;
    if(l<=mid)update(ls,l,r,val);
    if(mid+1<=r)update(rs,l,r,val);
    up(id);
}//修改操作

ll ask_max(int id,int l,int r){//查询区间最大值
    if(t[id].L>r || t[id].R<l) return -1e18;
    if(l<=t[id].L&&t[id].R<=r) 
        return t[id].max;
    /*  if(t[id].add !=0)*/ down(id);

    ll res=-1e18;
    int mid=(t[id].L+t[id].R)>>1;
    if(l<=mid)res=max(res,ask_max(ls,l,r));
    if(mid+1<=r)res=max(res,ask_max(rs,l,r));
    return res;

}
signed main(){
    int opt;
    int l,r;
    ll val;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            scanf("%lld",&val);
            change(1,l,r,val);

        } 
        else if(opt==2){
            scanf("%lld",&val);
            update(1,l,r,val);

        } 
        else{
            printf("%lld\n",ask_max(1,l,r));
        }
    }
    return 0;
}

矩形周长

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl node_line
#define nt node_SegmentTree
#define ls id<<1
#define rs id<<1|1
#define endl '\n'
const int MAXN=1e5+10;//mod=998224353
int tot,ans,last;//last上条底的长度
int X[MAXN*2];//离散化

struct node_line{
    int Lx,Rx,y;
    int state;//状态
}line[MAXN*2];
struct node_SegmentTree{
    int L,R,cnt,len,sum; //cnt表示当前区间被覆盖的次数,len当先扫描到的矩形的长,sum不相交包含的竖边个类 
    bool lcov,rcov;
} t[MAXN*4];

bool cmp(nl a,nl b){
    if(a.y==b.y)return a.state>b.state;
    return a.y<b.y;
}
void build(int id,int l,int r){
    t[id].L=l;t[id].R=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
}
void up(int id){
    int l=t[id].L,r=t[id].R;
    if(t[id].cnt>0){
        t[id].len=X[r+1]-X[l];

        t[id].lcov=t[id].rcov=1;
        t[id].sum=2;
    }
    else{
        t[id].len=t[ls].len+t[rs].len;
        t[id].sum=t[ls].sum+t[rs].sum;
        t[id].lcov=t[ls].lcov, t[id].rcov=t[rs].rcov;
        if(t[ls].rcov&&t[rs].lcov)t[id].sum-=2;
    }
}
void update(int id,int l,int r,int state){
    if (l<=t[id].L && t[id].R<=r) {
        t[id].cnt+=state;
        up(id);
        return;
    }
    int mid=(t[id].L+t[id].R)>>1;
    if(l<=mid)update(ls,l,r,state);
    if(r>mid)update(rs,l,r,state);
    up(id);
}
signed main(){
    last=tot=ans=0;
    int n,x,y,x2,y2;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>x2>>y2;
        line[i]={x,x2,y,1};
        line[i+n]={x,x2,y2,-1};
        X[i]=x;
        X[i+n]=x2;
    }
    n*=2;
    sort(line+1,line+n+1,cmp);
    sort(X+1, X+n+1);
    //去重离散化
    tot=unique(X+1, X+n+1)-X-1;
    build(1,1,tot);//建立线段树
    for(int i=1;i<n;i++) {
        int L=lower_bound(X+1,X+tot+1,line[i].Lx)-X;
        int R=lower_bound(X+1,X+tot+1,line[i].Rx)-X;
        update(1,L,R-1,line[i].state);
        ans=ans+abs(last-t[1].len);//横边长度
        last=t[1].len;
        ans=ans+t[1].sum*(line[i+1].y-line[i].y); 
    }
    ans=ans+line[n].Rx-line[n].Lx; 
    cout<<ans<<endl;
    return 0;
}

矩形面积并

#include<bits/stdc++.h>
#define int long long
#define nl node_line
#define nt node_SegmentTree
#define ls id<<1
#define rs id<<1|1
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=200000+10;
struct node_SegmentTree{
    int L,R;
    int cnt,len;
}t[MAXN*8];
struct node_line{
    int l,r,h,state;
}a[MAXN*2];

int n,maxv=0,b[MAXN*2];

bool cmp(nl a,nl b){
    return a.h<b.h;
}
void build(int id,int l,int r){
    t[id].L=l;t[id].R=r;
    if(t[id].L==t[id].R)return;
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
}
void update(int id,int l,int r,int state){
    if(t[id].L>r||t[id].R<l)return;
    if(t[id].L>=l&&t[id].R<=r){
        t[id].cnt+=state;
        if(t[id].cnt==0){
            t[id].len=t[ls].len+t[rs].len;
        }
        else t[id].len=b[t[id].R+1]-b[t[id].L];
        return;
    }
    update(ls,l,r,state);update(rs,l,r,state);
    if(t[id].cnt==0){
        t[id].len=t[ls].len+t[rs].len;
    }
    else t[id].len=b[t[id].R+1]-b[t[id].L];
}
signed main(){
    int x,y,x2,y2;
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>x2>>y2;
        if(x>x2){swap(x,x2),swap(y,y2);}
        maxv=max(maxv,x2);
        a[i*2-1].h=min(y,y2); 
        a[i*2-1].l=x; 
        a[i*2-1].r=x2; 
        a[i*2-1].state=1;
        a[i*2].h=max(y,y2); 
        a[i*2].l=x; a[i*2].r=x2; 
        a[i*2].state=-1;
        b[i*2-1]=x; 
        b[i*2]=x2;
    }
    n*=2;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1);
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int xl=lower_bound(b+1,b+tot+1,a[i].l)-b;
        int xr=lower_bound(b+1,b+tot+1,a[i].r)-b;
        a[i].l=xl; a[i].r=xr;
    }
    build(1,1,tot);
    int now=a[1].h;

    update(1,a[1].l,a[1].r-1,a[1].state);
    int ans=0;
    for(int i=2;i<=n;i++){
        int len=t[1].len;
        ans+=len*(a[i].h-now);
        now=a[i].h;
        update(1,a[i].l,a[i].r-1,a[i].state);
    }
    cout<<ans<<endl;
    return 0;
}

普通平衡树（离散化权值线段树）

#include<bits/stdc++.h>
#define int long long
using namespace std;
//该题是一个权值线段树离线算法实现平衡树，如果强制在线就不行
const int maxn=100000+10;
struct node {
    int l,r,cnt;//sum表示数值范围内，数字出现的总次数
} tr[maxn*4];
int a[maxn],b[maxn],n,opt[maxn],tot=0,p;
inline void build(int id,int l,int r) {
    tr[id].l=l;
    tr[id].r=r;
    if(l==r) return;
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
inline void update(int id,int l,int r,int x) {
    if(tr[id].l>r || tr[id].r<l) return;
    if(tr[id].l>=l && tr[id].r<=r) {
        tr[id].cnt+=x;
        return;
    }
    update(id*2,l,r,x);
    update(id*2+1,l,r,x);
    tr[id].cnt=tr[id*2].cnt+tr[id*2+1].cnt;
}
int q_rank(int id,int l,int r) { //查询数字在l-r范围内出现的个数
    if(tr[id].l>r || tr[id].r<l) return 0;
    if(tr[id].l>=l && tr[id].r<=r) return tr[id].cnt;
    return q_rank(id*2,l,r)+q_rank(id*2+1,l,r);
}
int q_num(int id,int x) {//查询当前线段树，出现次数为x的数
    if(tr[id].l==tr[id].r) return tr[id].l;
    if(x<=tr[id*2].cnt) return q_num(id*2,x);
    else return q_num(id*2+1,x-tr[id*2].cnt);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) { //把要用到的操作和数存下来
        cin>>opt[i]>>a[i];
        if(opt[i]!=4) b[++tot]=a[i];
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;//去重
    build(1,1,tot);
    for(int i=1; i<=n; i++) { //枚举操作
        if(opt[i]!=4) p=lower_bound(b+1,b+tot+1,a[i])-b;//因为4操作不是对数值操作
        if(opt[i]==1) update(1,p,p,1);//插入x
        if(opt[i]==2) update(1,p,p,-1);//删除x
        if(opt[i]==3) { //查询数x的排名,排名定义为比当前数小的数的个数+1
            if(p==1) cout<<1<<endl;
            else cout<<q_rank(1,1,p-1)+1<<endl;
        }
        if(opt[i]==4) { //排名为x的数,即出现的数字个数为x的数值
            int k=q_num(1,a[i]);
            cout<<b[k]<<endl;//注意离散化后的，所以需要还原
        }
        if(opt[i]==5) { //查询x的前驱
            int rk=q_rank(1,1,p-1);//先找到当前小于等于p-1的个数
            int k=q_num(1,rk);//再查询个数对应的数值
            cout<<b[k]<<endl;
        }
        if(opt[i]==6) { //查询数字x的后继
            int rk=q_rank(1,1,p)+1;//先找到当前小于等于p的个数+1
            int k=q_num(1,rk);//再查询个数对应的数值
            cout<<b[k]<<endl;
        }
    }
    return 0;
}

普通平衡树（平衡树）

有旋Treap

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
int root=0,k;
struct treap{
    int ls,rs;
    int val,pri;
    int cnt,size;
}t[MAXN];
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+t[id].cnt;}
void zag(int &rt){//左旋
    int b=t[rt].rs;
    t[rt].rs=t[b].ls;
    t[b].ls=rt;
    up(rt);up(b);
    rt=b;
}
void zig(int &rt){//右旋
    int b=t[rt].ls;
    t[rt].ls=t[b].rs;
    t[b].rs=rt;
    up(rt);up(b);
    rt=b;
}
void insert(int &rt,int x){
    if(rt==0){
        t[++k].val=x;
        t[k].cnt=t[k].size=1;
        t[k].pri=rand()%1145140;
        rt=k;
        return;
    }
    t[rt].size++;
    if(x==t[rt].val){
        t[rt].cnt++;
        return;
    }
    if(x<t[rt].val){
        insert(t[rt].ls,x);
        if(t[t[rt].ls].pri<t[rt].pri)zig(rt);
    }
    else{
        insert(t[rt].rs,x);
        if(t[t[rt].rs].pri<t[rt].pri)zag(rt);
    }
}
void del(int &rt,int x){
    if(rt==0)return;
    if(t[rt].val==x){
        if(t[rt].cnt>1){
            t[rt].cnt--;
            t[rt].size--;
            return;
        }
        if(t[rt].ls==0||t[rt].rs==0){
            rt=t[rt].ls+t[rt].rs;
        }
        else{
            if(t[t[rt].ls].pri<t[rt].pri){
                zig(rt);del(rt,x);
            }
            else{
                zag(rt);del(rt,x);  
            }
        }
    }
    else if(x<t[rt].val){
        t[rt].size--;del(t[rt].ls,x);
    }
    else {
        t[rt].size--;del(t[rt].rs,x);
    }
}
int fRank(int rt,int x){
    if(rt==0)return 1;
    if(x==t[rt].val)return t[t[rt].ls].size+1;
    if(t[rt].val<x)return t[t[rt].ls].size+t[rt].cnt+fRank(t[rt].rs,x);
    else return fRank(t[rt].ls,x);
}
int fVal(int rt,int x){
    if(rt==0)return 0;
    if(t[t[rt].ls].size>=x)return fVal(t[rt].ls,x);
    else if(t[t[rt].ls].size+t[rt].cnt<x)return fVal(t[rt].rs,x-t[t[rt].ls].size-t[rt].cnt);
    else return t[rt].val;
}
const int INF=0x7f7f7f7f;
int fPre(int rt,int x){
    if(rt==0)return -INF;
    if(t[rt].val<x)return max(t[rt].val,fPre(t[rt].rs,x));
    else return fPre(t[rt].ls,x);
}
int fNext(int rt,int x){
    if(rt==0)return INF;
    if(t[rt].val>x)return min(t[rt].val,fNext(t[rt].ls,x));
    else return fNext(t[rt].rs,x);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    srand(time(NULL));
    memset(t,0,sizeof(t));
    int m,n,opt,v,xx,ans=0,last=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v;
        insert(root,v);
    }
    while(m--){
        cin>>opt>>xx;
        int x=xx^last;
        if(opt==1)insert(root,x);
        if(opt==2)del(root,x);
        if(opt==3){last=fRank(root,x);ans=ans^last;}
        if(opt==4){last=fVal(root,x);ans=ans^last;}
        if(opt==5){last=fPre(root,x);ans=ans^last;}
        if(opt==6){last=fNext(root,x);ans=ans^last;}
    }
    cout<<ans;
    return 0;
}

FHQ Treap

#include<bits/stdc++.h>
using namespace std;
const signed int MAXN=1.1e6;
struct FHQNode{
    int ls,rs;
    int val,pri,size;
}t[MAXN];
int tot=0,root=0,n,m,opt,Fx,last=0,Tx;
void up(int id){t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;return;}
void crt_node(int x){//新建
    ++tot;
    t[tot].size=1;
    t[tot].ls=t[tot].rs=0;
    t[tot].val=x;
    t[tot].pri=rand();
    return;
}
void split(int u,int x,int &L,int &R){
    if(u==0){L=R=0;return;}
    if(t[u].val<=x){
        L=u;//左边确定
        split(t[u].rs,x,t[u].rs,R);
    }
    else{
        R=u;//右边确定
        split(t[u].ls,x,L,t[u].ls);
    }
    up(u);
    return;
}
int merge(int L,int R){
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri){
        t[L].rs=merge(t[L].rs,R);
        up(L);
        return L;
    }
    else{
        t[R].ls=merge(L,t[R].ls);
        up(R);
        return R;
    }
}
int insert(int x){
    int L,R;
    split(root,x,L,R);
    crt_node(x);
    root=merge(merge(L,tot),R);
    return tot;
}
int deldot(int x){//删除第一个值为x的点
    int L,R,mid;
    split(root,x,L,R);
    split(L,x-1,L,mid);
    mid=merge(t[mid].ls,t[mid].rs);
    root=merge(merge(L,mid),R);
    return root;
}
int delall(int x){//删除所有的值为x的点
    int L,R,mid;
    split(root,x,L,R);
    split(L,x-1,L,mid);
    root=merge(L,R);
    return root;
}
int fRank(int x){
    int L,R,ans;
    split(root,x-1,L,R);
    ans=t[L].size+1;
    root=merge(L,R);
    return ans;
}
int kth(int u,int k){
    if(k==t[t[u].ls].size+1)return u;
    if(k<=t[t[u].ls].size)return kth(t[u].ls,k);
    return kth(t[u].rs,k-t[t[u].ls].size-1);
}
int fPre(int x){
    int L,R,ans;
    split(root,x-1,L,R);
    ans=t[kth(L,t[L].size)].val;
    root=merge(L,R);
    return ans;
}
int fNext(int x){
    int L,R,ans;
    split(root,x,L,R);
    ans=t[kth(R,1)].val;
    root=merge(L,R);
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        insert(v);
    }
    int ans=0;
    while(m--){
        cin>>opt>>Fx;
        Tx=Fx^last;
        if(opt==1)insert(Tx);
        else if(opt==2)deldot(Tx);
        else if(opt==3)last=fRank(Tx),ans^=last;
        else if(opt==4)last=t[kth(root,Tx)].val,ans^=last;
        else if(opt==5)last=fPre(Tx),ans^=last;
        else if(opt==6)last=fNext(Tx),ans^=last;
    }
    cout<<ans;
    return 0;
}

树链剖分/重链剖分

#include<bits/stdc++.h>
#define ls id<<1
#define rs id<<1|1
#define int long long// use long long is very important!
using namespace std;
int dep[100001],fa[100001],head[100001],siz[100001],son[100001],top[100001],tid[100001],pos[100001],tot=0,ord=0;
int a[100001];
int n,m,root,p,opt;//son:重儿子,tid和pos处理树上与链上的映射
struct edge{
    int to,nxt;
}ed[100001*2];
struct SegmentTreeNode{
    int L,R;
    int sum,lazy;
} t[100001*4];

inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}//快读
inline void write(int x){
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    //puts("");
}//快输

void addedge(int a,int b){
    ed[++tot].to=b;
    ed[tot].nxt=head[a];
    head[a]=tot;
}
void dfs1(int id,int father){
    dep[id]=dep[father]+1;
    fa[id]=father;
    siz[id]=1;
    son[id]=0;
    for(int i=head[id];i;i=ed[i].nxt){
        int t=ed[i].to;
        if(t!=father){
            dfs1(t,id);
            siz[id]+=siz[t];
            if(siz[t]>siz[son[id]])son[id]=t;
        }
    }
}
void dfs2(int id,int topp){//树链剖分
    top[id]=topp;
    pos[id]=++ord;
    tid[ord]=id;
    if(!son[id])return;
    dfs2(son[id],topp);
    for(int i=head[id];i;i=ed[i].nxt){
        int t=ed[i].to;
        if(t!=son[id]&&t!=fa[id])dfs2(t,t);
    }
}

void up(int id){
    t[id].sum=(t[ls].sum+t[rs].sum);
}
void down(int id){//处理编号id的为标记，下传给它的儿子
    if (!t[id].lazy) return;
    t[ls].lazy+=t[id].lazy;
    t[rs].lazy+=t[id].lazy;
    t[ls].sum+=((t[ls].R-t[ls].L+1)*t[id].lazy);
    t[rs].sum+=((t[rs].R-t[rs].L+1)*t[id].lazy);
    t[id].lazy=0;
}
void build(int id,int l,int r){
    t[id].L=l,t[id].R=r;
    t[id].lazy=0;t[id].sum=0;
    if(l==r){t[id].sum=a[tid[l]];return;}
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    up(id);
}
void update(int id,int l,int r,int val){//将l，r区间同时加上一个val
    if(t[id].L>r || t[id].R<l) return;
    if(t[id].L>=l && t[id].R<=r){//节点自己处理
        t[id].lazy+=val;
        t[id].sum+=(t[id].R-t[id].L+1)*val;
        return;
    }
    if(t[id].lazy!=0) down(id);
    int mid=(t[id].L+t[id].R)>>1;
    if(l<=mid)update(ls,l,r,val);
    if(r>mid)update(rs,l,r,val);
    up(id);
}

int ask_sum(int id,int l,int r){
    if(t[id].L>r || t[id].R<l) return 0;
    if(t[id].L>=l && t[id].R<=r) return t[id].sum;
    if(t[id].lazy !=0) down(id);
    return (ask_sum(ls,l,r)+ask_sum(rs,l,r));
}
void tree_update(int u,int v,int val){//树上更新
    //不同重链
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);//先从top的depth深的那条重链开始
        update(1,pos[top[u]],pos[u],val);
        u=fa[top[u]];//轻边
    }
    //同一重链
    if(dep[u]>dep[v])swap(u,v);
    update(1,pos[u],pos[v],val);
}
void subtree_update(int id,int val){//子树树上更新
    update(1,pos[id],pos[id]+siz[id]-1,val);
}
void node_update(int id,int x, int val) {
    if (t[id].L==t[id].R) {
        t[id].sum+=val;
        return;
    }
    down(id);
    int mid = (t[id].L+t[id].R)>>1;
    if (x<=mid)node_update(ls,x,val);
    else node_update(rs,x,val);
    up(id);
}
int tree_sum(int u,int v){
    int sum=0;
    //不同重链
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);//先从top的depth深的那条重链开始
        sum+=ask_sum(1,pos[top[u]],pos[u]);
        u=fa[top[u]];//轻边
    }
    //同一重链
    if(dep[u]>dep[v])swap(u,v);
    sum+=ask_sum(1,pos[u],pos[v]);
    return sum;
}
int subtree_sum(int id){
    return ask_sum(1,pos[id],pos[id]+siz[id]-1);
}
signed main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    memset(head,0,sizeof(head));
    n=read();m=read();
    root=1;p=2147483647;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }

    for(int i=1;i<n;i++){
        int x,y;
        x=read();y=read();
        addedge(x,y);addedge(y,x);
    }

    dfs1(root,0);
    dfs2(root,root);
    build(1,1,n);
    while(m--){
        opt=read();

    return 0;
}

点分治

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+50;
struct ed{
    int v,w;
};
vector<ed>e[N];
int root,dep[N],f[N],siz[N],n,k,m,que[N],S,tot,len[N];
bool vis[N],ans[10000001];
void getroot(int u,int fa){
    f[u]=0,siz[u]=1;
    for(auto x:e[u]){
        int v=x.v;
        if(vis[v]||v==fa)continue;
        getroot(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],S-siz[u]);
    if(f[u]<f[root])root=u;
}
void getdep(int u,int fa){
    for(auto x:e[u]){
        int v=x.v,w=x.w;
        if(v==fa||vis[v])continue;
        dep[v]=dep[u]+w;
        len[++tot]=dep[v];
        if(len[tot]<=10000000)ans[len[tot]]=1;
        getdep(v,u);
    }
}
void getans(int u){
    vector<int> total;
    total.push_back(0);
    for(auto x:e[u]){
        int v=x.v,w=x.w;
        if(vis[v])continue;
        tot=0;
        dep[v]=w;
        len[++tot]=w;
        if(w<=10000000)ans[w]=1;
        getdep(v,u);
        for(int i=1;i<=tot;i++){
            for(int d:total){
                int sum=len[i]+d;
                if(sum<=10000000)ans[sum]=1;
            }
        }
        for(int i=1;i<=tot;i++)total.push_back(len[i]);
    }
}
void sol(int u){
    vis[u]=1;
    getans(u);
    for(auto x:e[u]){
        int v=x.v;
        if(vis[v])continue;
        S=siz[v];
        root=0,f[root]=N;
        getroot(v,0);
        sol(root);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,cu,cv,cw;i<n;i++){
        scanf("%d%d%d",&cu,&cv,&cw);
        e[cu].push_back({cv,cw});
        e[cv].push_back({cu,cw});
    }
    for(int i=1;i<=m;i++)scanf("%d",&que[i]);
    S=n,f[0]=N,root=0;
    getroot(1,0);
    sol(root);
    for(int i=1;i<=m;i++)puts(ans[que[i]]?"AYE":"NAY");
}

缩点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100050;
int a[maxn],dfn[maxn],low[maxn],instack[maxn],ord=0,color[maxn],sum[maxn],color_cnt=0,rudu[maxn],dis[maxn],n,m,ans=0;
//color：强连通编号 sum：强连通权值和 color_cnt：强连通个数
vector<int> G[maxn],G2[maxn];
stack<int> stk;
void tarjan(int u){
    dfn[u]=low[u]=++ord;
    stk.push(u);
    instack[u]=1;
    for(int v:G[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        color_cnt++;
        while(true){
            int v=stk.top();
            color[v]=color_cnt;
            instack[v]=0;
            sum[color_cnt]+=a[v];
            stk.pop();
            if(u==v)break;
        }
    }

}
void tp(){//拓扑
    queue<int>q;
    for(int i=1;i<=color_cnt;i++){
        if(!rudu[i]){
            q.push(i);
            dis[i]=sum[i];
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i:G2[u]){
            dis[i]=max(dis[i],dis[u]+sum[i]);
            if(--rudu[i]==0)q.push(i);
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int u=1;u<=n;u++){
        int uu=color[u];
        for(int v:G[u]){
            int vv=color[v];
            if(uu!=vv){
                G2[uu].push_back(vv);
                rudu[vv]++;
            }
        }
    }
    tp();
    cout<<ans;
    return 0;
} 

字典树

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
struct cnt_trie{
    vector<vector<int>>ch;
    vector<int>cnt;
    int ct=0;
    int gn_map[128];
    //如果用全局数组，不用vector，常数约为1/2
    void clear(){
        ch.clear();
        cnt.clear();
        ch.push_back(vector<int>(65, 0)); // 初始化根节点
        cnt.push_back(0);
        ct=0;
    }
    cnt_trie(){cnt_trie::init_gn();clear();}
    void init_gn() {
        for(int i=0;i<128;i++) gn_map[i]=-1;
        for(char c='A';c<='Z';c++) gn_map[c]=c-'A';
        for(char c='a';c<='z';c++) gn_map[c]=c-'a'+26;
        for(char c='0';c<='9';c++) gn_map[c]=c-'0'+52;
    }
    inline int gn(char x){return gn_map[(int)x];}
    void insert(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]){
                ch.push_back(vector<int>(65, 0));//全局数组就不用这两个push_back，直接用
                cnt.push_back(0);
                ch[p][c]=++ct;
            }
            p=ch[p][c];
            cnt[p]++;
        }
    }
    int find_cnt(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]) return 0;
            p=ch[p][c];
        }
        return cnt[p];
    }
    pair<int,int> find_range(string str){
        int p=0,l=str.size();
        for(int i=0;i<l;i++){
            int c=gn(str[i]);
            if(!ch[p][c]) return {0,0};
            p=ch[p][c];
        }
        return {p,ct};
    }
};
int main(){
    int T;
    cin>>T;
    cnt_trie tri;
    while(T--){
        tri.clear();
        int n,q;
        cin>>n>>q;
        while(n--){
            string s;
            cin>>s;
            tri.insert(s);
        }
        while(q--){
            string qr;
            cin>>qr;
            cout<<tri.find_cnt(qr)<<endl;
        }
    }
    return 0;
} 

文艺平衡树

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*114514;
struct FHQNode{
    int ls,rs;
    int val,pri,size;
    int lazy;
}t[maxn];
int tot=0,root=0,n,m;
void crt_node(int x){
    ++tot;
    t[tot].size=1;
    t[tot].lazy=t[tot].ls=t[tot].rs=0;
    t[tot].val=x;
    t[tot].pri=rand();
    return;
}
void up(int id){
    t[id].size=t[t[id].ls].size+t[t[id].rs].size+1;
}
void down(int id){
    if(t[id].lazy){
        swap(t[id].ls,t[id].rs);
        t[t[id].ls].lazy^=1;
        t[t[id].rs].lazy^=1;
        t[id].lazy=0;
    }
}
void split(int id,int x,int &L,int &R){
    if(id==0){L=R=0;return;}
    down(id);
    if(t[t[id].ls].size+1<=x){
        L=id;
        split(t[id].rs,x-t[t[id].ls].size-1,t[id].rs,R);
    }
    else {
        R=id;
        split(t[id].ls,x,L,t[id].ls);
    }
    up(id);
    return;
}
int merge(int L,int R){
    if(L==0||R==0)return L+R;
    if(t[L].pri>t[R].pri){
        down(L);
        t[L].rs=merge(t[L].rs,R);
        up(L);
        return L;
    }
    else{
        down(R);
        t[R].ls=merge(L,t[R].ls);
        up(R);
        return R;
    }
}
void print(int id){
    if(id==0)return;
    down(id);

    print(t[id].ls);
    printf("%d ",t[id].val);
    print(t[id].rs);//中序遍历
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        crt_node(i);
        root=merge(root,tot);
    }
    while(m--){
        int l,r,L,R,mid;
        cin>>l>>r;
        split(root,r,L,R);
        split(L,l-1,L,mid);
        t[mid].lazy^=1;
        root=merge(merge(L,mid),R);
    }
    print(root);
    return 0;
}

网络流

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205,M=5005,inf=2147483647;
int n,m,s,t;
int dis[N];
struct edge{
    int l,r,c;
    int nxt;
}ed[M*2];
int head[N],cnt=2;
void adde(int l,int r,int c){
    ed[cnt].l=l;
    ed[cnt].r=r;
    ed[cnt].c=c; 
    ed[cnt].nxt=head[l];
    head[l]=cnt;
    cnt++; 
}
bool bfs(){
    queue<int> q;
    for(int i=1;i<=n;i++) dis[i]=-1;
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(int i=head[curr];i;i=ed[i].nxt){
            if(dis[ed[i].r]==-1&&ed[i].c>0){
                dis[ed[i].r]=dis[curr]+1;  
                q.push(ed[i].r);
                if(ed[i].r==t)return 1;
            }
        }
    }
    return(dis[t]!=-1);
}
int dfs(int start,int flow){
    int cnt=0; 
    if(start==t) return flow;
    for(int i=head[start];i&&flow;i=ed[i].nxt){ 
        if((ed[i].c>0)&&(dis[ed[i].r]==dis[start]+1)){
            int ret=dfs(ed[i].r,min(flow,ed[i].c)); 
            if(ret==0)dis[ed[i].r]=inf;
            if(ret>0){
                ed[i].c-=ret; 
                ed[i^1].c+=ret;
                cnt+=ret;
                flow-=ret; 
            }
        }
    }   
    return cnt; 
}
void dinic(){
    int ans=0;
    while(bfs()){ 
        ans+=dfs(s,inf);
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adde(u,v,w);
        adde(v,u,0);
    }
    dinic();
    return 0;
}

二分图

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
vector<int> G[maxn];
int match[maxn],ans=0;
bool matched[maxn];
bool find(int u){
    for(int v:G[u]){
        if(!matched[v]){
            matched[v]=1;
            if(!match[v]||find(match[v])){
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}
int main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,e;
    cin>>n>>m>>e;
    for(int i=0;i<e;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        memset(matched,0,sizeof(matched));
        if(find(i))ans++;
    }
    cout<<ans;
    return 0;
} 

Dijkstra

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1100010,inf=0x7fffffff;
struct edge{
    int to,w;
};
vector<edge> G[maxn];
struct qnode{
    int id,val;
    qnode(int d,int v){id=d; val=v;}
    bool friend operator<(qnode n1,qnode n2)
    {
        return n1.val>n2.val;
    }
};
int dis[maxn],n,m,s;
bool vis[maxn];
priority_queue<qnode> q;
void dijkstra(){
    for(int i=1;i<=n;i++)dis[i]=inf;
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push(qnode(s,0));
    while(!q.empty()){
        qnode qnd=q.top();q.pop();
        int u=qnd.id;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].to,w=G[u][i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(qnode(v,dis[v]));//松弛
            }
        }
    }
}
signed main(){  
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G[u].push_back({v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]==inf) cout<<(1<<31)-1<<' ';
        else cout<<dis[i]<<' ';
    }
    return 0;
} 

可持久化线段树1

//“你说得对，但是主席树十分持♂久♂，因为它可→持↑久↓化→”
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e7+100;
int cnt=1,a[MAXN],n,m,roots[MAXN];

struct Tree{
    int L,R,val;
}t[MAXN*4];

inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}return x*f;}//快读
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}//快输

int crt_node(int id){
    cnt++;
    t[cnt]=t[id];
    return cnt;
}
int build(int id,int l,int r){
    id=++cnt;
    if(l==r){
        t[id].val=a[l];
        return cnt;
    }
    int mid=(l+r)>>1;
    t[id].L=build(t[id].L,l,mid);
    t[id].R=build(t[id].R,mid+1,r);
    return id;
}
int update(int id,int l,int r,int x,int val){
    id=crt_node(id);
    if(l==r)t[id].val=val;
    else{
        int mid=(l+r)>>1;
        if(x<=mid)t[id].L=update(t[id].L,l,mid,x,val);
        else t[id].R=update(t[id].R,mid+1,r,x,val);
    }
    return id;  
}
int ask(int id,int l,int r,int x){
    if(l==r)return t[id].val;//单点
    int mid=(l+r)>>1;
    if(x<=mid)return ask(t[id].L,l,mid,x);//在左
    else return ask(t[id].R,mid+1,r,x);//在右
}
int main(){
    int v,loc,val;
    int opt;
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    roots[0]=build(0,1,n);
    for(int i=1;i<=m;i++){
        v=read();opt=read();loc=read();
        if(opt==1){
            val=read();
            roots[i]=update(roots[v],1,n,loc,val);
        }
        else{
            write(ask(roots[v],1,n,loc)),puts("");
            roots[i]=roots[v];
        }
    }
    return 0;
}