蒟蒻RE on #5求助
查看原帖
蒟蒻RE on #5求助
1036693
carp_oier楼主2023/10/2 16:03

跑了几遍了都是 RE,蒟蒻求助。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

const ll N = 2e6+ 10;

ll n, m, tot = 1;

struct dynamicTree
{
    ll lson, rson;
    ll sum, flag; // 1 is to turn the work day, -1 is opposite 1.
}tr[N << 1];

inline void pushup(ll &u) { tr[u].sum = tr[tr[u].lson].sum + tr[tr[u].rson].sum; }

inline void pushdown(ll u, ll l, ll r)
{
    ll &lson = tr[u].lson, &rson = tr[u].rson;
    if(tr[u].flag == 1)
    {
        if(!lson) lson = ++ tot; if(!rson) rson = ++ tot;

        tr[lson].flag = tr[u].flag, tr[rson].flag = tr[u].flag;
        ll mid = l + r >> 1;

        tr[lson].sum = (mid - l + 1), tr[rson].sum = (r - mid);
        tr[u].flag = 0;
    }
    else if(tr[u].flag == -1)
    {
        if(!lson) lson = ++ tot; if(!rson) rson = ++ tot;

        tr[lson].flag = tr[u].flag, tr[rson].flag = tr[u].flag;
        ll mid = l + r >> 1;

        tr[lson].sum = tr[rson].sum = 0;
        tr[u].flag = 0;
    }
}

inline void build(ll &u, ll l, ll r, ll v, ll x)
{
    if(!u) u = ++ tot;
    if(l == r) { tr[u].sum = x; return ; }

    ll mid = l + r >> 1;

    if(v <= mid) build(tr[u].lson, l, mid, v, x);
    else if(v > mid) build(tr[u].rson, mid + 1, r, v, x);

    pushup(u);
}

inline void update(ll &u, ll l, ll r, ll L, ll R, ll x)
{
    if(!u) u = ++ tot;
    if(L <= l && R >= r)
    {
        tr[u].flag = (x == 1) ? -1 : 1, tr[u].sum = (x == 1) ? 0 : (r - l + 1);
        return ;
    }

    pushdown(u, l, r);
    ll mid = l + r >> 1;
    
    if(L <= mid) update(tr[u].lson, l, mid, L, R, x);
    if(R > mid) update(tr[u].rson, mid + 1, r, L, R, x);

    pushup(u);
}

// inline ll query(ll u, ll l, ll r, ll L, ll R)
// {
//     if(!u) return 0;
//     if(L <= l && R >= r) return tr[u].sum;

//     pushdown(u, l, r);
//     ll mid = l + r >> 1;
//     ll res = 0;

//     if(L <= mid) res += query(tr[u].lson, l, mid, L, R);
//     if(R > mid) res += query(tr[u].rson, mid + 1, r, L, R);

//     return res;
// }

int main()
{
    // freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);

    cin >> n >> m;

    for(rl i=1; i <= n; ++ i)
    {
        ll tmp = 1; build(tmp, 1, n, i, 1);
    }

    while(m -- )
    {
        ll a, b, c, tmp = 1;
        cin >> a >> b >> c;
        update(tmp, 1, n, a, b, c);
        cout << tr[1].sum << endl;
    }
    return 0;
}
2023/10/2 16:03
加载中...