板子

问题

1. 线段树码风不好,被批了,以后用rt做根.
2. 部分码风有点旧,将就着看.

写在前面,一些约定

除非特殊说明,数组有效空间是[1,n].

时间复杂度的所有涉及到 $\log$ 的默认 $\log_2$ .

顺序:快读,基本函数,数据结构,图论,数学,计算几何.

快读,基本函数

快读快写

std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

关同步流.

#include<bits/stdc++.h>
#define enter fout<<"\n"
#define space fout<<" "
#define dot fout<<","
#define oui fout<<"Yes"
#define non fout<<"No"
#define si fout<<"?"
using namespace std;
namespace fastio{
    const int bufl=1<<20;
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
        template<typename Temp>inline void getDouble(Temp &a){a=0;int b=0,c=getChar(),d=0;__int128 e=0,f=0;while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)e=(e<<1)+(e<<3)+c-48,c=getChar();if(c==46){c=getChar();while(c>=48&&c<=57)d++,f=(f<<1)+(f<<3)+c-48,c=getChar();}a=e+base1[d]*f;if(b)a=-a;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
        IN& operator>>(__int128 &a){getInt(a);return *this;}
        IN& operator>>(float &a){getDouble(a);return *this;}
        IN& operator>>(double &a){getDouble(a);return *this;}
        IN& operator>>(long double &a){getDouble(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=0.5;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=0.5;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
        template<typename Temp>inline void putLeading(Temp a,int b){if(!b)return;putLeading(a/10,b-1);putChar(a%10+48);}
        template<typename Temp>inline void putDouble(Temp a){if(a<0){putChar(45);a=-a;}__int128 b=a;putInt(b);a-=b;a*=base2[Eps];b=a+Acc;putChar(46);putLeading(b,Eps);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(const char *a){while(*a)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        OUT& operator<<(__int128 a){putInt(a);return *this;}
        OUT& operator<<(unsigned int a){putInt(a);return *this;}
        OUT& operator<<(unsigned long long a){putInt(a);return *this;}
        OUT& operator<<(unsigned __int128 a){putInt(a);return *this;}
        OUT& operator<<(float a){putDouble(a);return *this;}
        OUT& operator<<(double a){putDouble(a);return *this;}
        OUT& operator<<(long double a){putDouble(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;

long long n,m,res;
//#define NaraFluorine
int main(){
    #ifdef NaraFluorine
    freopen("P_.in","r",stdin);
    freopen("std.out","w",stdout);
    #endif
    int t;
    fin>>t;
    while(t--){
        fin>>n>>m;
        res=0;
        
        
        
        
        fout<<res<<'\n';
    }
    return 0;
}

fin替代cin,fout替代cout.其中eps默认的6是保留几位小数,可以改.

#include<bits/stdc++.h>
#define enter putchar('\n')
#define space putchar(' ')
#define dot putchar(',')
#define oui putchar('Y'),putchar('e'),putchar('s')
#define non putchar('N'),putchar('o')
#define si putchar('?')
using namespace std;

const unsigned int bufsize=1<<21;
char buf[bufsize],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bufsize,stdin),p1==p2)?EOF:*p1++)
char obuf[bufsize],*p3=obuf;
#define putchar(x) (p3-obuf<(bufsize))?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename T>void read(T &sum){
    int tf=0;
    char ch=getchar();
    sum=0;
    while(ch<'0'||ch>'9')
        tf=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')
        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
    (tf)&&(sum=-sum);
}
template<typename T,typename ...Args>void read(T &tmp,Args &...tmps){
    read(tmp);
    read(tmps...);
}
template<typename T>void printt(T x){
    if(x>=10)printt(x/10);
    putchar(x%10+48);
}
template<typename T>void print(T x){
    x<0?putchar('-'),printt(-x):printt(x);
}
template<typename T,typename ...Args>void print(T tmp,Args ...tmps){
    print(tmp);
    putchar(' ');
    print(tmps...);
}
template<typename T>void put(T x){
    print(x),putchar('\n');
}
template<typename T,typename ...Args>void put(T tmp,Args ...tmps){
    put(tmp);
    put(tmps...);
}

void readc(char &a){//获取一个字符,自动过滤空格回车 
    a=getchar();
    while(a==' '||a=='\n'||a=='\r')
        a=getchar();
}
template<char,typename ...Args>
void readc(char &a,Args &...b){
    readc(a);
    readc(b...);
}
//下面这俩是打印十六进制数和二进制数的 
template<typename T>void bprint(T x){
    (x>=2)?(bprint(x>>1),putchar('0'+(x&1))):(putchar('0'+(x&1)));
}
template<typename T>void xprint(T x){
    ((x^(x&0xf))!=0)?(xprint(x>>4),x&=0xf,(x>=10)?(putchar('A'+x-10)):(putchar('0'+x))):((x>=10)?(putchar('A'+x-10)):(putchar('0'+x)));
}




int t;
long long n,m,res;
//#define NaraFluorine
signed main(){
    #ifdef NaraFluorine
    freopen("P_.in","r",stdin);
    freopen("std.out","w",stdout);
    #endif
    read(t);
    while(t--){
        res=0;
        read(n,m);
        



        put(res);
    }
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}

位运算

template<typename T>inline T lowbit(T a){
    return a&-a;
}
inline int lowcnt(int num){
    return __builtin_ctz(num);
}//最低位1之前有多少个0
inline int lowcnt(long long num){
    return __builtin_ctzll(num);
}
inline int highcnt(int num){
    return __builtin_clz(num);
}//最高位1之后有多少个0
inline int highcnt(long long num){
    return __builtin_clzll(num);
}
inline int cnt1(int num){
    return __builtin_popcount(num);
}//统计这个数有多少个位是1
inline int cnt1(long long num){
    return __builtin_popcountll(num);
}
inline int even1(int num){
    return __builtin_parity(num);
}//这个数1的个数的奇偶
inline int even1(long long num){
    return __builtin_parityll(num);
}
inline int low1(int num){
    return __builtin_ffs(num);
}//最低位1是第几位
inline int low1(long long num){
    return __builtin_ffsll(num);
}
inline int highreal(int num){
    return __builtin_clrsb(num);
}//如果符号位是0返回前导0个数-1,否则返回前导1个数-1
inline int highreal(long long num){
    return __builtin_clrsbll(num);
}
#define abs(x) ((x^(x>>31))-(x>>31))
#define abs64(x) ((x^(x>>63))-(x>>63))
#define abs128(x) ((x^(x>>127))-(x>>127))
//绝对值

for(int i=num;i;i=(i-1)&num){
    //do something
}//枚举二进制子集(降序)

//0 is here
for(int i=0;(1<<i)-1<=num;i++){
    for(int x=(1<<i)-1,t;x<=num;t=x+(x&-x),x=(t|((((t&-t)/(x&-x))>>1)-1))){
        //do something
    }
}//二进制1位数相同数的枚举顺序增序排列,O(n)

常用库函数

template<typename T1,typename T2>
char cmax(T1& num,T2 val){
    return (num<=val)?(num=val,1):0;
}
template<typename T1,typename T2>
char cmin(T1& num,T2 val){
    return (num>=val)?(num=val,1):0;
}

数据结构

排序(归并排序) 逆序对

鉴于不好封装,保留源码了,res是逆序对,dat是需要排序的数组,ddat是辅助数组,程序跑完之后元素也会排序,区间 [0,n-1] 或 [1,n] 都可以.

long long res=0,dat[500001],ddat[500001];
void ssort(int l,int mid,int r){
    int hi=l,ho=mid+1,top=l;
    while(hi<=mid&&ho<=r){
        if(dat[hi]>dat[ho]){
            res+=mid-hi+1;
            ddat[top++]=dat[ho++];
        }else{
            ddat[top++]=dat[hi++];
        }
    }
    while(hi<=mid){
        ddat[top++]=dat[hi++];
    }
    while(ho<=r){
        ddat[top++]=dat[ho++];
    }
}
void msort(int l,int r){
    if(l>=r)return;
    int mid=(l+r)/2;
    msort(l,mid);
    msort(mid+1,r);
    ssort(l,mid,r);
    for(int o=l;o<=r;++o){
        dat[o]=ddat[o];
    }
}

二分(最小值)

比某个数大的数都满足某个性质.

template<typename T>
char BSCheck(T num){
    //checker自己写 
    
    
    
}
template<typename T>
T BS(T l,T r){//范围[l,r]
    T mid;
    while(l<r){
        mid=(l+r)>>1;
        if(BSCheck(mid))r=mid;
        else l=mid+1;
    }
    return l;
}

二分(最大值)

比某个数小的数都满足某个性质.

template<typename T>
char BSCheck(T num){
    //checker自己写 
    
    
    
}
template<typename T>
T BS(T l,T r){//范围[l,r]
    r++;
    T mid;
    while(l<r){
        mid=(l+r)>>1;
        if(BSCheck(mid))l=mid+1;
        else r=mid;
    }
    return r-1;
}

三分(最小值)

三分的板子,由于三分区间比较宽,我们使用eeps来限定误差,超出误差直接手动判定答案.
为啥要用三分?因为考试考,就让你两个点同时判断,只能三分.

template<typename T>
T TriSearch(T l,T r){//[l,r]
    T ll,rr,res,eeps=2;
    while(l+eeps<r){
        ll=((l<<1)+r)/3;
        rr=((r<<1)+l)/3;
        //Check
        
        
        if(){//[rr+1,r]
            l=rr+1;
        }else if(){//[ll+1,rr]
            l=ll+1;
            r=rr;
        }else{//[l,ll]
            r=ll;
        }
    }
    //Check
    
    
    if(){
        return l+2;
    }else if(){
        return l+1;
    }else{
        return l;
    }
}

搜联通块

char dat[1010][1010];
int n,m;
int dfs(int y,int x){
    return (y<0||x<0||y>n||x>m||dat[y][x]=='.')?0:(dat[y][x]='.',dfs(y+1,x)+dfs(y-1,x)+dfs(y,x+1)+dfs(y,x-1)+1);
}

并查集(路径压缩)(DSU)

struct dsu{
    int *ko,n;
    dsu(int num=1000000):n(num+5){
        ko=new int[num+5];
    }
    void init(int num=-1){
        if(num==-1)num=n;
        for(int i=0;i<num;++i){
            ko[i]=i;
        }
    }
    int ffind(int num){
        return ko[num]==num?num:ko[num]=ffind(ko[num]);
    }
    void uunion(int a,int b){//<--
        ko[ffind(b)]=ffind(a);
    }//b被a合并 
    char isUnion(int a,int b){
        return (ffind(a)==ffind(b))?1:0;
    }
};

链表

首尾链表,插入是倒着插的,支持快速合并(然而没有什么卵用).

template<typename T>
struct htlist{/*head-Tail-List*/
    struct node{
        int next;
        T val;
    };
    node* dat;
    int *sz,*head,*tail;
    int siz,top,n;
    htlist(int num=200010,int nn=100010):siz(num),n(nn),top(0){
        sz=new int[num]{};
        head=new int[num]{};
        tail=new int[num]{};
        dat=new node[num];
    }
    void add(int pos,T val){
        sz[pos]++;
        dat[++top].val=val;
        dat[top].next=head[pos];
        head=top;
        if(sz[pos]==1){
            tail[pos]=top;
        }
    }
    void merge(int a,int b){
        sz[b]+=sz[a];
        sz[a]=0;
        dat[tail[a]].next=head[b];
        head[b]=head[a];
        head[a]=tail[a]=0;
    }
    void size(int pos){
        return sz[pos];
    }
};

ST表

struct st{
    i64 sst[200010][20];
    void init(i64* dat,int n){
        for(int i=1;i<=n;++i){
            sst[i][0]=dat[i];
        }
        for(int i=1;i<=19;++i){
            for(int j=1;j+(1<<i)-1<=n;++j){
                sst[j][i]=max(sst[j][i-1],sst[j+(1<<(i-1))][i-1]);
            }
        }
    }
    i64 qquery(int l,int r){
        if(l>r)return 0;
        i64 k=log2(r-l+1);
        return max(sst[l][k],sst[r-(1<<k)+1][k]);
    }
};

区间划分

把一块非常大的[l,r]询问划分成左中右三部分,其中一块固定长度的区间信息非常好维护.

long long segDiv(i64 l,i64 r){
    long long lm=(l+n-1)/n*n,rl=(r-1)/n*n+1,block=((r-1)/n)-((l-1)/n)-1;//整块个数
    fout<<l<<" "<<lm<<" "<<rl<<" "<<r<<" "<<block<<"\n";
    long long res=0;
    if(block>=1){//中间至少存在一块,区间是[l,lm],[block*sum],[rl,r]
        // a
    }else if(block==0){//中间隔着一条区块线,[l,lm][rl,r]
        // a
    }else{//都在一个区块里面,[l,r],!区间编号分别是(x-1)/n默认区间从0开始!
        // a
    }
    return res;
}

树状数组

struct fenwick{//树状数组 fenwick
    #define lowbit(x) (x&-x)
    vector<int>ddat;
    int n;
    void resize(){
        ddat.resize(n+10,0);
        for(int i=0;i<=n+5;++i){
            ddat[i]=0;
        }
    }
    fenwick(int sz){
        n=sz;
        resize();
    }
    void bbuild(i64* dat,int n){//建树 
        for(int i=1;i<=n;++i){
            ddat[i]+=dat[i];
            int j=i+lowbit(i);
            if(j<=n)ddat[j]+=ddat[i];//向后找爹加和,实现O(n)建树 
        }
    }
    void aadd(int pos,int val){
        for(;pos<=n;pos+=lowbit(pos)){
            ddat[pos]+=val;
        }
    }
    long long qquery(int pos){//[1,pos]
        long long res=0;
        for(;pos;pos-=lowbit(pos)){
            res+=ddat[pos];
        }
        return res;
    }
    int lower_bound(int s){
        int ans=0,k=0,b=0;
        for(;(1<<k)<=n;k++);
        for(k--;k>=0;k--){
            b=1<<k;
            if(ans+b<=n&&ddat[ans+b-1]<s){
                ans^=b;
                s-=ddat[ans-1];
            }
        }
        return ans;
    }
    int upper_bound(int s){
        int ans=0,k=0,b=0;
        for(;(1<<k)<=n;k++);
        for(k--;k>=0;k--){
            b=1<<k;
            if(ans+b<=n&&ddat[ans+b-1]<=s){
                ans^=b;
                s-=ddat[ans-1];
            }
        }
        return ans;
    }
};

线段树(lazy,mulazy)

给的还是区间加乘的板子.

struct segtree{
    struct node{
        int l,r;
        long long val,lazy,mulazy;
    };
    node *dat;
    const long long p;//x mod p
    int top=0;
    segtree(int mxxn=500000,long long mod=998244353):p(mod){
        dat=new node[mxxn+5];
    }
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            fin>>dat[++top].val;
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].mulazy=1;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].val=(dat[dat[tmp].l].val+dat[dat[tmp].r].val)%p;
        return tmp;
    }
    void llazy(int mod,int l,int r){//down stream
        if(dat[mod].mulazy!=1||dat[mod].lazy!=0){
            int mid=(l+r)>>1;
            dat[dat[mod].l].val=(dat[dat[mod].l].val*dat[mod].mulazy%p+dat[mod].lazy*(mid-l+1)%p)%p;
            dat[dat[mod].r].val=(dat[dat[mod].r].val*dat[mod].mulazy%p+dat[mod].lazy*(r-mid)%p)%p;
            dat[dat[mod].l].lazy=(dat[dat[mod].l].lazy*dat[mod].mulazy%p+dat[mod].lazy)%p;
            dat[dat[mod].r].lazy=(dat[dat[mod].r].lazy*dat[mod].mulazy%p+dat[mod].lazy)%p;
            dat[dat[mod].l].mulazy=(dat[dat[mod].l].mulazy*dat[mod].mulazy)%p;
            dat[dat[mod].r].mulazy=(dat[dat[mod].r].mulazy*dat[mod].mulazy)%p;
            dat[mod].mulazy=1;
            dat[mod].lazy=0;
        }
    }
    void aaddchange(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].val=(dat[mod].val+val*(r-l+1)%p)%p;
            dat[mod].lazy=(dat[mod].lazy+val)%p;
            return;
        }
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        if(tl<=mid)aaddchange(dat[mod].l,l,mid,tl,tr,val);
        if(tr>mid)aaddchange(dat[mod].r,mid+1,r,tl,tr,val);
        dat[mod].val=(dat[dat[mod].l].val+dat[dat[mod].r].val)%p;
    }
    void mmulchange(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].val=(dat[mod].val*val)%p;
            dat[mod].mulazy=(dat[mod].mulazy*val)%p;
            dat[mod].lazy=(dat[mod].lazy*val)%p;
            return;
        }
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        if(tl<=mid)mmulchange(dat[mod].l,l,mid,tl,tr,val);
        if(tr>mid)mmulchange(dat[mod].r,mid+1,r,tl,tr,val);
        dat[mod].val=(dat[dat[mod].l].val+dat[dat[mod].r].val)%p;
    }
    long long qquery(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].val;
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        long long res=0;
        if(tl<=mid)res=(res+qquery(dat[mod].l,l,mid,tl,tr))%p;
        if(tr>mid)res=(res+qquery(dat[mod].r,mid+1,r,tl,tr))%p;
        return res;
    }
};

线段树(lazy)

给的是维护区间加和和lazytag的板子.

#define mxxn 2000000
struct segtree{
    struct segtreenode{
        int l,r;
        long long val,lazy;
    };
    segtreenode dat[mxxn];
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            read(dat[++top].val);
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].val=dat[dat[tmp].l].val+dat[dat[tmp].r].val;
        return tmp;
    }
    void llazy(int mod,int l,int r){//down stream
        if(dat[mod].lazy!=0){
            int mid=(l+r)>>1;
            dat[dat[mod].l].val+=dat[mod].lazy*(mid-l+1);
            dat[dat[mod].r].val+=dat[mod].lazy*(r-mid);
            dat[dat[mod].l].lazy+=dat[mod].lazy;
            dat[dat[mod].r].lazy+=dat[mod].lazy;
            dat[mod].lazy=0;
        }
    }
    void aaddchange(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].val=dat[mod].val+val*(r-l+1);
            dat[mod].lazy=dat[mod].lazy+val;
            return;
        }
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        if(tl<=mid)aaddchange(dat[mod].l,l,mid,tl,tr,val);
        if(tr>mid)aaddchange(dat[mod].r,mid+1,r,tl,tr,val);
        dat[mod].val=dat[dat[mod].l].val+dat[dat[mod].r].val;
    }
    void aaddchange(int mod,int l,int r,int pos,long long val){
        if(l>=r){
            dat[mod].val+=val;
            return;
        }
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        if(pos<=mid)aaddchange(dat[mod].l,l,mid,pos,val);
        else aaddchange(dat[mod].r,mid+1,r,pos,val);
        dat[mod].val=dat[dat[mod].l].val+dat[dat[mod].r].val;
    }
    long long qquery(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].val;
        llazy(mod,l,r);
        int mid=(l+r)>>1;
        long long res=0;
        if(tl<=mid)res+=qquery(dat[mod].l,l,mid,tl,tr);
        if(tr>mid)res+=qquery(dat[mod].r,mid+1,r,tl,tr);
        return res;
    }
};

线段树(权值)

#define mxxn 600000
struct segtree{//这个是权值线段树,由于区间加和,假如要求严格小于的有多少个就-1+1来弥补. 
    struct node{
        int l,r,val,cls;//
    };
    #define ls dat[mod].l
    #define rs dat[mod].r
    node dat[mxxn];
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            dat[++top].val=0;
            dat[top].cls=0;
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].cls=0;
        dat[tmp].val=dat[dat[tmp].l].val+dat[dat[tmp].r].val;
        return tmp;
    }
    void push_down(int mod){
        if(dat[mod].cls!=0){
            dat[ls].cls=1;dat[rs].cls=1;
            dat[ls].val=0;dat[rs].val=0;
            dat[mod].cls=0;
        }
    }
    void aadd(int mod,int l,int r,int pos,int val){//某点加多少 
        if(l>=r){
            dat[mod].val+=val;
            return;
        }
        dat[mod].val+=val;
        int mid=(l+r)>>1;
        push_down(mod);
        if(pos<=mid)aadd(dat[mod].l,l,mid,pos,val);
        else aadd(dat[mod].r,mid+1,r,pos,val);
    }
    long long qquery(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].val;
        int mid=(l+r)>>1;
        push_down(mod);
        long long res=0;
        if(tl<=mid)res+=qquery(ls,l,mid,tl,tr);
        if(tr>mid)res+=qquery(rs,mid+1,r,tl,tr);
        return res;
    }
    void clear(){//清空整棵树
        top=0;
    }
    void cclear(){//清空线段树,待会还得用这棵树
        dat[1].val=0;
        dat[1].cls=1;
    }
};

线段树(权值查找)

支持某点加,区间求和,快速查找大于(小于)等于某个数的数字(空值返回-1或1145141919).

#define mxxn 20000010
#define ls dat[mod].l
#define rs dat[mod].r
struct segtree{//这个是权值线段树,由于区间加和,能查找元素
    struct segtreenode{
        int l,r,val,vval;
    };
    segtreenode dat[mxxn];
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            ++top;
            if(s[l-1]=='1'){
                dat[top].val=1;
            }
            dat[top].vval=l;
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].val=dat[dat[tmp].l].val+dat[dat[tmp].r].val;
        return tmp;
    }
    void aadd(int mod,int l,int r,int pos,int val){//某点变成什么值
        if(l>=r){
            dat[mod].val=val;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)aadd(dat[mod].l,l,mid,pos,val);
        else aadd(dat[mod].r,mid+1,r,pos,val);
        dat[mod].val=dat[ls].val+dat[rs].val;
    }
    int qqquery(int mod,int l,int r,int pos){//查询pos单点 
        if(l>=r)return dat[mod].val;
        int mid=(l+r)>>1;
        if(pos<=mid)return qqquery(dat[mod].l,l,mid,pos);
        else return qqquery(dat[mod].r,mid+1,r,pos);
    }
    int get_and_pre(int mod,int l,int r,int pos){//查询第一个小于等于pos的数字
        if(dat[mod].val==0)return -1;
        if(l>=r){return l;}
        int mid=(l+r)>>1;
        if(pos<=mid)return get_and_pre(ls,l,mid,pos);
        int res=-1;
        if(dat[rs].val!=0)res=max(res,get_and_pre(rs,mid+1,r,pos));
        if(res==-1)res=max(res,get_and_pre(ls,l,mid,pos));
        return res;
    }
    int get_and_aft(int mod,int l,int r,int pos){//查询第一个大于等于pos的数字
        if(dat[mod].val==0)return 1145141919;
        if(l>=r){return l;}
        int mid=(l+r)>>1;
        if(pos>mid)return get_and_aft(rs,mid+1,r,pos);
        int res=1145141919;
        if(dat[ls].val!=0)res=min(res,get_and_aft(ls,l,mid,pos));
        if(res==1145141919)res=min(res,get_and_aft(rs,mid+1,r,pos));
        return res;
    }
};

线段树(连续子段)

单点修改,问一个区间里最长连续相同的长度是多少.

