mid

mid

关注
发信
关注(28)粉丝(399)

2019nc#4

Ameeting点击查看树直径604/2055 
Bxor点击查看线段树维护线性基交81/861未通过
Csequence点击查看单调栈，笛卡尔树479/2755 
Dtriples I点击查看构造464/2974 
Etriples II点击查看进入讨论35/84未通过
Fmerge点击查看splay，FHQ-TREE4/37 
Gtree点击查看进入讨论2/43未通过
HRNGs点击查看进入讨论1/66未通过
Istring点击查看后缀数组，回文树157/677 
Jfree点击查看分层图最短路784/2790 
Knumber点击查看dp859/3484 

K

题意

问一个字符串中有多少个连续子串是300的倍数

思路

O（300n）的dp即可

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

/**********showtime************/

            const int maxn = 1e5+;

            ll dp[maxn][];

            char str[maxn];

int main(){

            scanf("%s", str + );

            int n = strlen(str + );

//            dp[0][0] = 1;

            ll ans = ;

            for(int i=; i<n; i++) {

                int tp = str[i + ] - '';

                for(int j=; j<; j++) {

//                    debug(tp);

                    dp[i+][(j* + tp) % ] += dp[i][j];

                }

                dp[i+][tp] ++;

                ans += dp[i+][];

            }

            printf("%lld\n", ans);

            return ;

}

F merge

题意

给定一个1～n的排列，有两种操作，1）对区间 [le，mid]和[mid+1, ri] 进行一次归并排序，2）查询区间第i个位子上的值。

思路

利用fhq_tree。区间分裂操作。

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

/**********showtime************/

struct fhq_treap {

    static const int N = 1e5 + ;

    struct Node {

        int val, key, lc, rc, sz, mx;

    }tree[N];

    int rt, tot;

    inline void init() {

        rt = tot = ;

        tree[rt].sz = tree[rt].val = tree[rt].lc = tree[rt].rc = ;

        srand(time());

    }

    inline void update(int rt) {

        tree[rt].sz = tree[tree[rt].lc].sz +  + tree[tree[rt].rc].sz;

        tree[rt].mx = max(tree[tree[rt].lc].mx,max(tree[rt].val,tree[tree[rt].rc].mx));

    }

    void split_val(int rt, int &a, int &b, int val) {

        if(rt == ) {a = b = ; return ;}

        if(max(tree[rt].val , tree[tree[rt].lc].mx) <= val) {

            a = rt;

            split_val(tree[rt].rc, tree[a].rc, b, val);

        }

        else {

            b = rt;

            split_val(tree[rt].lc, a, tree[b].lc, val);

        }

        update(rt);

    }

    void split_sz(int rt, int &a, int &b, int sz) {

        if(rt == ) {a = b = ; return ;}

        if(tree[tree[rt].lc].sz +  > sz) {

            b = rt;

            split_sz(tree[rt].lc, a, tree[b].lc, sz);

        }

        else {

            a = rt;

            split_sz(tree[rt].rc, tree[a].rc, b, sz -  - tree[tree[rt].lc].sz);

        }

        update(rt);

    }

    void merge(int &rt, int a, int b) {

        if(a== || b==) {

            rt = a+b;

            return ;

        }

        if(tree[a].key < tree[b].key) {

            rt = a;

            merge(tree[rt].rc, tree[a].rc, b);

        }

        else {

            rt = b;

            merge(tree[rt].lc, a, tree[b].lc);

        }

        update(rt);

    }

    inline int new_node(int val) {

        tree[++tot].sz = ;

        tree[tot].val = val;

        tree[tot].lc = tree[tot].rc = ;

        tree[tot].key = rand();

        tree[tot].mx = val;

        return tot;

    }

    void ins(int &rt, int val) {

        int x = , y = , node = new_node(val);

        merge(rt, rt, node);

    }

    void delete_node(int &rt, int val) {

        int x = , y = , z = ;

        split_val(rt, x, y, val);

        split_val(x, x, z, val-);

        merge(z, tree[z].lc, tree[z].rc);

        merge(x, x, z);

        merge(rt, x, y);

    }

    inline int get_kth(int rt, int k) {

        while(tree[tree[rt].lc].sz+ != k) {

            if(tree[tree[rt].lc].sz >= k) rt = tree[rt].lc;

            else k -= tree[tree[rt].lc].sz+, rt = tree[rt].rc;

        }

        return tree[rt].val;

    }

    int get_rnk(int &rt, int val) {

        int x = , y = ;

        split_val(rt, x, y, val-);

        int tmp = tree[x].sz+;

        merge(rt, x, y);

        return tmp;

    }

    int get_pre(int &rt, int val) {

        int x = , y = ;

        split_val(rt, x,  y, val-);

        int tmp = get_kth(x, tree[x].sz);

        merge(rt, x, y);

        return tmp;

    }

    int get_scc(int &rt, int val) {

        int x = , y = ;

        split_val(rt, x, y, val);

        int tmp = get_kth(y, );

        merge(rt, x, y);

        return tmp;

    }

}t;

            const int maxn = 1e5+;

            int n,m;

            int a[maxn];

            void display(int x) {

                if(t.tree[x].lc) display(t.tree[x].lc);

                if(t.tree[x].rc) display(t.tree[x].rc);

            }

            void solve(int le, int mid ,int ri) {

                int x, y, z;

                t.split_sz(t.rt, x, z, ri);

                t.split_sz(x, x, y, mid);

                int tmp;

                int r = ;

                while(x && y) {

                    int p = t.get_kth(x, );

                    int q = t.get_kth(y, );

                    if(p > q) swap(p, q), swap(x, y);

                    t.split_val(x, tmp, x, q);

                    t.merge(r,r, tmp);

                }

                t.merge(r, r,  x);

                t.merge(r, r,  y);

                t.merge(r, r,  z);

                t.rt = r;

            }

int main(){

            t.init();

            scanf("%d%d", &n, &m);

            for(int i=; i<=n; i++) {

                scanf("%d", &a[i]);

                t.ins(t.rt, a[i]);

            }

            while(m--){

                int op; scanf("%d", &op);

                if(op == ) {

                    int x;  scanf("%d", &x);

                    printf("%d\n", t.get_kth(t.rt, x));

                }

                else {

                    int le, mid, ri;

                    scanf("%d%d%d", &le, &mid, &ri);

                    solve(le, mid, ri);

                }

            }

            return ;

}

/*

5 10

3 2 1 5 4

1 1 2 5

*/
05-28 16:07
Powered by LMLPHP ©2024 mid 0.051093