【板子】

skyx · 2025-07-22 16:03:03 · 个人记录

DATA STRUCTURE

单调队列

有些 dp 题要算 dp[i]，注意单调性维护位置

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int a[5000100],ans[5000010];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    deque<int> q;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && i-q.front()>=k) q.pop_front();
        while(!q.empty() && a[i]<=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k)
        {
            ans[i]=a[q.front()];
        }
    }
    for(int i=k;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
  cout<<endl;
  q.clear();
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && i-q.front()>=k) q.pop_front();
        while(!q.empty() && a[i]>=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k)
        {
            ans[i]=a[q.front()];
        }
    }
    for(int i=k;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
    return 0;
}

单调栈

#include<bits/stdc++.h>
using namespace std;
int n,a[3000005],f[3000005];
stack<int>s;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=n;i>=1;i--)
    {
        while(!s.empty()&& a[s.top()]<=a[i]) s.pop();
        if(s.empty()) f[i]=0;
        else f[i]=s.top();
        s.push(i);
    }
    for(int i=1;i<=n;i++) cout<<f[i]<<" ";
    return 0;
}

    for(int i=1;i<=n;i++)
    {
        while(top && a[sta[top]]<=a[i]) --top;
        lmx[i]=sta[top];
        sta[++top]=i;
    }

并查集

#include<bits/stdc++.h>
using namespace std;
int fa[200006];
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    fa[find(x)]=find(y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
     cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1) merge(x,y);
        else {
            if(find(x)==find(y)) cout<<"Y"<<endl;

            else cout<<"N"<<endl;
        }
    }
    return 0;
}

ST表

#include<bits/stdc++.h>
using namespace std;
int a[100006];
int f[100006][20];
int lg[100006];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main()
{
    int n=read();
    int m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        f[i][0]=a[i];
    }
//  cout<<log2(100000);
    for(int i=2;i<=100000;i++)
    {
        lg[i]=lg[i>>1]+1;
    }
    for(int j=1;j<=lg[n];j++)
    {
        for(int i=1;i<=n-(1<<(j))+1;i++)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int l=read();
        int r=read();
        int ler=lg[r-l+1];
        cout<<max(f[l][ler],f[r-(1<<(ler))+1][ler])<<"\n";//forger
    }
    return 0;
}

树状数组

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N=5e5+6;
ll c[N],a[N];
ll pre[N];
int n,m;
ll ask(int x)
{
    ll y=0;
    for(;x;x-=x&-x) y+=c[x];
    return y;
}//ask(r)-ask(l-1)
void add(int x,int y)
{
    for(;x<=n;x+=x&-x) c[x]+=y;
}
void init()
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1]+a[i];
        c[i]=pre[i]-pre[i-(i&-i)];
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    init();
    for(int i=1;i<=m;i++)
    {
        int op,b,d;
        cin>>op>>b>>d;
        if(op==1) add(b,d);
        else cout<<ask(d)-ask(b-1)<<endl;
    }
    return 0;
}

线段树

微缩版（带 mod）

/*
1   区间每个元素加上 k
2   区间每个元素乘上 k
3   区间每个元素变为 k
4   输出区间和
MADE BY SKYx
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// int->ll may useful
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

const int N=1e5+5;
int n, q, x, y, k;
int mod=998244353;
struct node
{
    int l,r;
    int s,add,mul;
    int set;

} tr[N<<2];

void build(int c,int l,int r)
{
    auto &t=tr[c];
    t.l=l;
    t.r=r;
    t.add=t.s=0;
    t.mul=1;
    t.set=INT_MIN;
    if(l==r)
    {
        cin>>t.s;
        t.s=t.s%mod;
        return;
    }
    int mid=(l+r)/2;
    build(c*2,l,mid);
    build(c*2+1,mid+1,r);
    t.s=(tr[c*2].s+tr[c*2+1].s)%mod;

}

void pushdown(int c)
{
    auto &t=tr[c];
    if(t.set!=INT_MIN)
    {
        int v=t.set;
        for(int i=0; i<2; i++)
        {
            auto &u=tr[c*2+i];
            u.set=v%mod;
            u.s=v*(u.r-u.l+1)%mod;
            u.add=0;
            u.mul=1;
        }
        t.set=INT_MIN;
    }
    if(t.mul!=1 || t.add!=0)
    {
        for(int i=0; i<2; i++)
        {
            auto &u=tr[c*2+i];
            u.s=(u.s*t.mul%mod+t.add*(u.r-u.l+1)%mod)%mod;
            u.mul=u.mul*t.mul%mod;
            u.add=(u.add*t.mul+t.add)%mod;
        }
        t.mul=1;
        t.add=0;
    }
}
void update(int c, int L, int R, int type, int v)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return;
    if(L<=t.l && t.r<=R)
    {
        if (type==1)
        {
            t.s=(t.s+v*(t.r-t.l+1))%mod;
            t.add=(t.add+v)%mod;
        }
        if (type==2)
        {
            t.s=t.s*v%mod;
            t.mul=t.mul*v%mod;
            t.add=t.add*v%mod;
        }

        if (type==3)
        {
            t.s=v*(t.r-t.l+1)%mod;
            t.set=v%mod;
            t.add=0;
            t.mul=1;
        }
        return;
    }
    pushdown(c);
    update(c*2,L,R,type,v);
    update(c*2+1,L,R,type,v);
    tr[c].s=(tr[c*2].s+tr[c*2+1].s)%mod;
}

int query(int c, int L, int R)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return 0;
    if(L<=t.l && t.r<=R) return t.s%mod;
    pushdown(c);
    return (query(c*2,L,R)+query(c*2+1,L,R))%mod;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    build(1,1,n);

    while (q--)
    {
        int op; 
        cin>>op;
        if (op == 1)
        {
            cin>>x>>y>>k;
            update(1,x,y,1,k);
        }
        if (op == 2)
        {
            cin>>x>>y>>k;
            update(1,x,y,2,k);
        }
        if (op == 3)
        {
            cin>>x>>y>>k;
            update(1,x,y,3,k);
        }
        if (op == 4)
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<'\n';
        }
    }
    return 0;
}
/*

*/

