线段树求最值(最大值和最小值)

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int last[N];
struct node{
    int l;
    int r;
    int mx;
}tr[N*4];
void pushup(int u){
    tr[u].mx=max(tr[u*2].mx,tr[u*2+1].mx);
}
void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        tr[u].mx=last[l];
        return ;
    }
    int mid=l+r>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].mx;
    }
    int mid=tr[u].l+tr[u].r>>1;
    int ans=0;
    if(l<=mid){
        ans=max(ans,query(u*2,l,r));
    }
    if(r>mid){
        ans=max(ans,query(u*2+1,l,r));
    }
    return ans;
}
void solved(){

}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __;
    __=1;
    while(__--){
        solved();
    }

    return 0;
}

字符串哈希

#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define ull unsigned long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=2e5+10,a=131;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}

int n;
ull h[N],q[N];
string p;
ull get(int l,int r)
{
    return h[r]-h[l-1]*q[r-l+1];
}
void solved(){
    cin>>n;
    cin>>p;
    p=" "+p;
    q[0]=1;
    for(int i=1;i<=n;i++)
    {
        q[i]=q[i-1]*a;
        h[i]=h[i-1]*a+p[i];
    }
}
int  main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __;
    cin>>__;
    while(__--){
        solved();
    }

    return 0;
}

读入个数不确定

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
string s;
void solved(){
  getline(cin,s);
    stringstream ssin(s);
    string str="";
    while(ssin>>str){
        if(str[0]>='a'&&str[0]<='z'){
            cout<<(char)(str[0]-32);
        }else{
            cout<<str[0];
        }
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __;
    __=1;
    while(__--){
        solved();
    }

    return 0;
}

stol函数将字符串转化为数字

矩阵快速幂求斐波拉契数列

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f,mod=10000;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int mul(int a[][2],int b[][2]){
    int c[2][2]={0};
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    memcpy(a,c,sizeof c);
}
int fib(int x){
    int f[2][2]={
        {0,1},
        {0,0}

    };
    int a[2][2]={
        {0,1},
        {1,1}
    };
    while(x){
        if(x&1){
           mul(f,a);
        }
           mul(a,a);
        x>>=1;
    }
    cout<<f[0][0]<<"\n";
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n,n!=-1){
        fib(n);
    }
    return 0;
}

set处理及时性区间删除、添加

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int n,m,q;
int a[N];
vector<pii1> vtadd[N],vtdel[N];
void solved(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(q--){
        int x,y,l,r;
        cin>>x>>y>>l>>r;
        if(y<10)
            y*=10;
        vtadd[l].push_back({a[x]*y/100,x});
        vtdel[r+1].push_back({a[x]*y/100,x});
    }
    set<pii1> se;
    for(int i=1;i<=n;i++){
        se.insert({a[i],i});
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<vtadd[i].size();j++){
            se.insert(vtadd[i][j]);
        }
        for(int j=0;j<vtdel[i].size();j++){
            se.erase(vtdel[i][j]);
        }
        cout<<(*se.begin()).second<<" ";
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __;
    __=1;
    while(__--){
        solved();
    }

    return 0;
}

__int128_t 板子

#include<bits/stdc++.h>
#define int __int128_t
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int read()
{
    char ch;
    ch = getchar();
    int x = 0;
    while(ch >= '0' and ch <= '9')
    {
      x = x * 10 + ch - '0';
      ch = getchar();
    }
    return x; 
}
void Print(int x)
{
    string s;
    while(x)
    {
        s += x % 10 + '0';
        x /= 10;
    }
    reverse(s.begin() , s.end());
    cout <<s << '\n';
}
int x,y,z,k,d;
void solved(){
int x, y, z, k, d;
    x = read();
    y = read();
    z = read();
    k = read();
    d = read();
    Print(ans);
}
signed main(){
    int __;
    __=1;
    while(__--){
        solved();
    }
    return 0;
}

知道三点求三角形面积