char str[1000000];
#define mxxn 2000000
struct segtree{
    struct segtreenode{
        int l,r;
        int fall,len;//整段是不是一个字符 区间长度
        int val;//区间内的最大值
        char lc,rc;//左端右端字符
        int lb,rb;//左端右端长度
    };
    segtreenode dat[mxxn];
    #define ls dat[mod].l
    #define rs dat[mod].r
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            ++top;
            dat[top].fall=dat[top].len=1;
            dat[top].val=1;
            dat[top].lc=dat[top].rc=str[l];
            dat[top].lb=dat[top].rb=1;
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].len=dat[dat[tmp].l].len+dat[dat[tmp].r].len;
        push_up(tmp);
        return tmp;
    }
    void push_up(int mod){
        if(dat[ls].rc==dat[rs].lc){
            dat[mod].val=max({dat[ls].val,dat[rs].val,dat[ls].rb+dat[rs].lb});
        }else{
            dat[mod].val=max({dat[ls].val,dat[rs].val});
        }
        if(dat[mod].val==dat[mod].len){
            dat[mod].fall=1;
        }else{
            dat[mod].fall=0;
        }
        dat[mod].lc=dat[ls].lc;
        dat[mod].lb=dat[ls].lb;
        dat[mod].rc=dat[rs].rc;
        dat[mod].rb=dat[rs].rb;
        if(dat[ls].rc==dat[rs].lc){
            if(dat[ls].fall==1){
                dat[mod].lb+=dat[rs].lb;
            }
            if(dat[rs].fall==1){
                dat[mod].rb+=dat[ls].rb;
            }
        }
    }
    array<int,6> qquery(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr){
            return {dat[mod].val,dat[mod].lc,dat[mod].lb,dat[mod].rc,dat[mod].rb,dat[mod].fall};
        }
        int mid=(l+r)>>1;
        array<int,6>res={0,0,0,0,0,0},rres={0,0,0,0,0,0};
        if(tl<=mid){
            res=qquery(ls,l,mid,tl,tr);
            if(tr>mid){
                rres=qquery(rs,mid+1,r,tl,tr);
                if(res[3]==rres[1]){
                    res[0]=max({res[0],rres[0],res[4]+rres[2]});
                    if(res[5]==1){
                        res[2]+=rres[2];
                    }
                    if(rres[5]==1){
                        rres[4]+=res[4];
                    }
                }else{
                    res[0]=max({res[0],rres[0]});
                }
                res[3]=rres[3];
                res[4]=rres[4];
                return res;
            }else{
                return res;
            }
        }else{
            if(tr>mid){
                rres=qquery(rs,mid+1,r,tl,tr);
                return rres;
            }else{
                assert(0);
            }
        }
    }
    void cchange(int mod,int l,int r,int tl,int tr,char vval){
        if(tl<=l&&r<=tr){
            dat[mod].lc=dat[mod].rc=str[l]=vval;
            return;
        }
        int mid=(l+r)>>1;
        if(tl<=mid)cchange(ls,l,mid,tl,tr,vval);
        if(tr>mid)cchange(rs,mid+1,r,tl,tr,vval);
        push_up(mod);
    }
};

吉司机线段树(势能线段树 Segment Beats)

给定板子支持区间加上某个数,求区间最大最小值,区间和,区间修改为 $\min(a_i,k)$ 以及 $\max(a_i,k)$ .

struct segtree{
    #define ls dat[mod].l
    #define rs dat[mod].r
    const long long inf=0x00ffffffffffffff;
    struct node{
        long long val;
        long long mx,se,cnt;//区间最大值,严格次大值
        long long mn,sn,cnn;//区间最小值,严格次小值
        long long tgmx,tgmn,tgsu;//maxtag,mintag,区间tgsutag
        int l,r;
        /*
        0
        x -inf 1
        x inf  1
        -inf inf 0
        x x
        */
    };
    node *dat;
    long long *a;
    int top;
    segtree(int num=1000000,int nnum=500000){
        dat=new node[num+5];
        a=new long long[nnum+5];
        top=0;
    }
    void push_up(int mod){
        dat[mod].val=dat[ls].val+dat[rs].val;
        dat[mod].mx=max(dat[ls].mx,dat[rs].mx);
        dat[mod].mn=min(dat[ls].mn,dat[rs].mn);
        if(dat[ls].mx==dat[rs].mx){
            dat[mod].cnt=dat[ls].cnt+dat[rs].cnt;
            dat[mod].se=max(dat[ls].se,dat[rs].se);
        }else if(dat[ls].mx<dat[rs].mx){
            dat[mod].cnt=dat[rs].cnt;
            dat[mod].se=max(dat[ls].mx,dat[rs].se);
        }else{
            dat[mod].cnt=dat[ls].cnt;
            dat[mod].se=max(dat[ls].se,dat[rs].mx);
        }
        if(dat[ls].mn==dat[rs].mn){
            dat[mod].cnn=dat[ls].cnn+dat[rs].cnn;
            dat[mod].sn=min(dat[ls].sn,dat[rs].sn);
        }else if(dat[ls].mn<dat[rs].mn){
            dat[mod].cnn=dat[ls].cnn;
            dat[mod].sn=min(dat[ls].sn,dat[rs].mn);
        }else{
            dat[mod].cnn=dat[rs].cnn;
            dat[mod].sn=min(dat[ls].mn,dat[rs].sn);
        }
    }
    void push_down(int mod,int l,int r){
        if(dat[mod].tgsu!=0){
            int mid=(l+r)>>1;
            auto &pos=dat[mod].tgsu;

            dat[ls].val+=1ll*pos*(mid-l+1);
            dat[ls].tgsu+=pos;
            dat[ls].mn+=pos;
            dat[ls].mx+=pos;
            if(dat[ls].se!=-inf)dat[ls].se+=pos;
            if(dat[ls].sn!= inf)dat[ls].sn+=pos;
            if(dat[ls].tgmx!=-inf)dat[ls].tgmx+=pos;
            if(dat[ls].tgmn!= inf)dat[ls].tgmn+=pos;

            dat[rs].val+=1ll*pos*(r-mid);
            dat[rs].tgsu+=pos;
            dat[rs].mn+=pos;
            dat[rs].mx+=pos;
            if(dat[rs].se!=-inf)dat[rs].se+=pos;
            if(dat[rs].sn!= inf)dat[rs].sn+=pos;
            if(dat[rs].tgmx!=-inf)dat[rs].tgmx+=pos;
            if(dat[rs].tgmn!= inf)dat[rs].tgmn+=pos;
            
            dat[mod].tgsu=0;
        }
        if(dat[mod].tgmn!=inf){
            auto &pos=dat[mod].tgmn;
            if(pos<dat[ls].mx){
                dat[ls].val-=1ll*(dat[ls].mx-pos)*dat[ls].cnt;
                if(dat[ls].mx==dat[ls].sn)dat[ls].sn=pos;
                if(dat[ls].mx==dat[ls].mn)dat[ls].mn=pos;
                dat[ls].tgmx=min(dat[ls].tgmx,pos);
                dat[ls].mx=dat[ls].tgmn=pos;
            }
            if(pos<dat[rs].mx){
                dat[rs].val-=1ll*(dat[rs].mx-pos)*dat[rs].cnt;
                if(dat[rs].mx==dat[rs].sn)dat[rs].sn=pos;
                if(dat[rs].mx==dat[rs].mn)dat[rs].mn=pos;
                dat[rs].tgmx=min(dat[rs].tgmx,pos);
                dat[rs].mx=dat[rs].tgmn=pos;
            }
            dat[mod].tgmn=inf;
        }
        if(dat[mod].tgmx!=-inf){
            auto &pos=dat[mod].tgmx;
            if(pos>dat[ls].mn){
                dat[ls].val-=1ll*(dat[ls].mn-pos)*dat[ls].cnn;
                if(dat[ls].mn==dat[ls].se)dat[ls].se=pos;
                if(dat[ls].mn==dat[ls].mx)dat[ls].mx=pos;
                dat[ls].tgmn=max(dat[ls].tgmn,pos);
                dat[ls].mn=dat[ls].tgmx=pos;
            }
            if(pos>dat[rs].mn){
                dat[rs].val-=1ll*(dat[rs].mn-pos)*dat[rs].cnn;
                if(dat[rs].mn==dat[rs].se)dat[rs].se=pos;
                if(dat[rs].mn==dat[rs].mx)dat[rs].mx=pos;
                dat[rs].tgmn=max(dat[rs].tgmn,pos);
                dat[rs].mn=dat[rs].tgmx=pos;
            }
            dat[mod].tgmx=-inf;
        }
    }
    int bbuild(int l,int r){
        if(l>=r){
            top++;
            dat[top].val=dat[top].mx=dat[top].mn=a[l];
            dat[top].cnn=dat[top].cnt=1;
            dat[top].tgmx=dat[top].se=-inf;
            dat[top].tgmn=dat[top].sn=inf;
            dat[top].tgsu=0;
            return top;
        }
        int tmp=++top,mid=(l+r)>>1;
        dat[tmp].tgmn=inf;
        dat[tmp].tgmx=-inf;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        push_up(tmp);
        return tmp;
    }
    long long qquerysum(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr){
            return dat[mod].val;
        }
        int mid=(l+r)>>1;
        long long res=0;
        push_down(mod,l,r);
        if(tl<=mid)res+=qquerysum(ls,l,mid,tl,tr);
        if(tr>mid)res+=qquerysum(rs,mid+1,r,tl,tr);
        return res;
    }
    long long qquerymax(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].mx;
        int mid=(l+r)>>1;
        long long mnn=-inf;
        push_down(mod,l,r);
        if(tl<=mid)mnn=max(mnn,qquerymax(ls,l,mid,tl,tr));
        if(tr>mid)mnn=max(mnn,qquerymax(rs,mid+1,r,tl,tr));
        return mnn;
    }
    long long qquerymin(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].mn;
        int mid=(l+r)>>1;
        long long mxx=inf;
        push_down(mod,l,r);
        if(tl<=mid)mxx=min(mxx,qquerymin(ls,l,mid,tl,tr));
        if(tr>mid)mxx=min(mxx,qquerymin(rs,mid+1,r,tl,tr));
        return mxx;
    }
    void mmin(int mod,int l,int r,int tl,int tr,long long val){//a=min(a,val)
        if(dat[mod].mx<=val)return;
        if(tl<=l&&r<=tr&&dat[mod].se<val){
            dat[mod].val-=1LL*(dat[mod].mx-val)*dat[mod].cnt;
            if(dat[mod].mx==dat[mod].mn)dat[mod].mn=val;
            if(dat[mod].mx==dat[mod].sn)dat[mod].sn=val;
            dat[mod].tgmx=min(dat[mod].tgmx,val);
            dat[mod].mx=dat[mod].tgmn=val;
            return;
        }
        push_down(mod,l,r);
        int mid=(l+r)>>1;
        if(tl<=mid)mmin(ls,l,mid,tl,tr,val);
        if(tr>mid)mmin(rs,mid+1,r,tl,tr,val);
        push_up(mod);
    }
    void mmax(int mod,int l,int r,int tl,int tr,long long val){//a=max(a,val)
        if(dat[mod].mn>=val)return;
        if(tl<=l&&r<=tr&&val<dat[mod].sn){
            dat[mod].val-=1LL*(dat[mod].mn-val)*dat[mod].cnn;
            if(dat[mod].mn==dat[mod].mx)dat[mod].mx=val;
            if(dat[mod].mn==dat[mod].se)dat[mod].se=val;
            dat[mod].tgmn=max(dat[mod].tgmn,val);
            dat[mod].mn=dat[mod].tgmx=val;
            return;
        }
        push_down(mod,l,r);
        int mid=(l+r)>>1;
        if(tl<=mid)mmax(ls,l,mid,tl,tr,val);
        if(tr>mid)mmax(rs,mid+1,r,tl,tr,val);
        push_up(mod);
    }
    void aadd(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].val+=1LL*(r-l+1)*val;
            dat[mod].tgsu+=val;
            if(dat[mod].tgmn!=inf)dat[mod].tgmn+=val;
            if(dat[mod].tgmx!=-inf)dat[mod].tgmx+=val;
            if(dat[mod].se!=-inf)dat[mod].se+=val;
            if(dat[mod].sn!=inf)dat[mod].sn+=val;
            dat[mod].mn+=val;
            dat[mod].mx+=val;
            return;
        }
        int mid=(l+r)>>1;
        push_down(mod,l,r);
        if(tl<=mid)aadd(ls,l,mid,tl,tr,val);
        if(tr>mid)aadd(rs,mid+1,r,tl,tr,val);
        push_up(mod);
    }
};

吉司机线段树2

支持区间加某个数,区间变成某个数(不是max,就是全部赋值成某个数),区间查询最大值,历史最大值.

constexpr long long inf=0x0000ffffffffffff;
long long a[100010];
struct node{
    int l,r;
    long long mxx,dmxx,tgsu,mxsu,tgbe,mxbe;
    //最大值,历史最大值,lazy,最大lazy,最大变成tag,当前变成值tag
    /*
    先传tgsu再传tgbe
    两个tag可以同时存在
    */
};
struct segtree{
    node dat[200010];
    int top=0;
    #define ls dat[mod].l
    #define rs dat[mod].r
    int bbuild(int l,int r){
        if(l>=r){
            ++top;
            dat[top].dmxx=dat[top].mxx=a[l];
            // dat[top].tgbe=dat[top].mxbe=-inf;
            return top;
        }
        int tmp=++top,mid=(l+r)>>1;
        dat[tmp].tgbe=dat[tmp].mxbe=dat[tmp].dmxx=-inf;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        push_up(tmp);
        return tmp;
    }
    void push_up(int mod){
        dat[mod].mxx=max(dat[ls].mxx,dat[rs].mxx);
        dat[mod].dmxx=(max(dat[ls].dmxx,dat[rs].dmxx));
    }
    void push_down(int mod){
        dat[ls].dmxx=max(dat[ls].dmxx,max(dat[ls].mxx+dat[mod].mxsu,dat[mod].mxbe));
        dat[rs].dmxx=max(dat[rs].dmxx,max(dat[rs].mxx+dat[mod].mxsu,dat[mod].mxbe));
        
        if(dat[ls].tgbe!=-inf){
            dat[ls].mxbe=max(dat[ls].mxbe,dat[ls].tgbe+dat[mod].mxsu);
        }else{
            dat[ls].mxsu=max(dat[ls].mxsu,dat[ls].tgsu+dat[mod].mxsu);
        }
        if(dat[rs].tgbe!=-inf){
            dat[rs].mxbe=max(dat[rs].mxbe,dat[rs].tgbe+dat[mod].mxsu);
        }else{
            dat[rs].mxsu=max(dat[rs].mxsu,dat[rs].tgsu+dat[mod].mxsu);
        }
        if(dat[mod].tgsu!=0){
            dat[ls].mxx+=dat[mod].tgsu;
            if(dat[ls].tgbe!=-inf){
                dat[ls].tgbe+=dat[mod].tgsu;
            }else{
                dat[ls].tgsu+=dat[mod].tgsu;
            }

            dat[rs].mxx+=dat[mod].tgsu;
            if(dat[rs].tgbe!=-inf){
                dat[rs].tgbe+=dat[mod].tgsu;
            }else{
                dat[rs].tgsu+=dat[mod].tgsu;
            }
        }
        if(dat[mod].tgbe!=-inf){
            long long& pos=dat[mod].tgbe;
            dat[ls].mxx=pos;
            dat[ls].tgbe=pos;
            dat[ls].tgsu=0;

            dat[rs].mxx=pos;
            dat[rs].tgbe=pos;
            dat[rs].tgsu=0;
        }
        dat[ls].mxsu=max(dat[ls].mxsu,dat[ls].tgsu);
        dat[ls].mxbe=max(dat[ls].mxbe,max(dat[ls].tgbe,dat[mod].mxbe));

        dat[rs].mxsu=max(dat[rs].mxsu,dat[rs].tgsu);
        dat[rs].mxbe=max(dat[rs].mxbe,max(dat[rs].tgbe,dat[mod].mxbe));
        
        dat[mod].mxsu=0;
        dat[mod].tgsu=0;
        dat[mod].mxbe=-inf;
        dat[mod].tgbe=-inf;
    }
    long long qquerymax(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].mxx;
        int mid=(l+r)>>1;
        long long res=-inf;
        push_down(mod);
        if(tl<=mid)res=max(res,qquerymax(ls,l,mid,tl,tr));
        if(tr>mid)res=max(res,qquerymax(rs,mid+1,r,tl,tr));
        return res;
    }
    long long qquerydmax(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].dmxx;
        int mid=(l+r)>>1;
        long long res=-inf;
        push_down(mod);
        if(tl<=mid)res=max(res,qquerydmax(ls,l,mid,tl,tr));
        if(tr>mid)res=max(res,qquerydmax(rs,mid+1,r,tl,tr));
        return res;
    }
    void aadd(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].mxx+=val;
            dat[mod].dmxx=max(dat[mod].dmxx,dat[mod].mxx);
            if(dat[mod].tgbe!=-inf){
                dat[mod].tgbe+=val;
                dat[mod].mxbe=max(dat[mod].mxbe,dat[mod].tgbe);
            }else{
                dat[mod].tgsu+=val;
                dat[mod].mxsu=max(dat[mod].mxsu,dat[mod].tgsu);
            }
            return;
        }
        push_down(mod);
        int mid=(l+r)>>1;
        if(tl<=mid)aadd(ls,l,mid,tl,tr,val);
        if(tr>mid)aadd(rs,mid+1,r,tl,tr,val);
        push_up(mod);
    }
    void cchange(int mod,int l,int r,int tl,int tr,long long val){
        if(tl<=l&&r<=tr){
            dat[mod].mxx=val;
            dat[mod].dmxx=max(dat[mod].dmxx,val);
            dat[mod].tgbe=val;
            dat[mod].mxbe=max(dat[mod].mxbe,val);
            return;
        }
        push_down(mod);
        int mid=(l+r)>>1;
        if(tl<=mid)cchange(ls,l,mid,tl,tr,val);
        if(tr>mid)cchange(rs,mid+1,r,tl,tr,val);
        push_up(mod);
    }
    void prr(){
        for(int i=1;i<=top;++i){
            fout<<i<<" "<<dat[i].l<<" "<<dat[i].r<<" "<<dat[i].mxx<<" "<<dat[i].dmxx<<" "<<dat[i].tgsu<<" "<<dat[i].tgbe<<" "<<dat[i].mxbe<<"\n";
        }enter;
    }
};

吉司机线段树(不是Flu写的)

区间加,区间查询和,区间min,区间查询历史最大值.

struct SegmentTree{
    struct Node{
        int l,r;
        int mx,hmx,se,cnt; ll sum;
        int tgsu,mxsu,tgdsu,mxdsu;
    }
    tr[4*MAXN];
    #define ls (mod<<1)
    #define rs (mod<<1|1)
    void pushup(int mod){
        tr[mod].sum=tr[ls].sum+tr[rs].sum;
        tr[mod].hmx=max(tr[ls].hmx,tr[rs].hmx);
        if(tr[ls].mx==tr[rs].mx){
            tr[mod].mx=tr[ls].mx;
            tr[mod].se=max(tr[ls].se,tr[rs].se);
            tr[mod].cnt=tr[ls].cnt+tr[rs].cnt;
        }else if(tr[ls].mx>tr[rs].mx){
            tr[mod].mx=tr[ls].mx;
            tr[mod].se=max(tr[ls].se,tr[rs].mx);
            tr[mod].cnt=tr[ls].cnt;
        }else{
            tr[mod].mx=tr[rs].mx;
            tr[mod].se=max(tr[ls].mx,tr[rs].se);
            tr[mod].cnt=tr[rs].cnt;
        }
    }
    void update(int mod,int k1,int k1_,int k2,int k2_){
        tr[mod].sum+=1ll*k1*tr[mod].cnt+1ll*k2*(tr[mod].r-tr[mod].l+1-tr[mod].cnt);
        tr[mod].hmx=max(tr[mod].hmx,tr[mod].mx+k1_);
        tr[mod].mxsu=max(tr[mod].mxsu,tr[mod].tgsu+k1_);
        tr[mod].mx+=k1,tr[mod].tgsu+=k1;
        tr[mod].mxdsu=max(tr[mod].mxdsu,tr[mod].tgdsu+k2_);
        if(tr[mod].se!=-inf) tr[mod].se+=k2;
        tr[mod].tgdsu+=k2;
    }
    void pushdown(int mod){
        int tmp=max(tr[ls].mx,tr[rs].mx);
        if(tr[ls].mx==tmp)update(ls,tr[mod].tgsu,tr[mod].mxsu,tr[mod].tgdsu,tr[mod].mxdsu);
        else update(ls,tr[mod].tgdsu,tr[mod].mxdsu,tr[mod].tgdsu,tr[mod].mxdsu);
        if(tr[rs].mx==tmp)update(rs,tr[mod].tgsu,tr[mod].mxsu,tr[mod].tgdsu,tr[mod].mxdsu);
        else update(rs,tr[mod].tgdsu,tr[mod].mxdsu,tr[mod].tgdsu,tr[mod].mxdsu);
        tr[mod].tgsu=tr[mod].mxsu=tr[mod].tgdsu=tr[mod].mxdsu=0;
    }
    void build(int mod,int l,int r,int* a){
        tr[mod].l=l,tr[mod].r=r;
        tr[mod].tgsu=tr[mod].mxsu=tr[mod].tgdsu=tr[mod].mxdsu=0;
        if(l==r){
            tr[mod].sum=tr[mod].hmx=tr[mod].mx=a[l];
            tr[mod].se=-inf,tr[mod].cnt=1;
            return;
        }
        int mid=l+r>>1;
        build(ls,l,mid,a);
        build(rs,mid+1,r,a);
        pushup(mod);
    }
    void aadd(int mod,int l,int r,int k){
        if(tr[mod].l>r||tr[mod].r<l) return;
        if(l<=tr[mod].l&&tr[mod].r<=r){update(mod,k,k,k,k);return;}
        pushdown(mod);
        aadd(ls,l,r,k),aadd(rs,l,r,k);
        pushup(mod);
    }
    void mmin(int mod,int l,int r,int k){
        if(tr[mod].l>r||tr[mod].r<l||k>=tr[mod].mx) return;
        if(l<=tr[mod].l&&tr[mod].r<=r&&k>tr[mod].se)
            { update(mod,k-tr[mod].mx,k-tr[mod].mx,0,0); return; }
        pushdown(mod);
        mmin(ls,l,r,k),mmin(rs,l,r,k);
        pushup(mod);
    }
    long long qquerysum(int mod,int l,int r){
        if(tr[mod].l>r||tr[mod].r<l) return 0;
        if(l<=tr[mod].l&&tr[mod].r<=r) return tr[mod].sum;
        pushdown(mod);
        return qquerysum(ls,l,r)+qquerysum(rs,l,r);
    }
    long long qquerymax(int mod,int l,int r){
        if(tr[mod].l>r||tr[mod].r<l) return -inf;
        if(l<=tr[mod].l&&tr[mod].r<=r) return tr[mod].mx;
        pushdown(mod);
        return max(qquerymax(ls,l,r),qquerymax(rs,l,r));
    }
    long long qqueryhmax(int mod,int l,int r){
        if(tr[mod].l>r||tr[mod].r<l)return -inf;
        if(l<=tr[mod].l&&tr[mod].r<=r)return tr[mod].hmx;
        pushdown(mod);
        return max(qqueryhmax(ls,l,r),qqueryhmax(rs,l,r));
    }
    #undef ls
    #undef rs
};
int a[MAXN];

可持久化权值线段树(区间第k小)

struct perSegTr{
    struct node{
        int l,r;
        int val;
    };
    node dat[8000000];
    int top=0,root[400010],adat[400010],ddat[400010],m;
    int newnode(int num=0,int ll=0,int rr=0){
        ++top;
        dat[top].val=num;
        dat[top].l=ll;
        dat[top].r=rr;
        return top;
    }
    int bbuild(int l,int r){
        if(l>=r){
            return newnode();
        }
        int tmp=newnode(),mid=(l+r)>>1;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        return tmp;
    }
    int uupdate(int ver,int l,int r,int pos,int val){
        int tmp=newnode(dat[ver].val+val,dat[ver].l,dat[ver].r);
        if(l>=r)return tmp;
        int mid=(l+r)>>1;
        if(pos<=mid)dat[tmp].l=uupdate(dat[ver].l,l,mid,pos,val);
        else dat[tmp].r=uupdate(dat[ver].r,mid+1,r,pos,val);
        return tmp;
    }
    int qqquery(int verl,int verr,int l,int r,int val){
        if(l>=r)return l;
        int delta=dat[dat[verr].l].val-dat[dat[verl].l].val;
        if(val<=delta)return qqquery(dat[verl].l,dat[verr].l,l,(l+r)>>1,val);
        return qqquery(dat[verl].r,dat[verr].r,((l+r)>>1)+1,r,val-delta);
    }
    void prepare(int n){
        sort(ddat+1,ddat+n+1);
        m=unique(ddat+1,ddat+n+1)-ddat-1;
        root[0]=bbuild(1,m);
        for(int i=1;i<=n;++i){
            int pos=lower_bound(ddat+1,ddat+m+1,adat[i])-ddat;
            root[i]=uupdate(root[i-1],1,m,pos,1);
        }
    }
    int qquery(int l,int r,int val){
        return ddat[qqquery(root[l-1],root[r],1,m,val)];
    }
};
/*
可持久化权值线段树
prepare(n)预处理
qquery(l,r,val)查询[l,r]中第val小的数
*/

主席树(可持久化线段树)

给定板子求静态区间第k小.

