[2018CCPC吉林赛区（重现赛）- 感谢北华大学] 补题记录 躁起来

1007 High Priestess

埃及分数

1008 Lovers

线段树维护取膜意义下的区间s和。

每个区间保存前缀lazy和后缀lazy。

#include <iostream>

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<class T> void _R(T &x) { cin >> x; }

void _R(int &x) { scanf("%d", &x); }

void _R(ll &x) { scanf("%lld", &x); }

void _R(double &x) { scanf("%lf", &x); }

void _R(char &x) { scanf(" %c", &x); }

void _R(char *x) { scanf("%s", x); }

void R() {}

template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }

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 int mod = 1e9+;

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

            const int maxn = 1e5+;

            ll sum[maxn<<];

            ll lazylen[maxn<<],lazyback[maxn<<],lazypre[maxn<<];

            ll sumten[maxn<<];

            char str[];

            void build(int le, int ri, int rt) {

                sum[rt] = ;

                lazylen[rt] = lazyback[rt] = lazypre[rt] = ;

                sumten[rt] = ;

                if(le == ri) {

                    return;

                }

                int mid = (le + ri) >> ;

                build(le, mid, rt<<);

                build(mid+, ri, rt<<|);

                sumten[rt] = sumten[rt<<] + sumten[rt<<|];

            }

            ll ten[maxn];

            void pushdown(int le, int ri, int rt){

                    int mid = (le + ri) >> ;

                    sumten[rt<<] = ten[lazylen[rt]] * sumten[rt<<]%mod;

                    sum[rt<<] = ((sum[rt<<]*ten[lazylen[rt]]%mod + sumten[rt<<]*lazypre[rt]%mod )%mod+ 1ll*(mid-le+)*lazyback[rt] % mod)%mod;

                    sumten[rt<<] = ten[lazylen[rt]] * sumten[rt<<]%mod;

                    sumten[rt<<|] = ten[lazylen[rt]]*sumten[rt<<|]%mod;

                    sum[rt<<|] = ((sum[rt<<|]*ten[lazylen[rt]]%mod + sumten[rt<<|]*lazypre[rt]%mod )%mod+ 1ll*(ri-mid)*lazyback[rt] % mod)%mod;

                    sumten[rt<<|] = ten[lazylen[rt]]*sumten[rt<<|]%mod;

                    lazypre[rt<<] = (lazypre[rt] * ten[lazylen[rt<<]]%mod + lazypre[rt<<] )% mod;

                    lazyback[rt<<] = ((lazyback[rt<<] * ten[lazylen[rt]])%mod + lazyback[rt]) % mod;

                    lazylen[rt<<] =  lazylen[rt<<] + lazylen[rt];

                    lazypre[rt<<|] = (lazypre[rt] * ten[lazylen[rt<<|]]%mod + lazypre[rt<<|])% mod;

                    lazyback[rt<<|] = (lazyback[rt<<|] * ten[lazylen[rt]]%mod + lazyback[rt]) % mod;

                    lazylen[rt<<|] =  lazylen[rt<<|] + lazylen[rt];

                    lazylen[rt] = ;

                    lazyback[rt] = ;

                    lazypre[rt] = ;

            }

            void pushup(int rt) {

                sum[rt] = (sum[rt<<] + sum[rt<<|])%mod;

                sumten[rt] = (sumten[rt<<] + sumten[rt<<|]) % mod;

            }

            void update(int L, int R, int b, int le, int ri, int rt) {

                if(le >= L && ri <= R) {

                    sumten[rt] = 1ll**sumten[rt]%mod;

                    sum[rt] = ((1ll*sum[rt]*%mod + 1ll*sumten[rt]*b%mod )%mod + 1ll*(ri-le+)*b % mod)%mod;

                    sumten[rt] = 1ll**sumten[rt]%mod;

                    lazypre[rt] = (1ll* b * ten[lazylen[rt]]%mod + lazypre[rt]) % mod;

                    lazyback[rt] = (1ll*lazyback[rt] *  %mod + b)%mod;

                    lazylen[rt]++;

                    return;

                }

                if(lazylen[rt]) pushdown(le, ri, rt);

                int mid = (le + ri) >> ;

                if(mid >= L) update(L, R, b, le, mid, rt<<);

                if(mid < R) update(L, R, b, mid+, ri, rt<<|);

                pushup(rt);

            }

            ll query(int L, int R, int le, int ri, int rt) {

                if(le >= L && ri <= R) {

                    return sum[rt];

                }

                if(lazylen[rt]) pushdown(le, ri, rt);

                int mid = (le + ri) >> ;

                ll res = ;

                if(mid >= L) res = (res + query(L, R, le, mid, rt<<) )% mod;

                if(mid < R) res = (res + query(L, R, mid+, ri, rt<<|)) % mod;

                pushup(rt);

                return res;

            }

int main(){

//            freopen("data.in", "r", stdin);

            ten[] = ;

            for(int i=; i<maxn; i++) ten[i] = ten[i-] *  % mod;

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

            int cas = ;

            while(T--) {

                int n,m;

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

                build(, n, );

                printf("Case %d:\n", ++cas);

                while(m--) {

                    scanf("%s", str);

                    if(str[] == 'w') {

                        int le, ri, b;

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

                        update(le, ri, b, , n, );

                    }

                    else {

                        int le, ri;

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

                        printf("%lld\n", query(le, ri, , n , ));

                    }

                }

            }

            return ;

}

1010 Wheel of Fortune

转化为判定问题，是否存在一种对于球的完备匹配，且

匹配次数最多的颜色数量不超过 ⌊n⌋。 2

1011 The Magician

硬核模拟

1012 The Hanged Man

树链剖分

普通树形背包复杂度 O(nm2)，不可取。 考虑在 dfs 序上做 01 背包。