CF915E Physical Education Lessons

CF915E Physical Education Lessons

题目

连接

题解

动态开点线段树裸题

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define re register

inline ll read()
{
    ll f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch<'0'||ch>'9');
    do
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}

const int MAXN = 3e5 + 10;

int n,q;
int lc[MAXN*50],rc[MAXN*50],sum[MAXN*50],add[MAXN*50],tot;
int root;

inline void pushdown(int o,int l,int r)
{
    if(!add[o]) return;
    int mid = (r+l)>>1;
    if(!lc[o]) lc[o] = ++tot;
    sum[lc[o]] = (add[o]-1)*(mid-l+1);
    add[lc[o]] = add[o];
    if(!rc[o]) rc[o] = ++tot;
    sum[rc[o]] = (add[o]-1)*(r-mid);
    add[rc[o]] = add[o];
    add[o]=0;
    return;
}

inline void update(int &rt,int l,int r,int x,int y,int v)
{
    if(!rt) rt = ++tot;
    if(x<=l&&y>=r)
    {
        sum[rt] = v * (r - l + 1);
        add[rt] = v+1;
        return;
    }
    int mid = (l+r)>>1;
    if(x>r||l>y) return;
    pushdown(rt,l,r);
    update(lc[rt],l,mid,x,y,v);
    update(rc[rt],mid+1,r,x,y,v);
    sum[rt]=sum[lc[rt]]+sum[rc[rt]];
    return;
}

int main()
{
    n = read(),q = read();
    for(int i=1;i<=q;i++)
    {
        int l = read(),r = read(),k = read();
        if(k==1)
        {
            update(root,1,n,l,r,1);
        }
        if(k==2)
        {
            update(root,1,n,l,r,0);
        }
        printf("%d\n",n-sum[root]);
    }
}