struct node{
    int l,r,val;
};
node dat[20000000];
int n,m,q,l,r,num,top,pos;
int ddat[200010];
int adat[200010];
int root[200010];
int bbuild(int l,int r){
    if(l>=r)return ++top;
    int mid=(l+r)>>1,tmp=++top;
    dat[tmp].l=bbuild(l,mid);
    dat[tmp].r=bbuild(mid+1,r);
    return tmp;
}
int uupdate(int ver,int l,int r,int val){
    int tmp=++top;
    dat[tmp].l=dat[ver].l;
    dat[tmp].r=dat[ver].r;
    dat[tmp].val=dat[ver].val+1;
    if(l<r){
        int mid=(l+r)>>1;
        if(val<=mid)dat[tmp].l=uupdate(dat[ver].l,l,mid,val);
        else dat[tmp].r=uupdate(dat[ver].r,mid+1,r,val);
    }
    return tmp;
}
int qquery(int verl,int verr,int val,int l,int r){
    if(l>=r)return l;
    int delta=dat[dat[verr].l].val-dat[dat[verl].l].val;
    if(val<=delta)return qquery(dat[verl].l,dat[verr].l,val,l,(l+r)>>1);
    return qquery(dat[verl].r,dat[verr].r,val-delta,((l+r)>>1)+1,r);
}
signed main(){
    fin>>n>>q;
    for(int i=1;i<=n;++i){
        fin>>ddat[i];
        adat[i]=ddat[i];//unique
    }
    sort(adat+1,adat+n+1);
    m=unique(adat+1,adat+n+1)-adat-1;
    root[0]=bbuild(1,m);
    for(int i=1;i<=n;++i){
        pos=lower_bound(adat+1,adat+m+1,ddat[i])-adat;
        root[i]=uupdate(root[i-1],1,m,pos);
    }
    for(int i=0;i<q;++i){
        fin>>l>>r>>num;
        fout<<adat[qquery(root[l-1],root[r],num,1,m)]<<'\n';
    }
    return 0;
}

可持久化数组

struct node{
    int l,r;
    long long val;
};
node dat[25000010];
int root[1000010];
int n,mm,vval,top=-1;
int res;
int bbuild(int l,int r){
    if(l==r){
        read(dat[++top].val);
        return top;
    }
    int res=++top,mid=(l+r)>>1;
    dat[res].l=bbuild(l,mid);
    dat[res].r=bbuild(mid+1,r);
    return res;
}
int ffind(int num,int p,int l,int r){
    if(l==r)return dat[num].val;
    int mid=(l+r)>>1;
    if(p<=mid)return ffind(dat[num].l,p,l,mid);
    return ffind(dat[num].r,p,mid+1,r);
}
int uupdate(int mod,int p,int l,int r){
    dat[++top]=dat[mod];
    int res=top;
    if(l==r){
        dat[top].val=vval;
        return top;
    }
    int mid=(l+r)>>1;
    if(p<=mid){
        dat[res].l=uupdate(dat[mod].l,p,l,mid);
    }
    else{
        dat[res].r=uupdate(dat[mod].r,p,mid+1,r);
    }
    return res;
}
int main(){
    read(n,mm);
    root[0]=bbuild(1,n);
    register int ver,opt,loc;
    for(int i=1;i<=mm;++i){
        read(ver,opt,loc);
        if(opt==1){
            read(vval);
            root[i]=uupdate(root[ver],loc,1,n);
        }
        else{
            root[i]=root[ver];
            res=ffind(root[ver],loc,1,n);
            put(res);
        }
    }
    return 0;
}

可持久化并查集

struct node{
    int l,r,val,dep;
};
node dat[6000000];
int n,m,mod,top,root[200010];
int bbuild(int l,int r){
    int p=++top;
    if(l==r){
        dat[p].val=l;
        return p;
    }
    int mid=(l+r)>>1;
    dat[p].l=bbuild(l,mid);
    dat[p].r=bbuild(mid+1,r);
    return p;
}
int qquery(int mod,int l,int r,int x){
    if(l==r)return mod;
    int mid=(l+r)>>1;
    if(mid>=x)return qquery(dat[mod].l,l,mid,x);
    else return qquery(dat[mod].r,mid+1,r,x);
}
int ffind(int mod,int a){
    int val=qquery(root[mod],1,n,a);
    if(dat[val].val==a)return val;
    return ffind(mod,dat[val].val);
}
int uupdate(int mod,int l,int r,int x,int f){
    int p=++top;
    dat[p]=dat[mod];
    if(l==r){
        dat[p].val=f;
        return p;
    }
    int mid=(l+r)>>1;
    if(mid>=x)dat[p].l=uupdate(dat[mod].l,l,mid,x,f);
    else dat[p].r=uupdate(dat[mod].r,mid+1,r,x,f);
    return p;
}
int add(int mod,int l,int r,int x){//深度计算 
    int p=++top;
    dat[p]=dat[mod];
    if(l==r){
        dat[p].dep++;
        return p;
    }
    int mid=(l+r)>>1;
    if(x<=mid)dat[p].l=add(dat[mod].l,l,mid,x);
    else dat[p].r=add(dat[mod].r,mid+1,r,x);
    return p;
}
void uunion(int mod,int a,int b){
    root[mod]=root[mod-1];
    a=ffind(mod,a);b=ffind(mod,b);
    if(dat[a].val!=dat[b].val){
        if(dat[a].dep>dat[b].dep)swap(a,b);
        root[mod]=uupdate(root[mod-1],1,n,dat[a].val,dat[b].val);
        if(dat[a].dep==dat[b].dep)root[mod]=add(root[mod],1,n,dat[b].val);
    } 
}
char aask(int mod,int a,int b){
    a=ffind(mod,a),b=ffind(mod,b);
    if(dat[a].val==dat[b].val)return 1;
    else return 0;
}

树链剖分(重链剖分),树剖

这里放的是一个能单点修改,查询区间max和区间和的板子.

int ddat[200010];
struct segtree{
    struct nnode{
        int l,r,val,mxx;
    };
    nnode dat[600000];
    int* rnk,top=0;
    void push_up(int num){
        dat[num].val=dat[dat[num].l].val+dat[dat[num].r].val;
        dat[num].mxx=max(dat[dat[num].l].mxx,dat[dat[num].r].mxx);
    }
    int bbuild(int l,int r){
        if(l>=r){
            ++top;
            dat[top].val=dat[top].mxx=ddat[rnk[l]];
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        push_up(tmp);
        return tmp;
    }
    void aadd(int mod,int l,int r,int pos,int val){
        if(l>=r){
            dat[mod].val=val;
            dat[mod].mxx=val;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)aadd(dat[mod].l,l,mid,pos,val);
        else aadd(dat[mod].r,mid+1,r,pos,val);
        push_up(mod);
    }
    int querymax(int num,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return dat[num].mxx;
        int mid=(l+r)>>1,mxx=-1145141919;
        if(ql<=mid)mxx=max(mxx,querymax(dat[num].l,l,mid,ql,qr));
        if(qr>mid)mxx=max(mxx,querymax(dat[num].r,mid+1,r,ql,qr));
        return mxx;
    }
    int querysum(int num,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return dat[num].val;
        int mid=(l+r)>>1,res=0;
        if(ql<=mid)res+=querysum(dat[num].l,l,mid,ql,qr);
        if(qr>mid)res+=querysum(dat[num].r,mid+1,r,ql,qr);
        return res;
    }
};
segtree koi;

struct heavyChainSeg{
    vector<vector<int> >edge;
    int sz,cnt,n,ttop,*_fa,*dep,*siz,*son,*top,*dfn,*rnk;
    heavyChainSeg(int nn=100010):sz(nn),n(0),cnt(0),ttop(0){
        edge.resize(sz);
        _fa=new int[sz]{};
        dep=new int[sz]{};
        siz=new int[sz]{};
        son=new int[sz]{};
        top=new int[sz]{};
        dfn=new int[sz]{};
        rnk=new int[sz]{};
    }
    void adddir(int u,int v){
        edge[u].push_back(v);
    }
    void adddedir(int u,int v){
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    void dfs1(int num){
        son[num]=-1;
        siz[num]=1;
        for(auto i:edge[num]){
            if(dep[i]==0){
                dep[i]=dep[num]+1;
                _fa[i]=num;
                dfs1(i);
                siz[num]+=siz[i];
                if(son[num]==-1||siz[i]>siz[son[num]]){
                    son[num]=i;
                }
            }
        }
    }
    void dfs2(int num,int ko){/*当前节点,当前重链顶*/
        top[num]=ko;
        dfn[num]=++cnt;
        rnk[cnt]=num;
        if(son[num]==-1)return;
        dfs2(son[num],ko);
        for(auto i:edge[num]){
            if(i!=son[num]&&i!=_fa[num]){
                dfs2(i,i);
            }
        }
    }
    int lca(int u,int v){
        while(top[u]!=top[v]){
            if(dep[top[u]]>dep[top[v]])
                u=_fa[top[u]];
            else
                v=_fa[top[v]];
        }
        return dep[u]>dep[v]?v:u;
    }
    void prepare(int nn,int root=1){
        n=nn;
        dep[root]=1;
        dfs1(root);
        dfs2(root,root);
        koi.rnk=rnk;
        koi.bbuild(1,n);
    }
    int qquerymax(int x,int y){
        int res=-1145141919;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            res=max(res,koi.querymax(1,1,n,dfn[top[x]],dfn[x]));
            x=_fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res=max(res,koi.querymax(1,1,n,dfn[x],dfn[y]));
        return res;
    }
    int qquerysum(int x,int y){
        int res=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            res+=koi.querysum(1,1,n,dfn[top[x]],dfn[x]);
            x=_fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res+=koi.querysum(1,1,n,dfn[x],dfn[y]);
        return res;
    }
};
heavyChainSeg ko;

平衡树(有旋treap)

有旋treap.
定义排名是比他小的数+1,逆排名是比他大的数+1.

查找排名可能不存在,此时先插一个元素再查排名再删即可.

getval查询排名为x的数(使用前请保证存在).

struct treap{
    private:
    struct phtnode{
        phtnode* p[2];
        int val,rank,cnt,size;
        phtnode(int vval):val(vval),cnt(1),size(1){
            p[0]=p[1]=nullptr;
            rank=rand();
        }
        void updsize(){
            size=cnt;
            if(p[0]!=nullptr)size+=p[0]->size;
            if(p[1]!=nullptr)size+=p[1]->size;
        }
    };
    enum rtype{
        L=1,R=0
    };
    phtnode* root;
    int ttmp;
    void rotate(phtnode*& num,rtype dir){
        phtnode* tmp=num->p[dir];
        num->p[dir]=tmp->p[!dir];
        tmp->p[!dir]=num;
        num->updsize();tmp->updsize();
        num=tmp;
    }
    void _insert(phtnode*& num,int val){
        if(num==nullptr){
            num=new phtnode(val);
            return;
        }else if(val==num->val){
            num->size++;
            num->cnt++;
        }else if(val<num->val){
            _insert(num->p[0],val);
            if(num->p[0]->rank<num->rank){
                rotate(num,R);
            }
            num->updsize();
        }else{
            _insert(num->p[1],val);
            if(num->p[1]->rank<num->rank){
                rotate(num,L);
            }
            num->updsize();
        }
    }
    void _del(phtnode*& num,int val){
        if(val>num->val){
            _del(num->p[1],val);
            num->updsize();
        }else if(val<num->val){
            _del(num->p[0],val);
            num->updsize();
        }else if(num->cnt>1){
            num->cnt--;
            num->size--;
        }else{
            char now=0;
            now|=(num->p[0]!=nullptr);
            now|=((num->p[1]!=nullptr)<<1);
            phtnode* tmp=num;
            switch(now){
                case 0:{
                    delete num;
                    num=nullptr;
                    break;
                }case 1:{
                    num=tmp->p[0];
                    delete tmp;
                    break;
                }case 2:{
                    num=tmp->p[1];
                    delete tmp;
                    break;
                }case 3:{
                    rtype dir=(num->p[0]->rank<num->p[1]->rank)?R:L;
                    rotate(num,dir);
                    _del(num->p[!dir],val);
                    num->updsize();
                    break;
                }
            }
        }
    }
    int _getrank(phtnode* num,int val){
        int res=(num->p[0]==nullptr)?0:num->p[0]->size;
        if(val==num->val){
            return res+1;
        }else if(val<num->val){
            if(num->p[0]!=nullptr)return _getrank(num->p[0],val);
            else return 1;
        }else if(num->p[1]!=nullptr)return res+num->cnt+_getrank(num->p[1],val);
        else return num->size+1;
    }
    int _getderank(phtnode* num,int val){
        int res=(num->p[1]==nullptr)?0:num->p[1]->size;
        if(val==num->val){
            return res+1;
        }else if(val>num->val){
            if(num->p[1]!=nullptr)return _getderank(num->p[1],val);
            else return 1;
        }else if(num->p[0]!=nullptr)return res+num->cnt+_getderank(num->p[0],val);
        else return num->size+1;
    }
    int _getval(phtnode* num,int rank){
        int lesssize=(num->p[0]==nullptr)?0:num->p[0]->size;
        if(rank<=lesssize)return _getval(num->p[0],rank);
        else if(rank<=lesssize+num->cnt)return num->val;
        else return _getval(num->p[1],rank-lesssize-num->cnt);
    }
    int _getprevious(phtnode* num,int val){
        if(val<=num->val){
            if(num->p[0]!=nullptr)return _getprevious(num->p[0],val);
        }else{
            ttmp=num->val;
            if(num->p[1]!=nullptr)_getprevious(num->p[1],val);
            return ttmp;
        }
        return -1;
    }
    int _getnext(phtnode* num,int val){
        if(val>=num->val){
            if(num->p[1]!=nullptr)return _getnext(num->p[1],val);
        }else{
            ttmp=num->val;
            if(num->p[0]!=nullptr)_getnext(num->p[0],val);
            return ttmp;
        }
        return -1;
    }
    public:
    treap(){srand(time(0));root=nullptr;}
    void insert(int val){_insert(root,val);}
    void del(int val){_del(root,val);}
    int getrank(int val){return _getrank(root,val);}
    int getderank(int val){return _getderank(root,val);}
    int getprevious(int val){return _getprevious(root,val);}
    int getnext(int val){return _getnext(root,val);}
    int getval(int val){return _getval(root,val);}
};

平衡树(无旋fhqtreap)

template<typename T>
struct fhqtreap{
    struct node{
        int l,r,rnd,siz;
        T val;
    };
    node *dat;
    int n,top,root;
    fhqtreap(int nn=1000010):n(nn),top(0),root(0){
        srand(time(0));
        dat=new node[nn]{};
    }
    int new_node(T val){
        ++top;
        dat[top].l=dat[top].r=0;
        dat[top].siz=1;
        dat[top].val=val;
        dat[top].rnd=rand();
        return top;
    }
    void push_up(int mod){
        dat[mod].siz=dat[dat[mod].l].siz+dat[dat[mod].r].siz+1;
    }
    void split(int mod,T val,int& x,int& y){
        if(mod==0){
            x=y=0;
            return;
        }
        if(dat[mod].val<=val){
            x=mod;
            split(dat[mod].r,val,dat[mod].r,y);
        }else{
            y=mod;
            split(dat[mod].l,val,x,dat[mod].l);
        }
        push_up(mod);
    }
    int merge(int x,int y){
        if(x==0||y==0)return (x+y);
        if(dat[x].rnd<dat[y].rnd){
            dat[x].r=merge(dat[x].r,y);
            push_up(x);
            return x;
        }else{
            dat[y].l=merge(x,dat[y].l);
            push_up(y);
            return y;
        }
    }
    void insert(T v){
        int x,y,z;
        split(root,v,x,y);
        z=new_node(v);
        root=merge(merge(x,z),y);
    }
    void del(T v){
        int x,y,z;
        split(root,v,x,z);
        split(x,v-1,x,y);
        y=merge(dat[y].l,dat[y].r);
        root=merge(merge(x,y),z);
    }
    int rank(T v){
        int x,y;
        split(root,v-1,x,y);
        int res=dat[x].siz+1;
        root=merge(x,y);
        return res;
    }
    T topk(int mod,int k){
        int lsz=dat[dat[mod].l].siz;
        if(k==lsz+1)return dat[mod].val;
        if(k<=lsz)return topk(dat[mod].l,k);
        return topk(dat[mod].r,k-lsz-1);
    }
    T getpre(T v){
        int x,y;
        split(root,v-1,x,y);
        T res=topk(x,dat[x].siz);
        root=merge(x,y);
        return res;
    }
    T getaft(T v){
        int x,y;
        split(root,v,x,y);
        T res=topk(y,1);
        root=merge(x,y);
        return res;
    }
};

动态树 Link-Cut Tree LCT

给定板子支持u到v路径加,路径都乘上一个数(取模),查询路径上节点和,加边断边.(由于加不知道要加多少,所以同时维护一个size).

struct LCT{
    struct node{
        int f,ls,rs,lz;
        i64 val,sum,siz,mul,add;
        //该点值,神秘和,子树大小,乘法标记,加法标记
    } s[100005];
    void mmullazy(int x,i64 val){
        s[x].val=(s[x].val*val)%mod;
        s[x].sum=(s[x].sum*val)%mod;
        s[x].mul=(s[x].mul*val)%mod;
        s[x].add=(s[x].add*val)%mod;
    }
    void aaddlazy(int x,i64 val){
        s[x].val=(s[x].val+val)%mod;
        s[x].add=(s[x].add+val)%mod;
        s[x].sum=(s[x].sum+val*(s[x].siz))%mod;
    }
    void pushup(int k){
        s[k].sum=(s[s[k].ls].sum+s[s[k].rs].sum+s[k].val)%mod;
        s[k].siz=s[s[k].ls].siz+s[s[k].rs].siz+1;
    }
    void pushdown(int k){
        if(s[k].mul!=1){
            mmullazy(s[k].ls,s[k].mul);
            mmullazy(s[k].rs,s[k].mul);
            s[k].mul=1;
        }
        if(s[k].add!=0){
            aaddlazy(s[k].ls,s[k].add);
            aaddlazy(s[k].rs,s[k].add);
            s[k].add=0;
        }
        if(s[k].lz){
            swap(s[k].ls,s[k].rs);
            if(s[k].ls)    s[s[k].ls].lz^=1;
            if(s[k].rs)    s[s[k].rs].lz^=1;
            s[k].lz=0;
        }
    }
    int identify(int k){
        if(s[s[k].f].ls==k)    return 0;
        if(s[s[k].f].rs==k)    return 1;
        return -1;
    }
    void connect(int k,int f,int op){
        s[k].f=f;
        if(op==1)    s[f].rs=k;
        if(op==0)    s[f].ls=k;
    }
    void rotate(int x){
        int y=s[x].f;
        int z=s[y].f;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1)        u=s[x].ls;
        if(opx==0)        u=s[x].rs;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
        pushup(y);
        pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1)    pushall(s[x].f);
        pushdown(x);
    }
    void splay(int k){
        pushall(k);
        while(identify(k)!=-1){
            int up=s[k].f;
            if(identify(up)==-1)                rotate(k);
            else if(identify(k)==identify(up))    rotate(up),rotate(k);
            else                                rotate(k),rotate(k);
        }
    }
    void access(int k){
        int l=0;
        while(k){
            splay(k);
            s[k].rs=l;
            pushup(k);
            l=k;
            k=s[k].f;
        }
    }
    void makeroot(int k){
        access(k);
        splay(k);
        swap(s[k].ls,s[k].rs);
        if(s[k].ls)    s[s[k].ls].lz^=1;
        if(s[k].rs)    s[s[k].rs].lz^=1;
    }
    int findroot(int k){
        access(k);
        splay(k);
        while(s[k].ls)    pushdown(k),k=s[k].ls;
        splay(k);
        return k;
    }
    void split(int x,int y){
        makeroot(x);
        access(y);splay(y);
    }
    bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x)    return 0;
        s[x].f=y;
        return 1;
    }
    bool cut(int x,int y){
        if(findroot(x)!=findroot(y))return 0;
        split(x,y);
        if(s[x].f!=y||s[x].rs)        return 0;
        s[x].f=s[y].ls=0;
        pushup(x);
        return 1;
    }
    i64 qquery(int x,int y){
        split(x,y);
        return s[y].sum;
    }
    void cchange(int x,int y){
        splay(x);
        s[x].val=y;
    }
    void aadd(int x,int y,i64 val){
        split(x,y);
        aaddlazy(y,val);
    }
    void mmul(int x,int y,i64 val){
        split(x,y);
        mmullazy(y,val);
    }
};

珂朵莉树(Chtholly Tree, Old-Driver Tree)

给定板子使用set动态分块支持 区间推平,区间第k小,区间加上某个数,区间求 $\sum_{i=l}^ra_i^x\mod y$ ,其中lrxy都是随机数.

struct Chtholly{
    struct node{
        int l,r;
        mutable i64 val;
        char operator <(const node& io)const{
            return l<io.l;
        }
        node(int a,int b,i64 c):l(a),r(b),val(c){}
    };
    set<node>st;
    int* dat;
    void init(int n){
        dat=new int[n+10];
        for(int i=1;i<=n;++i){
            fin>>dat[i];
        }
        int l=1;
        for(int i=1;i<=n;++i){
            if(dat[l]!=dat[i]){
                st.insert({l,i-1,dat[l]});
                l=i;
            }
        }
        st.insert({l,n,dat[l]});
    }
    set<node>::iterator split(int pos){
        auto i=st.lower_bound({pos,114514,114514});
        if(i!=st.end()&&(*i).l==pos){
            return i;
        }
        i--;
        int l=(*i).l;
        int r=(*i).r;
        i64 val=(*i).val;
        st.erase(i);
        st.insert({l,pos-1,val});
        return st.insert({pos,r,val}).first;
    }
    void bbe(int l,int r,i64 val){
        auto itr=split(r+1),itl=split(l);
        st.erase(itl,itr);
        st.insert({l,r,val});
    }
    void aadd(int l,int r,i64 x){
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            (*i).val+=x;
        }
    }
    i64 rrangek(int l,int r,int k){
        vector<node>vc;
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            vc.push_back(*i);
        }
        sort(vc.begin(),vc.end(),[&](node& a,node& b){
            return a.val<b.val;
        });
        for(auto i:vc){
            int del=i.r-i.l+1;
            k-=del;
            if(k<=0){
                return i.val;
            }
        }
        return 114514;
    }
    i64 ppow(int l,int r,int x,int mod){
        i64 res=0;
        auto itr=split(r+1),itl=split(l);
        for(auto i=itl;i!=itr;++i){
            res=(res+qp((*i).val%mod,x,mod)*((*i).r-(*i).l+1)%mod)%mod;
        }
        res=(res+mod)%mod;
        return res;
    }
};

左偏树(可并堆)

struct mheap{
    i64 val[N],adlazy[N],mulazy[N];
    int ls[N],rs[N],dis[N];
    void mull(int num,i64 vval){
        if(num){
            val[num]*=vval;
            adlazy[num]*=vval;
            mulazy[num]*=vval;
        }
    }
    void aadd(int num,i64 vval){
        if(num){
            val[num]+=vval;
            adlazy[num]+=vval;
        }
    }
    void push_down(int num){
        if(mulazy[num]!=1){
            mull(ls[num],mulazy[num]);//懒标记下传前先判断节点存不存在
            mull(rs[num],mulazy[num]);
            mulazy[num]=1;
        }
        if(adlazy[num]!=0){
            aadd(ls[num],adlazy[num]);
            aadd(rs[num],adlazy[num]);
            adlazy[num]=0;
        }
    }
    int merge(int x,int y){
        if(!x||!y)return x^y;
        if(val[x]>val[y])swap(x,y);//在这里修改小根堆大根堆
        push_down(x);//在这里下传懒标记
        rs[x]=merge(rs[x],y);
        if(dis[ls[x]]<dis[rs[x]])    //这两行(下面那行)删掉就是随机堆,常数小但是复杂度大(期望log^2)
            swap(ls[x],rs[x]);
        dis[x]=dis[rs[x]]+1;        //
        return x;
    }
    int pop(int num){
        push_down(num);
        int rt=merge(ls[num],rs[num]);
        ls[num]=rs[num]=0;
        return rt;
    }
    void init(){
        dis[0]=-1;
    }
};

三维偏序 CDQ分治

给定板子输入n m(值域上界),输入abc代表一个元素的三维(abc>0)