全功能

/*
1   区间每个元素加上 k
2   区间每个元素乘上 k
3   区间每个元素变为 k
4   输出区间和
5   输出区间最大值
6   输出区间最小值
MADE BY SKYx
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, q, m, x, y, k;

struct node
{
    int l,r;
    int s,add,mul;
    int set;
    int mx,mn;
} tr[N<<2];

void build(int c,int l,int r)
{
    auto &t=tr[c];
    t.l=l;
    t.r=r;
    t.add=t.s=t.mx=t.mn=0;
    t.mul=1;
    t.set=INT_MIN;
    if(l==r)
    {
        cin>>t.s;
        t.mx=t.mn=t.s;
        return;
    }
    int mid=(l+r)/2;
    build(c*2,l,mid);
    build(c*2+1,mid+1,r);
    t.s=(tr[c*2].s+tr[c*2+1].s);
    t.mx=max(tr[c*2].mx,tr[c*2+1].mx);
    t.mn=min(tr[c*2].mn,tr[c*2+1].mn);
}

void pushdown(int c)
{
    auto &t=tr[c];
    if(t.set!=INT_MIN)
    {
        int v=t.set;
        for(int i=0; i<2; i++)
        {
            int U=c*2+i;
            auto &u=tr[U];
            u.set=v;
            u.s=v*(u.r-u.l+1);
            u.mx=u.mn=v;
            u.add=0;
            u.mul=1;
        }
        t.set=INT_MIN;
    }
    if(t.mul!=1 || t.add!=0)
    {
        for(int i=0; i<2; i++)
        {
            int U=c*2+i;
            auto &u=tr[U];
            u.s=u.s*t.mul+t.add*(u.r-u.l+1);
            u.mx=u.mx*t.mul+t.add;
            u.mn=u.mn*t.mul+t.add;
            u.mul=u.mul*t.mul;
            u.add=(u.add*t.mul+t.add);
        }
        t.mul=1;
        t.add=0;
    }
}
void update(int c, int L, int R, int type, int v)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return;
    if (L<=t.l && t.r<=R)
    {
        if (type==1)
        {
            t.s=(t.s+v*(t.r-t.l+1));
            t.mx=(t.mx+v);
            t.mn=(t.mn+v);
            t.add=(t.add+v);
        }
        if (type==2)
        {
            t.s=t.s*v;
            int mx1=t.mx*v;
            int mn1=t.mn*v;
            t.mx=max(mx1,mn1);
            t.mn=min(mx1,mn1);
            t.mul=t.mul*v;
            t.add=t.add*v;
        }

        if (type==3)
        {
            t.s=v*(t.r-t.l+1);
            t.mx=t.mn=v;
            t.set=v;
            t.add=0;
            t.mul=1;
        }
        return;
    }
    pushdown(c);
    update(c*2,L,R,type,v);
    update(c*2+1,L,R,type,v);
    t.s=(tr[c*2].s+tr[c*2+1].s);
    t.mx=max(tr[c*2].mx,tr[c*2+1].mx);
    t.mn=min(tr[c*2].mn,tr[c*2+1].mn);
}

int query(int c, int L, int R)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return 0;
    if(L<=t.l && t.r<=R) return t.s;
    pushdown(c);
    return (query(c*2,L,R)+query(c*2+1,L,R));

}

int qmax(int c, int L, int R)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return INT_MIN;
    if(L<=t.l && t.r<=R) return t.mx;
    pushdown(c);
    return max(qmax(c*2,L,R),qmax(c*2+1,L,R));

}

int qmin(int c, int L, int R)
{
    auto &t=tr[c];
    if(R<t.l || t.r<L) return INT_MAX;
    if(L<=t.l && t.r<=R) return t.mn;
    pushdown(c);
    return min(qmin(c*2,L,R),qmin(c*2+1,L,R));
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    build(1,1,n);

    while (q--)
    {
        int op; 
        cin>>op;
        if (op == 1)
        {
            cin>>x>>y>>k;
            update(1,x,y,1,k);
        }
        if (op == 2)
        {
            cin>>x>>y>>k;
            update(1,x,y,2,k);
        }
        if (op == 3)
        {
            cin>>x>>y>>k;
            update(1,x,y,3,k);
        }
        if (op == 4)
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<'\n';
        }
        if (op == 5)
        {
            cin>>x>>y;
            cout<<qmax(1,x,y)<<'\n';
        }
        if (op == 6)
        {
            cin>>x>>y;
            cout<<qmin(1,x,y)<<'\n';
        }
    }
    return 0;
}
/*

*/

