首页 > 其他分享 >板子们

板子们

时间：2024-11-04 21:02:30浏览次数：1  
标签：ch int long 板子 read maxn ans

单调队列——滑动窗口 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 3;

int n, k, a[maxn], mx[maxn], mi[maxn], q[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void getmin()
{
    int h = 1, t = 0;
    for(int i=1; i<k; i++)
    {
        while(h <= t && a[q[t]] >= a[i]) t--;
        q[++t] = i;
    }
    for(int i=k; i<=n; i++)
    {
        while(q[h] <= i - k) h++;
        while(h <= t && a[q[t]] >= a[i]) t--;
        q[++t] = i; mi[i] = a[q[h]];
        //printf("mi[%d] = %d\n", i, mi[i]);
    }
}

void getmax()
{
    int h = 1, t = 0;
    for(int i=1; i<k; i++)
    {
        while(h <= t && a[q[t]] <= a[i]) t--;
        q[++t] = i;
    }
    for(int i=k; i<=n; i++)
    {
        while(q[h] <= i - k) h++;
        while(h <= t && a[q[t]] <= a[i]) t--;
        q[++t] = i; mx[i] = a[q[h]];
        //printf("mx[%d] = %d\n", i, mx[i]);
    }
}

int main()
{
    n = read(); k = read();
    for(int i=1; i<=n; i++) a[i] = read();
    getmax(); getmin();
    for(int i=k; i<=n; i++)
    {
        printf("%d ", mi[i]);
    }
    printf("\n");
    for(int i=k; i<=n; i++)
    {
        printf("%d ", mx[i]);
    }
    printf("\n");

    return 0;
}
树状数组——区间修改，区间查询 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 3;

int n, m, a[maxn];
ll c1[maxn], c2[maxn];
char op[7];

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void add(int x, ll d)
{
    int i = x;
    while(i <= n)
    {
        c1[i] += d;
        c2[i] += x * d;//注意是x*d而不是i*d
        i += (i & -i);
    }
}

ll query(int x)
{
    ll ans = 0;
    int i = x;
    while(i > 0)
    {
        ans += (x+1)*c1[i]-c2[i];
        i -= (i & -i);//x和i是不同的，从表达式里就可以看出来
    }
    return ans;
}

int main()
{
    n = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read();
        add(i, a[i]-a[i-1]);
    }
    m = read();
    for(int i=1; i<=m; i++)
    {
        scanf("%s", op);
        if(op[0] == 'A')
        {
            int l = read(), r = read(); ll d = read();
            add(l, d); add(r+1, -d);
        }
        else 
        {
            int l = read(), r = read();
            if(l == 1) printf("%lld\n", query(r));
            else printf("%lld\n", query(r) - query(l-1));
        }
    }

    return 0;
}
二维树状数组——移动电话 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1500;