#define mxxn 600000
struct segtree{//这个是权值线段树,由于区间加和,假如要求严格小于的有多少个就-1+1来弥补. 
    struct node{
        int l,r,val,cls;//
    };
    #define ls dat[mod].l
    #define rs dat[mod].r
    node dat[mxxn];
    int top=0;
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            dat[++top].val=0;
            dat[top].cls=0;
            return ++top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].cls=0;
        dat[tmp].val=dat[dat[tmp].l].val+dat[dat[tmp].r].val;
        return tmp;
    }
    void push_down(int mod){
        if(dat[mod].cls!=0){
            dat[ls].cls=1;dat[rs].cls=1;
            dat[ls].val=0;dat[rs].val=0;
            dat[mod].cls=0;
        }
    }
    void aadd(int mod,int l,int r,int pos,int val){//某点加多少 
        if(l>=r){
            dat[mod].val+=val;
            return;
        }
        dat[mod].val+=val;
        int mid=(l+r)>>1;
        push_down(mod);
        if(pos<=mid)aadd(dat[mod].l,l,mid,pos,val);
        else aadd(dat[mod].r,mid+1,r,pos,val);
    }
    long long qquery(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr)return dat[mod].val;
        int mid=(l+r)>>1;
        push_down(mod);
        long long res=0;
        if(tl<=mid)res+=qquery(ls,l,mid,tl,tr);
        if(tr>mid)res+=qquery(rs,mid+1,r,tl,tr);
        return res;
    }
    void clear(){//清空整棵树
        top=0;
    }
    void cclear(){//清空线段树,待会还得用这棵树
        dat[1].val=0;
        dat[1].cls=1;
    }
};
struct node{
    int a,b,c;
    char operator<(const node& io)const{
        if(a!=io.a)    return a<io.a;
        if(b!=io.b)    return b<io.b;
                    return c<io.c;
    }
    char operator ==(const node& io)const{
        return a==io.a&&b==io.b&&c==io.c;
    }
};
segtree ko;
long long n,nn,m,res;
node ddat[100010],dat[100010],tmp[100010];
int vval[100010];
int rres[100010];
void cdq(int l,int r){
    if(l>=r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int li=l,ri=mid+1,top=0;
    while(li<=mid&&ri<=r){
        if(dat[li].b<=dat[ri].b){//二维偏序满足,插入第三维度
            int pos=lower_bound(ddat+1,ddat+1+nn,dat[li])-ddat;
            ko.aadd(1,1,m,dat[li].c,vval[pos]);
            tmp[++top]=dat[li];
            li++;
        }else{
            int pos=lower_bound(ddat+1,ddat+1+nn,dat[ri])-ddat;
            rres[pos]+=ko.qquery(1,1,m,1,dat[ri].c);
            tmp[++top]=dat[ri];
            ri++;
        }
    }
    while(li<=mid){
        tmp[++top]=dat[li++];
    }
    while(ri<=r){
        int pos=lower_bound(ddat+1,ddat+1+nn,dat[ri])-ddat;
        rres[pos]+=ko.qquery(1,1,m,1,dat[ri].c);
        tmp[++top]=dat[ri++];
    }
    top=0;
    for(int i=l;i<=r;++i){
        dat[i]=tmp[++top];
    }
    ko.cclear();
}
int f[100010];
int main(){
    fin>>n>>m;
    for(int i=1;i<=n;++i){
        fin>>dat[i].a>>dat[i].b>>dat[i].c;
    }
    sort(dat+1,dat+1+n);
    int l=1;
    vval[l]=1;
    for(int i=2;i<=n;++i){
        if(dat[i-1]==dat[i]){
            vval[l]++;
        }else{
            vval[++l]++;
        }
    }
    nn=unique(dat+1,dat+1+n)-dat-1;//去重数组
    for(int i=1;i<=n;++i){
        ddat[i]=dat[i];
    }
    ko.bbuild(1,m);
    cdq(1,nn);
    for(int i=1;i<=nn;++i){
        f[rres[i]+vval[i]-1]+=vval[i];
    }
    for(int i=0;i<n;++i){
        fout<<f[i]<<"\n";
    }
    return 0;
}

k维偏序 cdq套cdq

skywave的板子,使用方法是传递一个 vector<array<T,k>> 构造好的函数, ko() 返回对每个数有多少个满足偏序条件(<=)的数字.

template<typename Tp, int k>
struct kDPO {
    static_assert(k > 1);
    const vector<array<Tp, k>> &arr;
    kDPO(const vector<array<Tp, k>> &arr_) : arr(arr_) {}
    struct Info {
        int pos;
        bool tp;
    };
    vector<int> a, cnt, ans;
    array<vector<Info>, k - 1> b;
    vector<Info> hero;
    void cdq(int l, int r) {
        if (l == r) {
            return ;
        }
        int mid = (l + r) >> 1;
        cdq(l, mid);
        cdq(mid + 1, r);
        int i = l, j = mid + 1;
        b[k - 2].clear();
        while (i <= mid || j <= r) {
            if (j > r || (i <= mid && arr[a[i]][k - 1] <= arr[a[j]][k - 1])) {
                b[k - 2].push_back({a[i], false});
                ++i;
            } else {
                b[k - 2].push_back({a[j], true});
                ++j;
            }
        }
        for (int i = 0; i < r - l + 1; ++i) {
            a[i + l] = b[k - 2][i].pos;
        }
        cdq(0, r - l, k - 2);
    }    
    void cdq(int l, int r, int d) {
        if (l == r) {
            return ;
        }
        int mid = (l + r) >> 1;
        cdq(l, mid, d);
        cdq(mid + 1, r, d);
        int i = l, j = mid + 1;
        hero.clear();
        if (!d) {
            int sum = 0;
            while (i <= mid || j <= r) {
                if (j > r || (i <= mid && arr[b[d][i].pos][0] <= arr[b[d][j].pos][0])) {
                    sum += b[d][i].tp ? 0 : cnt[b[d][i].pos];
                    hero.emplace_back(b[d][i]);
                    ++i;
                } else {
                    ans[b[d][j].pos] += b[d][j].tp ? sum : 0;
                    hero.emplace_back(b[d][j]);
                    ++j;
                }
            }
            for (int i = 0; i < r - l + 1; ++i) {
                b[d][i + l] = hero[i];
            }
            return ;
        }
        b[d - 1].clear();
        while (i <= mid || j <= r) {
            if (j > r || (i <= mid && arr[b[d][i].pos][d] <= arr[b[d][j].pos][d])) {
                if (!b[d][i].tp) {
                    b[d - 1].push_back({b[d][i].pos, false});
                }
                hero.emplace_back(b[d][i]);
                ++i;
            } else {
                if (b[d][j].tp) {
                    b[d - 1].push_back({b[d][j].pos, true});
                }
                hero.emplace_back(b[d][j]);
                ++j;
            }
        }
        for (int i = 0; i < r - l + 1; ++i) {
            b[d][i + l] = hero[i];
        }
        if (!b[d - 1].empty()) {
            cdq(0, (int)b[d - 1].size() - 1, d - 1);
        }
    }
    vector<int> operator () () {
        int n = (int)arr.size();
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            return arr[x] < arr[y];
        });
        vector<pair<int, int>> equa;
        cnt.resize(n);
        for (int i = 0; i < n; ) {
            int j = i + 1;
            for ( ; j < n && arr[ord[j]] == arr[ord[i]]; ++j) {
                equa.emplace_back(ord[j], ord[i]);
            }
            a.emplace_back(ord[i]);
            cnt[ord[i]] = j - i;
            i = j;
        }
        ans.resize(n);
        hero.reserve(n);
        for (vector<Info> &i : b) {
            i.reserve(n);
        }
        cdq(0, (int)a.size() - 1);
        for (int i = 0; i < n; ++i) {
            ans[i] += cnt[i] - 1;
        }
        for (pair<int, int> i : equa) {
            ans[i.first] = ans[i.second];
        }
        return ans;
    }
};

字符串

字符串匹配 KMP

void getnextt(char* b,int* nextt,int lb){
    int j=0;
    for(int i=1;i<lb;++i){
        if(b[j]==b[i]){
            nextt[i]=++j;
        }else{
            if(j==0){
                nextt[i]=0;
            }else{
                j=nextt[j-1];
                i--;
            }
        }
    }
}
void Kmp(std::vector<int>* res,char* a,char* b,int la,int lb,int* nextt){
    int p=0,q=0;
    while(p<la){
        if(a[p]==b[q]){
            p++,q++;
        }else if(q){
            q=nextt[q-1];
        }else p++;
        if(q==lb){
            res->push_back(p-q+1);
        }
    }
}

最小表示法(0-index)

给一个字符串,每次能够把首的字符放到最后或者尾端字符放到最前,问形成的字典序最小的字符串是哪个.
使用时要双倍克隆数组,返回最小下标[pos,pos+n).

const int N=10000010;
int n,i,t;
int a[N<<1];
int minrep(){
    int i=0,j=1,k=0,t;
    while(i<n&&j<n&&k<n)
        if(t=a[(i+k)%n]-a[(j+k)%n]){
            if(t>0)i+=k+1;
                else j+=k+1;
            if(i==j)j++;
            k=0;
        }else k++;
    return i<j?i:j;
}

字符串哈希

下面给了三个板子.分别是自然溢出哈希,单哈希以及双哈希.

//base: 101 103 131 233
unsigned long long strhashe64(char* dat,int n,unsigned long long base=131){
    uint64_t res=0;
    for(int i=1;i<=n;++i){
        res=res*base+dat[i];
    }
    return res&0x7fffffff;
}
//hash:1e16+61
unsigned long long strhashmod1(char* dat,int n,unsigned long long base=131,unsigned long long mod=10000000000000061){
    unsigned long long res=0;
    for(int i=1;i<=n;++i){
        res=(res*base+dat[i])%mod;
    }
    return res;
}
std::pair<unsigned long long,unsigned long long> strhashmod2(char* dat,int n,unsigned long long base=131,unsigned long long mod1=10000000000000061,unsigned long long mod2=100000000000031){
    unsigned long long res1=0,res2=0;
    for(int i=1;i<=n;++i){
        res1=(res1*base+dat[i])%mod1;
        res2=(res2*base+dat[i])%mod2;
    }
    return {res1,res2};
}

字典树

struct trie{
    #define nmxx 62
    struct node{
        int tar[nmxx];
        int val;
    };
    node *dat;
    int top;
    trie(int num=200000){
        dat=new node[num+5];
        top=1;
    }
    int newnode(){
        top++;
        dat[top].val=0;
        for(int i=0;i<nmxx;++i){
            dat[top].tar[i]=0;
        }
        return top;
    }
    int prj(char num){
        if('a'<=num&&num<='z')return num-'a';
        if('A'<=num&&num<='Z')return num-'A'+26;
        // if('0'<=num&&num<='9')
            return num-'0'+52;
    }
    void insert(char* arr){
        int mod=1;
        int len=strlen(arr);
        for(int i=0;i<len;++i){
            int tmp=prj(arr[i]);
            if(dat[mod].tar[tmp]==0){
                int ttmp=newnode();
                dat[mod].tar[tmp]=ttmp;
            }
            mod=dat[mod].tar[tmp];
            dat[mod].val++;
        }
    }
    int match(char* arr){
        int mod=1;
        int len=strlen(arr);
        for(int i=0;i<len;++i){
            int tmp=prj(arr[i]);
            mod=dat[mod].tar[tmp];
        }
        return dat[mod].val;
    }
    void clear(){
        top=0;
        newnode();
    }
};
/*
这是前缀字典树的代码,prj是字符映射,封装的aA0的映射,支持魔改.
前缀字典树是路径上所有节点的值在一遍过去之后都会+1
可以改成末端的,自己改吧.
*/

AC自动机

struct ACauto{
    #define nmxx 26
    struct node{
        int tar[nmxx];
        int end,fail,dp;
        //是不是字符串结尾,失配指针,dp值
    };
    node *dat;
    vector<vector<int> >pos;//所有出现的位置
    vector<vector<int> >e;//失配指针树
    vector<string>s;//所有插入的字符串
    vector<int>rres;//所有字符串的各自出现次数
    int top,rtop;
    ACauto(int num=100000){
        dat=new node[num+5];
        e.resize(num+5);
        pos.resize(num+5);
        top=0;
        rtop=-1;
    }
    int newnode(){
        top++;
        dat[top].dp=dat[top].fail=dat[top].end=0;
        for(int i=0;i<nmxx;++i){
            dat[top].tar[i]=0;
        }
        pos[top].clear();
        e[top].clear();
        return top;
    }
    int prj(char num){
        // if('a'<=num&&num<='z')
            return num-'a';
        // if('A'<=num&&num<='Z')
        //     return num-'A'+26;
        // if('0'<=num&&num<='9')
        //     return num-'0'+52;
    }
    char proj(int pos){
        return pos+'a';
    }
    void insert(char* arr){
        int mod=0;
        int len=strlen(arr);
        for(int i=0;i<len;++i){
            int tmp=prj(arr[i]);
            if(dat[mod].tar[tmp]==0){
                int ttmp=newnode();
                dat[mod].tar[tmp]=ttmp;
            }
            mod=dat[mod].tar[tmp];
        }
        dat[mod].end++;
        pos[mod].push_back(++rtop);
        s.push_back(arr);
    }
    void prepare(){
        queue<int>q;
        dat[0].fail=0;
        for(int i=0;i<nmxx;++i){
            if(dat[0].tar[i]!=0)q.push(dat[0].tar[i]),dat[dat[0].tar[i]].fail=0,e[0].push_back(dat[0].tar[i]);
        }
        while(!q.empty()){
            auto i=q.front();q.pop();
            for(int j=0;j<nmxx;++j){
                if(dat[i].tar[j]!=0){
                    dat[dat[i].tar[j]].fail=dat[dat[i].fail].tar[j];
                    e[dat[dat[i].fail].tar[j]].push_back(dat[i].tar[j]);
                    q.push(dat[i].tar[j]);
                }
                else dat[i].tar[j]=dat[dat[i].fail].tar[j];
            }
        }
    }
    void dfs(int num=0){
        for(auto j:e[num]){
            dfs(j);
            dat[num].dp+=dat[j].dp;
        }
    }
    void ddfs(){
        rres.resize(rtop+1);
        for(int i=0;i<=top;++i){
            if(dat[i].end){
                for(auto kk:pos[i]){
                    rres[kk]=dat[i].dp;
                }
            }
        }
    }
    void match(char* arr){
        int mod=0;
        int len=strlen(arr);
        for(int i=0;i<len;++i){
            int tmp=prj(arr[i]);
            mod=dat[mod].tar[tmp];
            dat[mod].dp++;
        }
        dfs();
        ddfs();
    }
    void clear(){
        top=rtop=-1;
        newnode();
    }
};

子序列自动机(值域二分,O(n+|t|logn))

struct sonAuto{
    vector<vector<int> >dat;
    int m,n;
    void prepare(int* ddat,int nn,int mm){//[1,nn]
        m=mm;n=nn;
        dat.resize(m+10);
        for(int i=1;i<=n;++i){
            dat[ddat[i]].push_back(i);
        }
        for(int i=1;i<=m;++i){
            dat[i].push_back(n+1);
        }
    }
    char match(int* ddat,int len){//[1,len]
        int l=0;
        for(int i=1;i<=len;++i){
            l=*upper_bound(dat[ddat[i]].begin(),dat[ddat[i]].end(),l);
            if(l>=(n+1))return 0;
        }
        return 1;
    }
};
/*
子序列自动机,使用值域二分
prepare输入母串,长度,值域上界
match输入子串,长度
*/

后缀数组

struct sufStr{
    char *dat;
    int *sa,*rk,n,sz;
    sufStr(int nn=200000):sz(nn){
        dat=new char[sz+10]{};
        sa=new int[2*sz+20]{};
        rk=new int[2*sz+20]{};
    }
    void prepare(){//[1,n]
        int *id=new int[sz+10]{};
        int *cnt=new int[sz+10]{};
        int *oldrk=new int[sz+10]{};
        n=strlen(dat+1);
        int m=128,p=0;
        for(int i=1;i<=n;++i)cnt[rk[i]=dat[i]]++;
        for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;
        for(int w=1;;w<<=1,m=p){
            int cur=0;
            for(int i=n-w+1;i<=n;++i)id[++cur]=i;
            for(int i=1;i<=n;++i){
                if(sa[i]>w)id[++cur]=sa[i]-w;
            }
            fill(cnt,cnt+sz+10,0);
            for(int i=1;i<=n;++i)cnt[rk[i]]++;
            for(int i=1;i<=m;++i)cnt[i]+=cnt[i-1];
            for(int i=n;i>=1;--i)sa[cnt[rk[id[i]]]--]=id[i];
            p=0;
            copy(rk,rk+sz+10,oldrk);
            for(int i=1;i<=n;++i){
                if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
                else rk[sa[i]]=++p;
            }
            if(p==n)break;
        }
    }
};

马拉车Manacher

struct Manacher{
    char* dat;
    int* p;
    int len;//[0,len]
    Manacher(int n=10000000){
        dat=new char[(n<<1)+10]{};
        p=new int[(n<<1)+10]{};
    }
    void init(const char* ddat){//[1,len]
        int n=strlen(ddat+1);
        for(int i=2;i<=2*n;i+=2){
            dat[i-1]='|';
            dat[i]=ddat[(i>>1)];
        }
        dat[2*n+1]='|';
        dat[0]='&';
        dat[2*n+2]='$';//这两个字符不能被用到
        len=2*n+2;
        for(int i=0;i<=len;++i){
            p[i]=0;
        }
    }
    int prepare(){
        int res=0;
        for(int t=1,r=0,mid=0;t<=len;++t){
            if(t<=r)p[t]=min(p[(mid<<1)-t],r-t+1);
            while(dat[t-p[t]]==dat[t+p[t]])++p[t];
            if(p[t]+t>r)r=p[t]+t-1,mid=t;
            res=max(res,p[t]);
        }//p计算的是某点向两侧拓展的长度(包含中心),所以res要-1
        return res-1;
    }
};

图论

加边 最短路(Dijkstra) 缩点(Tarjan) 直径(d) 割点 割边 点双连通分量

template<typename T>
struct graph{
    vector<vector<pair<int,T> > >edge;
    int n;
    graph(int num=200000):n(num+5){
        edge.resize(num);
    }
    void adddir(int u,int v,T val){
        edge[u].push_back({v,val});
    }
    void adddedir(int u,int v,T val){
        edge[u].push_back({v,val});
        edge[v].push_back({u,val});
    }
    T* dis;
    void Dijkstra(int first){//对哪个点遍历,多少个点 
        dis=new T[n];
        fill(dis,dis+n,2147483647);
        priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q;
        q.push({0,first});
        while(!q.empty()){
            pair<T,int>qq=q.top();
            q.pop();
            if(qq.first>dis[qq.second])continue;
            dis[qq.second]=qq.first;
            for(auto i:edge[qq.second]){
                if((qq.first+i.second)<dis[i.first]){
                    dis[i.first]=qq.first+i.second;
                    q.push({qq.first+i.second,i.first});
                }
            }
        }
    }
    int *scc,*sccsize,sc,*dfn,*low,dfntop,*s,*in_stack,tp;
    void tarjan(int num){
        low[num]=dfn[num]=++dfntop;
        in_stack[num]=1;
        s[++tp]=num;
        for(auto i:edge[num]){
            if(!dfn[i.first]){
                tarjan(i.first);
                low[num]=min(low[num],low[i.first]);
            }else if(in_stack[i.first]){
                low[num]=min(low[num],dfn[i.first]);
            }
        }
        if(dfn[num]==low[num]){
            ++sc;
            while(s[tp]!=num){
                scc[s[tp]]=sc;
                sccsize[sc]++;
                in_stack[s[tp]]=0;
                --tp;
            }
            scc[s[tp]]=sc;
            sccsize[sc]++;
            in_stack[s[tp]]=0;
            --tp;
        }
    }
    void SCC(int num){/*强连通分量*/
        scc=new int[n]{};
        sccsize=new int[n]{};
        dfn=new int[n]{};
        low=new int[n]{};
        s=new int[n]{};
        in_stack=new int[n]{};
        sc=0,dfntop=0,tp=0;
        for(int i=1;i<=num;++i){
            if(dfn[i]==0){
                tarjan(i);
            }
        }
    }
    T *pval;/*缩点之后的点权*/
    void SCCpoints(graph& io,int num){
        // io.pval=new T[n]{};
        SCC(num);
        for(int i=1;i<=n;++i){
            for(auto j:edge[i]){
                if(scc[i]==scc[j.first]){
                    io.pval[scc[i]]+=j.second;
                }else{
                    io.adddir(scc[i],scc[j.first],j.second/*新边权是啥写上*/);
                }
            }
        }
    }
};
//用法: graph<int> ko(114514)
//         存储边权  多少个点

无权边也来一个.