异或版

/*
1   输出区间和
2   区间每个元素异或上 k
把每个整数看成 $B$ 位二进制 ，对第 $b$ 位分别构建一棵线段树，
维护这棵树节点上该区间内“1 的个数”以及一个翻转懒标记，
当要对区间异或上 $k$ 时，只需对 $k$ 的二进制表示中为 1 的那些位的线段树，执行一次“翻转区间”操作
当要查询区间和时，对于每一位 $b$，查询该位线段树上 [l,r] 内 1 的个数，然后累加贡献
query(b, 1, l, r) 查询的是第 b 位在区间 [l, r] 内 1 的数量。
最终的答案是这些 1 的数量按其二进制位加权求和。通过 1LL * cnt1 * (1LL << b) 计算对应的贡献值并加到答案上。
MADE BY SKYx
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int B = 20;

int n, m;

struct node
{
    int l, r;
    int s;
    bool rev;
} tr[B][N<<2];

int a[N];

void build(int b, int c, int l, int r)
{
    auto &t = tr[b][c];
    t.l=l;
    t.r=r;
    t.rev=0;

    if(l==r)
    {
        t.s=((a[l]>>b)&1);
        return;
    }
    int mid = (l+r)/2;
    build(b,c*2,l,mid);
    build(b,c*2+1,mid+1,r);
    t.s=tr[b][c*2].s+tr[b][c*2+1].s;
}

void pushdown(int b, int c)
{
    auto &t = tr[b][c];
    if(!t.rev) return;
    for(int i=0; i<2; i++)
    {
        int U = c*2+i;
        auto &u=tr[b][U];
        u.rev^=1;
        int len=u.r-u.l+1;
        u.s=len-u.s;
    }
    t.rev = 0;
}

void update(int b,int c,int L,int R)
{
    auto &t = tr[b][c];
    if(R<t.l || t.r<L) return;
    if(L<=t.l && t.r<=R)
    {

        int len=t.r-t.l+1;
        t.s = len - t.s;
        t.rev ^= 1;
        return;
    }
    pushdown(b,c);
    update(b,c*2,L,R);
    update(b,c*2+1,L,R);
    t.s = tr[b][c*2].s + tr[b][c*2+1].s;
}

int query(int b,int c,int L,int R)
{
    auto &t = tr[b][c];
    if(R<t.l || t.r<L) return 0;
    if(L<=t.l && t.r<=R) return t.s;
    pushdown(b,c);
    return query(b,c*2,L,R)+query(b,c*2+1,L,R);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    for(int b=0; b<B; b++) build(b,1,1,n);

    cin >> m;
    while(m--)
    {
        int op;
        cin >> op;
        if(op==1)
        {
            int l,r;
            cin>>l>>r;
            ll ans=0;
            for(int b=0;b<B;b++)
            {
                ans += 1LL*query(b,1,l,r)*(1LL<<b);
            }
            cout<<ans<<"\n";
        }
        if(op==2)
        {
            int l,r,k;
            cin>>l>>r>>k;
            for(int b=0;b<B;b++)
            {
                if((k>>b)&1)
                {
                    update(b,1,l,r);
                }
            }
        }
    }
    return 0;
}

离线二维数点

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=2e6+10;
const int M=2e6+10;
struct node
{
    int x,id,val;
};
vector<node> v[N];
int ans[M],a[N];
int n,m;
int cnt[N];

void add(int x)
{
    for(;x<=N-5;x+=x&-x) cnt[x]++;
}
int ask(int x)
{
    int ans=0;
    for(;x;x-=x&-x) ans+=cnt[x];
    return ans;
    // ask 获得的是一个区间和 
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        v[l-1].push_back({x,i,-1});
        v[r].push_back({x,i,1});
    }
    for(int i=1;i<=n;i++)
    {
        add(a[i]);
        for(int j=0;j<v[i].size();j++)
        {
            ans[v[i][j].id]+=v[i][j].val*ask(v[i][j].x);
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    } 

    return 0;
}

GRAPH THEORY & TREE

LCA

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
int f[500006][21], dep[500006];
vector<int> g[500006];
void dfs(int u, int fa)
{
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (auto v : g[u])
    {
        if (v != fa) dfs(v, u);
    }
}
int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; i--)
    {
        if (f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
void init()
{
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(s, 0);
    init();
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}

最小生成树

kruskal

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int fa[8010];
int n, m;
struct edge
{
    int u, v, w;
}g[4000010];
int cnt;
void add(int u, int v, int w)
{
    cnt++;
    g[cnt].u = u;
    g[cnt].v = v;
    g[cnt].w = w;
}

int find(int x)
{
    if(fa[x]==x) return fa[x];
    else return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    fa[x]=y;
}
bool cmp(edge q, edge e)
{
    return q.w < e.w;
}
void kruskal()
{
    int tot=0;
    ll ans=0;
    for(int i=1;i<=2*m;i++)
    {
        int xr=find(g[i].u);
        int yr=find(g[i].v);
        if(xr!=yr)
        {
            merge(xr,yr);
            tot++;
            ans+=g[i].w;
         } 
        if(tot==n-1)
        {
            cout<<ans<<endl;
            return;
        }
    }
    cout<<"orz"<<endl;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v,u,w);
    }
    sort(g+1,g+2*m+1,cmp);
    kruskal();
    return 0;
}

prim

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

struct edge
{
    int to, dis, nxt;
} e[4000005];

struct node
{
    int pos, dis;
};
bool operator < (node q,node w)
{
    return q.dis>w.dis;
}

int head[5005], d[5005], cnt, n, m, ans;
bool vis[5005];

void add(int u, int v, int w)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].dis=w;
    e[cnt].nxt=head[u];
    head[u] = cnt;
}

priority_queue<node> q;
int prim(int s)
{

    q.push((node){s,0});
    d[s]=0;
    int tot=0;
    while(!q.empty() && tot<n)
    {
        node t=q.top();
        q.pop();
        int x=t.pos;
        if(vis[x]) continue;
        vis[x]=1;
        ans+=t.dis;
        tot++;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int v=e[i].to;
            int w=e[i].dis;
            if(!vis[v] && w<d[v])
            {
                d[v]=w;
                q.push((node){v,d[v]});
            }
        }
    }
    if(tot==n) return ans;
    else return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }

    for(int i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    int res=prim(1);
    if(res==-1)
    {
        cout<<"orz"<<endl;
    }
    else cout<<res;

    return 0;
}

DIJ

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int to;
    int dis;
    int nxt;
}e[500006];
int head[500006];
int d[500006];
bool vis[500006];
int cnt;
struct node
{
    int dis,pos;
};
bool operator <(node q,node w)
{
    return q.dis>w.dis;
}
priority_queue<node> q; 
void dij(int s)
{
    d[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node t=q.top();
        q.pop();
        int x=t.pos;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(d[y]>d[x]+e[i].dis)
            {
                d[y]=d[x]+e[i].dis; 
                if(!vis[y]) q.push((node){d[y],y});
            }
        }
    }
    return ;
}
void add(int u,int v,int di)
{
    cnt++;
    e[cnt].dis=di;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,s;  
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)d[i] = INT_MAX;
    for(int i=1;i<=m;i++)
    {
        int u,v,di;
        cin>>u>>v>>di;
        add(u,v,di);
    }
    dij(s);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

SPFA

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int to, dis, nxt;
}e[500010];
int head[100010], dis[100010], cnt;
bool vis[100010];
inline void add( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
struct node
{
    int dis;
    int pos;
};
queue<node> q;
inline void spfa(int s)
{
    dis[s]=0;
    vis[s]=1;
    q.push((node){0,s});
    while(!q.empty())
    {
        node t=q.front();
        q.pop();
        int x=t.pos;
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].dis)
            {
                dis[y]=dis[x]+e[i].dis;
                if(!vis[y])
            {
                q.push((node){dis[y],y});
                vis[y]=1;
            }
            }

        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)dis[i] = INT_MAX;
    for(int i=1;i<=m;i++)
    {
        int u, v, d;
       cin>>u>>v>>d;
        add( u, v, d );
    }
    spfa(s);
    for(int i=1;i<=n;i++)
       cout<<dis[i]<<" ";
    return 0;
}

Floyd

    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
                dp[j][i]=dp[i][j];
            }
        }
    }

强连通分量

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e4+10,M=1e5+10;
vector<int>g[N],ng[N];

int u[M],v[M];
int a[N];

int low[N],dfn[N],idx;
stack<int> st;

int rd[N],dp[N];
int num,scc[N],w[1000005];

void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    st.push(u);
    for(int v:g[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v]) low[u]=min(low[u],dfn[v]);
    }
        if(low[u]==dfn[u])
        {
            int t;
            num++;
            do
            {
                t=st.top();
                st.pop();
                scc[t]=num;
                w[num]+=a[t];
            }
            while(t!=u);
        }

}
queue<int> q;

void toposort()
{
    while(!q.empty())
    {
        q.pop();
    }
    for(int i=1; i<=num; i++)
    {
        if(!rd[i])
        {
            q.push(i);
            dp[i]=w[i];
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v:ng[u])
        {
            dp[v]=max(dp[v],dp[u]+w[v]);
            if(--rd[v]==0)
            {
                q.push(v);
            }
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }

    for(int i=1; i<=m; i++)
    {
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
    }

    for(int i=1; i<=n; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1; i<=m; i++)
    {
        int x=scc[u[i]];
        int y=scc[v[i]];
        if(x!=y)
        {
            ng[x].push_back(y);
            rd[y]++;
        }
    }
    toposort();
    int ans=0;
    for(int i=1; i<=num; i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

割点

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dfn[100004], low[100004], idx, res;
bool vis[100004], flag[100004];
vector<int> g[100004];

void tarjan(int u, int fa)
{
    vis[u] = 1;
    low[u] = dfn[u] = ++idx;
    int child = 0;
    vis[u]=1;
    low[u]=dfn[u]=++idx;
    for(int v : g[u])
    {
        if(!vis[v])
        {
            child++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(fa!=u && low[v]>=dfn[u])
            {
                flag[u]=1;
             } 
        }
        else if(v!=fa)
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==u && child>=2)
    {
        flag[u]=1;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            idx = 0;
            tarjan(i, i);
        }
    for (int i = 1; i <= n; i++)
    {
        if (flag[i]) res++;
    }
    cout << res << endl;
    for (int i = 1; i <= n; i++)
        if (flag[i]) cout << i << " ";
    return 0;
}

割边

#include <bits/stdc++.h>
using namespace std;
#define PP pair<int,int>
#define mp make_pair
const int MAXN = 100005; 
int n, m;
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], idx;
bool vis[MAXN];
vector<PP> bd;

void tarjan(int u, int father)
{

    vis[u]=1;
    dfn[u]=low[u]=++idx;
    for(int v:g[u])
    {
        if(!vis[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
            {
                int a=u;int b=v;
                if(a>b) swap(a,b);
                bd.push_back(mp(a,b));
            }
        }
        else if(v!=father)
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for (int i = 0; i < m;i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n;i++)
        if (!vis[i]) tarjan(i, i);

    sort(bd.begin(), bd.end());

    for (auto e : bd)
    {
        cout << e.first << ' ' << e.second << '\n';     
    }

    return 0;
}

点双

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge
{
    int to, nxt;
} e[M << 2];

int head[N << 1], cnt = 1;

void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int ans;
int dfn[N], low[N], idx;

stack<int> st;
bool cut[N];
vector<int> dcc[N];
int root;int num;

void tarjan(int u,int lst)
{
    dfn[u] = low[u] = ++idx;
    st.push(u);
    if (u == root && head[u] == 0)
    {
        dcc[++num].push_back(u);
        return;
    }
    int child = 0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(i==(lst^1)) continue;
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                if(++child>1 || u!=root) 
                {
                    cut[u]=1;//??
                }
                num++;
                int tt;
                do
                {
                    tt=st.top();
                    dcc[num].emplace_back(tt);
                    st.pop();
                }while(tt!=v);
                dcc[num].emplace_back(u);
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

int main()
{
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        if (u != v)
        {
            add(u,v);
            add(v,u);
        }
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) 
        {
            root=i;
            tarjan(i,0);
        }

    cout << num << '\n';
    for (int i = 1; i <= num; i++)
    {
        cout << dcc[i].size() << ' ';
        for (int j = 0; j < dcc[i].size(); j++) cout << dcc[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

边双

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = 2e6 + 5;
int n, m;

struct edge
{
    int to, nxt;
} e[M << 2];

int head[N << 1], cnt = 1;

void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int idx, sum;
int dfn[N], low[N];
bool vis[N];
vector<vector<int>> ans;
stack<int> st;

void tarjan(int u, int in)
{
    low[u] = dfn[u] = ++idx;
    st.push(u);
    vis[u]=1;
    for(int i=head[u]; i; i=e[i].nxt)
    {
        int v=e[i].to;
        if(i==(in^1)) continue;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }

    if(dfn[u]==low[u])
    {
        vector<int> t;
        int tt;

        do
        {
            tt=st.top();
            st.pop();
            t.push_back(tt);
            vis[tt]=0;

        }
        while(tt!=u);
        ans.push_back(t);
    }
    return;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        if (u != v)
        {
            add(u, v);
            add(v, u);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i]) tarjan(i, 0);

    }

    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i].size() << ' ';
        for (int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

STRING

KMP

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

char s[1000010];
char t[1000010];
int nxt[1000010];

int main()
{
    cin>>(s+1);
    cin>>(t+1);

    int n=strlen(s+1);
    int m=strlen(t+1);
    int p;
    nxt[0]=0;
    p=0;
    for(int i=1;i<m;i++)
    {
        while(t[p+1]!=t[i+1] && p) p=nxt[p];
        if(t[p+1]==t[i+1])
        {
            p++;
        }
        nxt[i+1]=p;
    } 

    p=0;
    for(int i=1;i<=n;i++)
    {
        while(t[p+1]!=s[i] && p) p=nxt[p];
        if(t[p+1]==s[i])
        {
            p++;
        }
        if(p==m)
        {
            cout<<i-m+1<<endl;
            p=nxt[p];
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<nxt[i]<<' ';
    }
    return 0;
}

Manacher

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

char s[60000005], S[30000005];
int p[30000005], n;

int manacher(char s[])
{

    int m=0;
    int r=0;
    for(int i=1;i<=n;i++)
    {
        if(i>r) p[i]=1;
        else p[i]=min(p[2*m-i],r-i+1); 
        while(i-p[i]>=1 && i+p[i]<=n && s[i-p[i]]==s[i+p[i]])
        {
            p[i]++;
        } 
        if(i+p[i]-1>r)
        {
            m=i;
            r=i+p[i]-1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,p[i]);
    }
    return ans-1;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> S;
    s[0]=' ';
    int idx=1;
    int ls=strlen(S);
    for(int i=0;i<ls;i++)
    {
        s[idx++]='#';
        s[idx++]=S[i];
    }
    s[idx++]='#';
    n=idx-1;

    cout << manacher(s) << endl;
    return 0;
}

字典树

#include<bits/stdc++.h>
using namespace std;
int t[3000005][127],cnt[3000005],idx;
char s[3000005];
int getnum(char x)
{
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
void insert(char str[])
{
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c]) t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}
int find(char str[])
{
    int p=0;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int c=getnum(str[i]);
        if(!t[p][c]) return 0;
        p=t[p][c];
    }
    return cnt[p];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0; i<=idx; i++)
        {
            for(int j=0;j<=122;j++)
            {
                t[i][j]=0;
            }
        }
        for(int i=0; i<=idx; i++)
        {
            cnt[i]=0;   
        }
        int n,q;
        idx=0;
        cin>>n>>q;
        for(int i=1; i<=n; i++)
        {
            cin>>s;
            insert(s);
        }
        for(int i=1; i<=q; i++)
        {
            cin>>s;
            cout<<find(s)<<'\n';
        }
    }
    return 0;
}

01 Trie

P10471。

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

int t[3000005][2], idx;

void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
        int c = (x >> i) & 1;
        if(!t[p][c]) t[p][c] = ++idx;
        p = t[p][c];
    }
}

int find(int x)
{
    int p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int c = (x >> i) & 1;
        int want = c ^ 1;
        if(t[p][want])
        {
            res |= (1 << i);
            p = t[p][want];
        }
        else
        {
            p = t[p][c];
        }
    }
    return res;
}
int a[31000005]; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    int ans = 0;
    insert(a[1]);
    for(int i = 2; i <= n; i++)
    {
        ans = max(ans, find(a[i]));
        insert(a[i]);
    }
    cout << ans << "\n";
    return 0;
}

MATH

算术基本定理（唯一分解定理）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

int p[103];
int c[103];
int calc(int x)
{

    int cnt=0;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            p[++cnt]=i;
            c[cnt]=0;
            while(x%i==0)
            {
                x=x/i;
                c[cnt]++;
            }
        }
    }
        if(x>1)
        {
            p[++cnt]=x;
            c[cnt]=1;
        }
    for(int i=1;i<=cnt;i++)
    {
        cout<<p[i]<<"^"<<c[i]<<endl; 
    }
}

signed main()
{
    int sti=clock();

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x;
    cin>>x;
    calc(x);

//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}

有理数取模

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod=19260817;
int a,b;
int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1; 
    }
    return ans;
}
inline int read()
{
    int x=0,ch=getchar();
    while(!isdigit(ch)&&ch!=EOF) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),x%=mod,ch=getchar();
    return x;
}

signed main(){
    a=read();
    b=read();
    cout<<(a%mod*qpow(b,mod-2))%mod;
    return 0;
}

排列组合

小的写上面！

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;

const ll mod=998244353;
ll a[5005];
ll ans[5005];

ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll cheng[10005005];
ll numinv[10005005];
ll inv[10005005];
ll c(ll a,ll b)
{
    if(b==0) return 1;
    return cheng[a]*inv[a-b]%mod*inv[b]%mod;
}
ll p(ll a,ll b)
{
    if(b==0) return 1;
    return cheng[a]*inv[a-b]%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cheng[0]=1;numinv[1]=1;
    for(int i=1;i<=10000;i++) //上界 
    {
        cheng[i]=cheng[i-1]*i%mod;
        if(i>1) numinv[i]=(mod-mod/i)*numinv[mod%i]%mod;
    }
    inv[0]=1;
/*
另外一种递推写法
    inv[n+m+3]=qpow(cheng[n+m+3],mod-2);
    for(int i=n+m+2;i>=1;i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;
    }

*/
    for(int i=1;i<=10000;i++)
    {
        inv[i]=inv[i-1]*numinv[i]%mod;
    }
    ll x,y;
    cin>>x>>y;
    // x should > y
    cout<<c(x,y)<<endl;
    cout<<p(x,y)<<endl;
    return 0;
}

    c[0][0]=1;
    for(int i=1;i<=N;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=N;j++)
        {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }

