首页 > 代码库 > bzoj 2631

bzoj 2631

lct 基础(‘ ‘   ) 就当个纪念吧(‘ ‘    )  毕竟写了4h, cut 部分一直naive 总是想找谁是儿子,然后最后发现直接提根就好了啊(‘ ‘   )

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const ll mod = 51061;const ll maxn = 100010;ll pl(ll a, ll b) {    ll ret = a + b;    if(ret >= mod) ret %= mod;    return ret;}ll mul(ll a, ll b) {    return a * b % mod;}struct node {    ll ans, lm, lp, lr, size, data, p;    node *son[2], *fa;}e[maxn]; ll ne = 0;void test(node* x) {    if(!x) return;    cout << x-> data <<" "<<x-> size <<" "<< x-> p << endl;    for(ll i = 0; i < 2; ++ i) test(x-> son[i]);}void update(node* x) {    x-> ans = x-> data, x-> size = 1;    for(ll i = 0; i < 2; ++ i)        if(x-> son[i])             x-> ans = pl(x-> ans, x-> son[i]-> ans), x-> size = pl(x-> son[i]-> size, x-> size); }void swap(node* &a, node* &b) {    node* mid = a; a = b, b = mid;}void pushdown(node* x) {    if(!x || (!x-> lp && !x-> lr && x-> lm == 1)) return;    if(x-> lr) {        swap(x-> son[0], x-> son[1]);        for(ll i = 0; i < 2; ++ i) if(x-> son[i]) x-> son[i]-> lr ^= 1;        x-> lr = 0;    }    for(ll i = 0; i < 2; ++ i) {        if(x-> son[i]) {             x-> son[i]-> ans = pl(mul(x-> son[i]-> ans, x-> lm), mul(x-> son[i]-> size, x-> lp));            x-> son[i]-> data = http://www.mamicode.com/pl(mul(x-> son[i]->data, x-> lm), x-> lp);"****\n";    while(m --) {        scanf("%s", s + 1);         if(s[1] == ‘+‘) {            ll a = ll_get(), b = ll_get(), c = ll_get();            reserve(a); access(b);             node* x = (e + b);            x-> lp = pl(c, x-> lp), x-> ans = pl(x-> ans, mul(c, x-> size)), x-> data = http://www.mamicode.com/pl(x-> data, c);"****\n";            link(c, d);            //for(int i = 1; i <= n; ++ i) test(e + i), cout << endl;                }        if(s[1] == ‘/‘) {            ll a, b; a = ll_get(), b = ll_get();             reserve(a), access(b);             printf("%lld\n", (e + b)-> ans);        }        //for(int i = 1; i <= n; ++ i) test(e + i), cout << endl;        //cout << "****\n";        //cout << (e + 1)-> son[0] << endl;    }}int main() {    //freopen("test.in", "r", stdin);    //freopen("test.out", "w", stdout);    read();     sov();}

 

bzoj 2631