struct graph{
    int n/*有多少个点*/,tmp;
    vector<vector<int> >edge;
    graph(int num=200000):n(num+5){
        edge.resize(n);
    }
    void adddir(int u,int v){
        edge[u].push_back(v);
    }
    void adddedir(int u,int v){
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    void clear(){
        for(int i=0;i<n;++i){
            edge[i].clear();
        }
    }
    int* d;
    void ddfs(int u,int fa){
        for(auto v:edge[u]){
            if(v==fa)continue;
            d[v]=d[u]+1;
            if(d[v]>d[tmp])tmp=v;
            ddfs(v,u);
        }
    }
    int getd(){/*get d by dfs*/
        tmp=-1145141919;
        d=new int[n]{};
        ddfs(1,0);
        d[tmp]=0;
        ddfs(tmp,0);
        tmp=d[tmp];
        delete[] d;
        return tmp;
    }
    void dpfs(int u,int fa){
        for(int v:edge[u]){
            if(v==fa)continue;
            dpfs(v,u);
            tmp=max(tmp,d[u]+d[v]+1);
            d[u]=max(d[u],d[v]+1);
        }
    }
    int getdpd(int root=1){/*get d by dp*/
        tmp=-1145141919;
        d=new int[n]{};
        dpfs(root,0);
        delete[] d;
        return tmp;
    }
    int *scc,*sccsize,sc,*dfn,*low,dfntop,*s,*in_stack,tp;
    void tarjan(int num){
        low[num]=dfn[num]=++dfntop;
        in_stack[num]=1;
        s[++tp]=num;
        for(auto i:edge[num]){
            if(!dfn[i]){
                tarjan(i);
                low[num]=min(low[num],low[i]);
            }else if(in_stack[i]){
                low[num]=min(low[num],dfn[i]);
            }
        }
        if(dfn[num]==low[num]){
            ++sc;
            while(s[tp]!=num){
                scc[s[tp]]=sc;
                sccsize[sc]++;
                in_stack[s[tp]]=0;
                --tp;
            }
            scc[s[tp]]=sc;
            sccsize[sc]++;
            in_stack[s[tp]]=0;
            --tp;
        }
    }
    void SCC(int num){/*强连通分量*/
        scc=new int[n]{};
        sccsize=new int[n]{};
        dfn=new int[n]{};
        low=new int[n]{};
        s=new int[n]{};
        in_stack=new int[n]{};
        sc=0,dfntop=0,tp=0;
        for(int i=1;i<=num;++i){
            if(dfn[i]==0){
                tarjan(i);
            }
        }
    }
    int *Cut,*Dfn,*Low,Dfntop;/*求割点*/
    void Tarjan(int num,int isroot){
        int subtree=0;/*子树有多少个*/
        Low[num]=Dfn[num]=++Dfntop;
        for(int i:edge[num]){
            if(!Dfn[i]){
                Tarjan(i,0);
                Low[num]=min(Low[num],Low[i]);
                subtree++;
                if(Dfn[num]<=Low[i]&&(!isroot))Cut[num]=1;
            }else Low[num]=min(Low[num],Dfn[i]);
        }
        if(isroot&&subtree>=2)Cut[num]=1;
    }
    void CUTpoint(int num){
        Dfn=new int[n]{};
        Low=new int[n]{};
        Cut=new int[n]{};
        Dfntop=0;
        for(int i=1;i<=num;++i){
            if(!Dfn[i]){
                Tarjan(i,1);
            }
        }
    }
    int *CUt,*DFn,*LOw,*_FA,DFntop;
    void TArjan(int num,int fa){
        _FA[num]=fa;
        LOw[num]=DFn[num]=++DFntop;
        for(int i:edge[num]){
            if(!DFn[i]){
                TArjan(i,num);
                LOw[num]=min(LOw[num],LOw[i]);
                if(DFn[num]<LOw[i])CUt[i]=1;
            }else if(DFn[i]<DFn[num]&&i!=fa){
                LOw[num]=min(LOw[num],DFn[i]);
            }
        }
    }
    void CUTedge(int num){/*当CUt[x]为1时,(_FA[x],x)是一条割边*/
        DFn=new int[n]{};
        LOw=new int[n]{};
        CUt=new int[n]{};
        _FA=new int[n]{};
        DFntop=0;
        for(int i=1;i<=num;++i){
            if(!DFn[i]){
                TArjan(i,0);
            }
        }
    }
    vector<vector<int> >DCCpoints;
    int *DCC,DCCtop;
    void DCCdfs(int num,int fa){
        DCC[num]=DCCtop;
        DCCpoints[DCCtop].push_back(num);
        for(auto j:edge[num]){
            if(DCC[j]||(CUt[num]==1&&_FA[num]==j)||(CUt[j]==1&&_FA[j]==num))continue;
            DCCdfs(j,num);
        }
    }
    void DCCedge(int num){
        DCC=new int[n]{};
        DCCpoints.resize(n);
        DCCtop=0;
        CUTedge(num);
        for(int i=1;i<=num;++i){//两点之间两条边,割一条还剩一条,这样的割边不是割边,要处理掉
            if(CUt[i]==1){
                int tmp=_FA[i],cnt=0;
                for(int j:edge[i]){
                    if(j==tmp)cnt++;
                }
                if(cnt>1)CUt[i]=0;
            }
        }
        for(int i=1;i<=num;++i){
            if(!DCC[i]){
                DCCtop++;
                DCCdfs(i,0);
            }
        }
    }
    int *bccdfn,*bcclow,bcctop,bc;
    vector<vector<int> >BCC;
    stack<int>st;
    void bcctarjan(int num,int fa){
        int subtree=0;
        bcclow[num]=bccdfn[num]=++bcctop;
        st.push(num);
        for(int i:edge[num]){
            if(!bccdfn[i]){
                subtree++;
                bcctarjan(i,num);
                bcclow[num]=min(bcclow[num],bcclow[i]);
                if(bcclow[i]>=bccdfn[num]){
                    bc++;
                    for(;;){
                        BCC[bc].push_back(st.top());
                        if(st.top()==i){
                            st.pop();
                            break;
                        }
                        st.pop();
                    }
                    BCC[bc].push_back(num);
                }
            }else if(i!=fa){
                bcclow[num]=min(bcclow[num],bccdfn[i]);
            }
        }
        if(fa==0&&subtree==0)BCC[++bc].push_back(num);
    }
    void BCCpoint(int num){/*点双连通分量*/
        bcclow=new int[n]{};
        bccdfn=new int[n]{};
        BCC.resize(n);
        bcctop=0;
        bc=0;
        for(int i=1;i<=num;++i){
            if(!bccdfn[i]){
                bcctarjan(i,0);
            }
        }
    }
    int *cens,*cenw,cenn,cenid[2];
    void GetCen(int num, int fa){
        cens[num]=1;cenw[num]=0;
        for(auto i:edge[num]){
            if(i==fa)continue;
            GetCen(i,num);
            cens[num]+=cens[i];
            cenw[num]=max(cenw[num],cens[i]);
        }
        cenw[num]=max(cenw[num],cenn-cens[num]);
        if(cenw[num]<=cenn/2){
            cenid[cenid[0]!=0]=num;
        }
    }
    void getCent(int nn){
        cens=new int[n]{};
        cenw=new int[n]{};
        cenid[0]=cenid[1]=0;
        cenn=nn;
        GetCen(1,0);
    }//求树的重心(删掉该店整棵树分成若干子树,其中最大的子树最小,平均)
    template<typename T1,typename T2,typename T3>
    T1 qp(T1 b,T2 po,T3 p){
        T1 res(1);
        while(po>0){
            if(po&1)
                res=res*b%p;
            b=b*b%p;
            po>>=1;
        }
        return res;
    }
    u64 base=19491001,mod=998244353;
    u64 *hsh;
    pair<u64,u64> *htmp;
    void hdfs(int num,int ko,i64 dep){//树哈希,求出一个数的哈希值
        cens[num]=1;
        for(auto i:edge[num]){
            if(i==ko)continue;
            hdfs(i,num,dep+1);
            cens[num]+=cens[i];
        }
        int top=0;
        for(auto i:edge[num]){
            if(i==ko)continue;
            htmp[++top]={hsh[i],cens[i]};
        }
        sort(htmp+1,htmp+1+top);
        u64 res=dep*19491001;
        dep=1;
        for(int i=1;i<=top;++i){//19491001    998244353
            res=(res+htmp[i].first*qp(base,dep,mod))%mod;
            dep+=htmp[i].second;
        }
        hsh[num]=res;
    }
    pair<u64,u64> hhash(int nn){
        htmp=new pair<u64,u64>[n];
        hsh=new u64[n];
        getCent(nn);
        if(cenid[1]==0){
            hdfs(cenid[0],0,1);
            return {hsh[cenid[0]],0};
        }else{
            hdfs(cenid[0],0,1);
            u64 tmp=hsh[cenid[0]];
            hdfs(cenid[1],0,1);
            u64 ttmp=hsh[cenid[1]];
            if(tmp<ttmp)swap(tmp,ttmp);
            return {tmp,ttmp};
        }
    }
};

树哈希

emmm的板子.

struct treehash{
    vector<int>*G;
    map<vector<int>,int>mp;
    int dfs(int pre,int cur){
        vector<int>vec;
        for(auto nxt:G[cur]){
            if(nxt!=pre){
                vec.push_back(dfs(cur,nxt));
            }
        }
        sort(vec.begin(),vec.end());
        if(mp.find(vec)==mp.end()){
            mp[vec]=mp.size();
        }
        return mp[vec];
    }
    int operator()(vector<int>G[],int root){
        this->G=G;
        return dfs(root,root);
    }
};

二维哈希

自然溢出法,分别求前缀哈希,然后计算答案.

u64 base1[100000],base2[100000];
void hhash(u64** a,int n,int m,const u64 base=998244353,const u64 mod=1e16+61){
    base1[0]=base2[0]=1;
    for(int i=1;i<=max(m,n);++i){
        base1[i]=base1[i-1]*base;
        base2[i]=base2[i-1]*mod;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j]=a[i][j-1]*base+a[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j]+=a[i-1][j]*mod;
        }
    }
}
u64 hh(u64** a,int y1,int y2,int x1,int x2){
    return a[y2][x2]-a[y1-1][x2]*base2[y2-y1+1]-a[y2][x1-1]*base1[x2-x1+1]+a[y1-1][x1-1]*base1[x2-x1+1]*base2[y2-y1+1];
}

二分图 最大匹配 匈牙利算法

复杂度 $O(nm)$ 因为要遍历整张图.

struct bipGraph{
    int *vis,*visb;
    vector<vector<int> >mat;
    int _n,_m,top;
    bipGraph(int n=500,int m=500):_n(n),_m(m){
        top=0;
        mat.resize(n+10);
        vis=new int[n+10]{};
        visb=new int[m+10]{};
    }
    void insert(int a,int b){
        mat[a].push_back(b);
    }
    int mmatch(int i){
        for(int j:mat[i]){
            if(vis[j]<top){//能匹配 
                vis[j]=top;
                if(visb[j]==0||mmatch(visb[j])){//也有人了 
                    visb[j]=i;
                    return 1;
                }
            }
        }
        return 0;
    }
    int match(){//[1,n]
        int res=0;
        for(int i=1;i<=_n;++i){
            top++;//使用时间戳取代memset,常数小的一批
            if(mmatch(i)==1){
                res++;
            }
        }
        return res;
    }
};

2-SAT 连边

[1-n]表示x取真值,[n+1,2n]表示x取假值.
将与或关系转化为蕴含关系:

a假或b假,现在要满足这条式子:
a真->b必假,所以连接 $a\to b+n$
b真->a必假,所以连接 $b\to a+n$

其余情况同理.

2-SAT Check

给出的是checker以及合法解的输出,使用图论把整张图缩成若干个强连通分量.

for(int i=1;i<=n;++i){
    if(ko.scc[i]==ko.scc[i+n]){
        fout<<"NO\n";
        return 0;
    }
}
fout<<"YES\n";
for(int i=1;i<=n;++i){
    if(ko.scc[i]>ko.scc[i+n]){
        fout<<"1 ";
    }else{
        fout<<"0 ";
    }
}

传递闭包

给一张邻接矩阵,计算任意两点是否能够到达,a[i][j]表示这两个点能不能到达.

bitset<110>dat[110];
void transitiveClosure(int n){
    for(int j=1;j<=n;++j){
        for(int i=1;i<=n;++i){
            if(dat[i][j]){
                dat[i]|=dat[j];
            }
        }
    }
}

负环

给一张图,判定有没有负环(一个边权和为负的环),使用SPFA,复杂度O(nm).

vector<vector<pair<int,long long> > >edge;
queue<int>q;
long long n,m,res;
long long dis[3010];
int vis[3010];
int cnt[3010];//最短路径边数
char negCirc(){
    while(!q.empty())q.pop();
    q.push(1);dis[1]=0;vis[1]=1;
    while(!q.empty()){
        auto u=q.front();q.pop();
        vis[u]=0;
        for(auto v:edge[u]){
            if(dis[v.first]>dis[u]+v.second){
                dis[v.first]=dis[u]+v.second;
                cnt[v.first]=cnt[u]+1;
                if(cnt[v.first]>=n){
                    return 1;
                }
                if(vis[v.first]==0){
                    vis[v.first]=1;
                    q.push(v.first);
                }
            }
        }
    }
    return 0;
}

网络最大流

struct maxFlow{
    #define inf 0x3f3f3f3f
    struct edge{
        int v,nxt,cap,flow;
    };
    edge* e;
    int *dep,*cur,*head,top;
    int n,s,t;
    maxFlow(int nn,int ss,int tt,int num=100000):n(nn),s(ss),t(tt){
        num=num*2+5;
        e=new edge[num];
        head=new int[num];
        for(int i=0;i<num;++i){head[i]=-1;}
        dep=new int[num]{};
        cur=new int[num]{};
        top=-1;
    }
    void adddir(int u,int v,int w){
        e[++top]={v,head[u],w,0};
        head[u]=top;
        e[++top]={u,head[v],0,0};
        head[v]=top;
    }
    bool bfs(){
        queue<int>q;
        memset(dep,0,sizeof(int)*(n+1));
        dep[s]=1;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for (int i=head[u];i!=-1;i=e[i].nxt){
                int v=e[i].v;
                if((!dep[v])&&(e[i].cap>e[i].flow)){
                    dep[v]=dep[u]+1;
                    q.push(v);
                }
            }
        }
        return dep[t];
    }
    int dfs(int u,int flow){
        if((u==t)||(!flow))return flow;
        int ret=0;
        for(int& i=cur[u];i!=-1;i=e[i].nxt){
            int v=e[i].v,d;
            if ((dep[v]==dep[u]+1)&&(d=dfs(v,min(flow-ret,e[i].cap-e[i].flow)))){
                ret+=d;
                e[i].flow+=d;
                e[i^1].flow-=d;
                if(ret==flow)return ret;
            }
        }
        return ret;
    }
    long long dinic(){
        long long res=0;
        while(bfs()){
            memcpy(cur,head,sizeof(int)*(n+1));
            res+=dfs(s,inf);
        }
        return res;
    }
};

最小费用最大流(无负环)

const i64 N=5010; //最大点数
const i64 M=1e5+7;// 反向边 双倍空间
const i64 inf=1e18;
struct MinCostMaxFlow{ // 只能处理正权边
    i64 n,S,T,d[N],p[N],h[N];
    bool inq[N],vis[N];
    i64 head[N],ec=1; // 边编号从 2 开始 方便寻找反向边
    struct Edge{
        i64 u,v,nxt,w,cost;
    }e[M];
    struct Node{
        i64 x,dis;
        bool operator<(const Node &p) const {
            return dis > p.dis;
        }
    };
    void AddEdge(i64 u,i64 v,i64 w,i64 cost){
        e[++ec]=(Edge){u,v,head[u],w,cost};
        head[u]=ec;
    }
    void span(i64 u,i64 v,i64 w,i64 cost){//u->v,流量限制,流量费用
        AddEdge(u,v,w,cost);//加一条有向流量边
        AddEdge(v,u,0,-cost);
    }
    bool SPFA(){
        static queue<i64> Q;
        for(i64 i=1;i<=n;++i){
            inq[i]=false,
            d[i]=inf;
        }
        Q.emplace(S),inq[S]=true,d[S]=0;
        while (!Q.empty()){
            i64 x=Q.front();
            Q.pop(),inq[x]=false;
            for (i64 i=head[x],v=e[i].v; i; i=e[i].nxt,v=e[i].v)
                if (e[i].w && d[v] > d[x]+e[i].cost){
                    d[v]=d[x]+e[i].cost;
                    if (!inq[v])
                        Q.emplace(v),inq[v]=true;
                }
        }
        return d[T] != inf;
    }
    pair<i64,i64> solve(){
        if (!SPFA())
            return {0,0};
        static priority_queue<Node> Q;
        for(i64 i=1;i<=n;++i){
            h[i]=d[i],
            vis[i]=false,d[i]=inf; // 初始势能
        }
        i64 flow=0,cost=0;
        while (1){
            Q.emplace((Node){S,d[S]=0});
            while (!Q.empty()){ // 执行 Dijkstra.
                i64 x=Q.top().x;
                Q.pop();
                if (vis[x])
                    continue;
                else
                    vis[x]=true;
                for (i64 i=head[x],v=e[i].v; i; i=e[i].nxt,v=e[i].v)
                    if (e[i].w && d[v] > d[x]+e[i].cost+h[x] - h[v])
                        d[v]=d[x]+e[i].cost+h[x] - h[v],p[v]=i,Q.emplace((Node){v,d[v]});
            }
            if (d[T] == inf)
                break;
            i64 fb=inf,cb=0; // 当前增广路流流量,当前增广路流单位费用
            for (i64 x=T; x != S; x=e[p[x]].u)
                fb=min(fb,e[p[x]].w),cb += e[p[x]].cost;
            flow += fb,cost += fb*cb;
            for (i64 x=T; x != S; x=e[p[x]].u)
                e[p[x]].w -= fb,e[p[x] ^ 1].w += fb;
            for(i64 i=1;i<=n;++i){
                h[i] += d[i],
                vis[i]=false,d[i]=inf; // 更新势能
            }
        }
        return {flow,cost};
    }
};

最小费用最大流(有负环)

n最大200个点,值域最大1e5.

#include<bits/stdc++.h>
using namespace std;
constexpr int inf=1000000000;
namespace net{
    int cnt,lim,h[205],hc[205],dis[205],f[100005],w[100005],to[100005],nxt[100005];
    bool on[205];
    queue<int> q;
    void lockstar(int x){lim=x;}//封锁下标大于 x 的边 
    void reset(){cnt=1,lim=inf;}
    inline void addstar(int x,int y,int _f,int _w){
        f[++cnt]=_f,w[cnt]=_w,to[cnt]=y,nxt[cnt]=h[x],h[x]=cnt;
        f[++cnt]=0,w[cnt]=-_w,to[cnt]=x,nxt[cnt]=h[y],h[y]=cnt;
    }
    bool SPFA(int x,int y){
        memset(dis,63,sizeof(dis)),dis[x]=0;
        for(q.push(x);!q.empty();q.pop()){
            int now=q.front();
            on[now]=0;
            for(int i=h[now];i;i=nxt[i]) if(i<=lim&&f[i]&&dis[to[i]]>dis[now]+w[i]){
                dis[to[i]]=dis[now]+w[i];
                if(!on[to[i]]) on[to[i]]=1,q.push(to[i]);
            }
        }
        return dis[y]<inf;
    }
    int dfs(int x,int flow,int aim){
        if(x==aim||!flow) return flow;
        int ret=0;
        on[x]=1;
        for(int &i=hc[x];i;i=nxt[i]) if(i<=lim&&!on[to[i]]&&dis[to[i]]==dis[x]+w[i]){
            int now=dfs(to[i],min(flow,f[i]),aim);
            ret+=now,f[i]-=now,f[i^1]+=now,flow-=now;
            if(!flow) break;
        }
        on[x]=0;
        return ret;
    }
    pair<int,int> SSP(int S,int T){
        pair<int,int> ret;
        while(SPFA(S,T)){
            memcpy(hc,h,sizeof(hc));
            int flow=dfs(S,inf,T);
            ret.first+=flow;
            ret.second+=dis[T]*flow;
        }
        return ret;
    }
}
//强制满流负权边 连反向正权边退流 限制退流流量
//有源汇上下界最小费用可行流解决
int n,m,S,T,SS,TT,ans,mem,maxflow,w[205];
int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    net::reset();//n点m边,源汇点
    for(int i=1;i<=m;i++){
        static int x,y,f,_w;
        scanf("%d%d%d%d",&x,&y,&f,&_w);//x->y flow cost
        if(!f) continue;//要你何用
        if(_w>=0) net::addstar(x,y,f,_w);
        else{//下界0 上界f 费用取反
            w[x]-=f,w[y]+=f,ans+=_w*f;
            net::addstar(y,x,f,-_w);
        }
    }
    SS=n+1,TT=SS+1,mem=net::cnt;
    for(int i=1;i<=n;i++){
        if(w[i]>0) net::addstar(SS,i,w[i],0);
        if(w[i]<0) net::addstar(i,TT,-w[i],0);
    }
    net::addstar(T,S,inf,0);
    auto SSP=net::SSP(SS,TT);//可行流
    maxflow=net::f[net::cnt];//拿到可行流实际流量
    ans+=SSP.second;//拿到可行流费用
    net::lockstar(mem);//封边
    SSP=net::SSP(S,T);//在原图上跑
    maxflow+=SSP.first,ans+=SSP.second;
    printf("%d %d\n",maxflow,ans);
    return 0;
}

数学

快速幂,龟速乘(qp,qmul),快速乘

ps:如果希望求负几次方直接反转成 $1/x$ 然后直接反转n即可.

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}

template<typename T>
T qmul(T a,T b,T p){//a*b对p取模,由于没有int128所以要用快速幂思想解这个问题 
    T res=0;
    for(;b;b>>=1){
        if(b&1)res=(res+a)%p;
        a=(a<<1)%p;
    }
    return res;
}

long long qmul(long long a,long long b,long long p){//a*b对p取模 
    a%=p;b%=p;
    long long c=(long double)a*b/p;
    long long res=a*b-c*p;
    if(res<0)res+=p;
    else if(res>=p)res-=p;
    return res;
}

CRT exCRT 中国剩余定理 拓展中国剩余定理

template<typename T>
T exgcd(T a,T b,T &x,T &y){//返回值是gcd 
    T x1=1,x2=0,x3=0,x4=1;
    while(b!=0){
        T c=a/b;
        tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
    }
    x=x1,y=x2;
    return a;
}
template<typename T>
__int128 CRT(T* mmod,T* rres,int n){//模几,剩几
    __int128 sum=1,res=0,m,c,x,y;
    for(int i=1;i<=n;++i){
        sum*=mmod[i];
    }
    for(int i=1;i<=n;++i){
        m=sum/mmod[i];
        exgcd(m,(__int128)mmod[i],x,y);
        x=(x%sum+sum)%sum;
        c=m*x;
        res=(res+rres[i]*c)%sum;
    }
    return res;
}
template<typename T>
__int128 exCRT(T* mmod,T* rres,int n){//模几 剩几
    __int128 tmp=mmod[1],ttmp,res=rres[1],x,y,k;
    for(int i=2;i<=n;++i){
        ttmp=((rres[i]-res)%mmod[i]+mmod[i])%mmod[i];
        __int128 gg=exgcd(tmp,(__int128)mmod[i],x,y);
        x=ttmp/gg*x%mmod[i];
        res+=tmp*x;
        tmp*=mmod[i]/gg;
        res=(res+tmp)%tmp;
    }
    return res;
}

离散化

sort(dat+1,dat+1+n);
m=unique(dat+1,dat+1+n)-dat-1;
//m是实际不重合元素个数.
//tmp是每个元素离散化之后的值(排名).
tmp=upper_bound(dat+1,dat+1+m,val)-dat-1;

组合数(杨辉三角)

说在前面,Flu的排列组合大的n永远放在前面,这是约定.

解决模数不是质数的组合数求解情况(没逆元).

long long yh[114][114];
void init(int num,long long mod=100000000000000003){
    for(int i=1;i<=num;++i){
        yh[i][1]=yh[i][i]=1;
        for(int j=2;j<i;++j){
            yh[i][j]=(yh[i-1][j]+yh[i-1][j-1])%mod;
        }
    }
}
inline long long C(int n,int m){
    return yh[n+1][m+1];
}

排列组合数(预处理阶乘)

long long fac[200010],defac[200010];
const int mod=1000000007;
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
void init(int n){
    fac[0]=defac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=(i*fac[i-1])%mod;
    }
    defac[n]=qp(fac[n],mod-2,mod);
    for(int i=n-1;i>0;--i){
        defac[i]=defac[i+1]*(i+1)%mod;
    }
}
long long C(int n,int m){
    if(m==0)return 1;
    if(m<0||m>n)return 0;
    return fac[n]*defac[m]%mod*defac[n-m]%mod;
}
long long A(int n,int m){
    if(m==0)return 1;
    if(m<0||m>n)return 0;
    return fac[n]*defac[n-m]%mod;
}

排列组合数(直接计算)

template<typename T>
T A(T n,T m,T p){
    if(n<m)return 0;
    T  res=1;
    for(T i=n-m+1;i<=n;++i){
        res=res*i%p;
    }
    return res;
}
template<typename T>
T C(T n,T m,T p){
    if(n<m)return 0;
    m=min(m,n-m);
    T res=1,udd=1,tmp=n-m,x,y;
    for(T i=1;i<=m;++i){
        res=res*(i+tmp)%p;
        udd=udd*i%p;
    }
    exgcd(udd,p,x,y);
    x=(x%p+p)%p;//x是逆元
    return res*x%p;
}

最大公约数,最小公倍数(GCD,LCM)

别用 __gcd() ,可以用 std::gcd() .

最快的版本.

long long stein(long long x,long long y){
    if(x==y)return x;
    long long a=y-x;
    long long b=x-y;
    int n=__builtin_ctzll(b);
    long long s=(x<y?a:b);
    long long t=(x<y?x:y);
    return stein(s>>n,t);
}
long long gcd(long long x,long long y){
    if(x==0)return y;
    if(y==0)return x;
    int n=__builtin_ctzll(x);
    int m=__builtin_ctzll(y);
    return (stein(x>>n,y>>m)<<(n<m?n:m));
}
long long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}//注意在函数外特判负数的情况

最好记最好写的版本.

template<typename T>
T gcd(T a,T b){
    return b?gcd(b,a%b):a;
}//欧几里得算法 

以下是高精适用的版本,只需要支持判定是不是奇数以及除2的操作和减法即可.

template<typename T>//优化的更相减损术 
T gcd(T a,T b){//a>=b guarantee
    if(a==b)return a;
    if(a&1){//a ji
        if(b&1){//b ji
            T tmp=a-b;
            return tmp>b?gcd(tmp,b):gcd(b,tmp);
        }
        else{
            return gcd(a,b>>1);
        }
    }
    else{
        if(b&1){//b ji
            T tmp=a>>1;
            return tmp>b?gcd(tmp,b):gcd(b,tmp);
        }
        else{
            return gcd(a>>1,b>>1)<<1;
        }
    }
}

拓展欧几里得算法(EXGCD)

常用的迭代版本.(求逆元只要求两数互质就行了,不然逆元不存在也就求不了了,qp求逆元要求mod是质数)

template<typename T>
T exgcd(T a,T b,T &x,T &y){//返回值是gcd 
    T x1=1,x2=0,x3=0,x4=1;
    while(b!=0){
        T c=a/b;
        tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
    }
    x=x1,y=x2;
    return a;
}

很好记的版本

template<typename T>
void exgcd(T a,T b,T &x,T &y){
    if(b)exgcd(b,a%b,y,x),y-=a/b*x;
    else x=1,y=0;
}

Lucas(卢卡斯定理)

$$\binom{n}{m}\mod p=\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\binom{n\mod p}{m\mod p}\mod p$$

template<typename T>
T lucas(T n,T m,T p){//p must be a prime
    if(m==0)return 1;
    return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}

线性求逆元

能够线性求出[1,n]中每个数的逆元.