卡特兰数

    printf("%d",c[2*n][n]-c[2*n][n-1]);

欧拉筛

    int cnt=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) {
            p[cnt]=i;
            cnt++;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(p[j]*i>n) break;
            vis[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }

欧拉函数

for (int i = 2 ; i < n ; i ++)
    {
        if (!is[i])
            p[++ tot]=i, e[i] =i-1;
        for (int j = 1 ; j <= tot ; j ++)
        {
            if (i * p[j] >n-1) break ;
            is[i * p[j]] = 1 ;
            if (i % p[j] == 0)
            {
                e[i * p[j]] =e[i]*p[j] ;
//φ(i*p[j])=φ(i)*p[j]，互质的再乘个质数还是互质
                break;
            }
            else e[i*p[j]] =e[i]*e[p[j]];
//φ(i*p[j])=φ(i)*φ(p[j])=φ(i)*(p[j]-1)
        }
    }

单个数求 phi。

int phi(int n)
{
    int ans=n;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0) ans=ans/i*(i-1);
        while(n%i==0) n/=i;
    }
    if(n==1) return ans;
    else return ans=ans/n*(n-1);
}

杂项

表达式求值

支持 + - * / ^，正确的括号匹配。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
int p[130];
bool isop(char c)
{
    return c=='+'||c=='-'||c=='*'||c=='/'||c=='^';
}
int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
signed main()
{
    int sti=clock();

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    s='('+s+')';
    p['+']=1;p['-']=1;p['*']=2;p['/']=2;p['^']=3;
    string ss="";
    int ban=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='+' || s[i]=='-')
        {
            if(ss.size()==0 || ss.back()=='(' || isop(ss.back()) )
            {
                ss+='0';
            }
        }
        ss+=s[i];
    }
    s=ss;
    string ans="";
    stack<char> st1;
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))
        {
            ans+=s[i];
            if(i+1==s.size() || !isdigit(s[i+1]))
            {
                ans+='.';
            }
        }
        else if(s[i]=='(')
        {
            st1.push(s[i]);
        }
        else if(s[i]==')')
        {
            while(!st1.empty() && st1.top()!='(')
            {
                ans+=st1.top();
                st1.pop();
            }
            if(!st1.empty())
            {
                st1.pop();
            }
        }
        else if(isop(s[i]))
        {
            while(!st1.empty() && st1.top()!='(')
            {
                if(p[st1.top()]>p[s[i]] || (p[st1.top()]==p[s[i]] && s[i]!='^'))
                {
                    ans+=st1.top();
                    st1.pop();
                }
                else break;
            }
            st1.push(s[i]);
        }
    }
    while(!st1.empty())
    {
        if(st1.top()!='(')
        {
            ans+=st1.top();
        }
        st1.pop();
    } 
    stack<int> st;
    int num=0;
    for(int i=0;i<ans.size();i++)
    {
        if(isdigit(ans[i]))
        {
            num=num*10+ans[i]-'0';
        }
        else if(ans[i]=='.')
        {
            st.push(num);
            num=0;
        } else if(isop(ans[i]))
        {
            int b=st.top();st.pop();
            int a=st.top();st.pop();
            if(ans[i]=='+') st.push(a+b);
            if(ans[i]=='-') st.push(a-b);
            if(ans[i]=='*') st.push(a*b);
            if(ans[i]=='/') st.push(a/b);
            if(ans[i]=='^') st.push(qpow(a,b));
        }
    }
    cout<<st.top();
