洛谷P1276 校门外的树（增强版）未完工

题目描述

校门外马路上本来从编号0到L，每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树，就连树苗也不放过（记 0 A B ，含A和B）；幸运的是还有植树者每次从编号C到D 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含C和D）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

输入输出格式

输入格式：

第一行L和N,表示校园外原来有L+1棵树，并有N次砍树或种树的操作。

以下N行，砍树或植树的标记和范围，每行3个整数。

L（1 <= L <= 10000）和 N（1 <= N <= 100）

输出格式：

共两行。第1行校门外留下的树苗数目，第2行种上又被拔掉的树苗数目。

输入输出样例

输入样例#1：

输出样例#1：

3
2
线段树写炸了，模拟也不想写，放个代码在这里等以后我回来填坑吧.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int sum1[5000100],sum2[5000100],ans,ans2,flag[5000100];
int n,ll;

void pushup(int o)
{
    sum1[o] = sum1[o * 2] + sum1[o * 2 + 1];
    sum2[o] = sum2[o * 2] + sum2[o * 2 + 1];
}

void build(int l,int r,int o)
{
    if (l == r)
    {
        sum1[o] = 1;
        sum2[o] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l,mid,o * 2);
    build(mid + 1,r,o * 2 + 1);
    pushup(o); 
}

void pushdown(int o,int len)
{
    if (flag[o] == 1)
    {
        flag[o * 2] = flag[o * 2 + 1] = flag[o];
        sum1[o * 2] = sum1[o * 2 + 1] = sum2[o * 2] = sum2[o * 2 + 1] = 0;
        flag[o] = 0;
    }
    else
    if (flag[o] == 2)
    {
        flag[o * 2] = flag[o * 2 + 1] = flag[o];
        flag[o] = 0;
        sum2[o * 2] = (len - (len >> 1)) - sum1[o * 2];
        sum2[o * 2 + 1] = (len >> 1) - sum1[o * 2 + 1];
    }
}

void cut(int l,int r,int o,int x,int y)
{
    if (x <= l && r <= y)
    {
        ans2 += sum2[o];
        ans -= sum2[o];
        sum1[o] = 0;
        sum2[o] = 0;
        flag[o] = 1;
        return;
    }
    pushdown(o,r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid)
    cut(l,mid,o * 2,x,y);
    if (y > mid)
    cut(mid + 1,r,o * 2 + 1,x,y);
    pushup(o);
}

void plant(int l,int r,int o,int x,int y)
{
    if (x <= l && r <= y)
    {
        ans += (r - l + 1) - sum1[o];
        sum2[o] = (r - l + 1) - sum1[o];
        flag[o] = 2;
        return;
    }
    pushdown(o,r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid)
    plant(l,mid,o * 2,x,y);
    if (y > mid)
    plant(mid + 1,r,o * 2 + 1,x,y);
    pushup(o);
}

int main()
{
    scanf("%d%d",&ll,&n);
    build(1,ll + 1,1);
    for (int i = 1; i <= n; i++)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        l++;
        r++;
        if (op == 0)
        cut(1,ll + 1,1,l,r);
        if (op == 1)
        plant(1,ll + 1,1,l,r);
    }
    printf("%d
%d",sum2[1],ans2);
    
    return 0;
}