inv[1]=1;
for(int i=2;i<=n;++i){
    inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

数论分块

for(long long l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    //do something
}

for(long long l=1,r;l<=min(n,m);l=r+1){
    r=min(n/(n/l),m/(m/l));
    //do something
}

欧拉筛

int   vis[1000010];//存最小质因数,负的表示质数表中的位置(负的)
int  p[100010],ptop=0;//存质数 
short  mu[1000010];//莫比乌斯函数 
int  musu[1000010];//梅滕斯函数,莫比乌斯前缀和 
int   phi[1000010];//欧拉函数 
long long phisu[1000010];//欧拉函数前缀和 
int     d[1000010];//存每个数的约数个数 
int mnnum[1000010];//最小质因子出现次数 
void sieve(int n){//[1,n]
    phi[1]=1;phisu[1]=1;mu[1]=1;musu[1]=1;d[1]=1;
    int tmp;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            vis[i]=-(++ptop);
            p[ptop]=i;
            mu[i]=-1;//
            phi[i]=i-1;//
            d[i]=2;//
            mnnum[i]=1;//
        }
        for(int j=1;j<=ptop&&i*p[j]<=n;++j){
            vis[i*p[j]]=p[j];
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];//
                mnnum[i*p[j]]=mnnum[i]+1;//
                d[i*p[j]]=d[i]/mnnum[i*p[j]]*(mnnum[i*p[j]]+1);//
                break;
            }else{
                mu[i*p[j]]=-mu[i];//
                phi[i*p[j]]=phi[i]*(p[j]-1);//
                mnnum[i*p[j]]=1;//
                d[i*p[j]]=d[i]*2;//
            }
        }
        musu[i]=musu[i-1]+mu[i];//
        phisu[i]=phisu[i-1]+phi[i];//
    }
}

DLC:因数分解板子,复杂度 $O(d(n)\log(d(n)))$ ,d(n)表示数的因子,在1e6范围内max(d(n))=240,数据大的情况下也许能打过根号暴力找因子的,但是数据大了欧拉筛就成瓶颈了……
返回值不保证递增,结合欧拉筛一起用

int ddivtop;
vector<pair<int,int> >ddiv;
void divdfs(vector<int>& res,int num,int val){
    if(num>=ddivtop){
        res.push_back(val);
        return;
    }
    for(int i=0;i<=ddiv[num].first;++i){
        divdfs(res,num+1,val);
        val*=ddiv[num].second;
    }
}
vector<int>divsor(int num){
    vector<int> res;
    unordered_map<int,int>mp;
    while(1){
        if(vis[num]<0){
            mp[prime[-vis[num]]]++;
            break;
        }
        mp[vis[num]]++;
        num/=vis[num];
    }
    ddiv.clear();ddivtop=0;
    for(auto i:mp){
        ddiv.push_back({i.second,i.first});
        ddivtop++;
    }
    divdfs(res,0,1);
    return res;
}

杜教筛(S_sieve)

建立在欧拉筛的基础上,算是一个插件(?).
使用前需先使用欧拉筛筛到 mxxn 的范围,然后再进行单点求积性函数前缀和.

constexpr int mxxn=1000000;
unordered_map<long long,long long>_S_mu;
long long S_mu(long long n){
    if(n<=mxxn)return musu[n];
    if(_S_mu[n]!=0)return _S_mu[n];
    long long res=1;
    for(long long l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=S_mu(n/l)*(r-l+1);
    }
    return _S_mu[n]=res;
}
unordered_map<unsigned long long,unsigned long long>_S_phi;
unsigned long long S_phi(long long n){
    if(n<=mxxn)return phisu[n];
    if(_S_phi[n]!=0)return _S_phi[n];
    unsigned long long res=0;
    res=(n&1)?((n+1)>>1)*n:(n>>1)*(n+1);
    for(long long l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        res-=S_phi(n/l)*(r-l+1);
    }
    return _S_phi[n]=res;
}

单点求phi

复杂度O(logn)(其实你可以用两次杜教筛解决一切问题…).

template<typename T>
T phi(T n){
    T res=n;
    for(T i=2;i*i<=n;i++){
        if(n%i==0)res=res/i*(i-1);
        while(n%i==0)n/=i;
    }
    return (n!=1)?(res/n*(n-1)):(res);
}

Min_25筛(min25 sieve)

给出的板子是求 $\sum_{i=1}^n\mu(i)$ .

long long sq,n;
const int mod=1000000007;
long long id1[200010],id2[200010],w[200010];
int   vis[1000010];//存最小质因数,负的表示质数表中的位置(负的)
long long  p[100010],ptop=0;//存质数 
void sieve(int n){//[1,n]
    int tmp;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            vis[i]=-(++ptop);
            p[ptop]=i;
        }
        for(int j=1;j<=ptop&&i*p[j]<=n;++j){
            vis[i*p[j]]=p[j];
            if(i%p[j]==0){
                break;
            }
        }
    }
}
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
long long getid(long long x){
    if(x<=sq)return id1[x];
    return id2[n/x];
}
long long g[200010],sum[200010];
long long f(long long x){//快速计算构造的完全积性函数前缀和
    return -x+1;
}
long long S(long long n,long long j){
    if(p[j]>n)return 0;
    i64 res=(g[getid(n)]-sum[j])%mod;
    for(int k=j+1;k<=ptop&&p[k]*p[k]<=n;++k){
        for(i64 e=1,pk=p[k];pk<=n;++e,pk*=p[k]){
            res=(res+(/*f(p^e_k)*/(e>1?0:-1)*(S(n/pk,k)+(e>1))%mod))%mod;
        }
    }
    return (res%mod+mod)%mod;
}
long long solve(long long n){
    sq=sqrt(n);
    sieve(sq);
    int m=0;
    for(i64 i=1;i<=ptop;++i){
        sum[i]=(sum[i-1]-1)%mod;
    }
    for(i64 l=1,r;l<=n;l=r+1){
        r=(n/(n/l));
        w[++m]=n/l;
        g[m]=f(w[m]);
        if(w[m]<=sq)id1[w[m]]=m;
        else id2[n/w[m]]=m;
    }
    for(int i=1;i<=ptop;++i){
        for(int j=1;j<=m&&p[i]*p[i]<=w[j];++j){
            g[j]=(g[j]-/*f(p_i)*/1*(g[getid(w[j]/p[i])]-sum[i-1])%mod)%mod;
        }
    }
    return (S(n,0)+1)%mod;
}

BSGS(exBSGS)大步小步

求形如下面的式子.(叫做离散对数同余方程)

$$a^x\equiv n\mod p$$

的式子,其中 $\gcd(a,p)=1$ 时使用BSGS即可,否则使用exBSGS,无解输出 -1 ,复杂度 $O(\sqrt p)$ ,常数大一点,因为用了umap

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
unordered_map<u64,u64>bsgsmp;
u64 BSGS(u64 a,u64 n,u64 p,u64 ad=1){
    bsgsmp.clear();
    u64 m=ceil(sqrt(p));
    for(u64 k=0,val=n;k<m;++k,val=val*a%p){
        bsgsmp[val]=k;
    }
    for(u64 i=0,tmp=qp(a,m,p),val=ad;i<=m;++i,val=val*tmp%p){
        if(bsgsmp.find(val)!=bsgsmp.end()&&(i*m)>=bsgsmp[val]){
            return i*m-bsgsmp[val];
        }
    }
    return -1;//无解
}
u64 exBSGS(u64 a,u64 n,u64 p){
    a%=p;n%=p;
    if(n==1||p==1)return 0;
    u64 cnt=0,gg,curd=1;
    while((gg=__gcd(a,p))!=1){
        if(n%gg!=0)return -1;
        cnt++;n/=gg;p/=gg;
        curd=(curd*a/gg)%p;
        if(curd==n)return cnt;
    }
    u64 res=BSGS(a,n,p,curd);
    if(res==-1)return -1;
    return res+cnt;
}

二次剩余

求解形如 $x^2\equiv n\mod p$ 的式子.其中,p是奇质数,必须读入全局变量,程序将从小到大返回两个值代表程序的两个解.(n=0时只有0一个解)

long long sq,p;
struct ccomplex{
    long long real,imag;
    ccomplex(long long a=0,long long b=0):real(a),imag(b){}
    ccomplex operator *(const ccomplex& io)const{
        return ccomplex{(real*io.real%p+sq*imag%p*io.imag%p+p)%p,(imag*io.real%p+real*io.imag%p+p)%p};
    }
    ccomplex operator %(const long long& io)const{
        return ccomplex{real%io,imag%io};
    }
};
template<typename T1,typename T2>
T1 qp(T1 b,T2 po){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
pair<long long,long long>Cipolla(long long n){
    n%=p;
    if(n==0)return {0,0};
    if(qp(n,(p-1)>>1)==(p-1))return {-1,-1};
    long long res1=-1,res2=-1,a;
    while(1){
        a=rand()%p;
        sq=(a*a%p-n+p)%p;
        if(qp(sq,(p-1)>>1)==(p-1))break;
    }
    res1=qp(ccomplex(a,1),(p+1)>>1).real;
    res2=p-res1;
    return (res1>res2)?pair<long long,long long>(res2,res1):pair<long long,long long>(res1,res2);
}

拉格朗日插值1(自然数次方前缀和)

计算 $\sum_{i=1}^ni^k$ ,复杂度 $O(k\log n)$ .

const long long mod=1000000007;
template<typename T1,typename T2>
T1 qp(T1 b,T2 po){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%mod;
        b=b*b%mod;
        po>>=1;
    }
    return res;
}
long long dat[1000010];//插值点（原地取值） 
long long pre[1000010];//前缀积 
long long suf[1000010];//后缀积 
long long fac[1000010];//阶乘 
long long Lag1(long long n,long long k){
    fac[0]=1;pre[0]=1;
    for(long long i=1;i<=k+2;++i){
        dat[i]=(qp(i,k)+dat[i-1])%mod;
        fac[i]=(fac[i-1]*i)%mod;
        pre[i]=(pre[i-1]*(n-i))%mod;
    }
    suf[k+3]=1;
    for(long long i=k+2;i>=0;--i){
        suf[i]=((n-i)*suf[i+1])%mod;
    }
    long long res=0;
    for(int i=1;i<=k+2;++i){
        res=(res+(((k+2-i)&1)?-1LL:1LL)*dat[i]*pre[i-1]%mod*suf[i+1]%mod*qp(fac[i-1]*fac[k+2-i]%mod,mod-2)%mod)%mod;
    }
    res=(res%mod+mod)%mod;
    return res;
}

拉格朗日插值2(函数多项式拟合预测)