s=1/2*(x1*(y2-y3)+x2*(y3-y2)+x3*(y1-y2)));

三分整数求解板子

实数三分

const double EPS = 1e-7;
double check(double mid){
    double mx=fabs(x[1]-mid)+t[1];
    for(int i=1;i<=n;i++){
        mx=max(mx,fabs(x[i]-mid)+t[i]);
    }
    return mx;
}
double tri_search(double l,double r){
    while(r - l > EPS) {
    double lmid = l + (r - l) / 3.0;
    double rmid = r - (r - l) / 3.0;
    double f1 = check(lmid),f2 = check(rmid);
    // 求凹函数的极小值
    if(f1 <= f2) r = rmid;
    else l = lmid;
    // 求凸函数的极大值
//    if(f1 >= f2) l = lmid;
//    else r = rmid;
    }
    //输出极小值
//    return min(f1,f2);
    //输出极大值
//    return max(f1,f2);
    // 输出 l 或 r 都可
   return l;
}

xy整除ab可以化为y整除ab/gcd(ab,x)

拓扑排序判环(可以直接找环),双向边已行

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int n,a,b;
int in[N];
vector<int> vt[N];
int dist1[N],dist2[N];
bool st1[N],st2[N];
void dij1(int x){
    for(int i=1;i<=n;i++){
        dist1[i]=INF;
        st1[i]=0;
    }
    dist1[x]=0;
    priority_queue<pii1,vector<pii1>,greater<pii1>> q;
    q.push({0,x});
    while(q.size()){
        auto t=q.top();
        q.pop();
        if(st1[t.second])
        continue;
        st1[t.second]=true;
        for(int i=0;i<vt[t.second].size();i++){
            auto v=vt[t.second][i];
            if(v==t.second)
            continue;
            if(dist1[v]>dist1[t.second]+1){
                dist1[v]=dist1[t.second]+1;
                q.push({dist1[v],v});
            }
        }
    }
}
void dij2(int x){
    for(int i=1;i<=n;i++){
        dist2[i]=INF;
        st2[i]=0;
    }
    dist2[x]=0;
    priority_queue<pii1,vector<pii1>,greater<pii1>> q;
    q.push({0,x});
    while(q.size()){
        auto t=q.top();
        q.pop();
        if(st2[t.second])
        continue;
        st2[t.second]=true;
        for(int i=0;i<vt[t.second].size();i++){
            auto v=vt[t.second][i];
            if(v==t.second)
            continue;
            if(dist2[v]>dist2[t.second]+1){
                dist2[v]=dist2[t.second]+1;
                q.push({dist2[v],v});
            }
        }
    }
}
void solved(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        in[i]=0;
        vt[i].clear();
    }
    for(int i=1;i<=n;i++){
        int aa,bb;
        cin>>aa>>bb;
        vt[aa].push_back(bb);
        vt[bb].push_back(aa);
        in[aa]++;
        in[bb]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==1){
            q.push(i);
        }
    }
    while(q.size()){
        auto t=q.front();
        q.pop();
        //cout<<t<<"-----\n";
        for(int i=0;i<vt[t].size();i++){
            auto v=vt[t][i];
            if(v==t)
            continue;
            --in[v];
            if(in[v]==1){
                q.push(v);
            }
        }
    }
    map<int,int> mp;//存环

    for(int i=1;i<=n;i++){
        if(in[i]>=2){
            mp[i]++;
        }
    }
    if(a==b){
        cout<<"NO\n";
        return ;
    }
    if(mp.count(b)){
        cout<<"YES\n";
        return ;
    }
    dij1(a);
    dij2(b);
    for(auto it=mp.begin();it!=mp.end();it++){
        if(dist2[it->first]<dist1[it->first]){
            cout<<"YES\n";
            return ;
        }
    }
    cout<<"NO\n";
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __=1;
    cin>>__;
    while(__--){
        solved();
    }

    return 0;
}

