首页 > 代码库 > bzoj 3626

bzoj 3626

2024-11-19 17:03:39   203人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=3626

让我比较惊讶的一道链剖裸题(‘ ‘    ) 做法很精妙

首先我们考虑对于单个询问时可以拆分成(1, l - 1, z) 和 (1, r, z) 的， 然后考虑对于每一次询问可以表示为将(1, l) 的所有点到根的全部加1 然后求z到根路径的的和。 所以将询问离线， 按询问的l值排序，每一次遇到新的l值就将这一段的点到根的路径全部加1，然后查询即可

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const ll maxn = 100001;const ll mod = 201314;ll n, m;ll int_get() {    ll x = 0; char c = (char)getchar(); bool f = 0;    while(!isdigit(c)) {        if(c == ‘-‘) f = 1;        c = (char)getchar();    }    while(isdigit(c)) {        x = x * 10 + (int)(c - ‘0‘);        c = (char)getchar();    }    if(f) x = -x;    return x;}struct seg {    ll data, lazy;     seg *l, *r;}tr[maxn * 3];ll sege = 0;seg* root;void test(seg* x, ll l, ll r) {    cout << l <<" "<< r <<" "<< x-> data <<" "<< x-> lazy << endl;    if(l ^ r) {        ll mid = (l + r) >> 1;        test(x-> l, l, mid), test(x-> r, mid + 1, r);    }}seg* build(ll l, ll r) {    seg* x = tr + sege ++;    if(l ^ r) {        ll mid = (l + r) >> 1;        x-> l = build(l, mid);        x-> r = build(mid + 1, r);    }    return x;}void update(seg* x) {    if(x-> l) x-> data = http://www.mamicode.com/x-> l-> data + x-> r-> data;"%lld\n", (ans[i] % mod + mod)% mod);}int main() {    //freopen("test.in", "r", stdin);    //freopen("test.out", "w", stdout);    read();     sov();    return 0;}

 

bzoj 3626


联系
我们