int fl, s, c[maxn][maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void add(int x, int y, int d)
{
    for(int i=x; i<=s; i+=(i&-i))
    {
        for(int j=y; j<=s; j+=(j&-j))
        {
            c[i][j] += d;
        }
    }
}

int query(int x, int y)
{
    int ans = 0;
    for(int i=x; i>0; i-=(i&-i))
    {
        for(int j=y; j>0; j-=(j&-j))
        {
            ans += c[i][j];
        }
    }
    return ans;
}

int main()
{
    fl = read(); s = read();
    fl = read();
    while(fl != 3)
    {
        if(fl == 1)
        {
            int x = read()+1, y = read()+1, d = read();
            add(x, y, d);
        }
        else if(fl == 2)
        {
            int l = read()+1, b = read()+1, k = read()+1, t = read()+1;
            int ans = query(k, t)-query(k, b-1)-query(l-1, t)+query(l-1, b-1);
            printf("%d\n", ans);
        }
        fl = read();
    }

    return 0;
}
线段树——最大值 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 3;

int n, m, a[maxn];

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    struct tree 
    {
        int max;
    }t[maxn<<2];
    void pushup(int x)
    {
        t[x].max = max(t[x<<1].max, t[x<<1|1].max);
    }
    void build(int x, int l, int r)
    {
        if(l == r) 
        {
            t[x].max = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
        pushup(x);
    }
    int query(int x, int l, int r, int L, int R)
    {
        if(L <= l && r <= R)
        {
            return t[x].max;
        }
        int mid = (l + r) >> 1, ans = 0;
        if(L <= mid) ans = max(ans, query(x<<1, l, mid, L, R));
        if(R > mid) ans = max(ans, query(x<<1|1, mid+1, r, L, R));
        return ans;
    }
}t;

int main()
{
    n = read();
    for(int i=1; i<=n+1; i++) a[i] = read();
    t.build(1, 1, n+1);
    m = read();
    for(int i=1; i<=m; i++)
    {
        int l = read()+1, r = read()+1;
        int ans = t.query(1, 1, n+1, l, r);
        printf("%d\n", ans);
    }

    return 0;
}
线段树——区间求和 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 3;

int n, m;
ll a[maxn];
char op[5];

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    struct tree 
    {
        ll sum, lazy;
    }t[maxn<<2];
    void pushup(int x)
    {
        t[x].sum = t[x<<1].sum + t[x<<1|1].sum;
    }
    void pushdown(int x, int l, int r)
    {
        int ls = x<<1, rs = x<<1|1, mid = (l + r) >> 1;
        ll lz = t[x].lazy; t[x].lazy = 0;
        t[ls].lazy += lz;
        t[ls].sum += lz * (mid - l + 1);
        t[rs].lazy += lz;
        t[rs].sum += lz * (r - mid);
    }
    void build(int x, int l, int r)
    {
        if(l == r) 
        {
            t[x].sum = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
        pushup(x);
    }
    void update(int x, int l, int r, int L, int R, ll d)
    {
        if(L <= l && r <= R)
        {
            t[x].sum += (r - l + 1) * d; t[x].lazy += d;
            return;
        }
        if(t[x].lazy) pushdown(x, l, r);
        int mid = (l + r) >> 1;
        if(L <= mid) update(x<<1, l, mid, L, R, d);
        if(R > mid) update(x<<1|1, mid+1, r, L, R, d);
        pushup(x);
    }
    ll query(int x, int l, int r, int L, int R)
    {
        if(L <= l && r <= R)
        {
            return t[x].sum;
        }
        if(t[x].lazy) pushdown(x, l, r);
        int mid = (l + r) >> 1; ll ans = 0;
        if(L <= mid) ans += query(x<<1, l, mid, L, R);
        if(R > mid) ans += query(x<<1|1, mid+1, r, L, R);
        return ans;
    }
}t;

int main()
{
    n = read();
    for(int i=1; i<=n; i++) a[i] = read();
    t.build(1, 1, n);
    m = read();
    for(int i=1; i<=m; i++)
    {
        scanf("%s", op);
        if(op[0] == 'A')
        {
            int l = read(), r = read(); ll d = read();
            t.update(1, 1, n, l, r, d);
        }
        else 
        {
            int l = read(), r = read();
            ll ans = t.query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }

    return 0;
}
树状数组——区间修改，单点查询 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 3;

int n, m, a[maxn];
ll c[maxn];
char op[7];

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void add(int x, ll d)
{
    while(x <= n)
    {
        c[x] += d;
        x += (x & -x);
    }
}

ll query(int x)
{
    ll ans = 0;
    while(x > 0)
    {
        ans += c[x];
        x -= (x & -x);
    }
    return ans;
}

int main()
{
    n = read();
    for(int i=1; i<=n; i++) a[i] = read();
    add(1, a[1]);
    for(int i=2; i<=n; i++) add(i, a[i]-a[i-1]);
    m = read();
    for(int i=1; i<=m; i++)
    {
        scanf("%s", op);
        if(op[0] == 'A')
        {
            int l = read(), r = read(); ll d = read();
            add(l, d); add(r+1, -d);
        }
        else 
        {
            int p = read();
            ll ans = query(p);
            printf("%lld\n", ans);
        }
    }

    return 0;
}
HH的项链——树状数组 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 3;
const int maxm = 2e5 + 3;

int n, m, R, a[maxn], ans[maxm], las[maxn], c[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct que 
{
    int l, r, id;
    bool operator < (const que &T) const 
    {
        return r < T.r;
    }
}q[maxm];

inline void add(int x, int d)
{
    while(x <= n)
    {
        c[x] += d;
        x += (x & -x);
    }
}

inline int query(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += c[x];
        x -= (x & -x);
    }
    return ans;
}

int main()
{
    n = read();
    for(int i=1; i<=n; i++) a[i] = read();
    m = read();
    for(int i=1; i<=m; i++)
    {
        q[i].l = read(); q[i].r = read(); q[i].id = i;
    }
    sort(q+1, q+1+m);
    for(int i=1; i<=m; i++)
    {
        while(R < q[i].r)
        {
            R++;
            if(las[a[R]]) add(las[a[R]], -1);
            add(R, 1);
            las[a[R]] = R;
        }
        if(q[i].l == 1) ans[q[i].id] = query(R);
        else ans[q[i].id] = query(R)-query(q[i].l-1);
    }
    for(int i=1; i<=m; i++)
    {
        printf("%d\n", ans[i]);
    }

    return 0;
}
dfs序1 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 3;

int dfn[maxn], v[maxn], nt, n, m, r, siz[maxn], fnd[maxn];
ll c[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int nxt, to;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    a[++len].to = y; a[len].nxt = head[x];
    head[x] = len;
}

void dfs(int u, int fa)
{
    dfn[++nt] = u; fnd[u] = nt;
    siz[u] = 1;
    for(int i=head[u]; i; i=a[i].nxt)
    {
        int v = a[i].to;
        if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}

void addt(int x, ll d)
{
    while(x <= n)
    {
        c[x] += d;
        x += (x & -x);
    }
}

ll query(int x)
{
    ll ans = 0;
    while(x > 0)
    {
        ans += c[x];
        x -= (x & -x);
    }
    return ans;
}

int main()
{
    n = read(); m = read(); r = read();
    for(int i=1; i<=n; i++) v[i] = read();
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dfs(r, 0);
    for(int i=1; i<=n; i++)
    {
        addt(i, v[dfn[i]]);
    }
    for(int i=1; i<=m; i++)
    {
        int fl = read();
        if(fl == 1)
        {
            int a = read(), x = read();
            addt(fnd[a], x);//不用dfn数组
        }
        else 
        {
            int a = read();
            ll ans = query(fnd[a]+siz[a]-1)-query(fnd[a]-1);//不用dfn数组
            printf("%lld\n", ans);
        }
    }

    return 0;
}
倍增LCA——牧场旅行 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1130;

int n, q, f[maxn][12], c[maxn][12], dep[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int nxt, to, w;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y, int w)
{
    a[++len].to = y; a[len].nxt = head[x]; a[len].w = w;
    head[x] = len;
}

void dfs(int x, int fa)
{
    f[x][0] = fa; 
    dep[x] = dep[fa] + 1;
    for(int i=1; i<12; i++)
    {
        f[x][i] = f[f[x][i-1]][i-1];
        c[x][i] = c[f[x][i-1]][i-1] + c[x][i-1];
    }
    for(int i=head[x]; i; i=a[i].nxt)
    {
        int v = a[i].to;
        if(v == fa) continue;
        c[v][0] = a[i].w;
        dfs(v, x);
    }
}

int query(int x, int y)
{
    if(dep[x] > dep[y]) swap(x, y);
    int tmp = dep[y] - dep[x], ans = 0;
    for(int i=0; tmp; i++,tmp>>=1)
    {
        if(tmp & 1) ans += c[y][i], y = f[y][i];
    }
    if(y == x) return ans;//LCA return x;
    for(int i=11; i>=0&&x!=y; i--)
    {
        if(f[x][i] != f[y][i])
        {
            ans += c[x][i] + c[y][i];
            x = f[x][i]; y = f[y][i];//因为写成了y = c[y][i]错了3次！？
        }
    }
    ans += c[x][0] + c[y][0];
    return ans;//LCA return f[x][0]
}

int main()
{
    n = read(); q = read();
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read(), w = read();
        add(x, y, w); add(y, x, w);
    }
    dfs(1, 0);
    for(int i=1; i<=q; i++)
    {
        int x = read(), y = read();
        printf("%d\n", query(x, y));
    }

    return 0;
}
树链剖分——路径求和+最大值 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 3e4 + 2;

int n, m, w[maxn], fa[maxn];
int dep[maxn], dfn[maxn], nt, fnd[maxn], siz[maxn], son[maxn], top[maxn];
char op[8];
ll ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int nxt, to;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    a[++len].to = y; a[len].nxt = head[x];
    head[x] = len;
}

void dfs1(int u, int fat, int depth)
{
    fa[u] = fat;
    dep[u] = depth;
    siz[u] = 1;
    son[u] = 0;
    int maxsize = 0;
    
    for(int i=head[u]; i; i=a[i].nxt)
    {
        int v = a[i].to;
        if(v == fat) continue;
        dfs1(v, u, depth+1);
        siz[u] += siz[v];
        if(siz[v] > maxsize)
        {
            maxsize = siz[v];
            son[u] = v;
        }
    }
}

void dfs2(int u, int ancestor)
{
    dfn[u] = ++nt; fnd[nt] = u;
    top[u] = ancestor;
    if(son[u])
    {
        dfs2(son[u], ancestor);
    }
    for(int i=head[u]; i; i=a[i].nxt)
    {
        int v = a[i].to;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

struct node 
{
    struct tree 
    {
        int max; ll sum;
    }t[maxn<<2];
    void pushup(int x)
    {
        t[x].max = max(t[x<<1].max, t[x<<1|1].max);
        t[x].sum = t[x<<1].sum + t[x<<1|1].sum;
    }
    void build(int x, int l, int r)
    {
        if(l == r)
        {
            t[x].max = t[x].sum = w[fnd[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(x<<1, l, mid);
        build(x<<1|1, mid+1, r);
        pushup(x);
    }
    void update(int x, int l, int r, int p, int v)
    {
        if(l == r)
        {
            t[x].max = t[x].sum = v;
            return;
        }
        int mid = (l + r) >> 1;
        if(p <= mid) update(x<<1, l, mid, p, v);
        else update(x<<1|1, mid+1, r, p, v);
        pushup(x);
    }
    int querymax(int x, int l, int r, int L, int R)
    {
        if(L <= l && r <= R)
        {
            return t[x].max;
        }
        int mid = (l + r) >> 1, ans = -1e9;
        if(L <= mid) ans = querymax(x<<1, l, mid, L, R);
        if(R > mid) ans = max(ans, querymax(x<<1|1, mid+1, r, L, R));
        return ans;
    }
    ll querysum(int x, int l, int r, int L, int R)
    {
        if(L <= l && r <= R)
        {
            return t[x].sum;
        }
        int mid = (l + r) >> 1; ll ans = 0;
        if(L <= mid) ans = querysum(x<<1, l, mid, L, R);
        if(R > mid) ans += querysum(x<<1|1, mid+1, r, L, R);
        return ans;
    }
}t;

int querymax(int x, int y)
{
    int ans = -1e9;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = max(ans, t.querymax(1, 1, n, dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans = max(ans, t.querymax(1, 1, n, dfn[x], dfn[y]));
    return ans; 
}

ll querysum(int x, int y)
{
    ll ans = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += t.querysum(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ans += t.querysum(1, 1, n, dfn[x], dfn[y]);
    return ans;
}

int main()
{
    n = read();
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dfs1(1, 1, 1);
    dfs2(1, 1);
    for(int i=1; i<=n; i++) w[i] = read();
    t.build(1, 1, n);
    m = read();
    while(m--)
    {
        scanf("%s", op);
        if(op[0] == 'C')
        {
            int x = read(), d = read();
            t.update(1, 1, n, dfn[x], d);
        }
        else if(op[1] == 'M')
        {
            int l = read(), r = read();
            ans = querymax(l, r);
            printf("%lld\n", ans);
        }
        else 
        {
            int l = read(), r = read();
            ans = querysum(l, r);
            printf("%lld\n", ans);
        }
    }
    
    return 0;
}
正反图Spfa——奶牛派对 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1303;
const int M = 1e6 + 2;

int n, m, q, dis[maxn][2], ans;
bool vis[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int nxt, to, w;
}a[M][2];
int head[maxn][2], len[2];

void add(int x, int y, int w, int c)
{
    a[++len[c]][c].to = y; a[len[c]][c].nxt = head[x][c]; a[len[c]][c].w = w;
    head[x][c] = len[c];
}

queue<int> que;

void spfa(int s, int c)
{
    memset(vis, 0, sizeof(vis));
    que.push(s);
    vis[s] = 1;
    dis[s][c] = 0;
    while(!que.empty())
    {
        int x = que.front(); que.pop();
        vis[x] = 0;
        for(int i=head[x][c]; i; i=a[i][c].nxt)
        {
            int y = a[i][c].to;
            if(dis[y][c] > dis[x][c] + a[i][c].w)
            {
                dis[y][c] = dis[x][c] + a[i][c].w;
                if(!vis[y])
                {
                    que.push(y);
                }
            }
        }
    }
}

int main()
{
    n = read(); m = read(); q = read();
    for(int i=1; i<=m; i++)
    {
        int x = read(), y = read(), w = read();
        add(x, y, w, 0); add(y, x, w, 1);
    }
    memset(dis, 0x3f, sizeof(dis));
    spfa(q, 0); spfa(q, 1);
    for(int i=1; i<=n; i++)
    {
        ans = max(ans, dis[i][0] + dis[i][1]);
    }
    printf("%d\n", ans);
    
    return 0;
}
带权并查集——银河英雄传说 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 3e4 + 4;

int T, fa[maxn], fnt[maxn], num[maxn];
char op[3];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int find(int x)
{
    if(x == fa[x]) return x;
    //else return fa[x] = find(fa[x]);
    int fx = find(fa[x]);
    fnt[x] += fnt[fa[x]];//not fx，一次只跳一步
    fa[x] = fx;
    return fa[x];
}

int main()
{
    T = read();
    for(int i=1; i<=30000; i++)
    {
        fa[i] = i; num[i] = 1; fnt[i] = 0;
    }
    while(T--)
    {
        scanf("%s", op);
        int x = read(), y = read();
        int fx = find(x), fy = find(y);
        if(op[0] == 'M')
        {
            fnt[fx] += num[fy];
            num[fy] += num[fx];
            num[fx] = 0;
            fa[fx] = fy;
        }
        else 
        {
            if(fx != fy) printf("-1\n");
            else printf("%d\n", abs(fnt[x]-fnt[y])-1);
        }
    }
    
    return 0;
}
RMQ_ST表 
void RMQ_init()
{
    for(int i=1; i<=n; i++) d[i][0] = a[i];
    for(int j=1; (1<<j)<=n; j++)
    {
        for(int i=1; i+(1<<j)-1<=n; i++)
        {
            d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
        }
    }
}

int RMQ(int L, int R)
{
    int k = 0;
    while((1<<(k+1)) <= R-L+1) k++;
    return min(d[L][k], d[R-(1<<k)+1][k]);
}
tarjan缩点（有向图的强连通分量） 
 void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    stk.push(x);
    v[x] = 1;
    vis[x] = 1;
    for(int i=head[x]; i; i=a[i].nxt)
    {
        if(!dfn[a[i].to])
        {
            tarjan(a[i].to);
            low[x] = min(low[x], low[a[i].to]);
        }
        else if(v[a[i].to])
        {
            low[x] = min(low[x], dfn[a[i].to]);
        }
    }
    if(low[x] == dfn[x])
    {
        int y, tot = 0;
        ++t;
        do 
        {
            y = stk.top();
            stk.pop();
            v[y] = 0;
            belong[y] = t;
            tot++;
        }while(y != x);
        if(tot > 1) ans = min(ans, tot);
    }
}
tarjan求割点（无向图） 
 void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    int son = 0;
    for(int i=head[x]; i; i=a[i].nxt)
    {
        if(!dfn[a[i].to])
        {
            son++;
            tarjan(a[i].to);
            low[x] = min(low[x], low[a[i].to]);
            if(dfn[x] <= low[a[i].to])
            {
                if(x != root || son > 1) cut[x] = true;
            }
        }
        else 
        {
            low[x] = min(low[x], dfn[a[i].to]);
        }
    }
}
tarjan求割边（无向图） 
 void tarjan(int now, int fa)
{
    dfn[now] = low[now] = ++num;
    bool first = true;
    for(int i=head[now]; i; i=a[i].nxt)
    {
        if(first && a[i].to == fa)//first不是没有用，它管跳过第一次，考虑重边了
        {
            first  = false;
            continue;
        }
        if(!dfn[to[i]])
        {
            tarjan(to[i]);
            low[now] = min(low[now], low[a[i].to]);
            if(dfn[now] < dfn[a[i].to])
            {
                cnt++;
                cut[i] = cut[i^1] = true;
            }
        }
        else 
        {
            low[now] = min(low[now], dfn[a[i].to]);
        }
    }
}
tarjan点双连通（无向图） 
 void tarjan(int now, int fa)
{
    vis[now] = true;
    dfn[now] = low[now] = ++dfs_clock;
    stk[++top] = now;

    bool first = true;
    int son = 0;
    for(int i=head[now]; i; i=a[i].nxt)
    {
        int to = a[i].to;
        if(first && to == fa)
        {
            first = false;
            continue;
        }
        if(!dfn[to])
        {
            son++;
            tarjan(to, now);
            low[now] = min(low[now], low[to]);
            if(dfn[now] <= low[to])
            {
                cut[now] = true;
                cnt++;
                dslt[cnt].push_back(now);//既然不出栈就提前放进去
                int x;
                do 
                {
                    x = stk[top--];
                    dslt[cnt].push_back(x);
                }while(x != to);//now不能直接出栈，它有可能属于多个点双
            }
        }
        else 
        {
            low[now] = min(low[now], dfn[to]);
        }
    }
    if(fa == -1 && son == 1) cut[now] = false;
}
Tarjan边双联通（无向图） 
 void tarjan(int now, int eid)
{
    vis[now] = true;
    dfn[now] = low[now] = ++dfs_clock;
    stk[++top] = now;

    for(int i=head[now]; i; i=a[i].nxt)
    {
        int to = a[i].to;
        int id = a[i].id;
        if(id == eid^1) continue;

        if(!dfn[to])
        {
            tarjan(to, id);
            low[now] = min(low[now], low[to]);
        }
        else 
        {
            low[now] = min(low[now], dfn[to]);
        }
    }
    if(dfn[now] == low[now])
    {
        cut[eid] = true;
        cnt++;
        int x;
        do 
        {
            x = stk[top--];
            bslt[cnt].push_back(x);
        }while(x != now);
    }
}
二分图 
 bool dfs(int x)
{
    for(int i=1; i<=n; i++)
    {
        if(!vis[i] && mp[x][i])
        {
            vis[i] = 1;
            if(match[i] == 0 || dfs(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    n = read(); k = read();
    for(int i=1; i<=k; i++)
    {
        int x = read(), y = read();
        mp[x][y] = 1;
    }
    for(int i=1; i<=n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    printf("%d", ans);

    return 0;
}
重载运算符 
 struct node 
{
    int r;
    bool operator < (const node &a) const 
    {
        return r < a.r;//return r > a.r;优先队列小的优先出队
    }
}p[maxn];
//如果使用sort得到按照r从小到大排序的p
//优先队列是相反的
lazy 
 #include<bits/stdc++.h>
using namespace std;

#define maxn 100000
#define lson (rt << 1)
#define rson (rt << 1 | 1)
long long n, m, a[maxn], u, t, v, ans;
char s[7];

struct node
{
    long long l, r, sum, lazy;//结构体里的数据类型别忘了改！
};
node tree[maxn * 4];

long long read()
{
    long long x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1)+ (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}


void pushup(long long rt)
{
    tree[rt].sum = tree[lson].sum + tree[rson].sum;
    //tree[rt].min = min(tree[lson].min, tree[rson].min);
}

void build(long long rt, long long l, long long r)
{
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r)
    {
        tree[rt].sum = a[l];
        return;
    }
    long long mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid+1, r);

    pushup(rt);
}

void pushdown(long long rt)
{
    if(tree[rt].lazy)
    {
        long long lz = tree[rt].lazy;
        tree[rt].lazy = 0;
        tree[lson].lazy += lz;
        tree[rson].lazy += lz;
        tree[lson].sum += lz * (tree[lson].r - tree[lson].l + 1);
        tree[rson].sum += lz * (tree[rson].r - tree[rson].l + 1);
    }
}

void update(long long rt, long long l, long long r, long long val)
{
    if(l <= tree[rt].l && tree[rt].r <= r)
    {
        tree[rt].lazy += val;
        tree[rt].sum += val * (tree[rt].r - tree[rt].l + 1);
        return;
    }
    pushdown(rt);
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if(l <= mid) update(lson, l, r, val);
    if(r > mid) update(rson, l, r, val);
    pushup(rt);
}

long long query(long long rt, long long l, long long r)
{
    if(l <= tree[rt].l && tree[rt].r <= r)
    {
        return tree[rt].sum;
    }
    pushdown(rt);
    long long mid = (tree[rt].l + tree[rt].r) >> 1;
    long long val = 0;
    if(l <= mid) val += query(lson, l, r);
    if(r > mid) val += query(rson, l, r);
    return val;
}

/*void update(int rt, int pos, int val)
{
    if(tree[rt].l == tree[rt].r)
    {
        tree[rt].sum += val;
        tree[rt].min += val;
        return;
    }
    int mid = (tree[rt].l + tree[rt].r) >> 1;
    if(pos <= mid) update(lson, pos, val);
    else update(rson, pos, val);

    pushup(rt);
}*/

/*int query(int rt, int l, int r)
{
    if(l <= tree[rt].l && tree[rt].r <= r)
    {
        return tree[rt].sum;
    }
    int mid = (tree[rt].l + tree[rt].r) >> 1;

    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return (query(lson, l, r) + query(rson, l, r));
}*/

/*int monn(int rt, int l, int r)
{
    if(l <= tree[rt].l && tree[rt].r <= r)
    {
        return tree[rt].min;
    }
    int mid = (tree[rt].l + tree[rt].r) >> 1;

    int mi = 0x7fffffff;
    if(l <= mid) mi = min(mi, monn(lson, l ,r));
    if(r > mid) mi = min(mi, monn(rson, l, r));
    return mi;
}*/

int main()
{
    n = read();
    if(n == 0) exit(0);
    for(int i=1; i<=n; i++)
    {
        a[i] = read();
    }
    build(1, 1, n);
    m = read();
    for(int i=1; i<=m; i++)
    {
        scanf("%s", s);
        u = read();
        if(s[0] == 'A')
        {
            t = read();
            v = read();
            update(1, u, t, v);
        }
        if(s[0] == 'Q')
        {
            ans = query(1, u, u);
            printf("%lld\n", ans);
        }
    }
}
混合背包 
 #include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<stack>
#include<map>
#include<queue>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cstdio>
#include<deque>
#include<bitset>
using namespace std;

#define maxn 300000
int n, m;
int f[maxn], c[maxn];
int v[maxn], p[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    m = read(); n =read();
    for(int i=1; i<=n; i++)
    {
        v[i] = read();
        c[i] = read();
        p[i] = read();
    }
    for(int i=1; i<=n; i++)
    {
        if(p[i] == 0)
        {
            for(int j=v[i]; j<=m; j++)
            {
                f[j] = max(f[j], f[j-v[i]]+c[i]);
            }
        }
        else
        {
            for(int k=1; k<=p[i]; k<<=1)
            {
                for(int j=m; j>=v[i]*k; j--)
                {
                    f[j] = max(f[j], f[j-v[i]*k]+c[i]*k);
                }
                p[i] -= k;
            }
            if(p[i])
            {
                for(int j=m; j>=v[i]*p[i]; j--)
                {
                    f[j] = max(f[j], f[j-v[i]*p[i]]+c[i]*p[i]);
                }
            }
        }
    }
    printf("%d", f[m]);

    return 0;
}
Hash 
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 1e6 + 7;
const int M = 998244353;
const int B = 233;

char w[maxn], t[maxn];
int n, len1, len2, ans;
ll h1, f[maxn], p[maxn], h2;

int main()
{
    p[0] = 1;
    for(int i=1; i<=10000; i++)
    {
        p[i] = p[i-1] * B;
    }
    scanf("%d", &n);
    while(n--)
    {
        ans = 0; h1 = 0;
        memset(f, 0, sizeof(f));

        scanf("%s%s", w, t);
        len1 = strlen(w);
        len2 = strlen(t);

        for(int i=0; i<len1; i++)
        {
            h1 = h1 * B + w[i];
        }
        f[0] = t[0];
        for(int i=1; i<len2; i++)
        {
            f[i] = f[i-1] * B + t[i];
        }
        h2 = f[len1-1];
        if(h1 == h2) ans++;
        for(int i=1; i+len1-1<len2; i++)
        {
            h2 = f[i+len1-1] - f[i-1]*p[len1];
            if(h1 == h2) ans++;
        }
        printf("%d\n",ans);
    }

    return 0;
}
KMP 
 int main()
{
    //找到b在a中出现的所有位置
    scanf("%s%s", a+1, b+1);
    int la = strlen(a+1), lb = strlen(b+1);
    int j = 0;
    p[1] = 0;
    for(int i=2; i<=lb; i++)
    {
        while(j > 0 && b[i] != b[j+1]) j = p[j];
        if(b[i] == b[j+1]) j++;
        p[i] = j;
    }
    j = 0;
    for(int i=1; i<=la; i++)
    {
        while(j > 0 && a[i] != b[j+1]) j = p[j];
        if(a[i] == b[j+1]) j++;
        if(j == lb) printf("%d\n", i-lb+1), j = p[j];
    }
    
    return 0;
}

最近开始复习了，或许以后还会继续用这个平台记录一些题。曾经卷来卷去死记硬背怎么都记不住的那些板子，不知道为什么这一遍忽然理解了，当我终于有了一篇记录板子的blog时已经不再需要背，当我终于看清楚了一点点OI的面目，我已经离开这篇乐土很久了……

感觉大学生活总体上是比高中幸福的，但是在hzoi的回忆，却一次又一次让我幻想重来，就好像如果这样，我当年就不会走得那么早，就好像如果我的时间永远定格在那些日子里的任意一天，都值得让我放弃之后所有的可能性，嗯，我太恋旧了，这是弱点。

在整个大学大一范围内找不到一个能和我一起讨论编程的女生，不在高处，却不胜寂寞，好在找到陪我玩第5人格的搭子还是很容易的。

关于上一篇博客使用了某些专有名词和专有图片，我狡辩，我不玩原神（虽然有账号），因为不知道怎么在这个游戏里活下去，不是被反派制裁就是在被反派制裁的路上，我太菜了。但是因为受到同学的感染而喜欢刻晴。

标签：ch,int,long,板子,read,maxn,ans
From： https://www.cnblogs.com/Catherine2006/p/17166763.html

相关文章

  • 板子们（未完成）
    模板与重要性质（自用）ACM用的资料的前体。正巧要CSP-S了就突然发出来吧（列的多了大多数用处也不大，考CSP-S的学弟不必太在意）。太简单的就不写了。字符串AC自动机实质上是trie树+fail指针，建AC自动机时把不存在的trie树上的边指向了失配后到达的位置。跳fail就是......
  • 打板子机器启动！
    快读#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;intn;intans;intread(){ intff=1,kk=0; charcc=getchar(); while(cc>'9'||cc<'0'){ if(cc=='-')ff=-1; cc=getchar(); } while(cc<=......
  • 区间dp板子
    比较简单的dp，但是建模可能会比较困难。以P1775石子合并（弱化版）为例（https://www.luogu.com.cn/problem/P1775）思路：要求1-n的石子合并的代价，可以看成小的区间问题，化为1-k+k-n的两个区间。然后就有递推式子：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[j]-w[i-1]。编......
  • 板子库
    字符串KMPconstintN=1e6+5;intn,m;intnxt[N];//t串前缀的border长度chars[N],t[N];intmain(){scanf("%s%s",s+1,t+1);n=strlen(s+1);m=strlen(t+1);for(inti=2;i<=m;i++){intj=nxt[i-......
  • PbootCMS设置当前站点模板,模板子目录,黑白名单,敏感词过滤等
    进入【全局配置】在后台左侧菜单中选择【全局配置】。进入【配置参数】在【全局配置】菜单下，选择【配置参数】。进入【基本配置】在【配置参数】页面中，找到【基本配置】选项。配置敏感词过滤在【基本配置】页面中，找到【敏感词过滤】选项并添加需要过滤的敏......
  • PbootCMS设置当前站点模板,模板子目录,黑白名单,敏感词过滤等
    在PbootCMS中，后台操作涉及多个配置项，包括更换模板路径、配置后台模板子目录、配置后台黑名单和白名单以及敏感词过滤。以下是详细的步骤和解释。后台操作更换模板路径进入【基础内容】在后台管理界面左侧菜单栏中点击“基础内容”。选择【站点信息】在“基础内容”......
  • 板子大全
    数据结构01trieconstintM=30;constintN=2e5+5;intn,a[N];structTrie{ intt[N*M][2],ed[N*M],dp[N*M],tot; inlinevoidclear(void){ for(inti=0;i<=tot;i++)t[i][0]=t[i][1]=ed[i]=dp[i]=0; tot=0; } Trie(void......
  • P3478 STA-Station/换根 $dp$ 板子
    P3478[POI2008]STA-Stationlink给定一个\(n\)个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。对于全部的测试点，保证\(1\leqn\leq10^6\)，\(1\lequ,v\leqn\)，给出的是一棵树。思路：树......
  • PCB双面制造解析，你的板子是这么做出来的
    图形电镀工艺是制造高质量电路板的关键步骤。这一过程不仅需要精确的控制，还涉及到多个复杂的化学和物理操作。一、图形电镀工艺流程首先，让我们从最基本的步骤开始：电路板的制作始于一块覆有铜箔的板材。接下来，根据设计要求，板材会被裁剪并冲钻出基准孔，以确保后续工序的精确......
  • PbootCMS设置当前站点模板,模板子目录,黑白名单,敏感词过滤
    在PBootCMS中，后台操作涉及多个配置项，包括更换模板路径、配置后台模板子目录、配置后台黑名单和白名单以及敏感词过滤。下面是详细的步骤和说明。1.更换模板路径步骤进入站点信息页面：登录PBootCMS后台。导航至 【基础内容】-【站点信息】-【站点模板】。选择模板......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99