//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}

矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
const int Mod = 1000000007;
#define ll long long
struct M
{
    long long c[101][101];
} A, ANS;
const int N = 3;

M operator * ( M &x, M &y)
{
    M guo;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            guo.c[i][j] = 0;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            for (int k = 1; k <= N; k++)
            {
                guo.c[i][j] += x.c[i][k] * y.c[k][j] % Mod;
                guo.c[i][j] %= Mod;
            }
        }
    }
    return guo;
}

M qpow(M A, ll m)
{
    while (m > 0)
    {
        if (m & 1) ANS = ANS * A;
        A = A * A;
        m >>= 1;
    }
    return ANS;
}
void init()
{
    ANS.c[1][1] = 1;
    ANS.c[1][2] = 1;
    ANS.c[1][3] = 1;
    A.c[1][1] = 0;
    A.c[1][2] = 0;
    A.c[1][3] = 1;
    A.c[2][1] = 1;
    A.c[2][2] = 0;
    A.c[2][3] = 0;
    A.c[3][1] = 0;
    A.c[3][2] = 1;
    A.c[3][3] = 1;
}
int main()
{

    int T;
    cin >> T;
    while (T--)
    {
        ll n;
        cin >> n;
        if (n <= 3)
        {
            cout << 1 << endl;
            continue;
        }
        init();
        M ANS = qpow(A, n - 3);
        cout << ANS.c[1][3] % Mod << endl;

    }
    return 0;
}

