跑了几遍了都是 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;
}