vector自定义排序

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f3f3f3f3f;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int n;
int a[N];
struct node{
    int w;
    int id;
}aa[N];
bool cmp(node a1,node a2){
    return a1.w<a2.w;
}
void solved(){
  cin>>n;
  map<int,vector<int>> mp;

  for(int i=1;i<=n;i++){
    cin>>a[i];
    mp[a[i]/4].push_back(i);
  }
  vector<int> ans(n+5,0);
  for(auto it=mp.begin();it!=mp.end();it++){
    auto temp=it->first;
    vector<int> aa=mp[temp];
    sort(aa.begin(),aa.end(),[&](int i,int j){
        return a[i]<a[j];
    });
    for(int i=0;i<mp[temp].size();i++){
        ans[mp[temp][i]]=a[aa[i]];
    }
  }
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
  }
  cout<<"\n";

}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __=1;
    cin>>__;
    while(__--){
        solved();
    }

    return 0;
}

字典树求所有的最长公共前缀

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=3e5+10,INF=0x3f3f3f3f3f3f3f3f,mod=1e8;
//前四个是上右下左，后四个是右上右下左下左上.
int dx[9]={-1,0,1,0,-1,1,1,-1};
int dy[9]={0,1,0,-1,1,1,-1,-1};
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}
int quick(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=res*a;
        }
        a=a*a;
        b>>=1;
    }
    return res;
}
int a[N];
int sum[N];
int n;
map<string,int> mp;
int son[N][26],cnt[N*26],idx=0;
void insert(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int c=s[i]-'a';
        if(!son[p][c])
        son[p][c]=++idx;
        p=son[p][c];
        cnt[p]++;
    }
}
int query(string s){
    int p=0,res=0;
    for(int i=0;i<s.size();i++){
        int u=s[i]-'a';
        if(!son[p][u])
        return res;
        p=son[p][u];
        res+=cnt[p];
    }
    return res;
}
void solved(){
   cin>>n;
   vector<string> vt(n+1);
   for(int i=0;i<n;i++){
    cin>>vt[i];
    mp[vt[i]]++;
   }
   int res=0;
   for(int i=0;i<n;i++){
    res+=query(vt[i]);
    insert(vt[i]);
   }
   cout<<res<<"\n";
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int __=1;
    //cin>>__;
    while(__--){
        solved();
    }

    return 0;
}

lca板子

#include<bits/stdc++.h>
#define int long long
#define pii1 pair<int,int>
#define pii2 pair<int,pair<int,int>>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
struct node{
    int v,w;
};
vector<int> vt[N];
int d[N],dist[N],w[N];
int f[N][25];
int a[N];
int n,m;
void bfs(){
    memset(d,INF,sizeof d);
    d[1]=1,d[0]=0;
    queue<int> q;
    q.push(1);
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<vt[t].size();i++){
            auto v=vt[t][i];
            if(d[v]>d[t]+1){
                d[v]=d[t]+1;
                q.push(v);
                f[v][0]=t;
                for(int i=1;i<=20;i++){
                    f[v][i]=f[f[v][i-1]][i-1];
                }
                dist[v]=dist[t]+1;
            }
        }
    }
}
int lca(int a,int b){
    if(d[a]<d[b])
    swap(a,b);
    for(int i=20;i>=0;i--){
        if(d[f[a][i]]>=d[b]){
            a=f[a][i];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=20;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
void dfs(int x,int fa,int sum)
{
    sum^=a[x];
    w[x]=sum;
    for(auto y:vt[x])
    {
        if(y==fa)continue;
        dfs(y,x,sum);
    }
}
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<n;i++){
       int x,y;
       cin>>x>>y;
       vt[x].push_back(y);
       vt[y].push_back(x);
    }
    dfs(1,0,0);
    bfs();
    while(m--){
        int x,y;
        cin>>x>>y;
        int p=lca(x,y);
        cout<<(w[x]^w[y]^a[p])<<'\n';
    }
    return 0;
}