二维前缀和

以模板题为例：

for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {       
            cin>>a[i][j];
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
        ull ans=0;
        for(int i=1;i<=q;i++)
        {
            int u,v,x,y;
            cin>>u>>v>>x>>y;
            ans^=sum[x][y]-sum[u-1][y]-sum[x][v-1]+sum[u-1][v-1];
        }

高精度

注意实际位数，预防 MLE。

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

const int maxn = 10001;

struct bign
{
    int d[maxn], len;

    void clean()
    {
        while(len > 1 && !d[len-1]) len--;
    }

    bign()
    {
        memset(d, 0, sizeof(d));
        len = 1;
    }
    bign(int num)
    {
        *this = num;
    }
    bign(char* num)
    {
        *this = num;
    }
    bign operator = (const char* num)
    {
        memset(d, 0, sizeof(d));
        len = strlen(num);
        for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
        clean();
        return *this;
    }
    bign operator = (int num)
    {
        char s[maxn];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    bign operator + (const bign& b)
    {
        bign c = *this;
        int i;
        for (i = 0; i < b.len; i++)
        {
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
        }
        while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
        c.len = max(len, b.len);
        if (c.d[i] && c.len <= i) c.len = i+1;
        return c;
    }
    bign operator - (const bign& b)
    {
        bign c = *this;
        int i;
        for (i = 0; i < b.len; i++)
        {
            c.d[i] -= b.d[i];
            if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
        }
        while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
        c.clean();
        return c;
    }
    bign operator * (const bign& b)const
    {
        int i, j;
        bign c;
        c.len = len + b.len;
        for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
                c.d[i+j] += d[i] * b.d[j];
        for(i = 0; i < c.len-1; i++)
            c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
        c.clean();
        return c;
    }
    bign operator / (const bign& b)
    {
        int i, j;
        bign c = *this, a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            c.d[i] = j;
            a = a - b*j;
        }
        c.clean();
        return c;
    }
    bign operator % (const bign& b)
    {
        int i, j;
        bign a = 0;
        for (i = len - 1; i >= 0; i--)
        {
            a = a*10 + d[i];
            for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
            a = a - b*j;
        }
        return a;
    }
    bign operator += (const bign& b)
    {
        *this = *this + b;
        return *this;
    }

    bool operator <(const bign& b) const
    {
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
            if(d[i] != b.d[i]) return d[i] < b.d[i];
        return false;
    }
    bool operator >(const bign& b) const
    {
        return b < *this;
    }
    bool operator<=(const bign& b) const
    {
        return !(b < *this);
    }
    bool operator>=(const bign& b) const
    {
        return !(*this < b);
    }
    bool operator!=(const bign& b) const
    {
        return b < *this || *this < b;
    }
    bool operator==(const bign& b) const
    {
        return !(b < *this) && !(b > *this);
    }

    string str() const
    {
        char s[maxn]= {};
        for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
        return s;
    }
};

istream& operator >> (istream& in, bign& x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream& out, const bign& x)
{
    out << x.str();
    return out;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    bign a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

对拍

make.cpp

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

int random(int mod)
{
    int ans=114514;
    ans=ans*rand()%mod;
    return (ans+mod)%mod+1;
}// 1 to mod
int main()
{
    srand(time(0));

    int n=random(10000);
    cout<<n<<endl;
    return 0;
}

pai.cpp

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

int main()
{
    while (1)
    {
        system("make.exe > make.in");
        system("baoli.exe < make.in > baoli.out");
        system("ceshi.exe < make.in > ceshi.out");
        if(system("fc baoli.out ceshi.out"))
        {
            cout<<"WARN!"<<endl;
            break;
        }
        else cout<<"NO PROBLEM"<<endl;
    }
    return 0;
}

END