const long long mod=998244353;
template<typename T1,typename T2>
T1 qp(T1 b,T2 po,T1 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
long long Lag2(long long* x,long long* y,long long pos,int n){//[1,n]
    long long res=0,tmpu,tmpd;
    for(int i=1;i<=n;++i){
        tmpu=1,tmpd=1;
        for(int j=1;j<i;++j){
            tmpu=(tmpu*(pos-x[j]))%mod;
            tmpd=(tmpd*(x[i]-x[j]))%mod;
        }
        for(int j=i+1;j<=n;++j){
            tmpu=(tmpu*(pos-x[j]))%mod;
            tmpd=(tmpd*(x[i]-x[j]))%mod;
        }
        res=(res+y[i]*tmpu%mod*qp(tmpd,mod-2,mod)%mod)%mod;
    }
    res=(res%mod+mod)%mod;
    return res;
}

PollardRho(PR,Pollard_Rho)质因数分解

namespace decompos{
    unsigned long long Number(unsigned long long a,unsigned long long b){
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        return (a+rng()%(b-a+1));
    }
    unsigned long long stein(unsigned long long x,unsigned long long y){
        if(x==y)return x;
        unsigned long long a=y-x;
        unsigned long long b=x-y;
        int n=__builtin_ctzll(b);
        unsigned long long s=(x<y?a:b);
        unsigned long long t=(x<y?x:y);
        return stein(s>>n,t);
    }
    unsigned long long gcd(unsigned long long x,unsigned long long y){
        if(x==0)return y;
        if(y==0)return x;
        int n=__builtin_ctzll(x);
        int m=__builtin_ctzll(y);
        return (stein(x>>n,y>>m)<<(n<m?n:m));
    }
    unsigned long long limit=2147483648;
    vector<int>small={2,7,61};
    vector<int>large={2,325,9375,28178,450775,9780504,1795265022};
    unsigned long long qp(unsigned long long x,unsigned long long y,unsigned long long m){
        unsigned long long res=1;
        while(y){
            if(y&1)res=((unsigned __int128)res*x)%m;
            x=((unsigned __int128)x*x)%m;
            y>>=1;
        }
        return res;
    }
    bool isComposite(unsigned long long a,unsigned long long d,unsigned long long n,unsigned long long s){
        unsigned long long x=qp(a,d,n);
        if(x==1)return false;
        while(s--){
            if(x==n-1)return false;
            x=((unsigned __int128)x*x)%n;
        }
        return true;
    }
    bool isPrime(unsigned long long n){
        if(n==1)
            return false;
        vector<int>bases=(n<limit?small:large);
        if(find(bases.begin(),bases.end(),n)!=bases.end())
            return true;
        for(int p:bases)
            if(n%p==0)
                return false;
        unsigned long long s=__builtin_ctzll(n-1);
        unsigned long long d=(n-1)>>s;
        for(int base:bases){
            if(isComposite(base,d,n,s))
                return false;
        }
        return true;
    }
    class Montgomery{
        unsigned long long m;
        unsigned long long r;
        public:
        Montgomery(unsigned long long n):m(n),r(n){
            for(int i=0;i<5;i++){
                r*=2-m*r;
            }
        }
        unsigned long long fma(unsigned long long a,unsigned long long b,unsigned long long c)const{
            unsigned __int128 d=(unsigned __int128)(a)*b;
            unsigned long long e=c+m+(d>>64);
            unsigned long long f=(unsigned long long)(d)*r;
            unsigned long long g=((unsigned __int128)(f)*m)>>64;
            return (e-g);
        }
        unsigned long long mul(unsigned long long a,unsigned long long b)const{return fma(a,b,0);}
    };
    unsigned long long PollardRho(unsigned long long n){
        if(n%2==0)return 2;
        Montgomery m(n);
        unsigned long long c1=1;
        unsigned long long c2=2;
        unsigned long long M=512;
        unsigned long long w1=1;
        unsigned long long w2=2;
    retry:
        unsigned long long z1=w1;
        unsigned long long z2=w2;
        for(unsigned long long k=M;;k <<= 1){
            unsigned long long x1=z1+n;
            unsigned long long x2=z2+n;
            for(unsigned long long j=0;j<k;j+=M){
                unsigned long long y1=z1;
                unsigned long long y2=z2;
                unsigned long long q1=1;
                unsigned long long q2=2;
                z1=m.fma(z1,z1,c1);
                z2=m.fma(z2,z2,c2);
                for(unsigned long long i=0;i<M;i++){
                    unsigned long long t1=x1-z1;
                    unsigned long long t2=x2-z2;
                    z1=m.fma(z1,z1,c1);
                    z2=m.fma(z2,z2,c2);
                    q1=m.mul(q1,t1);
                    q2=m.mul(q2,t2);
                }
                q1=m.mul(q1,x1-z1);
                q2=m.mul(q2,x2-z2);
                unsigned long long q3=m.mul(q1,q2);
                unsigned long long g3=gcd(n,q3);
                if(g3==1)continue;
                if(g3!=n)return g3;
                unsigned long long g1=gcd(n,q1);
                unsigned long long g2=gcd(n,q2);
                unsigned long long c=(g1!=1?c1:c2);
                unsigned long long x=(g1!=1?x1:x2);
                unsigned long long z=(g1!=1?y1:y2);
                unsigned long long g=(g1!=1?g1:g2);
                if(g==n){
                    do{
                        z=m.fma(z,z,c);
                        g=gcd(n,x-z);
                    }while(g==1);
                }
                if(g!=n)return g;
                w1+=2;
                w2+=2;
                goto retry;
            }
        }
    }
    void factorize(unsigned long long n,vector<unsigned long long>& res){
        if(n<=1)return;
        if(isPrime(n)){
            res.push_back(n);
            return;
        }
        unsigned long long p=PollardRho(n);
        factorize(p,res);
        factorize(n/p,res);
    }
}
//用法:使用factorize(数,接受答案的vec)进行一个数的分解,返回一个数的所有不重因子(记得排序)别的函数都不用管 

快速傅里叶变换(FFT)

用于解决多项式快速乘法问题…

#define cp complex<double>
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
const double pi(acos(-1));
int rev[2100000];
int init(int n){
    int k=0,lim=1;/*n是数列长度,k是log(s),s是答案的最长长2*n-1*/
    while(lim<n)k++,lim<<=1;
    for(int i=0;i<lim;i++){//生成旋转交换数列 
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return lim;//这个是紧接着进行FFT的填的范围[0,lim)
}
void FFT(cp* a,int n,int flag){//区间[0,n) 
    for(int i=0;i<n;i++){
        if(i<rev[i]){
            swap(a[i],a[rev[i]]);
        }
    }
    for(int h=1;h<n;h<<=1){
        cp wn=exp(cp(0,flag*pi/h));
        for(int j=0;j<n;j+=(h<<1)){
            cp w(1,0);
            for(int k=j;k<j+h;k++){
                tie(a[k],a[k+h])=make_tuple(a[k]+w*a[k+h],a[k]-w*a[k+h]);
                w*=wn;
            }
        }
    }
    if(flag==-1){//IFFT
        for(int i=0;i<n;i++){
            a[i]/=n;
        }
    }
}
long long gt(const double& io){
    return ((long long)(io+0.5));
}
__int128 gt(const long double& io){
    return ((__int128)(io+0.5));
}
void getres(cp* res,int* rres){
    memset(rres,0,sizeof(rres));
    for(int i=0;i<lim;++i){
        rres[i]+=res[i].real()+0.5;
        rres[i+1]+=rres[i]/10;
        rres[i]%=10;
    }
    int ff=0;
    for(int i=lim-1;i>=0;--i){
        if(ff==1){
            printf("%d",rres[i]);
        }else if(rres[i]!=0){
            ff=1;
            printf("%d",rres[i]);
        }
    }
    if(ff==0){
        printf("0");
    }
}

快速数论变换(NTT)

使用逆元代换上式的复数和一堆奇奇怪怪的东西得到这个…

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
int rev[2100000];
int iinit(int num){return num;}
template<typename ...Args>
int iinit(int n,Args ...nn){
    return n+iinit(nn...);
}
template<typename ...Args>
int init(int n,Args ...nn){
    n=iinit(n,nn...);/*n是每个数列长度,k=log(lim)*/
    int k=0,lim=1;
    while(lim<(n))k++,lim<<=1;
    for(int i=0;i<lim;i++){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return lim;//[0,lim)
}
constexpr int mod=998244353;
constexpr int ord=3;
void NTT(int* a,int n,int flag){//[0,n)
    for(int i=0;i<n;i++){
        if(rev[i]<i){
            swap(a[i],a[rev[i]]);
        }
    }
    for(int h=2;h<=n;h<<=1){
        int k=h>>1;
        int gn=qp((long long)ord,(mod-1)/h,mod);
        for(int i=0;i<n;i+=h){
            int g=1;
            for(int j=0;j<k;++j,g=1LL*g*gn%mod){
                int tmp=1LL*a[i+j+k]*g%mod;
                a[i+j+k]=(a[i+j]-tmp+mod)%mod;
                a[i+j]=(a[i+j]+tmp)%mod;
            }
        }
    }
    if(flag==-1){//FNTT
        reverse(a+1,a+n);
        int inv=qp((long long)n,mod-2,mod);
        for(int i=0;i<n;i++){
            a[i]=1LL*a[i]*inv%mod;
        }
    }
}

MTT 任意模数卷积

模数可以不是质数.

经测试不能通过 FFT-killer 的数据,但是洛谷的板子题能过.这是分拆FFT的版本,下面还会有三模NTT的版本.

#define cp complex<long double>
template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
const long double pi=(acos(-1));
int rev[2100000];
int iinit(int num){return num;}
template<typename ...Args>
int iinit(int n,Args ...nn){
    return n+iinit(nn...);
}
template<typename ...Args>
int init(int n,Args ...nn){
    n=iinit(n,nn...);/*n是每个数列长度,k=log(lim)*/
    int k=0,lim=1;
    while(lim<(n))k++,lim<<=1;
    for(int i=0;i<lim;i++){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return lim;//[0,lim)
}
void FFT(cp* a,int n,int flag){//[0,n) 
    for(int i=0;i<n;i++){
        if(i<rev[i]){
            swap(a[i],a[rev[i]]);
        }
    }
    for(int h=1;h<n;h<<=1){
        cp wn=exp(cp(0,flag*pi/h));
        for(int j=0;j<n;j+=(h<<1)){
            cp w(1,0);
            for(int k=j;k<j+h;k++){
                tie(a[k],a[k+h])=make_tuple(a[k]+w*a[k+h],a[k]-w*a[k+h]);
                w*=wn;
            }
        }
    }
    if(flag==-1){//IFFT
        for(int i=0;i<n;i++){
            a[i]/=n;
        }
    }
}
long long mod=1000000007;
long long cceil(const long double& num){
    return ((long long)(num+0.5))%mod;
}
long long gt(const double& io){
    return ((long long)(io+0.5))%mod;
}
__int128 gt(const long double& io){
    return ((__int128)(io+0.5))%mod;
}
void MTT(long long* a,long long* b,long long* res,int la,int lb){//[0,la) [0,lb)
    int lim=init(la+lb-1);
    static cp f[1500010],g[1500010],h[1500010];
    for(int i=0;i<la;++i){
        f[i]=complex<long double>(a[i]&32767,0);
        g[i]=complex<long double>(a[i]>>15,0);
    }
    for(int i=0;i<lb;++i){
        h[i]=complex<long double>(b[i]&32767,b[i]>>15);
    }
    FFT(f,lim,1);
    FFT(g,lim,1);
    FFT(h,lim,1);
    for(int i=0;i<lim;++i){
        f[i]=(f[i]*h[i]);
        g[i]=(g[i]*h[i]);
    }
    FFT(f,lim,-1);
    FFT(g,lim,-1);
    for(int i=0;i<lim;++i){
        res[i]=(cceil(f[i].real())+
               ((cceil(g[i].real()+cceil(f[i].imag())))<<15)+
               (cceil(g[i].imag())<<30))%mod;
    }
    for(int i=0;i<lim;++i){//复原
        f[i]=g[i]=h[i]=complex<long double>(0,0);
    }
}

FWT 快速沃尔什变换

求解 $C_i=\sum_{j\oplus k=i}A_j\times B_k$ 的问题,其中 $\oplus$ 可代表 |或 &与 ^抑或运算.

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
constexpr long long mod=998244353;
long long lim,inv2;
void FWT_or(long long *a,int opt){//[0,2^n)
    for(int i=1;i<lim;i<<=1){
        for(int p=i<<1,j=0;j<lim;j+=p){
            for(int k=0;k<i;++k){
                if(opt==1)
                    a[i+j+k]=(a[j+k]+a[i+j+k])%mod;
                else
                    a[i+j+k]=(a[i+j+k]+mod-a[j+k])%mod;
            }
        }
    }
}
void FWT_and(long long *a,int opt){//[0,2^n)
    for(int i=1;i<lim;i<<=1){
        for(int p=i<<1,j=0;j<lim;j+=p){
            for(int k=0;k<i;++k){
                if(opt==1)
                    a[j+k]=(a[j+k]+a[i+j+k])%mod;
                else
                    a[j+k]=(a[j+k]+mod-a[i+j+k])%mod;
            }
        }
    }
}
void FWT_xor(long long *a,int opt){//[0,2^n)
    for(int i=1;i<lim;i<<=1){
        for(int p=i<<1,j=0;j<lim;j+=p){
            for(int k=0;k<i;++k){
                tie(a[j+k],a[i+j+k])=make_tuple((a[j+k]+a[i+j+k])%mod,(mod+a[j+k]-a[i+j+k])%mod);
                if(opt==-1)
                    a[j+k]=a[j+k]*inv2%mod,a[i+j+k]=a[i+j+k]*inv2%mod;
            }
        }
    }
}

FST 子集卷积

int da[1<<21],db[1<<21];
int f[21][1<<21],g[21][1<<21],h[21][1<<21];
long long n,m,res;
constexpr int mod=1000000009;
void FWT_or(int *a,int opt){//[0,2^n)
    if(opt==1){
        for(int i=1;i<m;i<<=1){
            for(int p=i<<1,j=0;j<m;j+=p){
                for(int k=0;k<i;++k){
                    a[i+j+k]=(a[j+k]+a[i+j+k])%mod;
                }
            }
        }
    }else{
        for(int i=1;i<m;i<<=1){
            for(int p=i<<1,j=0;j<m;j+=p){
                for(int k=0;k<i;++k){
                    a[i+j+k]=(a[i+j+k]+mod-a[j+k])%mod;
                }
            }
        }
    }
}
int main(){
    fin>>n;
    m=1<<n;
    for(int i=0;i<m;++i){
        fin>>da[i];
        f[__builtin_popcount(i)][i]=da[i];
    }
    for(int i=0;i<m;++i){
        fin>>db[i];
        g[__builtin_popcount(i)][i]=db[i];
    }
    for(int i=0;i<=n;++i){
        FWT_or(f[i],1);
        FWT_or(g[i],1);
    }
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            for(int k=0;k<m;++k){
                h[i][k]=(h[i][k]+1LL*f[j][k]*g[i-j][k]%mod)%mod;
            }
        }
    }
    for(int i=0;i<=n;++i){
        FWT_or(h[i],-1);
    }
    for(int i=0;i<m;++i){
        fout<<h[__builtin_popcount(i)][i]<<" ";
    }
    return 0;
}

多项式求乘法逆 多项式求逆 INV

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res=1;
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
int rev[2100000];
int init(int n){
    int k=0,lim=1;/*n是数列长度,k是log(s),s是答案的最长长度,2*n-1*/
    while(lim<(n<<1))k++,lim<<=1;
    for(int i=0;i<lim;i++){//生成旋转交换数列 
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return lim;
}
constexpr int mod=998244353;
constexpr int ord=3;
void NTT(long long* a,int n,int flag){//[0,n)
    for(int i=0;i<n;i++){
        if(rev[i]<i){
            swap(a[i],a[rev[i]]);
        }
    }
    for(int h=2;h<=n;h<<=1){
        int k=h>>1;
        int gn=qp((long long)ord,(mod-1)/h,mod);
        for(int i=0;i<n;i+=h){
            int g=1;
            for(int j=0;j<k;++j,g=1LL*g*gn%mod){
                int tmp=1LL*a[i+j+k]*g%mod;
                a[i+j+k]=(a[i+j]-tmp+mod)%mod;
                a[i+j]=(a[i+j]+tmp)%mod;
            }
        }
    }
    if(flag==-1){//FNTT
        reverse(a+1,a+n);
        int inv=qp((long long)n,mod-2,mod);
        for(int i=0;i<n;i++){
            a[i]=1LL*a[i]*inv%mod;
        }
    }
}
/*        原函数        结果          辅助数组       [0,len)*/
void INV(long long* a,long long* b,long long* tmp,int len){
    if(len==1){
        b[0]=qp(a[0],mod-2,mod);
    }else{
        INV(a,b,tmp,(len+1)>>1);
        int p=init(len);
        copy(a,a+len,tmp);
        fill(tmp+len,tmp+p,0);
        NTT(tmp,p,1);
        NTT(b,p,1);
        for(int i=0;i<p;++i){
            b[i]=(2-b[i]*tmp[i]%mod+mod)%mod*b[i]%mod;
        }
        NTT(b,p,-1);
        fill(b+len,b+p,0);
    }
}

BostanMori

多项式P/Q求第M单项的系数是多少,可以取模

#define i64 long long;
const int mod=998244353;
const int G=3;
const int GI=332748118;
#define poly vector<i64>
#define be begin
#define en end
i64 qp(i64 a,i64 b){
    i64 r=1;
    while(b){
        if(b&1)r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}
namespace NTT{
    vector<int>rev;
    void ntt(poly &a,int n,int inv){
        for(int i=0;i<n;i++){
            if(i<rev[i]){
                swap(a[i],a[rev[i]]);
            }
        }
        for(int mid=1;mid<n;mid<<=1){
            i64 w1=qp(inv==1?G:GI,(mod-1)/(mid<<1));
            for(int i=0;i<n;i+=(mid<<1)){
                i64 w=1;
                for(int j=0;j<mid;j++,w=w*w1%mod){
                    i64 x=a[i+j],y=w*a[i+j+mid]%mod;
                    a[i+j]=(x+y)%mod;
                    a[i+j+mid]=(x-y+mod)%mod;
                }
            }
        }
        if(inv==-1){
            i64 invn=qp(n,mod-2);
            for(int i=0;i<n;i++){
                a[i]=a[i]*invn%mod;
            }
        }
    }
    poly mul(const poly &a,const poly &b){
        if(a.empty()||b.empty()){
            return {};
        }
        int n=1,bit=0;
        int len=a.size()+b.size()-1;
        while(n<len){
            n<<=1;
            bit++;
        }
        rev.resize(n);
        for(int i=0;i<n;i++){
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        }
        poly fa(n),fb(n);
        copy(a.be(),a.en(),fa.be());
        copy(b.be(),b.en(),fb.be());
        ntt(fa,n,1);
        ntt(fb,n,1);
        for(int i=0;i<n;i++){
            fa[i]=fa[i]*fb[i]%mod;
        }
        ntt(fa,n,-1);
        fa.resize(len);
        return fa;
    }
}
i64 BostanMori(const poly&P,const poly&Q,i64 n){
    poly p=P,q=Q;
    while(n>0){
        poly qn=q;
        for(size_t i=0;i<qn.size();i++){
            if(i&1){
                qn[i]=(mod-qn[i])%mod;
            }
        }
        poly u=NTT::mul(p,qn);
        poly v=NTT::mul(q,qn);
        p.clear();
        for(size_t i=(n&1);i<u.size();i+=2){
            p.push_back(u[i]);
        }
        q.clear();
        for(size_t i=0;i<v.size();i+=2){
            q.push_back(v[i]);
        }
        n>>=1;
    }
    return p[0]*qp(q[0],mod-2)%mod;
}//多项式P/Q取第M项

线性基

支持插入元素(返回能不能插进去),查询所有数的最大抑或最小抑或第k小抑或,dat记录插入的原数据

struct basis{
    __int128 *dat,*tmp;
    int len,flag;/*有效长度,即logn长度,能不能表示0*/
    basis(int llen=64):len(llen),flag(0){
        dat=new __int128[len]{};
        tmp=new __int128[len]{};
    }
    char insert(__int128 x){
        for(int i=len-1;i>=0;--i){
            if((x>>i)&1){
                if(dat[i]!=0){
                    x^=dat[i];
                }else{
                    dat[i]=x;
                    return 0;
                }
            }
        }
        flag=1;
        return 1;/*没有插进去*/
    }
    __int128 getmin(){
        if(flag==1)return 1;
        for(int i=0;i<len;++i){
            if(dat[i]!=0)return dat[i];
        }
        return 0x0d000721;/*理论上这个值不会出现*/
    }
    __int128 getmax(__int128 res=0){//某个数必须选
        for(int i=len-1;i>=0;--i){
            res=max(res,res^dat[i]);
        }
        return res;
    }
    __int128 getkmin(__int128 k){
        __int128 res=0,cnt=0;
        k-=flag;
        if(k==0)return 0;
        for(int i=0;i<len;++i){
            for(int j=i-1;j>=0;--j){
                if((dat[i]>>j)&1)dat[i]^=dat[j];
            }
            if(dat[i]!=0)tmp[cnt++]=dat[i];
        }
        if(k>=(1<<cnt))return 0x0d000721;
        for(int i=0;i<cnt;++i){
            if((k>>i)&1)res^=tmp[i];
        }
        return res;
    }
};

模拟退火(SA)

double SAcheck(double v){
    
}
double SA(double rres,double t=3000,double EPS=1e-10,double down=0.996){
    srand(time(0));
    double res=SAcheck(rres);
    while(t>EPS){
        double eres=rres+t*((rand()<<1)-RAND_MAX);//新随机答案
        double tmp=SAcheck(eres);
        double de=tmp-res;//答案下降多少
        if(de<0){//保留答案
            res=tmp;
            rres=eres;
        }else if(exp(-de/t)*RAND_MAX>rng()){//有多少的概率保留答案
            rres=eres;
        }else{//恢复原局面

        }
        t*=down;
    }
}
double solve(){
    double res=1145141919;
    for(int i=1;i<=200;++i){//进行多少轮退火
        res=min(res,SA(res));
    }
    return res;
}

计算几何

直角坐标转极坐标

使用 atan2(double y,double x) !!!

旋转函数

array<double,2>rot(double x, double y, double arc){
    // 旋转矩阵公式：
    // x' = x * cos(arc) - y * sin(arc)
    // y' = x * sin(arc) + y * cos(arc)
    double c=cos(arc);
    double s=sin(arc);
    return {x*c-y*s,x*s+y*c};//点绕(0,0)逆时针旋转,负值是顺时针旋转,弧度制
}

旋转卡壳

给定n个点,求凸包直径(平面最远点对)(注意下面的板子里面v是直径,只是题干要求输出v的平方)

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

int n;

const double eps=1e-9;
int dcmp(double x){
    return (fabs(x)<=eps)?0:(x<0?-1:1);
}
struct Point{
    double x,y;
    Point(double X=0,double Y=0){x=X,y=Y;}
};
struct Vector{
    double x,y;
    Vector(double X=0,double Y=0){x=X,y=Y;}
};
inline Vector operator-(Point x,Point y){// 点-点=向量
    return Vector(x.x-y.x,x.y-y.y);
}
inline double cross(Vector x,Vector y){ // 向量叉积
    return x.x*y.y-x.y*y.x;
}
inline double operator*(Vector x,Vector y){ // 向量叉积
    return cross(x,y);
}
inline double len(Vector x){ // 向量模长
    return sqrt(x.x*x.x+x.y*x.y);
}

int stk[50005];
bool used[50005];
vector<Point> ConvexHull(Point* poly, int n){ // Andrew算法求凸包
    int top=0;
    sort(poly+1,poly+n+1,[&](Point x,Point y){
        return (x.x==y.x)?(x.y<y.y):(x.x<y.x);
    });
    stk[++top]=1;
    for(int i=2;i<=n;i++){
        while(top>1&&dcmp((poly[stk[top]]-poly[stk[top-1]])*(poly[i]-poly[stk[top]]))<=0){
            used[stk[top--]]=0;
        }
        used[i]=1;
        stk[++top]=i;
    }
    int tmp=top;
    for(int i=n-1;i;i--){
        if(used[i]) continue;
        while(top>tmp&&dcmp((poly[stk[top]]-poly[stk[top-1]])*(poly[i]-poly[stk[top]]))<=0){
            used[stk[top--]]=0;
        }
        used[i]=1;
        stk[++top]=i;
    }
    vector<Point> a;
    for(int i=1;i<=top;i++){
        a.push_back(poly[stk[i]]);
    }
    return a;
}

struct Line{
    Point x;Vector y;
    Line(Point X,Vector Y){x=X,y=Y;}
    Line(Point X,Point Y){x=X,y=Y-X;}
};

inline double DistanceToLine(Point P,Line x){// 点到直线的距离
    Vector v1=x.y, v2=P-x.x;
    return fabs(cross(v1,v2))/len(v1);
}

double RoatingCalipers(vector<Point> poly){// 旋转卡壳
    if(poly.size()==3) return len(poly[1]-poly[0]);
    int cur=0;
    double ans=0;
    for(int i=0;i<poly.size()-1;i++){
        Line line(poly[i],poly[i+1]);
        while(DistanceToLine(poly[cur], line) <= DistanceToLine(poly[(cur+1)%poly.size()], line)){
            cur=(cur+1)%poly.size();
        }
        ans=max(ans, max(len(poly[i]-poly[cur]), len(poly[i+1]-poly[cur])));
    }
    return ans;
}

Point poly[50005];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>poly[i].x>>poly[i].y;
    double v=RoatingCalipers(ConvexHull(poly, n));
    // cerr << v << '\n';
    cout<<(int)round(v * v);
    return 0;
}

半平面交

三个直线,按照某种规律选择哪个边

#include<bits/stdc++.h>
using namespace std;
int read(){
    int a;
    scanf("%d",&a);
    return a;
}
#define N 100006
#define eps 1e-13
// inline double abs(const double &a){return a>0?a:-a;}
struct Vector{
    double x,y;
    inline double len(){return std::sqrt(x*x+y*y);}
    inline void operator += (const Vector &a){x+=a.x;y+=a.y;}
    inline void operator -= (const Vector &a){x-=a.x;y-=a.y;}
    inline void operator *= (const double &a){x*=a;y*=a;}
    inline void operator /= (const double &a){x/=a;y/=a;}
};
inline Vector operator + (const Vector &a,const Vector &b){return (Vector){a.x+b.x,a.y+b.y};}
inline Vector operator - (const Vector &a,const Vector &b){return (Vector){a.x-b.x,a.y-b.y};}
inline Vector operator * (const Vector &a,const double &b){return (Vector){a.x*b,a.y*b};}
inline Vector operator / (const Vector &a,const double &b){return (Vector){a.x/b,a.y/b};}
inline double dot(const Vector &a,const Vector &b){return a.x*b.x+a.y*b.y;}
inline double cross(const Vector &a,const Vector &b){return a.x*b.y-a.y*b.x;}
struct Line{
    Vector p,way;
    double ang;
    inline void makeLine(const Vector &a,const Vector &b){p=a;way=b;ang=atan2(b.y,b.x);}
};
inline int onRight(const Line &a,const Vector &b){return cross(a.way,b-a.p)<=-eps;}
inline int cmp(const Line &a,const Line &b){return a.ang<b.ang;} 
inline Vector intersect(const Line &a,const Line &b){
    double x=cross(b.way,a.p-b.p)/cross(a.way,b.way);
    return a.p+a.way*x;
}
inline double polygonArea(int n,Vector *a){
    double S=0;
    for(int i=1;i<n;i++) S+=cross(a[i],a[i+1]);
    S+=cross(a[n],a[1]);
    return S/2;
}
int l,r;
Line que[N];
inline int halfPlane(int n,Line *a,Vector *p){
    std::sort(a+1,a+1+n,cmp);
    l=r=0;que[0]=a[1];
    for(int i=2;i<=n;i++){
        while(l<r&&onRight(a[i],p[r])) r--;
        while(l<r&&onRight(a[i],p[l+1])) l++;
        que[++r]=a[i];
        if(abs(cross(que[r].way,que[r-1].way))<=eps){//平行
            if(onRight(que[r],que[r-1].p)&&dot(que[r].way,que[r-1].way)<=-eps) return 0;
            r--;
            if(!onRight(que[r],a[i].p)) que[r]=a[i];
        }
        if(l<r) p[r]=intersect(que[r],que[r-1]);
    }
    while(l<r&&onRight(que[l],p[r])) r--;
    if(r-l<=1) return 0;
    p[l]=intersect(que[l],que[r]);
    return 1;
}
Vector p[N],in[N];
Line a[N];
int main(){
    int n=read(),o=0;
    while(n--){
        int m=read();
        for(int i=1;i<=m;i++) in[i].x=read(),in[i].y=read();
        for(int i=1;i<m;i++) a[++o].makeLine(in[i],in[i+1]-in[i]);
        a[++o].makeLine(in[m],in[1]-in[m]);
    }
    if(!halfPlane(o,a,p)) puts("0.000");
    else printf("%.3lf\n",polygonArea(r-l+1,p+l-1));
    return 0;
}//只求多边形的面积:poly...(m(点数),in(读入的东西));

最小圆覆盖

#include<bits/stdc++.h>
using namespace std;
#define db double

const int M=1e6+1;
const db eps=1e-10;
db dcmp(db x){if(fabs(x)<eps) return 0;return x;}
int n;
struct point{
    db x,y;
    point(db a=0,db b=0):x(a),y(b){}
    void in(){scanf("%lf%lf",&x,&y);}
}pp[M];

point operator +(point a,point b){return point(a.x+b.x,a.y+b.y);}
point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);}
point operator *(point a,db    b){return point(a.x*b  ,a.y*b  );}
point operator /(point a,db    b){return point(a.x/b  ,a.y/b  );}

db cross(point a,point b){return a.x*b.y-a.y*b.x;}
db dot  (point a,point b){return a.x*b.x+a.y*b.y;}

double dis(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

point getmid(point a,point b){return point((a.x+b.x)/2,(a.y+b.y)/2);}
point rotate(point a){return point(-a.y,a.x);}


struct circle{
    point o;db r;
    circle(){}
    circle(point a,db r):o(a),r(r){}
};
struct triangle{
    point t1,t2,t3;
    circle cir2(){
        db Bx = t2.x-t1.x, By = t2.y-t1.y;
          db Cx = t3.x-t1.x, Cy = t3.y-t1.y;
          db D = 2*(Bx*Cy-By*Cx);
          db cx = (Cy*(Bx*Bx+By*By) - By*(Cx*Cx+Cy*Cy))/D + t1.x;
          db cy = (Bx*(Cx*Cx+Cy*Cy) - Cx*(Bx*Bx+By*By))/D + t1.y;
          point p = point(cx, cy);
          return circle(p, dis(t1,p));
    }//数学方法求外心
    triangle(){}
    triangle(point a,point b,point c):t1(a),t2(b),t3(c){}
};
circle circlein(point t1,point t2,point t3){
        point v1=t2-t1,v2=t1-t3;v1=rotate(v1),v2=rotate(v2);
        point p1=getmid(t1,t2),p2=getmid(t1,t3);point u=p1-p2;
        db t=cross(v2,u)/cross(v1,v2);
        point oo=p1+v1*t;
        return circle(oo,dcmp(dis(oo,t1)));
}//几何方法求外心，三角形两边中垂线交点
array<db,3> work(){
    circle ans;
    ans.o=pp[1];ans.r=0;
    for(int i=2;i<=n;i++){
        if(dis(pp[i],ans.o)>ans.r+eps){
            ans=circle(pp[i],0);
            for(int j=1;j<i;j++){
                if(dis(pp[j],ans.o)>ans.r+eps){
                    ans.o=getmid(pp[i],pp[j]);
                    ans.r=dis(pp[j],pp[i])/2;
                    for(int k=1;k<j;k++){
                        if(dis(pp[k],ans.o)>ans.r+eps){
                            ans=circlein(pp[i],pp[j],pp[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.2lf %.2lf %.2lf\n",ans.o.x,ans.o.y,ans.r);
    return {ans.r,ans.o.x,ans.o.y};//答案半径 答案坐标 期望复杂度O(n),最坏复杂度O(n**3)
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)pp[i].in();
    random_shuffle(pp+1,pp+n+1);//记得打乱
    work();//不打乱的话会被卡复杂度和精度，蒟蒻我被卡了十几次90分。
    return 0;
}

多边形的核

多边形的核也是一个多边形,满足核内部任意一点能够看到整个多边形(也就是把多边形由线段构成改为由直线构成,求那个交集)
输入:T组数据
n个点
顺时针给出点的坐标

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MN 50000
#define eps 1e-10
using namespace std;
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 - '0';ch = getchar();}
    return x * f;
}

struct P{
    double x,y;
    P(double _x=0,double _y=0):x(_x),y(_y){}
    P operator + (P b) {return P(x+b.x,y+b.y);}
    P operator - (P b) {return P(x-b.x,y-b.y);} 
    P operator * (double b) {return P(x*b,y*b);}
    friend double cross(P a,P b) {return a.x*b.y-b.x*a.y;}
}p[MN+5],pt[MN+5];

struct L{
    P p,v;double slop;
    L(){}
    L(P x,P y):p(x),v(y){slop=atan2(y.y,y.x);}
    P operator * (L b){P a=p-b.p;double t=cross(b.v,a)/cross(v,b.v);return p+v*t;}
    bool left(P b){ return cross(v,b-p)>eps;}
    bool operator < (const L &y) const {return slop<y.slop;} 
}s[MN+5],q[MN+5];

int n,top,tail;

void solve(){
    q[top=tail=1]=s[1];
    for(int i=2;i<=n;i++)
    {
        while(top>tail&&!s[i].left(p[top])) --top;
        while(top>tail&&!s[i].left(p[tail+1])) ++tail;
        if(fabs(s[i].slop-q[top].slop)<eps) 
            q[top]=s[i].left(q[top].p)?q[top]:s[i];
        else q[++top]=s[i];
        p[top]=q[top]*q[top-1];
    }
    while(tail<top&&(q[tail].left(p[top])==0)) --top;
}

int main(){
    for(int T=read();T;T--){
        n=read();    
        for(int i=1;i<=n;i++) scanf("%lf%lf",&pt[i].x,&pt[i].y);
        for(int i=2;i<=n;i++) s[i]=L(pt[i-1],pt[i]-pt[i-1]);
        s[1]=L(pt[n],pt[1]-pt[n]);
        sort(s+1,s+n+1); solve();
        if(top-tail+1<3) {    
            for(int i=1;i<n;i++) s[i]=L(pt[i+1],pt[i]-pt[i+1]);
            s[n]=L(pt[1],pt[n]-pt[1]);
            sort(s+1,s+n+1);solve();
        }
        if(top-tail+1<3) puts("0.00");
        else { 
            p[tail]=q[tail]*q[top];double area=0;
            for(int i=tail;i<top;i++) area+=cross(p[i],p[i+1]);
            area+=cross(p[top],p[tail]);
            printf("%.2f\n",fabs(area)/2.00+eps);
        }
    }
    return 0;
}

全家桶

正在研发中…

#define double long double
constexpr double eeps=1e-5;
int sgn(double x){
    return (abs(x)<eeps)?(0):(x<0?-1:1);
}
char equ(double x,double y){
    return abs(x-y)<eeps;
}

struct point{
    double x,y;
    point(double xx=0,double yy=0):x(xx),y(yy){}
    char operator<(point io){
        return (x==io.x)?(y<io.y):(x<io.x);
    }
    double dis(point io){return sqrt((io.y-y)*(io.y-y)+(io.x-x)*(io.x-x));}
    point operator-(point io){return {x-io.x,y-io.y};}
    char operator==(point io){return equ(x,io.x)&&equ(y,io.y);}
    void prr(){fout<<"("<<x<<","<<y<<")";}
};
struct circle{
    point p;
    double r;
    circle(double xx=0,double yy=0,double rr=0):p(xx,yy),r(rr){}
    int isincircle(point io){
        double tmp=p.dis(io)-r;
        if(tmp==0)return 0;//在圆上
        if(tmp<0)return 1; //在圆内
        else return -1;    //在园外
    }
};
struct direct{
    double x,y;
    direct(const double& xx=0,const double& yy=0):x(xx),y(yy){}
    direct(const point& a,const point& b):x(b.x-a.x),y(b.y-a.y){}//a->b
    double xmul(const direct& io){return x*io.y-y*io.x;}//正值代表逆时针方向,负值代表顺时针方向,0代表共线
    double dotmul(const direct& io){return x*io.x+y*io.y;}
    direct inv(){return {-x,-y};}
    double lenth(){return sqrt(x*x+y*y);}
    direct operator+(direct io)const{return direct(x+io.x,y+io.y);}
    direct operator-(direct io){return direct(x-io.x,y-io.y);}
    direct operator*(double io){return direct(io*x,io*y);}
    double operator*(direct io){return x*io.x+y*io.y;}
};
double xmul(point a,point b,point c,point d){
    return direct(a,b).xmul({c,d});
}
struct line{
    double k,b;
    line(double a=0,double bb=0):k(a),b(bb){}
    line(point a,point bb){
        if(a.x==bb.x){
            k=0,b=0;
        }else{
            k=(a.y-bb.y)/(a.x-bb.x);
            b=bb.y-k*bb.x;
        }
    }
    char operator<(line io){return (k==io.k)?(b>io.b):(k<io.k);}
    point cross(line io){return (sgn(k-io.k)==0)?point(0,0):point((io.b-b)/(k-io.k),k*(io.b-b)/(k-io.k)+b);}
    int ishigher(const point& io){return sgn(io.y-k*io.x-b);}
    void prr(){fout<<"y="<<k<<"x+"<<b<<" ";}
};
struct triangle{
    point a,b,c;
    triangle(double x,double y,double xx,double yy,double xxx,double yyy):a(x,y),b(xx,yy),c(xxx,yyy){}
    char isValid(){if(a==b||a==c||b==c)return 0;}//检查三角形三个点是否合法
    char isInTri(point io){
        direct u(a,b),v(a,c),x(a,io);
        if(equ(u.x,0)){
            if(equ(v.x,0))return 0;
            double alp=x.x/v.x;
            if(equ(u.y,0))return 0;
            double mu=(x.y-alp*v.y)/u.y;
            if(0<=mu&&0<=alp&&alp+mu<=1)return 1;
            else return 0;
        }else{
            double tmp=u.x*v.y-u.y*v.x;
            if(equ(tmp,0))return 0;
            double alp=(u.x*x.y-u.y*x.x)/tmp;
            double mu=(x.x-alp*v.x)/u.x;
            if(0<=mu&&0<=alp&&alp+mu<=1)return 1;
            else return 0;
        }
    }//判断一个点在不在三角形内,不检查三角形点重合情况
};


point dat[400010];
double res=0;
double AndrewHull(point* dat,int n){
    sort(dat+1,dat+1+n);
    double res=0;
    int stac[n+3]{},top=0;
    top=0;
    stac[++top]=1;
    for(int i=2;i<=n;++i){
        while(top>=2){
            double tmp=xmul(dat[stac[top-1]],dat[stac[top]],dat[stac[top]],dat[i]);
            if(tmp<0)top--;
            else break;
        }
        stac[++top]=i;
    }
    for(int i=1;i<top;++i){
        //在这里求出下凸包并且计算距离,do something
        res+=dat[stac[i]].dis(dat[stac[i+1]]);
    }
    top=0;
    stac[++top]=n;
    for(int i=n-1;i>=1;--i){
        while(top>=2){
            double tmp=xmul(dat[stac[top-1]],dat[stac[top]],dat[stac[top]],dat[i]);
            if(tmp<0)top--;
            else break;
        }
        stac[++top]=i;
    }
    for(int i=1;i<top;++i){
        //在这里求出上凸包并计算距离,do something
        res+=dat[stac[i]].dis(dat[stac[i+1]]);
    }
    return res;
}

扫描线

long long a[1000010];
#define mxxn 2000000
struct segtree{
    struct segtreenode{
        int l,r;
        int lazy;//区间被覆盖的厚度
        long long val,mxx;//当前和,最大和
    };
    segtreenode dat[mxxn];
    int top=0;
    void push_up(int mod){
        if(dat[mod].lazy>0){
            dat[mod].val=dat[mod].mxx;
        }else{
            dat[mod].val=dat[dat[mod].l].val+dat[dat[mod].r].val;
        }
    }
    void aadd(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr){
            dat[mod].lazy++;
            dat[mod].val=dat[mod].mxx;
            return;
        }
        int mid=(l+r)>>1;
        if(tl<=mid)aadd(dat[mod].l,l,mid,tl,tr);
        if(tr>mid)aadd(dat[mod].r,mid+1,r,tl,tr);
        push_up(mod);
    }
    void ddec(int mod,int l,int r,int tl,int tr){
        if(tl<=l&&r<=tr){
            if(dat[mod].lazy>0){
                dat[mod].lazy--;
                if(dat[mod].lazy==0){
                    push_up(mod);
                }else{
                    dat[mod].val=dat[mod].mxx;
                }
            }else{
                int mid=(l+r)>>1;
                ddec(dat[mod].l,l,mid,tl,tr);
                ddec(dat[mod].r,mid+1,r,tl,tr);
                push_up(mod);
            }
            return;
        }
        int mid=(l+r)>>1;
        if(tl<=mid)ddec(dat[mod].l,l,mid,tl,tr);
        if(tr>mid)ddec(dat[mod].r,mid+1,r,tl,tr);
        push_up(mod);
    }
    long long qquery(){
        return dat[1].val;
    }
    int bbuild(int l,int r){//建空树,返回根节点 
        if(l>=r){
            dat[++top].val=0;
            dat[top].mxx=a[l];
            return top;
        }
        int mid=(l+r)>>1,tmp=++top;
        dat[tmp].l=bbuild(l,mid);
        dat[tmp].r=bbuild(mid+1,r);
        dat[tmp].mxx=dat[dat[tmp].l].mxx+dat[dat[tmp].r].mxx;
        return tmp;
    }
};
segtree ko;
struct node{
    long long l,r,ver,val;
};
char cmp(const node& a,const node& b){
    if(a.ver==b.ver)return a.val>b.val;
    return a.ver<b.ver;
}
node ddat[1000010];
int dat[1000010],top=0,ttop=0;
long long n,m,res;
int main(){
    fin>>n;
    int l,r,u,d;
    for(int i=1;i<=n;++i){
        fin>>l>>u>>r>>d;
        if(r<l)swap(r,l);
        if(u<d)swap(u,d);
        ddat[++ttop]={l,r,d,1};
        ddat[++ttop]={l,r,u,-1};
        dat[++top]=l;
        dat[++top]=r;
    }
    sort(dat+1,dat+1+top);
    int ni=unique(dat+1,dat+1+top)-dat-1;
    for(int i=1;i<ni;++i){
        a[i]=dat[i+1]-dat[i];
    }
    ko.bbuild(1,ni);
    sort(ddat+1,ddat+1+ttop,cmp);
    res=0;
    long long pre=ddat[1].ver,li,ri;
    for(int i=1;i<=ttop;++i){
        res+=ko.qquery()*(ddat[i].ver-pre);
        li=upper_bound(dat+1,dat+1+ni,ddat[i].l)-dat-1;
        ri=upper_bound(dat+1,dat+1+ni,ddat[i].r)-dat-1;
        if(ddat[i].val==1){
            ko.aadd(1,1,ni,li,ri-1);
        }else{
            ko.ddec(1,1,ni,li,ri-1);
        }
        pre=ddat[i].ver;
    }
    fout<<res<<"\n";
    return 0;
}

动态线 下凸包

维护一个由线段构成的下凸包,重复的线只算做一条,每次查询从y轴上方可以看到多少条线段.

struct dLHull{
    #define inf 0x3f3f3f3f3f3f3f3f
    struct line{
        long long k,b;
        char operator<(line io){
            return (k==io.k)?(b<io.b):(k<io.k);
        }
    };
    struct zjj{
        mutable long double l,r;
        mutable long long k,b;
        zjj(long double _l=0,long double _r=0,long long _k=0,long long _b=0){
            l=_l,r=_r,k=_k,b=_b;
        }
        void add(long double l_,long double r_){
            if(l==inf){
                l=l_;r=r_;
                return;
            }
            if(l_>l)r=r_;
            else l=l_;
        }
        bool operator<(const zjj &tp)const{
            return k<tp.k;
        }
    };
    set<zjj>q;
    line *a;
    int *d;
    dLHull(int num=1000000){
        a=new line[num+5];
        d=new int[num+5];
    }
    int tail;
    int init(int n){
        for(int i=1;i<=n;++i){
            fin>>a[i].k>>a[i].b;
        }
        sort(a+1,a+n+1);
        int i;
        for (i=1;i<=n;i++){
            for(;i<n&&a[i+1].k==a[i].k;i++);
            for(;tail>1;tail--)
                if(check(i,d[tail])>check(d[tail],d[tail-1]))break;
            d[++tail]=i;
        }
        for(i=1;i<=tail;i++){
            long double l=-inf,r=inf;
            if (i!=1)
                l=check(d[i],d[i-1]);
            if (i!=tail)
                r=check(d[i], d[i+1]);
            q.insert(zjj(l,r,a[d[i]].k,a[d[i]].b));
        }
        return tail;
    }
    long double check(int x,int y){
        return (long double)(a[x].b-a[y].b)/(a[y].k-a[x].k);
    }
    double check_(const zjj& x,const zjj& y){
        return (long double)(x.b-y.b)/(y.k-x.k);
    }
    void insert(long long k,long long b){
        zjj now(inf,-inf,k,b);
        if(q.empty()){
            now.l = -inf;
            now.r = inf;
            q.insert(now);
            return;
        }
        set<zjj>::iterator i=q.lower_bound(now);
        if(i!=q.end()&&(i->k==k)){
            if(i->b>=b)return;
            now.l=i->l;now.r=i->r;
            q.erase(i);
            if (q.empty()){
                q.insert(now);
                return;
            }
            i=q.lower_bound(now);
        }
        if(i!=q.end()&&i!=q.begin()){
            long double mid=check_(now,(*i));
            if(mid<=i->l)return;
        }
        if(i!=q.end()){
            while(1){
                long double mid = check_(now, (*i));
                if (mid >= i->r){
                    now.add(i->l, i->r);
                    q.erase(i);
                    if (q.empty()) { q.insert(now);return; }
                    i = q.lower_bound(now);
                    if (i == q.end())break;
                }
                else { if (mid >= i->l) { now.add(i->l, mid);i->l = mid; }break; }
            }
        }
        if(q.empty()){
            now.l=-inf;
            if(now.r!=-inf)
                q.insert(now);
            return;
        }
        i=q.lower_bound(now);
        if(i==q.begin()){
            now.l=-inf;
            if(now.r!=-inf)
                q.insert(now);
            return;
        }
        i--;
        while(1){
            long double mid=check_(now,(*i));
            if(mid<=i->l){
                now.add(i->l,i->r);
                q.erase(i);
                if(q.empty())break;
                i=q.lower_bound(now);
                if(i==q.begin())break;
                i--;
            }else{
                if(mid<=i->r){
                    now.add(mid, i->r);
                    i->r=mid;
                }
                break;
            }
        }
        if(now.l<now.r)
            q.insert(now);
    }
    int qquery(){
        return q.size();
    }
};

镜面反射

镜子解析式:

$$y=k_1x+b_1$$

入射光线:

$$y=k_2x+b_2$$

交点:

$$x_0=\frac_{b_2-b_1}{k_1-k_2},y_0=k_1x_0+b_1$$

反射光线:

$$k_3=\frac_{(k_1^2-1)k_2+2k_1}{2k_1k_2-(k_1^2-1)},b_3=y_0-k_3x_0$$

随机点集最短距离

struct ppoint{
    long long x, y;
};
char cmpx(const ppoint& a,const ppoint& b){
    return (a.x!=b.x)?(a.x<b.x):(a.y<b.y);
}
char cmpy(const ppoint& a,const ppoint& b){
    return (a.y==b.y)?(a.x<b.x):(a.y<b.y);
}
double dist(const ppoint& p1,const ppoint& p2){
    return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double bruteForce(ppoint P[], int n){
    double min = FLT_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}
double stripClosest(ppoint strip[],int size,double d){
    double min=d;
    for(int i=0;i<size;++i)
        for(int j=i+1;j<size&&(strip[j].y-strip[i].y)<min;++j)
            if(dist(strip[i],strip[j])<min)
                min=dist(strip[i],strip[j]);
    return min;
}
double closestUtil(ppoint Px[],ppoint Py[],int n){
    if(n<=3)return bruteForce(Px,n);
    int mid=n/2;
    ppoint midppoint=Px[mid];
    ppoint Pyl[mid];
    ppoint Pyr[n-mid];
    int li=0,ri=0;
    for(int i=0;i<n;i++){
        if((Py[i].x<midppoint.x||(Py[i].x==midppoint.x&&Py[i].y<midppoint.y))&&li<mid)
            Pyl[li++]=Py[i];
        else
        Pyr[ri++]=Py[i];
    }
    double dl=closestUtil(Px,Pyl,mid);
    double dr=closestUtil(Px+mid,Pyr,n-mid);
    double d=min(dl,dr);
    ppoint strip[n];
    int j=0;
    for (int i=0;i<n;i++)
        if(abs(Py[i].x-midppoint.x)<d)
            strip[j]=Py[i],j++;
    return stripClosest(strip,j,d);
}
double closest(ppoint P[],int n){
    ppoint Px[n];
    ppoint Py[n];
    for(int i=0;i<n;i++){
        Px[i]=P[i];
        Py[i]=P[i];
    }
    sort(Px,Px+n,cmpx);
    sort(Py,Py+n,cmpy);
    return closestUtil(Px,Py,n);
}
ppoint dat[2000000];
int s[4000010];
int main(){
    s[0]=290797;
    for(int i=1;i<=4000000;++i){
        s[i]=1LL*s[i-1]*s[i-1]%50515093;
    }
    for(int i=0;i<2000000;++i){
        dat[i].x=s[2*i];
        dat[i].y=s[2*i+1];
    }
    double tmp=closest(dat,2000000);
    printf("%.9f",tmp);
    return 0;
}

神秘科技

生成一个防止被Hack的种子

• 随便取一个变量的地址
• 当前时间(可以和其他数字加起来增强安全性)

const ll INF = 4e18,Mod = 1e9+7;
mt19937_64 rnd((uintptr_t)(char*)(&INF)+time(0));

取模类

自己随便写的取模类,只能保证不WA,速度不能保证.
测了线段树板子,一发比一发慢.

谨慎使用.
因为取模问题导致WA很难纠错,所以归类神秘科技.

template<typename T1,typename T2,typename T3>
T1 qp(T1 b,T2 po,T3 p){
    T1 res(1);
    while(po>0){
        if(po&1)
            res=res*b%p;
        b=b*b%p;
        po>>=1;
    }
    return res;
}
int mod=1e9+7;
template<typename T>
struct Zmod{
    T x;
    Zmod(T io = 0){x = io % mod; if(x < 0) x += mod;}
    Zmod operator +(const Zmod& io)const{return Zmod(x + io.x);}
    Zmod operator -(const Zmod& io)const{return Zmod(x - io.x);}
    Zmod operator *(const Zmod& io)const{return Zmod(x * io.x);}
    Zmod operator /(const Zmod& io)const{return Zmod(x * qp((__int128)io.x, mod - 2, mod));}
    Zmod& operator +=(const Zmod& io){x = (x + io.x) % mod; return *this;}
    Zmod& operator -=(const Zmod& io){x = (x - io.x + mod) % mod; return *this;}
    Zmod& operator *=(const Zmod& io){x = x * io.x % mod; return *this;}
    Zmod& operator /=(const Zmod& io){x = x * qp((__int128)io.x, mod - 2, mod) % mod; return *this;}
    bool operator ==(const Zmod& io)const{return x == io.x;}
    bool operator !=(const Zmod& io)const{return x != io.x;}
    bool operator <(const Zmod& io)const{return x < io.x;}
    bool operator >(const Zmod& io)const{return x > io.x;}
    bool operator <=(const Zmod& io)const{return x <= io.x;}
    bool operator >=(const Zmod& io)const{return x >= io.x;}
    bool operator ==(const T& io)const{return x == Zmod(io).x;}
    bool operator !=(const T& io)const{return x != Zmod(io).x;}
    bool operator <(const T& io)const{return x < Zmod(io).x;}
    bool operator >(const T& io)const{return x > Zmod(io).x;}
    bool operator <=(const T& io)const{return x <= Zmod(io).x;}
    bool operator >=(const T& io)const{return x >= Zmod(io).x;}
    Zmod pow(T po)const{return Zmod(qp((__int128)x, po, mod));}
    T val()const{return x;}
    friend fastio::IN& operator >>(fastio::IN &in, Zmod &z){T tmp; in >> tmp; z = Zmod(tmp); return in;}
    friend fastio::OUT& operator <<(fastio::OUT &out, const Zmod &z){out << z.x; return out;}
    friend std::istream& operator >>(std::istream &is, Zmod &z){T tmp; is >> tmp; z = Zmod(tmp); return is;}
    friend std::ostream& operator <<(std::ostream &os, const Zmod &z){os << z.x; return os;}
};

编译期指定随机质数

借用skip2004佬的一篇博客,在编译期指定了质数,防止被hack.

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll=long long;
using u64=unsigned long long;
using u128=__uint128_t;

constexpr ll pow(ll a,ll x,ll p,ll res=1){
    for(;x;x>>=1,a=(u128)a*a%p)
        if(x&1)res=(u128)res*a%p;
    return res;
}
constexpr bool checkprime(ll p){
    if(p==1)return 0;
    ll d=__builtin_ctzll(p-1),s=(p-1)>>d;
    for(ll a:{2,3,5,7,11,13,82,373}){
        if(a%p==0)
            continue;
        ll x=pow(a,s,p),y=0;
        for(int i=0;i<d;++i,x=y){
            y=(u128)x*x%p;
            if(y==1&&x!=1&&x!=p-1)return 0;
        }
        if(x!=1)return 0;
    }
    return 1;
}
constexpr ll gen_prime(ll L,ll R){
    // gen prime in [L, R)
    u64 x=1128471;
    for(char c:__TIME__  __TIMESTAMP__){
        x+=c,x^=x<<13,x^=x>>7,x^=x<<17;
    }
    for(;;) {
        x^=x<<13,x^=x>>7,x^=x<<17;
        ll y=L+x%(R-L);
        if(checkprime(y))
            return y;
    }
    return 0;
}
constexpr ll mod=gen_prime(1e17,1e18);
int main(){
    cout<<mod<<'\n';
}

高精度

早就放弃维护的版本,慎用,Flu自己都不知道哪里错了.

#define MXX 1300      //最大数组
#define MXF 1298      //pos to end calculation, some 
#define MXE 9         //最大数字位数
#define MXN 1000000000//最大数字
using namespace std;
struct bint{
    char flag=0;
    long long dat[MXX];
    char operator <(bint io){
        if(flag==io.flag){
            if(flag==0){
                for(int fg=MXF;fg>=0;--fg){
                    if(dat[fg]>io.dat[fg])return 0;
                    if(dat[fg]<io.dat[fg])return 1;
                }
                return 0;
            }else{
                for(int fg=MXF;fg>=0;--fg){
                    if(dat[fg]>io.dat[fg])return 1;
                    if(dat[fg]<io.dat[fg])return 0;
                }
                return 1;
            }
        }
        else{
            return flag==1?1:0;
        }
    }
    char operator >(const bint io)const{
        if(flag==io.flag){
            if(flag==0){
                for(int fg=MXF;fg>=0;--fg){
                    if(dat[fg]>io.dat[fg])return 1;
                    if(dat[fg]<io.dat[fg])return 0;
                }
                return 1;
            }
            else{
                for(int fg=MXF;fg>=0;--fg){
                    if(dat[fg]>io.dat[fg])return 0;
                    if(dat[fg]<io.dat[fg])return 1;
                }
                return 0;
            }
        }
        else{
            return flag==1?0:1;
        }
    }
    char operator <=(const bint io)const{
        for(int fg=MXF;fg>=0;--fg){
            if(dat[fg]<io.dat[fg])return 1;
            if(dat[fg]>io.dat[fg])return 0;
        }
        return 1;
    }
    bint operator +(const bint io)const{
        bint ress;
        memset(ress.dat,0,sizeof(dat));
        for(int ii=0;ii<=MXF;++ii){
            ress.dat[ii]+=dat[ii]+io.dat[ii];
            ress.dat[ii+1]=ress.dat[ii]/MXN;
            ress.dat[ii]%=MXN;
        }
        return ress;
    }
    void operator +=(bint io){
        for(int ii=0;ii<=MXF;++ii){
            dat[ii]+=io.dat[ii];
            dat[ii+1]+=dat[ii]/MXN;
            dat[ii]%=MXN;
        }
    }
    void operator -=(bint io){//ensure this>=io
        for(int gh=0;gh<=MXF;++gh){
            dat[gh]-=io.dat[gh];
            if(dat[gh]<0){
                dat[gh+1]--;
                dat[gh]+=MXN;
            }
        }
    }
    bint operator *(const bint io)const{
        bint ress;
        ress.flag=flag^io.flag;
        memset(ress.dat,0,sizeof(dat));
        for(int i=0;i<=MXF;++i){
            for(int j=0;j+i<=MXF;++j){
                ress.dat[i+j]+=dat[i]*io.dat[j];
                ress.dat[i+j+1]+=ress.dat[i+j]/MXN;
                ress.dat[i+j]%=MXN;
            }
        }
        return ress;
    }
    bint operator *(long long io){
        bint ress;
        flag^=(io>0)?0:1;
        memset(ress.dat,0,sizeof(dat));
        for(int i=0;i<=MXF;++i){
            ress.dat[i]+=dat[i]*io;
            ress.dat[i+1]+=ress.dat[i]/MXN;
            ress.dat[i]%=MXN;
        }
        return ress;
    }
    bint operator -(bint io){
        io.flag^=1;
        bint ress,*ppp,*qqq;
        int tmp;
        memset(ress.dat,0,sizeof(dat));
        if((*this)<=io)ppp=&io,qqq=this,ress.flag=io.flag ;
        else ppp=this,qqq=&io,ress.flag=this->flag;
        for(int gh=0;gh<=MXF;++gh){
            tmp=ppp->dat[gh]-qqq->dat[gh];
            if(tmp>=0){
                ress.dat[gh]+=tmp;
            }
            else{
                ress.dat[gh]+=MXN+tmp;
                ress.dat[gh+1]--;
            }
        }
        for(int gh=0;gh<=MXF;++gh){
            if(ress.dat[gh]<0){
                for(;ress.dat[gh]<0;){
                    for(int hj=gh+1;hj<=MXF;++hj){
                        if(ress.dat[hj]>0){
                            ress.dat[hj]--;
                            ress.dat[hj-1]+=MXN;
                            break;
                        }
                    }
                }
            }
        }
        return ress;
    }
    bint operator <<(const int x)const{
        bint ress;
        memset(ress.dat,0,sizeof(dat));
        for(int bh=MXF;bh>=x;--bh){
            ress.dat[bh]=dat[bh-x];
        }
    return ress;
    }
    void operator <<=(const int x){
        for(int bh=MXF;bh>=x;--bh){
            dat[bh]=dat[bh-x];
        }
        for(int bh=x-1;bh>=0;--bh){
            dat[bh]=0;
        }
    }
    bint operator >>(const int x)const{
        bint ress;
        memset(ress.dat,0,sizeof(dat));
        for(int bh=x;bh<=MXF;++bh){
            ress.dat[bh-x]=dat[bh];
        }
        return ress;
    }
    void operator >>=(const int x){
        for(int bh=x;bh<=MXF;++bh){
            dat[bh-x]=dat[bh];
        }
    }
//    bint operator /(bint io){
//        bint ress;
//        memset(ress.dat,0,sizeof(dat));
//        io<<=op;
//        for(;op>=0;--op,io>>=1){
//            for(unsigned long long mid=1<<30;mid;mid>>=1){
//                bint tmp=(io*mid);
//                if(!((*this)<tmp)){
//                    (*this)=(*this)-tmp;
//                    ress.dat[op]+=mid;
//                }
//            }
//        }
//        return ress;
//    }
    bint operator /(long long io){
        bint ress;
        memset(ress.dat,0,sizeof(dat));
        for(int hj=MXF;hj>=0;--hj){
            dat[hj]+=dat[hj+1]*MXN;
            ress.dat[hj]=dat[hj]/io;
            dat[hj]%=io;
        }
        return ress;
    }
//    bint operator %(bint io){
//        bint ress;
//        memset(ress.dat,0,sizeof(dat));
//        ress=(*this)-(*this)/io*io;
//        return ress;
//    }
    bint operator %(long long io){
        bint ress;
        flag=0;
        memset(ress.dat,0,sizeof(dat));
        ress=(*this)-((*this)/io)*io;
        ress.flag=0;
        return ress;
    }
    void prr(){
        bool fff=0;
        if(flag==1)printf("-");
        for(int h=MXF;h>=0;--h){
            if(fff==1){
                printf("%09llu",dat[h]);
                continue;
            }
            if(dat[h]!=0){
                printf("%llu",dat[h]);
                fff=1;
            }
        }
        if(fff==0)printf("0");
    }
    void read(){
        string abcg;
        unsigned long long topp=0,folk=1;
        cin>>abcg;
        if(abcg[0]=='-')flag=1,abcg.erase(0,1);
        for(int kk=abcg.size()-1,len=kk;kk>=0;kk--){
            if(folk==MXN){folk=1;topp++;}
            dat[topp]+=(abcg[kk]-'0')*folk;
            folk*=10;
        }
    }
};

bint a,res,b;
int main(){
    a.read();
    b.read();
    res=a*b;
    res.prr();
    return 0;
}

莫队

精髓在于排序.

char cmp(node a,node b){
    return block[a.l]^block[b.l]?(block[a.l]<block[b.l]):((block[a.l]&1)?(a.r<b.r):(a.r>b.r));
}

三维莫队

将修改看成一个维度,跑莫队即可.

int block=pow(n,0.667);//这里的块长比较特殊,不是sqrt(n)
sort(ddat+1,ddat+1+qtop,[&](node& a,node& b){
    if(a.l/block!=b.l/block)return a.l/block<b.l/block;
    if(a.r/block!=b.r/block)return a.r/block<b.r/block;
    return a.t>b.t;//排序可以在r/block这里使用奇偶优化
});
l=1,r=0,t=0,pt=0;
for(int i=1;i<=qtop;++i){
    while(r<ddat[i].r){add(dat[++r]);}
    while(r>ddat[i].r){del(dat[r--]);}
    while(l<ddat[i].l){del(dat[l++]);}
    while(l>ddat[i].l){add(dat[--l]);}
    while(pt<ddat[i].t){
        pt++;
        if(l<=ppos[pt]&&ppos[pt]<=r){
            del(dat[ppos[pt]]);
            add(ppto[pt]);
        }
        swap(dat[ppos[pt]],ppto[pt]);
    }
    while(pt>ddat[i].t){
        if(l<=ppos[pt]&&ppos[pt]<=r){
            del(dat[ppos[pt]]);
            add(ppto[pt]);
        }
        swap(dat[ppos[pt]],ppto[pt]);
        pt--;
    }
    rres[ddat[i].ref]=res;
}